Augmented Lagrangian Dual And Algorithm For Composite Optimization Based On The Moreau Envelope

Augmented Lagrangian methods play an important part in optimization, which has been extensively used in many fields due to its excellent performance in theoretical and computational aspects. In this paper, augmented Lagrangian dual and first-and second-order conditions ensuring the existence of augment-ed Lagrange multipliers will be obtained for composite optimization problem. In particular, the conclusions are applied to set inclusion optimization problems and eigenvalue composite optimization problems, and a series of specific second-order conditions are obtained. Under the assumption of second-order sufficient condition, an inexact augmented Lagrangian algorithm for set inclusion opti-mization problems is given, and the local convergence and rate of convergence are discussed. In this approach, the augmented Lagrangian expressed by the Moreau envelope plays an important role. Therefore, the classical Moreau enve-lope is extended to the case of Bregman distance, and its properties and applica-tions are considered. The main contents in this paper have been summarized as follows:1. Augmented Lagrangian dual for composite optimization problem is es-tablished, and the corresponding duality theory is obtained. The relation between the existence of augmented Lagrange multipliers and the property of no duality gap is studied and the optimal solutions pair of primal-dual problems is charac-terizes as the saddle point of augmented Lagrangian.2. Based on the Moreau envelope, a new expression of augmented La-grangian is given, which is used to characterize the set of standard Lagrange multipliers and prove the relation between the augmented Lagrange multipliers and the standard Lagrange multipliers. Utilizing the reformulation of the aug-mented Lagrangian and its second-order epi-derivative, second-order conditions for the existence of augmented Lagrange multipliers are obtained. A series of second-order conditions are listed for set inclusion optimization problems and eigenvalue composite optimization problems. The sensitivity of optimal solu-tions of the minimization of augmented Lagrangian to small perturbations of augmented Lagrange multipliers is studied.3. For the optimization problems with set inclusion, an inexact augmented Lagrangian method is constructed, and a result about error bound of the solution mapping of perturbed generalized equation is proved, and the local convergence and rate of convergence of this algorithm is studied under the assumption of second-order sufficient condition.4. By utilizing the Bregman distance in stead of the usual metric distance, an extended Moreau envelope is considered. Without the assumption of con-vexity, the properties such as the continuity, differentiability and Clarke regular-ity of the extended Moreau envelope and the upper semicontinuity and single-valuedness of its corresponding proximal mapping are studied.