Improving ADMMs for solving doubly nonnegative programs through dual factorization
- PDF / 542,788 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 215 Views
Improving ADMMs for solving doubly nonnegative programs through dual factorization Martina Cerulli1 · Marianna De Santis2 · Elisabeth Gaar3 · Angelika Wiegele3 Received: 23 December 2019 © The Author(s) 2020
Abstract Alternating direction methods of multipliers (ADMMs) are popular approaches to handle large scale semidefinite programs that gained attention during the past decade. In this paper, we focus on solving doubly nonnegative programs (DNN), which are semidefinite programs where the elements of the matrix variable are constrained to be nonnegative. Starting from two algorithms already proposed in the literature on conic programming, we introduce two new ADMMs by employing a factorization of the dual variable. It is well known that first order methods are not suitable to compute high precision optimal solutions, however an optimal solution of moderate precision often suffices to get high quality lower bounds on the primal optimal objective function value. We present methods to obtain such bounds by either perturbing the dual objective function value or by constructing a dual feasible solution from a dual approximate optimal solution. Both procedures can be used as a post-processing phase in our ADMMs. Numerical results for DNNs that are relaxations of the stable set problem are presented. They show the impact of using the factorization of the dual variable in order to improve the progress towards the optimal solution within an iteration of the ADMM. This decreases the number of iterations as well as the CPU time to solve the DNN to a given precision. The experiments also demonstrate that within a computationally cheap post-processing, we can compute bounds that are close to the optimal value even if the DNN was solved to moderate precision only. This makes ADMMs applicable also within a branch-and-bound algorithm.
This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant agreement MINOA No 764759 and the Austrian Science Fund (FWF): I 3199-N31. Extended author information available on the last page of the article
123
M. Cerulli et al.
1 Introduction In a semidefinite program (SDP) one wants to find a positive semidefinite (and hence symmetric) matrix such that linear — in the entries of the matrix — constraints are fulfilled and a linear objective function is minimized. If the matrix is also required to be entrywise nonnegative, the problem is called doubly nonnegative program (DNN). Since interior point methods fail (in terms of time and memory required) when the scale of the SDP is big, augmented Lagrangian approaches became more and more popular to solve this class of programs. Wen et al. (2010) as well as Malick et al. (2009) and De Santis et al. (2018) considered alternating direction methods of multipliers (ADMMs) to solve SDPs. One can directly apply these ADMMs to solve DNNs, too, by introducing nonnegative slack variables for the nonnegativity constraints in order to obtain equality constraints only. However
Data Loading...
