Improving ADMMs for Solving Doubly Nonnegative Programs through Dual Factorization

摘要: 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 (DNN), which where elements matrix variable constrained be nonnegative. Starting from two algorithms already proposed in literature conic programming, introduce new ADMMs by employing a factorization dual variable. It is well known first order not suitable compute high precision optimal solutions, however an solution moderate often suffices get quality lower bounds primal objective function value. We present obtain such either perturbing value or constructing feasible approximate solution. Both procedures can used as post-processing phase our ADMMs. Numerical results for DNNs relaxations stable set problem presented. They show impact using improve progress towards within iteration ADMM. This decreases number iterations CPU time solve DNN given precision. The experiments also demonstrate computationally cheap post-processing, close even if was solved only. makes applicable branch-and-bound algorithm.