Second-Order Conditions for the Existence of Augmented Lagrange Multipliers for Sparse Optimization

In this paper, we consider the augmented Lagrangian duality for optimization problems with sparsity and abstract set constraints and present second-order conditions for the existence of augmented Lagrange multipliers by calculating the second-order epi-derivative of the augmented Lagrangian. The ingredient of the augmented Lagrangian here includes the indicator function of a sparse set and a composition of the Moreau envelope of the indicator function of a second-order regular set and a twice continuously differentiable mapping. The main process depends heavily on the calculation of the second-order epi-derivative of the indicator function of sparse set which is shown to be second-order regular and also parabolically regular. The second-order sufficient conditions for the sparse nonlinear programming, the sparse inverse covariance selection problem, and the sparse second-order cone programming are obtained as special cases of our general results. We prove that the existence of augmented Lagrange multipliers ensures the exactness of penalty functions and the stability of augmented solutions under small perturbations of the corresponding augmented Lagrange multipliers.