Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming

Shiwei Wang, Chao DingComput. Optim. Appl 2024 · DOI

TL;DR

This paper analyzes the local convergence of the Augmented Lagrangian Method (ALM) for nonlinear semidefinite programming (NLSDP). The authors establish a Q-superlinear convergence rate for the primal-dual sequences without assuming the uniqueness of Lagrange multipliers, which is a significant improvement over previous work. This advancement is crucial for developing more robust and efficient solvers for a broad range of optimization problems.

What Problem Does This Paper Address?

Nonlinear semidefinite programming (NLSDP) is a powerful class of optimization problems with applications in various fields, including machine learning and control system design. The Augmented Lagrangian Method (ALM) is a popular and effective technique for solving such problems. However, a key challenge in analyzing ALM's convergence, especially for non-convex NLSDP, is the potential non-uniqueness of Lagrange multipliers. Existing theoretical results often rely on assumptions like the uniqueness of multipliers or specific problem structures (e.g., convexity or polyhedral constraints), which limit their applicability. This paper aims to bridge this gap by providing a local convergence analysis for ALM applied to general NLSDP, specifically relaxing the assumption of unique multipliers and handling non-polyhedral constraints.

Methods

The authors employ a rigorous mathematical approach to analyze the local convergence of the ALM. Key techniques include:

  • Second-Order Analysis: The paper heavily relies on second-order conditions, particularly the second-order sufficient condition (SOSC) and the concept of uniform second-order expansion for the Moreau envelop of the SDP cone indicator function.
  • Semi-Isolated Calmness: A crucial concept introduced and utilized is "semi-isolated calmness" of the KKT solution mapping. This condition helps to establish convergence without requiring the uniqueness of multipliers.
  • Augmented Lagrangian Function Analysis: The paper meticulously analyzes the properties of the augmented Lagrangian function, including its uniform quadratic growth condition, which is essential for proving convergence rates.
  • Error Bounds and Lipschitz Continuity: The analysis leverages error bounds and Lipschitz continuity properties of various mappings and functions involved in the optimization problem and the ALM iterations.
  • Algorithm 1 (Augmented Lagrangian Method): The paper presents a standard inexact ALM algorithm and analyzes its convergence behavior under specific conditions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Relaxing Multiplier Uniqueness: The most significant insight is the successful establishment of Q-superlinear convergence for ALM in NLSDP without assuming the uniqueness of Lagrange multipliers. This is a major theoretical advancement that broadens the applicability of ALM.
  • Semi-Isolated Calmness as a Key Condition: The paper highlights the importance of semi-isolated calmness as a critical condition for achieving convergence in the presence of non-unique multipliers.
  • Uniform Second-Order Expansion: Demonstrating the uniform second-order expansion of the Moreau envelop of the SDP cone indicator function is a crucial technical step that underpins the convergence analysis.
  • Bridging Theory and Practice: By providing theoretical guarantees for a more general class of problems, this work contributes to the development of more robust and practical optimization solvers.

Key Results

The paper establishes the following key results:

  • Q-Superlinear Convergence: Under the second-order sufficient condition (SOSC) and semi-isolated calmness of the KKT solution mapping, the primal-dual sequences generated by the ALM for NLSDP are shown to converge locally at an asymptotic Q-superlinear (or Q-linear) rate.
  • Sufficient Conditions for Semi-Isolated Calmness: The paper provides sufficient conditions for the semi-isolated calmness of the KKT solution mapping, which are crucial for the main convergence result.
  • Uniform Quadratic Growth: The analysis demonstrates the uniform quadratic growth condition for the augmented Lagrangian function, which is a standard requirement for proving convergence rates of optimization algorithms.
  • Illustrative Examples: Two examples are provided to illustrate that the conditions required for the main results can be satisfied.

Limitations and Future Work

  • Local Convergence: The analysis focuses on local convergence, meaning it guarantees convergence from a sufficiently close starting point to a stationary point. Global convergence properties are not the primary focus.
  • Practical Error Criteria: While the paper analyzes the convergence of an inexact ALM, it does not propose a practical relative error criterion for the subproblem solutions. This is identified as a future research direction.
  • Primal Convergence Rate: The paper primarily establishes primal-dual convergence. Further work is suggested to investigate whether primal convergence can be shown to be linear under weaker conditions.
  • Assumption 1: The paper introduces "Assumption 1" for the case where the Lagrange multiplier lies on the relative boundary of its set. While its validity is discussed in certain circumstances and illustrated with examples, further investigation into its general applicability and potential relaxation is suggested.

Summary updated

BibTeX
@article{wang2024local,
  author = {Shiwei Wang and Chao Ding},
  title = {{Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming}},
  journal = {Comput. Optim. Appl},
  year = {2024},
  doi = {10.1007/s10589-023-00520-0},
}
Figure