Hierarchical distributed optimization of constraint-coupled convex and mixed-integer programs using approximations of the dual function

• Published in: EURO journal on computational optimization 2023, Vol.11, p.100058, Article 100058
• Main Authors: Yfantis, Vassilios, Wenzel, Simon, Wagner, Achim, Ruskowski, Martin, Engell, Sebastian
• Format: Article
• Language: English
• Subjects: ADMM; Bundle method; Distributed optimization; Dual decomposition; Nonsmooth optimization; Quadratic approximation; Quasi-Newton; Subgradient method
• ISSN: 2192-4406; 2192-4414
• DOI: 10.1016/j.ejco.2023.100058

In this paper, two new algorithms for dual decomposition-based distributed optimization are presented. Both algorithms rely 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. The first algorithm approximates the dual function by solving a regression problem, based on the values of the dual function collected from previous iterations. The second algorithm updates the parameters of the quadratic approximation via a quasi-Newton scheme. Both algorithms employ step size constraints for the update of the dual variables. Furthermore, 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. In order to demonstrate the efficiency of the algorithms, they are evaluated on a large set of constrained quadratic, convex and mixed-integer benchmark problems and compared to the subgradient method, the bundle trust method, the alternating direction method of multipliers and the quadratic approximation coordination algorithm. The results show that the proposed algorithms perform better than the compared algorithms both in terms of the required number of iterations and in the number of solved benchmark problems in most cases. •Dual decomposition is employed to decouple separable optimization problems.•The dual function of separable optimization problems is approximated by a quadratic function.•The dual variables are updated by maximizing the approximated dual function subject to step size constraints.•Subgradients collected from previous iterations are used to construct cutting planes.•The performance of the algorithm is evaluated on a large set of convex and integer benchmark problems.