On Degenerate Doubly Nonnegative Projection Problems

Ying Cui (), Ling Liang (), Defeng Sun () and Kim-Chuan Toh ()
Additional contact information
Ying Cui: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis 55455
Ling Liang: Department of Mathematics, National University of Singapore, Singapore 119077, Singapore
Defeng Sun: Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Hong Kong
Kim-Chuan Toh: Department of Mathematics, and Institute of Operations Research and Analytics, National University of Singapore, Singapore 119077, Singapore

Mathematics of Operations Research, 2022, vol. 47, issue 3, 2219-2239

Abstract: 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 subregularity 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.

Keywords: 90C06; 90C22; 90C25; doubly nonnegative cone; semidefinite programming; augmented Lagrangian method; semismooth Newton; degeneracy; metric subregularity (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1205 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:3:p:2219-2239

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().