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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.