Optimization Online


Constraint Nondegeneracy, Strong Regularity and Nonsingularity in Semidefinite Programming

Zi Xian Chan(u0301479***at***nus.edu.sg)
Defeng Sun (matsundf***at***nus.edu.sg)

Abstract: It is known that the Karush-Kuhn-Tucker (KKT) conditions of semidefinite programming can be reformulated as a nonsmooth system via the metric projector over the cone of symmetric and positive semidefinite matrices. We show in this paper that the primal and dual constraint nondegeneracies, the strong regularity, the nonsingularity of the B-subdifferential of this nonsmooth system, and the nonsingularity of the corresponding Clarke's generalized Jacobian, which is the convex hull of the B-subdifferential, at a KKT point are all equivalent. Moreover, we prove the equivalence between each of these conditions and the nonsingularity of the B-subdifferential (or Clarke's generalized Jacobian) of the smoothed counterpart of this nonsmooth system used in several smoothing Newton methods. In particular, we establish the quadratic convergence of these methods under the primal and dual constraint nondegeneracies, but without the strict complementarity.

Keywords: Semidefinite programming, constraint nondegeneracy, strong regularity, nonsingularity, variational analysis, quadratic convergence

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report, Department of Mathematics, National University of Singapore, January 2007.

Download: [Postscript][PDF]

Entry Submitted: 01/29/2007
Entry Accepted: 01/29/2007
Entry Last Modified: 01/29/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society