Abstract
Certain matrix relationships play an important role in optimally conditions and algorithms for nonlinear and semidefinite programming. Let H be an n x n symmetric matrix. A an m x n matrix, and Z a basis for the null space of A. (In a typical optimization context H is the Hessian of a smooth function and A is the Jacobian of a set of constraints.) When the reduced Hessian ZTHZ is positive definite, augmented Lagrangian methods rely on the known existence of a finite ρ̄ > O such that, for all ρ > ρ̄, the augmented Hessian H + ρATA is positive definite. In this note we analyze the case when ZTHZ is positive semidefinite, i.e., singularity is allowed, and show that the situation is more complicated. In particular, we give a simple necessary and sufficient condition for the existence of a finite ρ̄ so that H + ρATA is positive semidefinite for ρ ≥ ρ̄. A corollary of our result is that if H is nonsingular and indefinite while ZTHZ is positive semidefinite and singular, no such ρ̄ exists.
Original language | English (US) |
---|---|
Pages (from-to) | 243-253 |
Number of pages | 11 |
Journal | SIAM Journal on Optimization |
Volume | 11 |
Issue number | 1 |
DOIs | |
State | Published - 2000 |
Keywords
- Augmented Hessian
- Augmented Lagrangian methods
- Inertia
- Reduced Hessian
ASJC Scopus subject areas
- Software
- Theoretical Computer Science