title: A Primal-Dual Augmented Lagrangian Method for the Solution of Convex Semidefinite Programming Problems
title: Eine Primal-Dual Augmented Lagrangian Methode zur Lösung von konvexen semidefiniten Programmierproblemen
Creators: name: Kavand, Arefeh
Publisher: name: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Year: 2024

description: This thesis introduces a Penalty/Barrier Multiplier (PBM) approach within the augmented Lagrangian framework, to address convex semidefinite programming problems characterized by linear objective functions and linear matrix inequality (LMI) constraints. At the core of this work is a comprehensive convergence analysis carried out for this method. In the first part of this thesis, we provide an exploration of preliminaries, including crucial definitions, assumptions, such as the Slater's constraint qualification applied to both our primal and dual SDP problems, as well as the fundamental concepts related to exact penalty functions. Building upon these essential foundations, we introduce the PBM Augmented Lagrangian (PBM-AL) algorithm, which incorporates a specific matrix penalty function. Our analysis uses the established equivalence between the PBM-AL algorithm and the dual Proximal-Point Algorithm (PPA), where the produced multiplier in PBM-AL coincides with the variables of the dual PPA. This alignment is achieved by expressing the proximal term as a non-quadratic distance-like function linked to the Fenchel conjugate of the primal penalty function. This equivalence serves as the basis for our dual convergence analysis for PBM-AL, under the assumption that the sequence of the penalty parameters is a decreasing sequence approaching zero. Subsequently, we delve into the details of the primal convergence analysis. In our ongoing exploration, we are enhancing the stability of the PBM-AL algorithm by integrating a concept for Lagrange multiplier damping. This adjustment is accompanied by a thorough convergence analysis to ensure the preservation of convergence properties in this modified context. We introduce the Fenchel primal and dual optimization pair, which are the unconstrained minimization of the augmented Lagrangian function and the dual proximal-point maximization problem. Two pivotal concepts of weak and strong Fenchel duality emerge from this framework, playing a crucial role in shaping subsequent analyses. Utilizing the principles of Fenchel duality, we establish specific theoretical stopping criteria to enable the avoidance of obtaining an accurate solution for the sub-problems. It is noteworthy that in this scenario, we assume the algorithm initiates with a fully feasible multiplier, thus earning its designation as a theoretical algorithm. Subsequently, we present the convergence analysis of both the dual multiplier sequence generated by this algorithm and its primal counterpart. In our experiments, achieving full precision in solving the Newton-type systems arising within the PBM-AL algorithm, is often so expensive. This led us to explore the possibilities where the algorithm starts without a fully feasible dual variable. To investigate convergence, we introduced an $\ell_1$ penalty function, penalizing violations from equality constraints. Establishing a lower bound for the associated penalty parameter ensures its exactness. Introducing implementable stopping criteria, based on Fenchel duality, we analyze both dual and primal convergence in this setting as well. In order to generate multipliers that meet the so-called early stopping criteria is not possible within the original PBM-AL algorithm. This realization inspired us to introducing the Primal-Dual Augmented Lagrangian method (PDAL). Using this approach, we formulate a hybrid PDAL algorithm, which employs a direct solver to handle the primal-dual Newton system and integrates a hybrid primal-dual update strategy. Motivated by the necessity for iterative solvers to tackle large-scale SDP problems, we delve into the complexity associated with both the PBM-AL and PDAL approaches. Assuming a low-rank assumption for our dual variables, we introduce a practical preconditioner along with a Preconditioned Conjugate Gradient (PCG) into our hybrid PDAL algorithm. To demonstrate the efficiency of our proposed algorithms, the thesis presents numerical results for three distinct problem classes. We evaluate the performance of our hybrid PDAL algorithm by employing direct solvers to handle the Newton system and applying our derived practical stopping criteria. For large-scale problems, we employ iterative solvers with and without a preconditioner, and we assess the hybrid PDAL-PCG algorithm with some heuristic stopping criteria.