As is stated in chapter 9 of Boyd et al.1, ADMM can be used as a heuristic method for solving non-convex problems.
Here, my case contains binary variables and it is more special since the binary variable only appears in individual problem and has no connection with other agents. The multi-agent problem in my case can be formulated as follows:
$$\text{min}\quad\sum\limits_if_i(\boldsymbol{x_i}) \\ \text{s.t.}\quad \sum\limits_i\boldsymbol{x_i}=0,\\ g_i(\boldsymbol{x_i},y_i)\leq0, \\ y_i\in\{0,1\},\\ \boldsymbol{x_i}\in\Omega_i $$ $\boldsymbol{x_i}$ is continuous, $\Omega_i$ is a convex set and $f_i$ is a convex function. $g_i$ is a linear function. You can find an example below in the comment section.
I want to solve the above problem in a distributed manner by exploiting the exchange problem formulation in Boyd's paper (Chapter 7). Hence, the binary variable $y_i$ only appears in each individual constraint and individual problems are MIPs, which can be solved easily with commercial solvers.
I am wondering whether ADMM in this case can converge to the global optimum. Or is there any modification of standard ADMM to achieve the global optimum? If not, does the standard ADMM of this case promise to converge to a suboptimal point?
Thank you for your kind help.
- Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends in Machine Learning, Volume 3, Number 1, 2011.