Working with Composite Optimization part4(Machine Learning 2024)
- Perturbation analysis of a class of composite optimization problems(arXiv)
Author : Peipei Tang, Chengjing Wang
Abstract : In this paper, we study the perturbation analysis of a class of composite optimization problems, which is a very convenient and unified framework for developing both theoretical and algorithmic issues of constrained optimization problems. The underlying theme of this paper is very important in both theoretical and computational study of optimization problems. Under some mild assumptions on the objective function, we provide a definition of a strong second order sufficient condition (SSOSC) for the composite optimization problem and also prove that the following conditions are equivalent to each other: the SSOSC and the nondegeneracy condition, the nonsingularity of Clarke’s generalized Jacobian of the nonsmooth system at a Karush-Kuhn-Tucker (KKT) point, and the strong regularity of the KKT point. These results provide an important way to characterize the stability of the KKT point. As for the convex composite optimization problem, which is a special case of the general problem, we establish the equivalence between the primal/dual second order sufficient condition and the dual/primal strict Robinson constraint qualification, the equivalence between the primal/dual SSOSC and the dual/primal nondegeneracy condition. Moreover, we prove that the dual nondegeneracy condition and the nonsingularity of Clarke’s generalized Jacobian of the subproblem corresponding to the augmented Lagrangian method are also equivalent to each other. These theoretical results lay solid foundation for designing an efficient algorithm.
