Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming

Z.X. Chan, Defeng Sun

Research output: Journal article publicationJournal articleAcademic researchpeer-review

40 Citations (Scopus)

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, at a KKT point, are all equivalent. Moreover, we prove the equivalence between each of these conditions and the nonsingularity of Clarke's generalized Jacobian of the smoothed counterpart of this nonsmooth system used in several globally convergent 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. © 2008 Society for Industrial and Applied Mathematics.
Original languageEnglish
Pages (from-to)370-396
Number of pages27
JournalSIAM Journal on Optimization
Volume19
Issue number1
DOIs
Publication statusPublished - 1 Dec 2008
Externally publishedYes

Keywords

  • Constraint nondegeneracy
  • Nonsingularity
  • Quadratic convergence
  • Semidefinite programming
  • Strong regularity
  • Variational analysis

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software

Cite this