A Note on the Augmented Hessian When the Reduced Hessian is Semidefinite

Certain matrix relationships play an important role in optimality 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 the context of optimization, H is the Hessian of a smooth function and A is the Jacobian of a set of constraints.) When the reduced Hessian Z sup T HZ is positive definite, augmented Lagrangian methods rely on the known existence of a finite p bar such that, for all p > p bar, the augmented Hessian H + pA sup T A is positive definite. In this note, we analyze the case when Z sup T HZ 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 p bar so that H + pA sup T A is positive semidefinite for p >= p bar. A corollary of our result is that if H is nonsingular and indefinite while Z sup T HZ is positive semidefinite and singular, no such p bar exists.