Distributed Optimization

1

Hi,

I am trying to solve a distributed optimization problem using CVX.
Consider the function to optimize J, which is divided in two “agents”: J = J1 + J2
The minimization is: min [J1(u1,u2) + J2(u1,u2)]

The idea is to replicate the independent variables for each agent

  • Agent 1 minimizes J1(u1,v2), where v2 is a replica of u2
  • Agent 2 minimizes J2(v1,u2), where v1 is a replica of u1

Dual decomposition gives us the master problem:
min[J1(u1,v2) + J2(v1,u2) + lambda1*(u2-v2) + lambda2*(u1-v1)]

So, my question is, to solve this kind of problem, can I include both minimizations in the same “cvx_begin cvx_end”, or should I have two cycles? Agent 1 receives lambda2 and u2 from Agent2. Agent2 receives lambda1 and u1 from Agent1. How do I guarantee that the variables are shared properly?
Also, can I control using the “dual ascent” or “subgradient” methods? Maybe this question doesn’t make sense…

Thank you.

2

It sounds to me like you want to have a high-level for loop, inside of which you have two successive cvx_begin … cvx_end blocks, one for each of agent 1 and agent 2… Use the optimal variable values from the previous problem as inputs to the current problem. Of course, you’ll need initial values to input into the first problem on the first time through the loop; or bring that first instance of agent 1 out of (before) the loop, and then do agent 2, agent 1 inside the loop).

As to whether this approach converges, to the correct answer, and performs well, I will leave to your determination.

As for dual ascent, subgradient methods, I think their applicability or not is an optimization question outside the scope of this forum.

1 Like