On Degenerate Doubly Nonnegative Projection Problems

• 成果类型: Article; Early Access
• 署名作者: Cui, Ying; Liang, Ling; Sun, Defeng; Toh, Kim-Chuan
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities; National University of Singapore; Hong Kong Polytechnic University; National University of Singapore
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1205
• 发表日期: 2021
• 关键词: Augmented Lagrangian method; constraint nondegeneracy; error-bounds; convex; CONVERGENCE; approximation; intersection; REGULARITY; algorithm; graph

摘要

The doubly nonnegative (DNN) cone, being the set of all positive semidefinite matrices whose elements are nonnegative, is a popular approximation of the computationally intractable completely positive cone. The major difficulty for implementing a Newton-type method to compute the projection of a given large-scale matrix onto the DNN cone lies in the possible failure of the constraint nondegeneracy, a generalization of the linear independence constraint qualification for nonlinear programming. Such a failure results in the singularity of the Jacobian of the nonsmooth equation representing the Karush-Kuhn-Tucker optimality condition that prevents the semismooth Newton-conjugate gradient method from solving it with a desirable convergence rate. In this paper, we overcome the aforementioned difficulty by solving a sequence of better conditioned nonsmooth equations generated by the augmented Lagrangian method (ALM) instead of solving one aforementioned singular equation. By leveraging the metric sub regularity of the normal cone associated with the positive semidefinite cone, we derive sufficient conditions to ensure the dual quadratic growth condition of the underlying problem, which further leads to the asymptotically superlinear convergence of the proposed ALM. Numerical results on difficult randomly generated instances and from the semidefinite programming library are presented to demonstrate the efficiency of the algorithm for computing the DNN projection to a very high accuracy.