Why can't we discretize continuous domains in distributed non-convex constraint optimization problems?

Question

Consider a non-convex distributed optimization problem.

• We have $X$ = a set of $n$ decision variables: $x_i$ where $i=1..n$ and $x_i \in R$, the set of Reals.
• We have $F$ = a set of $m$ constraint cost functions: $f_j($x$)$ where $j=1..m$ and each $f_j$ is defined for a subset of $X$ and each $f_j$ is known only to the respective $x_i$'s $\in X$. We assume each variable to be an agent in a distributed multiagent system.
• We have $D = \{d_1, d_2, ..d_n\}$, a set of domains for each $x_i$ where $d_i$ is of the form: $l_i<=x_i<=u_i$ i.e. $x_i$ can take values between $l_i$, the lower bound and $u_i$, the upper bound. Hence each $x_i$ is bounded in the space of real numbers.

We have to $minimize \sum_{j=1}^{m} f_{j}($x$)$ which is the global objective. We also have to satisfy certain hard constraints (e.g.: $x_1 = x_2 + x_3$, $x_2+x_5<=5.5$, etc.) - these are again known to the respective variables/agents.

Each of the $f_j$'s could be non-convex Eg:$f_2(x_2, x_3) = x_2^3 + x_3^3 + x_2x_3$, etc. which may lead to a hills and valleys terrain for the overall objective function (something like in here)

The question in the exam was about what approach one would use to solve such a problem. Begin familiar with Distributed Constraint Optimization Problems (DCOPs), I thought that one could discretize the continuous space to integers (or into even more granularity if required, depending on the domain - this can be thought of as sampling) and use a DCOP algorithm to solve this problem (since DCOP algorithms don't make convexity assumptions and are general purpose) Once we get the integer solutions, we could do a distributed gradient descent (assuming that we've ended up in a convex space) to get a solution between integers (do this if needed).

I understand that we will (may) not get an exact real valued solution because of the granularity of the discretization and that this isn't mathematically elegant by any means, but isn't this one of the best possible approaches in practice, given that we have the conditions of distributed optimization (assuming that the problem is inherently distributed and cannot be solved centrally) and that we have optimal, complete DCOP algorithms? Is this a feasible approach or am I missing something? If I am missing something, what is the state of the art? If this is a feasible approach, how may I prove to the professor that this approach works in practice?

Answer 1

You are missing that, in general, integer optimization problems are much more expensive to solve than real-valued optimization problems. That's because for real-values optimization problems, you have the tools of gradients and Hessians that can guide you to a minimum, whereas the integer equivalents are at best crutches that can help you, but are not nearly as efficient. In other words, unless you discretize each variable into only a few discrete values, and unless you have only a small number of variables, discretization will make your problem vastly more expensive to solve.