Exact regularization in an augmented lagrangian method for semidefinite programming

Augmented Lagrangian method is emerging as an important class of methods in semidef-inite programming, especially when there are many constraints. This is done by applying the standard augmented Lagrangian method to the dual problem. The resulting method can be cast as Moreau-Yosida regularization of the primal problem. Despite its numerical success, there still lacks theoretical justification on the penalty parameter selection, which often in practice does not have to be big to achieve good approximate solutions. This phenomenon is related to exact regularization of convex programs. This paper studies when the regulariza-tion in the augmented Lagrangian method is exact. Under strict complementarity condition, a necessary and sufficient condition is that the gradient of the quadratic regularization func-tion at a concerned optimal solution belongs to the positive polar cone of the critical cone at the concerned solution. In the absence of strict complementarity condition, singleton of the critical cone proves to be necessary and sufficient for uniqueness of optimal solutions and exactness of arbitrary quadratic functions. We also characterize this latter condition via directional regularity of a perturbed normal condition. Key words. Exact regularization, augmented Lagrangian method, critical cone, directional regularity, semidefinite programming. AMS subject classifications. 49M45, 90C25, 90C33