Augmented Lagrangian Approaches for Solving Doubly Nonnegative Progra...

Augmented Lagrangian methods are among the most popular first-order approaches to handle large-scale semidefinite programs (SDP). Alternating direction method of multipliers (ADMM) is a variant of the augmented Lagrangian scheme that performs consecutive updates on certain blocks of the dual variables. We present an ADMM where we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. A description on how to deal with the resulting unconstrained maximization of the augmented Lagrangian is given. In particular, we look at doubly nonnegative programs (DNN), these are semidefinite programs where the elements of the matrix variable are constrained to be nonnegative. In an ADMM, these constraints can be handled efficiently since this simply amounts in projections onto the non-negative orthant.

Whenever the SDP or DNN is a relaxation of a combinatorial optimization problem, one is interested in using its solution within a branch-and-bound framework. ADMM typically does not yield solutions with a high precision. Having solutions of moderate precision only, the obtained optimum of the SDP or DNN might not be a valid bound for the underlying combinatorial optimization problem. We present a post-processing to obtain valid bounds from the solution of the ADMM. This valid bound can be computed at low cost and the numerical results demonstrate that this procedure does not weaken the bound significantly. This is joint work with Martina Cerulli, Marianna De Santis, Elisabeth Gaar and Franz Rendl.