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 × n symmetric matrix, A an m × 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 ρ≥ 0 such that, for all ρ > ρ, the augmented Hessian H + ρ 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 + ρ 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.