Vassilios Yfantis, Chair of Machine Tools and Control Systems (WSKL), TU Kaiserslautern
Distributed Optimization of Separable Convex and Integer Programs by Quadratically Approximated Dual Ascent
In this talk, a new algorithm for dual decomposition-based distributed optimization is presented. It relies on the quadratic approximation of the dual function of the primal optimization problem. The dual variables are updated in each iteration through a maximization of the approximated dual function subject to stepsize constraints. Firstly, the updated dual variables are constrained to lie in an ellipsoid around the current dual variables. The ellipsoid is defined by the covariance matrix of the dual variables from previous iterations which have been used for the quadratic approximation. Secondly, the subgradients from previous iterations are stored in order to construct cutting planes, similar to bundle methods for nonsmooth optimization. However, instead of using the cutting planes to formulate a piece-wise linear over-approximation of the dual function, they are used to construct valid inequalities for the update step. The algorithm is evaluated on a large set of convex and integer benchmark problems and compared to the subgradient method, the alternating direction method of multipliers and the quadratic approximation coordination algorithm. The results show that the proposed algorithm performs better than the compared algorithms both in terms of the required number of iterations and in the number of solved benchmark problems.
How to join online
The talk is held online via Zoom. You can join with the following link: