Inexact Augmented Lagrangian Methods for Conic Optimization: Quadratic Growth and Linear Convergence

Authors: feng-yi  liao
lijun  ding
yang  zheng
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 07:55:49

Abstract: Augmented Lagrangian Methods (ALMs) are widely employed in solving constrained optimizations, and some efficient solvers are developed based on this framework. Under the quadratic growth assumption, it is known that the dual iterates and the Karush–Kuhn–Tucker (KKT) residuals of ALMs applied to conic programs converge linearly. In contrast, the convergence rate of the primal iterates has remained elusive. In this paper, we resolve this challenge by establishing new $\textit{quadratic growth}$ and $\textit{error bound}$ properties for primal and dual conic programs under the standard strict complementarity condition. Our main results reveal that both primal and dual iterates of the ALMs converge linearly contingent solely upon the assumption of strict complementarity and a bounded solution set. This finding provides a positive answer to an open question regarding the asymptotically linear convergence of the primal iterates of ALMs applied to conic optimization.

Main paper: 
 introduction: 
 We consider the standard primal and dual semidefinite programs (SDPs) of the formEQUATIONEQUATIONwhere the problem data consists of a cost matrix C ∈ S n , a constant vector b ∈ R m , a linear mapA : S n → R m A(X) = [⟨A 1 , X⟩ , • • • , ⟨A m , X⟩] T with A 1 , • • • , A m ∈ S n ,A * : R m → S n as A * (y) = m i=1 A i y i that satisfy ⟨A(X), y⟩ = ⟨X, A * (y)⟩ , ∀X ∈ S n , y ∈ R m . SDPs are a broad and powerful class of conic programs, which include linear programs and secondorder cone programs as special cases. The class of SDPs has found an extensive list of applications, including control theory [1] , combinatorial optimization [2] , polynomial optimization [3] , machine learning [4] [5] [6] , and beyond [7] . Meanwhile, many algorithms have been developed to solve (P) and (D), ranging from reliable interior point methods [8] [9] [10] to scalable first-order methods [11] [12] [13] [14] .In particular, it is demonstrated that Augmented Lagrangian methods (ALMs) [15, 16] are suitable for solving large-scale optimization problems. Some efficient ALM-based algorithms have been developed to solve (P) and (D). For example, the celebrated low-rank matrix factorization [17] was integrated with ALM for efficient algorithm design. A semi-smooth Newtown-CG algorithm was proposed for ALM to solve SDPs with many affine constraints in [18] . An enhanced version was introduced in [19] to tackle degenerate SDPs by combining a warm starting strategy. The algorithms [18, 19] have been implemented into a solver, SDPNAL+, which has shown very impressive numerical performance in benchmark problems. Other recent ALM-based algorithms include [20] [21] [22] .Despite the impressive practical performance, theoretical convergence guarantees of applying ALMs to (P) and (D) are less complete. Thanks to the seminal work [23] , it is well-known that running ALMs for the primal (P) is equivalent to executing the proximal point method (PPM) for the dual (D). Thus, the classical convergences of ALM are typically inherited from PPM, which only guarantees that the dual iterates converge linearly when a Lipschitz continuity property is satisfied [24] . The Lipchitz condition requires (P) to have a unique solution. The uniqueness assumption was relaxed in [25] , which allows multiple optimal solutions but requires an error bound property. Recently, this error bound property was established in [26] in a general conic optimization setup. The work [26] also proves linear convergence of KKT residuals when applying ALM to convex composite conic programming. However, due to the connections between ALM and PPM, all these results only guarantee linear convergence for the dual iterates, while the convergence rate of the primal iterates in ALM remains unclear. Indeed, it is noted in [21, 26] that the problem of whether the primal sequence generated by the ALM can also converge asymptotically linearly is open. This asymmetry in convergence guarantees is notably dissatisfying, especially considering the elegant duality in (P) and (D). In this paper, our main goal is to establish linear convergence guarantees for both primal and dual iterates when applying an inexact ALM to SDPs (either (P) or (D)), under the usual assumption of strong duality and strict complementarity.Our contributions. To resolve the challenge, we have made novel contributions from two aspects. On the problem structure side:(a) Under the standard strict complementarity assumption, we establish the quadratic growth and error bound for both primal and dual SDPs (P) and (D) over any compact set containing an optimal solution (see Theorems 1 and 2). Our results not only extend the findings of [27] from a small (yet unknown) neighborhood to any compact set, benefiting the analysis of iterative algorithms, but also improves the recent results in [28] [29] [30] ; see Remark 1 for a comparison. (b) To establish the quadratic growth, we unveil a new characterization of the preimage of the subdifferential of the exact penalty functions for SDPs. This reveals a useful connection between exact penalty functions and indicator functions (see (11) in Lemma 3) . We believe that this new characterization is of independent interest. (c) Using the new characterization, we further provide a new and simple proof for the growth properties in the exact penalty functions of S n + (see Appendix B), and clarify some subtle differences in constructing exact penalty functions (see Section 3.1 and Remark B.1).On the algorithm analysis side:(a) By leveraging the established quadratic growth and error bound, we show that applying ALM to solve either the primal or dual SDPs (P) and (D) has linear convergence for both the primal and dual iterates (see Theorem 3). (b) We establish symmetric versions of inexact ALMs for solving both the primal and dual conic programs (see Section 4 and Appendix E.3), which is less emphasized in the literature. (c) We clarify the subtlety concerning the (in)feasibility of the dual iterates by inexact ALMs (see Section 4.2), which is an important issue concerning the relationship between PPM and ALM.We here review some closely related results in the literature.Quadratic growth and error bound. Many studies have been dedicated to establishing quadratic growth or error bound for conic optimizations under various assumptions [28, 31, 27, [32] [33] [34] [35] . Starting from the famous Hoffman's lemma [36] , a global error bound for linear systems has been established, which was later extended to a partially infinite-dimensional case [37] . Sturm investigated the error bound for SDPs, in which the exponent term is bounded by 2 d with d being the sigularity degree that is at most n -1 [32] . Zhang provided a simple proof of error bound for a feasibility system under Slater's condition [33] . Zhou and So provided a unified proof to establish error bound for a class of structured convex optimization [35] . The results in [35] are generalized to convex problems with spectral functions [31] . Drusvyatskiy and Lewis discussed quadratic growth for a convex problem of the form min x f (Ax) + g(x) under dual strict complementarity [34, Section 4] . Very recently, Ding and Udell established an error bound property for general conic programs via an elementary framework using strict complementarity [28] . All the aforementioned results have slightly different assumptions, resulting in different forms of quadratic growth properties. They are not directly applicable to our purpose of establishing linear convergences of primal and dual iterates in ALM; a detailed comparison will be provided in Remark 1 after introducing our main result.Augmented Lagrangian method (ALM) and Proximal point method (PPM). The ALM is first introduced in [15, 16] to improve numerical performance of penalty methods. It is shown by Rockafellar that the augmented dual function is continuously differentiable [38] , and the ALM can be viewed as an augmented dual ascent method [24] , thus the convergence of ALM can be analyzed via dual ascent. The seminal work [23] established a strong relation between ALM and PPM: the dual iterate by ALM is the same as the proximal update on the dual function by PPM.From the convergence of PPM, we know that the dual iterates of ALM converge linearly when the preimage of the subdifferential map of the dual function is Lipschitz continuous at the origin [24] . However, the Lipchitz condition requires the solution to be unique, which is not suitable for many practical applications. Luque made an important extension in PPM to allow multiple solutions while maintaining linear convergence [25] . Recently, Cui et. al relaxed the Lipschitz assumption to upper-Lipschtiz continuous which allows multiple primal and dual solutions [26] . In addition, the KKT residuals of convex composite conic programs are shown to converge linearly under the assumption that the dual function satisfies quadratic growth [26] . The primal iterates of ALM are also known to converge linearly under a much stronger Lipschitz assumption on the augmented Lagrangian function [23, 26] . As pointed out in [26, Section 3] , the Lipschitz property of the Lagrangian function is more conservative than the quadratic growth of the primal or dual function. To the best of our knowledge, when applying ALM to conic optimization (P) and (D), the problem of whether the primal iterates converge linearly under the normal quadratic growth condition remains open.Paper outline. The rest of this paper is structured as follows. Section 2 reviews some preliminaries in SDPs and PPM. Section 3 establishes quadratic growth and error bound properties. Section 4 establishes the linear convergence of primal and dual iterates of ALMs under standard assumptions. Section 5 presents numerical experiments, and Section 6 concludes the paper. While all results are presented for SDPs, analogous versions exist for other conic programs, such as LPs and SOCPs. 
strong duality and strict complementarity: 
 In this paper, we assume the linear mapping A to be surjective (or A * is injective, thus y and Z have a unique correspondence). This is equivalent to A 1 , • • • , A m being linear independent. We here introduce two important regularity conditions: strong duality and strict complementarity. Definition 1 (Strong duality). We say (P) and (D) satisfies strong duality if we have p ⋆ = d ⋆ .Strong duality only requires the optimal values to be the same. The existence of optimal primal and dual variables (X ⋆ , y ⋆ , Z ⋆ ) is ensured by the primal and dual Slater's condition [8, Theorem 3.1], i.e., there exist primal and dual feasible points X and y satisfying X ∈ int(S n + ) and C -A * (y) ∈ int(S n + ). Let Ω P ⊆ S n and Ω D ⊆ R m × S n denote the optimal solutions of (P) and (D), respectively,EQUATIONEQUATION) Under the primal and dual Slater's condition, the solution sets Ω P , Ω D are nonempty and compact (see e.g., [30, Section 2] or [29, Prop. 2.1]). We further have ⟨Z ⋆ , X ⋆ ⟩ = 0, ∀X ⋆ ∈ Ω P , (y ⋆ , Z ⋆ ) ∈ Ω D , which is called complementary slackness.Next, we introduce another regularity condition: dual strict complementarity, which is the key to ensuring many nice properties in a range of conic problems [34, 28, 35] . Definition 2 (Dual strict complementarity for SDPs). Given a pair of optimal solutionsX ⋆ ∈ Ω P , (y ⋆ , Z ⋆ ) ∈ Ω D , we say that (X ⋆ , y ⋆ , Z ⋆ ) satisfies dual strict complementarity if X ⋆ ∈ relint(N (S n + ) • (-Z ⋆ )), where (S n + ) • is the polar cone of S n + , N (S n + ) • (-Z ⋆ )denotes the normal cone of (S n + ) • at -Z ⋆ , and relint denotes relative interior. If (P) and (D) have one such pair, we say that (P) and (D) satisfy dual strict complementarity.We note that the usual notion of strict complementarity for SDPs is equivalent to Definition 2, as pointed out in [28, Appendix B] . For completeness, we also review the standard notion of strict complementarity in Appendix A.1. The notion of (dual) strict complementarity is not restrictive, and it holds generically for conic programs [39] , [40, Theorem 15] . Recently, it has been revealed that many structured SDPs from practical applications also satisfy strict complementarity [41] . One can also define primal strict complementarity, and the primal and dual strict complementarity are not equivalent in general, but they are equivalent for the so-called self-dual cones, such as S n + .It is now well-known that running ALMs for the primal (P) is equivalent to executing a PPM for the dual (D), and vice versa [23] . We here give a quick review of PPMs and their standard convergences.Let f : R n → R be a proper closed convex function, and consider the problem f ⋆ = min x∈R n f (x). Let S = argmin x f (x), which we assume to be nonempty. We define the proximal operator asEQUATIONwhere α > 0. Starting with an initial point x 0 ∈ R n , the PPM generates a sequence of points as follows x k+1 = prox c k ,f (x k ), k = 0, 1, 2, . . ., where {c k } k≥0 is a sequence of positive numbers bounded away from zero. The proximal operator ( 2) is always well-defined thanks to strong convexity.In practice, the proximal operator (2) may not be easily evaluated, and thus an inexact version is often used [42] . In particular, an inexact PPM generates a sequence of points asEQUATIONTwo classical types of inexactness, originating from the seminal work [42] , areEQUATIONEQUATIONwhere {ϵ k } k≥0 and {δ k } k≥0 are two sequences of inexactness for (3). The classical work [42] has established asymptotic convergence of the iterates x k from (3) when using criterion (a). Fast linear convergences have also been established under various regularity conditions, such as the inverse of the subdifferential (∂f ) -1 is locally Lipschitz at 0 [42] (or relaxed to be upper Lipschitz continuous at 0 [25] ), and more generally ∂f is metrically subregular [27, 43] (or f satisfies quadratic growth [34, 44] ). Recall that f satisfies quadratic growth if there exists a constant µ q > 0 such thatEQUATIONwhere U is a neighborhood containing an optimal solution x ⋆ ∈ S. Convergence results for (3) are: Lemma 1. Let S = argmin x∈R n f (x) and suppose S ̸ = ∅. Let {x k } k≥0 be a sequence from (3). > 0 such that dist(x k+1 , S) ≤ θk dist(x k , S), ∀k ≥ k, where θk = θ k +2δ k 1-δ k with θ k = 1/ c k µ q +1 < 1.The first asymptotic convergence is taken from [42, Theorem 1], and different proofs for the second linear convergence under (QG) are available, and a simple one can be found in [44, Theorem 5.3] . Criterion (a) guarantees the iterate x k will arrive within a neighbor U where (QG) holds after some number k, then criterion (b) ensures the linear convergence; see [44, Theorem 5.3] for details.Note that Lemma 1 only guarantees the (linear) convergence of iterates x k , which corresponds to the dual iterates in the ALM [23] (see Lemma 4 in Section 4). Thus, once a suitable condition like (QG) is established for (P) and (D), applying the ALM will enjoy linear convergence for dual iterates [21, 25, 26] . In this paper, we aim to establish linear convergences of both primal and dual iterates in the ALM, when applied to (P) or (D). For this, we first establish quadratic growth in Section 3. 
quadratic growth in sdps: 
 In this section, we identify favorable quadratic growth and error bound properties for both primal and dual SDPs in (P) and (D), under the usual assumptions of strong duality and strict complementarity (cf. Definitions 1 and 2). These favorable structural properties will allow us to establish linear convergences of both primal and dual iterates of inexact ALMs applied to either (P) or (D).To analyze PPM or ALM, we consider an equivalent reformulation of (P) or (D) in the following formEQUATIONEQUATIONwhere g (and h, respectively) is chosen as either an indicator function δ S n + or an exact penalty function, defined as2 g(X) = ρ max{0, λ max (-X)} with ρ > tr(Z ⋆ ).(6) where (y ⋆ , Z ⋆ ) ∈ Ω D can be any optimal solution. In (5) , the exact penalty function h is designed in the same way as (6) where the lower bound on ρ is replaced by ρ > tr(X ⋆ ) and X ⋆ is any optimal solution in Ω P . The common feature in (4) and ( 5) is to move the difficult conic constraint X ∈ S n + and Z ∈ S n + as a nonsmooth term g(X) and h(Z) in the cost function. It is clear that for both indicator and exact penalty functions, we have g(X) = 0, ∀X ∈ S n + and h(Z) = 0, ∀Z ∈ S n + . For clarity, we state the following technical result. Lemma 2. Suppose strong duality holds for (P) and (D). Under the choice of an indicator function or an exact penalty function in (6) , the set of optimal solutions for (4) is the same as Ω P in (1a), and the set of optimal solutions for (5) is the same as Ω D in (1b).The equivalence with an indicator function is obvious, and the equivalence with an exact penalty function has appeared in [30] and [29, Propositions 3.1&3.2] . Their proofs rely on a general characterization in exact penalty methods [45, Theorem 7.21] . In Appendix B, we present a simple, different, and self-contained proof without relying on prior results. Our proof uses a new characterization of the subdifferential of exact penalty functions (Proposition B.1), which might be of independent interest. Our first main theoretical results are the following growth and error bound properties for primal and conic programs. The proofs will be outlined in Section 3.2. Theorem 1 (Growth properties in the primal). Suppose strong duality and dual strict complementarity hold for (P) and (D). Consider the primal conic programs (P) and (4). Let ( X⋆ , ȳ⋆ , Z⋆ ) satisfy strict complementarity, and the exact penalty parameter is chosen as ρ > tr( Z⋆ ). For any compact set U ⊆ S n containing an optimal solution X ⋆ ∈ Ω P , there exist positive constants κ, γ, α > 0 such thatEQUATIONEQUATIONIf Ω P is further compact, then set U in (7a) and (7b) can be chosen as any sublevel set of f P , i.e., {X ∈ S n | f P (X) ≤ β, A(X) = b} with a finite β.In (7a), the impact of the conic constraint X ∈ S n + is reflected in the reformulated cost f P (X). When using the indicator function as f P (X) = ⟨C, X⟩ + δ S n + (X), the left-hand side of (7a) implicitly requires X ∈ S n + ; otherwise f P (X) = +∞ and thus the inequality (7a) holds trivially. If using the exact penalty function (6) , we have f P (X) = ⟨C, X⟩ + g(X) < +∞ for X / ∈ S n + , which is closer to (7b). Indeed, our proof of (7b) utilizes a characterization of the exact penalty function (6) .Both (7a) and (7b) give useful bounds when X moves away from the optimal solution set Ω P in terms of suboptimality f P (X) -p ⋆ or ⟨C, X⟩ -p ⋆ , affine feasibility ∥A(X) -b∥, and conic feasibility dist(X, S n + ). They are closely related to quadratic growth in (QG), and are also referred to error bound properties [46, 33, 28] . The error bound plays a vital role in proving fast linear convergence for many iterative algorithms [34, 35, 44, 47] . Indeed, some previous studies [27] [28] [29] [30] have established similar results to Theorem 1 for conic optimization, especially SDPs. As we will detail in Remark 1 below, our results are more general and unified. Similarly, the growth and error bound properties also hold for the dual conic program. Theorem 2 (Growth properties in the dual). Suppose strong duality and dual strict complementarity hold for (P) and (D). Consider the dual problems (D) and (5). Let ( X⋆ , ȳ⋆ , Z⋆ ) satisfy strict complementarity, and the penalty parameter is chosen as ρ > tr( X⋆ ). For any compact set V ⊆ R m ×S n containing an optimal solution (y ⋆ , Z ⋆ ) ∈ Ω D , there exist constants κ, γ, α > 0 such thatEQUATIONd ⋆ -⟨b, y⟩ + γ∥C -A * (y) -Z∥ + α • dist(Z, S n + ) ≥ κ • dist 2 ((y, Z), Ω D ), ∀(y, Z) ∈ V. (8b) If Ω D is further compact, then set V can be chosen as any sublevel set of f D , i.e., {(y, Z) ∈ R m ×S n | f D (y, Z) ≤ β, C + Z = A * (y)} with a finite β.The compactness of Ω P and Ω D in Theorems 1 and 2 is not restrictive, as it can be ensured by the dual and primal Slater's conditions (and A * is injective) respectively; see e.g., [29, Proposition 2.1] . Remark 1. Our results in Theorems 1 and 2 are more general and unified than previous ones [27] [28] [29] [30] . Theorems 1 and 2 hold for both the indicator function and the penalty function (6) , while all previous results [27] [28] [29] [30] have only discussed either one of them. We provide more comparisons below. The guarantees in (7a) and (8b) directly lead to a quadratic growth property of f P and f D :EQUATIONf D (y, Z) + d ⋆ ≥ κ•dist 2 ((y, Z), Ω D ), ∀(y, Z) ∈ V ∩ {(y, Z) ∈ R m ×S n | A * (y) + Z = C}. (9b)When considering indicator functions, this property ( 9) is more general than [27, Corollary 3.1] since we allow for any compact set U (and also any sublevel set of f P or f D ). In contrast, the size of the neighborhood around an optimal solution X ⋆ in [27, Corollary 3.1] depends on the eigenvalues of an optimal dual solution Z ⋆ . Thus the neighborhood only exists but its size might be unknown. Furthermore, our results (7a) and (8a) allow for the residual of the affine constraints A(X) = b and C -A * (y) = Z, while [27, Corollary 3.1] requires strict affine feasible points.When considering exact penalty functions, similar quadratic growth properties appear in [29, 30] . However, the penalty ρ in [29, 30] needs to be as large as ρ ≥ 2 sup (y ⋆ ,Z ⋆ )∈ΩD tr(Z ⋆ ). Our results in Theorems 1 and 2 only require a smaller constant as ρ > tr( Z⋆ ) where Z⋆ is an optimal dual solution satisfying strict complementarity, and this result is established via a new and simple argument (see Proposition B.2 in the appendix). Finally, an error bound similar to (7b) was also established in [28, Corollary 1] under similar assumptions of strong duality and strict complementarity. Our error bound (7b) does not require the absolute value of f P (X) -p ⋆ , and our proof strategy relies on a new characterization of exact penalty functions (see Lemma 3), which offers a new (possibly simpler) perspective than [28, Corollary 1] . The dual property (8b) is new and not discussed in [28] . □ Remark 2 (Conic programs). Theorems 1 and 2 are stated specifically for SDPs (P) and (D). It is known that linear programs (LP) and second-order cone programs (SOCP) are special cases of SDPs. Therefore, results similar to Theorems 1 and 2 when replacing S n + by nonnegative orthant or second-order cone also exist. Theorems 1 and 2 hold for a general class of conic programs.We here provide key proof sketches for Theorems 1 and 2. One key step is the following growth properties of an indicator function and a penalty function. Lemma 3. Let X, Z ∈ S n + satisfying X, Z = 0 (i.e., both X and Z are on the boundary unless one of them is zero). If l :EQUATIONthen we have thatEQUATIONMoreover, for any positive value µ ∈ (0, ∞), there exists a positive constant κ such thatEQUATION)Note that l in ( 10) is related to, but not identical to, the exact penalty function in (6) . The proof of Lemma 3 heavily exploits the nice self-dual structure of the cone S n + . For better clarity, we provide the proofs of ( 11) and ( 12) in Proposition B.1 and Appendix C respectively. Remark 3. We believe that the results in Lemma 3 are of independent interest, especially in terms of the penalty function (10) . Building upon (12) , one can further show l is metrically subregular [48, Theorem 3.3] . The most closely related characterization is [27, Proposition 3.3] , which focuses solely on the indicator function of the positive semidefinite cone S n + . However, even in this scenario, the result in [27, Proposition 3.3] only guarantees the existence of a small neighborhood around X. In contrast, our result (12) works for any closed ball B( X, µ) around X with a finite radius µ > 0. □ Upon establishing Lemma 3, with bounded linear regularity (see Appendix A.4) that is guaranteed by dual strict complementarity, we can establish the following growth properties for (4) and ( 5). Proposition 1. Consider primal and dual conic programs (P) and (D) and their equivalent forms in (4) and (5) respectively. Suppose strong duality and dual strict complementarity hold for (P) and (D). Let (X ⋆ , y ⋆ , Z ⋆ ) be a pair of primal and dual optimal solutions, i.e., X ⋆ ∈ Ω P and (y ⋆ , Z ⋆ ) ∈ Ω D . For any µ > 0, there exist positive constants κ 1 , γ 1 , κ 2 , γ 2 such thatf P (X) -f ⋆ P + γ 1 ∥A(X) -b∥ ≥ κ 1 • dist 2 (X, Ω P ), ∀X ∈ B(X ⋆ , µ), f D (y, Z) -f ⋆ D + γ 2 ∥C -A * (y) -Z∥ ≥ κ 2 • dist 2 ((y, Z), Ω D ), ∀(y, Z) ∈ B((y ⋆ , Z ⋆ ), µ).The proof of Proposition 1 is given in Appendix D.1. We now see that Theorems 1 and 2 are direct consequences of Proposition 1 as max{0, λ max (-X)} ≤ dist(X, S n + ) for all X ∈ S n . The compactness statement in Theorems 1 and 2 comes from the fact that the solution set Ω P (resp. Ω D ) is compact if and only if any sublevel set of f P (resp. f D ) is compact (see, e.g., [29, Lemma D.1] ). 
augmented lagrangian methods (alms) for sdps: 
 In this section, we prove that both primal and dual iterates of ALMs, when applied to (P) and (D), enjoy linear convergence under the usual assumption of strict complementarity.In principle, ALM can be applied to solve both (P) and (D). However, most existing results focus on solving (D) [18, 19] . For simplicity, we here focus on one formulation of the augmented Lagrangian function for (P). The dual formulation is presented in Appendix E.3 for completeness.We start by introducing two dual variables y ∈ R m and Z ∈ S n + and defining the Lagrangian function for (P) as L 0 (X, y, Z) = ⟨C, X⟩ + ⟨y, b -A(X)⟩ + ⟨Z, X⟩. The corresponding Lagrangian dual function and dual problem read asEQUATION)It can be verified the dual in ( 13) is the same as the dual conic program (D). Given a penalty parameter r > 0, the Augmented Lagrangian function of (P) corresponding to L 0 is defined asEQUATIONwhere Π S n + (•) denotes the orthogonal projection onto the coneS n + . Note that L r is continuously differentiable as ∥Π S n + (•)∥ 2 is continuously differentiable [18, Section 1]. Given initial points (y 0 , Z 0 ) ∈ R m × S n+ and a sequence of positive scalars r k ↑ r ∞ < +∞, the inexact ALM generates a sequence of {X k } (primal variables) and {y k , Z k } (dual variables) asEQUATIONEQUATIONEQUATIONFor notational convenience, we write w = (y, Z) and w k = (y k , Z k ) and consider the following two inexactness criteria for solving (15a) (since it can be a challenge to solve (15a) exactly):L r k (X k+1 , w k ) -min X∈S n L r k (X, w k ) ≤ ϵ 2 k /(2r k ), ∞ k=1 ϵ k < ∞, (A ′ ) L r k (X k+1 , w k ) -min X∈S n L r k (X, w k ) ≤ δ 2 k ∥w k+1 -w k ∥ 2 /(2r k ), ∞ k=1 δ k < ∞. (B ′ )The two stopping criteria above are suggested by the seminal work of Rockafellar [23] .After [23] , one classical method for analyzing the convergence of the inexact ALM ( 15) is to utilize the connection between ALM and PPM. We review the following important lemma.Lemma 4 ([23, Proposition 6] ). The dual iterates w k+1 = (y k+1 , Z k+1 ) in (15b) and (15c) satisfy the following relationship∥w k+1 -prox r k ,-g0 (w k )∥ 2 /(2r k ) ≤ L r k (X k+1 , w k ) -inf X∈S n L r k (X, w k ), where g 0 is the Lagrangian dual function in (13) .If (15a) is updated exactly, Lemma 4 confirms that w k+1 = prox r k ,-g0 (w k ): the dual iterate of the ALM agree with the PPM iterate for the dual problem (13) . If (15a) is updated inexactly, the iterate w k+1 may not satisfy the affine constraint C = Z k+1 + A * (y k+1 ). Moreover, viewing Lemma 4, the stopping criteria (A ′ ) and (B ′ ) naturally imply that the dual iterate w k+1 satisfies∥w k+1 -prox r k ,-g0 (w k )∥ ≤ ϵ k and ∥w k+1 -prox r k ,-g0 (w k )∥ ≤ δ k ∥w k+1 -w k ∥.Then, we can establish the convergence of the dual sequence {w k } in ( 15) from Lemma 1 via PPM.In particular, this observation was first discovered in [23] and later tailored in convex composite conic programmings in [26] . We summarize asymptotic convergences of ( 15) below. Proposition 2 (Asymptotic convergences). Consider (P) and (D). Assume strong duality holds andΩ D ̸ = ∅. Let {X k , w k } be a sequence from the ALM (15) under (A ′ ).The following hold.(a) The dual sequence {w k } is bounded. Further, lim k→∞ w k = w ∞ ∈ Ω D (i.e., the whole sequence converges to a dual optimal solution). (b) The primal feasibility and cost value gap satisfy dist(X k+1 , S n+ ) ≤ ∥Z k -Z k+1 ∥/r k → 0, ∥A(X k+1 ) -b∥ = ∥y k -y k+1 ∥/r k → 0, ⟨C, X k+1 ⟩ -p ⋆ ≤ L r k (X k+1 , w k ) -min X∈S n L r k (X, w k ) + (∥w k ∥ 2 -∥w k+1 ∥ 2 )/(2r k ) → 0. (c) If the primal solution set Ω P in (1a) is nonempty and bounded, then the primal sequence {X k } is also bounded, and all of its cluster points belongs to Ω P .Proof. We give the sketch of proof for parts (a) and (b). A complete proof can be found in Appendix E.1. Part (a) comes directly from the PPM convergence Lemma 1 as Lemma 4 and the stopping criteria (A ′ ) naturally imply the dual iterate w k+1 satisfies ∥w k+1 -prox r k ,-g0 (w k )∥ ≤ ϵ k and ∞ k=1 ϵ k < ∞. In part (b), the first inequality uses the fact that Z k+1 + (X k+1 -X k )/r k ∈ S n + by performing Moreau decomposition [49, Exercise 12.22] on r k X k+1 -Z k and using the update rule (15b); The second inequality comes directly from (15c); The last inequality uses the definition of L r k (X k+1 , w k ) in ( 14) and the fact minX∈S n L r k (X, w k ) ≤ p ⋆ .Part (c) is a consequence of part (b) and the fact that Ω P is bounded if and only if for anyγ ∈ R 3 the set {X ∈ S n | dist(X, S n + ) ≤ γ 1 , ∥A(X) -b∥ ≤ γ 2 , ⟨C, X⟩ ≤ γ 3 } is bounded [23, page 110].Proposition 2 establishes the asymptotic convergences for both the primal and dual variables. The linear convergence of the dual iterates can also be deduced when the negative of the dual g 0 defined in ( 13) satisfies (QG). However, the rate of the primal iterates remains unclear. Here, leveraging the error bound (8b), we also derive a linear convergence of the primal iterates, which is one main technical contribution of this work. We summarize linear convergence results below. Theorem 3 (Linear convergences). Consider (P) and (D). Assume strong duality and dual strict complementarity holds (implying Ω P ̸ = ∅ and Ω D ̸ = ∅). Let {X k , w k } be a sequence from the ALM (15) under (A ′ ) and (B ′ ). The following statements hold.(a) (Dual iterates and KKT residuals) There exist constants k > 0 such that for all k ≥ k, we haveEQUATIONwhere 0 < µ k < 1, µ ′ k > 0, and µ ′′ k > 0 are positive finite constants. (b) (Primal iterates) If Ω P is bounded, then the primal sequence {X k } also converges linearly to the solution set Ω P , i.e., there a constant k > 0 such that for all k ≥ k,EQUATIONwhere τ k > 0 is a finite constant.Proof. The proof of part (a) is largely motivated by the techniques in [26] that focus on ALMs on dual SDPs. Part (b) is a consequence of the error bound (7b). Here, we highlight the key steps of the proof of part (a) due to the page limit, and detailed arguments about part (a) can be found in Appendix E.2. Note that if dual strict complementarity holds, Theorem 2 (with h in (5) as an indicator function) guarantees the following two nice properties: 1) -g 0 in (13) satisfies quadratic growth in (9b); 2) the error bound (7b) holds.1. By the discussion after Lemma 4, since (A) and (B ′ ) are in force, the dual sequence{w k } satisfies ∥w k+1 -prox r k ,-g0 (w k )∥ ≤ ϵ k , ∥w k+1 -prox r k ,-g0 (w k )∥ ≤ δ k ∥w k+1 -w k ∥, ∀k ≥ 0.Applying the convergence result of PPM in Lemma 1 yields the linear convergence of the dual distance, i.e., there exists ak 1 ≥ 0 such that dist(w k+1 , Ω D ) ≤ µ k • dist(w k , Ω D ), µ k < 1, ∀k ≥ k 1 . Using part (b) in Proposition 2 and ∥w k+1 -w k ∥ ≤ 1 1-δ k dist(w k , Ω D ) if δ k < 1, we can show max{dist(X k+1 , S n + ), ∥A(x k+1 ) -b∥} ≤ 1 (1 -δ k )r k dist(w k , Ω D ), ⟨C, X k+1 ⟩ -p ⋆ ≤ δ 2 k ∥w k+1 -w k ∥ + ∥w k ∥ + ∥w k+1 ∥ 2r k (1 -δ k ) dist(w k , Ω D ).Finally, as δ k → 0, there exists k 2 ≥ 0 such that δ k < 1 and for all k ≥ k 2 . Thus, part (a) then follows from taking k = max{k 1 , k 2 }.2. Note that the error bound (7b) and the assumption that Ω P is bounded guarantee that for any bounded set U containing Ω P , there exist constantsα 1 , α 2 , α 3 > 0 such that ⟨C, X⟩ -⟨C, X ⋆ ⟩ + α 1 ∥A(X) -b∥ + α 2 • dist(X, S n + ) ≥ α 3 • dist 2 (X, Ω P ), ∀X ∈ U. (18) By Proposition 2 -part (c), the sequence {X k } is bounded. Let U ⊆ S nbe a bounded set that contains Ω P and all the iterates {X k }. Combing ( 18) with ( 16), we haveα 3 • dist 2 (X k+1 , Ω P ) ≤ (µ ′′ k + (α 1 + α 2 )µ ′ k ) • dist(w k , Ω D ), ∀k ≥ k.Dividing both sides by α 3 leads to the desired result in part (b). This completes the proof.To our best knowledge, achieving linear convergence for the primal iterates of inexact ALMs requires a significantly stronger condition on the Lagrangian function [23, Theorem 5] and implementing an additional stopping criterion [26, Proposition 3] . Unfortunately, as highlighted in [26, Section 3] , such an assumption in [23, Theorem 5] can easily fail for general conic programs.Our result Theorem 3, however, reveals that the linear convergence of the primal iterates also happens under the standard assumption of strict complementarity and bounded primal solution set. This suggests that primal linear convergence is often expected since strict complementary is a generic property of conic programs [40, Theorem 15] . Our result not only completes theoretical convergences of inexact ALMs but also offers insights for practical successes in [18, 19] . Remark 4 (Strict complementarity). As we see in the proof of Theorem 3, strict complementarity is the key to ensure that 1) the negative of the function g 0 in (13) satisfies quadratic growth; 2) the error bound property (E.2) holds for the primal conic program. The quadratic growth is used to derive the dual linear convergence (16) , and the error bound is to conclude the primal linear convergence. □ 
numerical experiments: 
 In this section, we present numerical experiments to examine the empirical performance of ALM introduced in Section 4. We consider two applications in combinational problems and machine learning, including the SDP relaxation of maximum cut (Max-Cut) problem [50] and linear Support Vector Machine (SVM). The Max-Cut problem and the linear SVM can be formulated asmin X∈S n ⟨C, X⟩ subject to Diag(X) = 1, X ∈ S n + , min x∈R n ,t∈R m λ1 T t + 1 2 ∥x∥ 2 , subject to diag(b)Ax + 1 ≤ t, t ∈ R m + .where 1 is an all one vector, A ∈ R m×n and b ∈ R m are problem data in the linear SVM, diag(b) denotes the diagonal matrix with b as the diagonal elements, and λ > 0 is a constant. We can see that Max-Cut is of the same form as (P). Despite linear SVM is not in the form of SDP (P) but a quadratic program, the corresponding ALM with similar convergence guarantees can also be derived since a quadratic program is a special case of SDP. For Max-Cut problem, we select the graph G 1 , G 2 , and G 3 from the website https://web.stanford.edu/~yyye/yyye/Gset/ and only take the first 20 × 20 submatrix as the considered problem data C. For linear SVM, we randomly generate the problem data A ∈ R 10×100 and b ∈ {-1, 1} 100 . We then apply the ALM (15) for those instances and compute the relative primal and dual cost value gap and the relative feasibility residuals as followsϵ 1 = | ⟨C, X k ⟩ -p ⋆ | 1 + |p ⋆ | , ϵ 2 = | ⟨b, y k ⟩ -d ⋆ | 1 + |d ⋆ | , η 1 = ∥A(X k ) -b∥ 1 + ∥b∥ , η 2 = ∥X k -Π S n + (X k )∥ 1 + ∥X k ∥ , η 3 = ∥C -A * (y k ) -Z k ∥ 1 + ∥C∥ , η 4 = ∥Z k -Π S n + (Z k )∥ 1 + ∥Z k ∥ , η 5 = | ⟨C, X k ⟩ -⟨b, y k ⟩ | 1 + |d ⋆ | .The numerical results are presented in Figure 1 . In all cases, the primal and dual cost value gap and the KKT residuals all converge linearly to at least the accuracy of 10 -5 . The oscillation or flattening behavior that appears in the tail (when the iterates are close to the solution set) could be due to the inaccuracy of the subproblem solver and computational impreciseness. A detailed theoretical analysis of such behavior is interesting, and we leave it to future work.Further details on the algorithm parameters, problem instances, and more numerical experiments for machine learning applications can be found in Appendix F. 
conclusion: 
 In this paper, we have established the quadratic growth and error bound of two different variants (4) and ( 5) of SDPs under the condition of strict complementarity. Central to our approach is the examination of the growth properties of the indicator and exact penalty functions. By leveraging these new quadratic growth and error bounds, we establish the linear convergence of both primal and dual iterates of inexact ALMs when applied to semidefinite programs, under the usual assumption of strict complementarity and a bounded solution set on the primal side. Our result not only fills a void in the convergence theory of inexact ALMs but also offers valuable insights into the exceptional numerical performance of solvers rooted in ALMs, such as SDPNAL+ [19] . We expect further interesting applications in machine learning and polynomial optimization [11] for inexact ALMs. where X 0 ⊆ R n is a closed convex set and f, f i : E → R are proper closed convex functions. We associate each inequality constraint in (A.4) with a dual variable z i ≥ 0, and the Lagrangian functionfor (A.4) is L 0 (x, z) = f (x) + m i=1 z i f i (x). The corresponding dual function is g 0 (z) = inf x∈X0 L 0 (x, z). (A.5)One way to define the augmented Lagrangian for (A.4) is to transform the inequality constraints into equality constraints [45, Chapter 4.7] . After some manipulation (see [45, Equation 4 .79] or Appendix A.3), the classical augmented Lagrangian with parameter r > 0 for (A.4) reads asL r (x, z) = f (x) + 1 2r ∥Π R m + (z + rf (x))∥ 2 -∥z∥ 2 2 , (A.6)where Π R m + (•) denotes the Euclidean projection onto R m + . Note that L r is differentiable in z [52] . Given an initial point z 0 ∈ R m and a sequence of positive scalars r 0 ↑ r ∞ < +∞, the inexact ALM generates a sequence of {x k } (primal variables) and {z k } (dual variables) asx k+1 ≈ min x∈X0 L r k (x, z k ), (A.7a) z k+1 = z k + r k ∇ z L r k (x k+1 , z k ) = Π R m + (z k + r k f (x k+1 )), k = 0, 1, . . . . (A.7b)The convergence of x k and z k depends on the inexactness in (A.7a). For this, the seminal work by Rockafellar [23] points out an important connection between PPM and ALM, summarized below. Lemma A.1 ([23, Proposition 6] ). The dual iterate z k+1 in (A.7b) satisfies the following relationship∥z k+1 -prox r k ,-g0 (z k )∥ 2 /(2r k ) ≤ Lr k (x k+1 , z k ) -inf x∈X0 L r k (x, z k ),where g 0 is the Lagrangian dual function in (A.5), and Lr denotes an extended form of the augmented Lagrangian L r as Lr (x, z) = L r (x, z), if x ∈ X 0 , otherwise Lr (x, z) = ∞.Note the subtle difference between Lemmas 4 and A.1. If (A.7a) is updated exactly, Lemma A.1 confirms that z k+1 = prox c k ,-g0 (z k ). In other words, the dual iterates of the ALM are the same as the iterates from PPM on the dual problem (A.5). Moreover, by controlling the inexactness (A.7a), the convergence of the dual variables z k can be naturally guaranteed from Lemma 1. Motivated by (a) and (b), the following two criteria are commonly used in (A.7a)EQUATIONwhere {ϵ k } k≥0 and {δ k } k≥0 are two sequences of inexactness. Note that (A) and (B) guarantee the dual variables z k from ALM (A.7) satisfy (a) and (b) with the inexact PPM (3), respectively. Let S = argmax z≥0 g 0 (z) denote the set of optimal dual solutions for (A.4). Combining Lemma A.1 with Lemma 1, the iterates from the inexact ALM (A.7) has the following convergence guarantees. Lemma A.2. Assume S ̸ = ∅. Let {x k , z k } be a sequence generated by the inexact ALM (A.7).(a) If criterion (A) is used, then lim k→∞ z k = z ∞ ∈ S (i.e., z k converges to a dual optimal solution), and the primal sequence {x k } satisfies f i (x k+1 ) ≤ ∥z k -z k+1 ∥/c k , i = 1, . . . , m (primal feasibility), and ⟨c, x k+1 ⟩ -p ⋆ ≤ (ϵ 2 k + ∥z k -z k+1 ∥ 2 )/(2c k ) (cost value gap). (b) If both criteria (A) and (B) are used, and the dual function -g 0 in (A.5) further satisfies (QG) with a coefficient µ q > 0, then there exists a k > 0 such that dist(z k+1 , S)≤ µ k • dist(z k , S), ∀k ≥ k, where µ k = θ k +2δ k 1-δ k with θ k = 1/ c k µ q +1 < 1.The first asymptotic convergence for lim k→∞ z k = z ∞ ∈ S directly comes from Lemma 1, and the asymptotic convergence in terms of primal feasibility and cost value gap is taken from [23, Theorem 4] . The second linear convergence in Lemma A.2 is only guaranteed for the dual iterates z k , which is also implied by Lemma 1. However, the rate of the primal iterates x k is unclear even with the quadratic growth condition. With a much stronger condition on the Lagrangian, the classical result in [23, Theorem 5] can ensure linear convergence of x k . 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We have followed closely the Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer:[Yes]Justification: We have discussed the positive societal impacts from efficient algorithms to solve conic optimization. We do not see negative societal impacts of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: One straightforward way to define the augmented Lagrangian for the inequality form (A.4) is to first transform (A.4) into the following equivalent problemmin x∈X0,v≥0 f (x) subject to f i (x) + v = 0, ∀i = 1, 2, . . . , m. (A.8)Then the augmented Lagrangian for the above equality-constrained problem with a penalty term r > 0 is defined asL r (x, v, z) = f (x) + m i=1 z i (f i (x) + v i ) + r 2 m i=1 (f i (x) + v i ) 2 = f (x) + 1 2r ∥z + r(f (x) + v)∥ 2 -∥z∥ 2 .Note that L r is a decoupled quadratic function in terms of v i . Minimizing L r (x, v, z) with respect to v ≥ 0 with a fixed x and y, we derive the optimal v asv i = max 0, - z i r -f i (x) , ∀i = 1, . . . , m.Upon plugging the optimal v in the L r with some arrangements, we arrive at the classical augmented Lagrangian for the problem with inequality constraints (A.4)L r (x, z) = f (x) + 1 2r ∥Π R m + (z + rf (x))∥ 2 -∥z∥ 2 .We review an important concept: bounded linear regularity of a collection of closed convex sets. Bounded linear regularity allows us to bound (up to some constant) the distance to the intersection D (which can be complicated) by the maximum of the distance to D i , which is often easier to compute.The following result shows a sufficient condition for bounded linear regularity. (∩ i=1,2,...,r D i ) (∩ i=r+1,...,m relint(D i )) ̸ = ∅,where relint denotes the relative interior.This result indicates that a collection of closed convex sets is boundedly linear regular if the relative interiors of non-polyhedral sets have a non-empty intersection with the rest of the polyhedra. Lemma A.3 plays a key role in the proof of Theorems 1 and 2. In particular, as we will see in Appendix D.1, the optimal solution set of (P), i.e., Ω P , can be characterized asΩ P = X 0 ∩ (∂g) -1 (-Z ⋆ ), ∀(y ⋆ , Z ⋆ ) ∈ Ω D ,where X 0 = {X ∈ S n + | A(X) = b}. Thus, assuming dual strict complementarity (there exists X ⋆ ∈ relint((∂g) -1 (-Z ⋆ ))), given a compact set U ⊆ S n containing X ⋆ , Lemma A.3 ensures the following holds dist(X, Ω P ) ≤ α 1 dist(X, X 0 ) + α 2 dist(X, (∂g) -1 (-Z ⋆ )), ∀X ∈ U, where α 1 and α 2 are two positive constants.In this section, we characterize the connection between exact penalty functions and indicator functions (6) . Most importantly, we give a simple proof for the exact penalty functions. The main result is stated in Proposition B.2. We first state the preimage characterization of subdifferential mapping of the exact penalty function in Proposition B.1, which is a more general result of the first part of Lemma 3 (i.e., (11) ). The second part of Lemma 3 (i.e., (12) ) is postponed to Appendix C. Then for all S ∈ S n + satisfying ρ > tr(S), it holds that(∂l) -1 (-S) = (δ S n + ) -1 (-S) = N (S n + ) • (-S). (B.2)One can see that ( 11) is a special case of Proposition B.1 with S = Z. We postpone the proof of Proposition B.1 to Appendix B.2. Be aware that (B.2) does not mean the mappings (∂l) -1 and (δ S n + ) -1 are the same for each point in the domain, while the equality only holds for certain points satisfying the relationship with the penalty coefficient ρ in (B.1). We use a simple example to illustrate this subtlety. Example B.1. Consider l : R → R as l(x) = 2 max{0, -x} which is the scalar version of the function in (B.1) with ρ = 2. The subdifferential ∂l : R ⇒ R and ∂δ R+ = N R+ can be computed as∂l(x) =    0, if x > 0, [-2, 0], if x = 0, -2, if x < 0,and ∂δ R+ (x) =    0, if x > 0, (-∞, 0], if x = 0, ∅, if x < 0.Thus, the preimages can be verified asEQUATION∂(δ R+ ) -1 (-z) =    0, if z > 0, [0, ∞), if z = 0, ∅, if z < 0.This shows that (∂l) -1 (-z) = (δ R+ ) -1 (-z) holds only when z < 2.With the preimage characterization in Proposition B.1, the following result on the exact penalty functions follows easily by choosing the penalty term ρ correctly. Proposition B.2 (Exact penalty function). Assuming strong duality holds for (P) and (D), ( 4) is equivalent to the primal SDP (P) if the function g in ( 4) is chosen to be the corresponding indicator function, i.e., g = δ S n + , or the exact penalty function l(X) = ρ max{0, λ max (-X)} with ρ > tr(Z ⋆ ),(B.3)where (y ⋆ , Z ⋆ ) ∈ Ω D is an optimal dual solution of (D).Proof. The case for the indicator function δ S n + is clear. We consider the case for the exact penalty function. Note the dual of (4) ismax y,Z ⟨b, y⟩ subject to A * (y) + Z = C, tr(Z) ≤ ρ, Z ∈ S n + . (B.4)Let Ω P2 and Ω D2 denote the optimal solution of ( 4) and (B.4) respectively. First, it is clear that Ω D2 ⊆ Ω D as there is an extra constraint in (B.4), compared with (D). Second, as the problem is convex, a pair of primal and dual solutions ( X⋆ , ŷ⋆ , Ẑ⋆ ) solves ( 4) and (B.4) if and only if the following KKT system holdsA( X⋆ ) = b, Z ⋆ = C -A * (ŷ ⋆ ), 0 ∈ Ẑ⋆ + ∂g( X⋆ ).Then the primal solution set can be written asΩ P2 = X 0 ∩ (∂g) -1 (-Ẑ⋆ ), ∀(ŷ ⋆ , Ẑ⋆ ) ∈ Ω D2 .where X 0 = {X ∈ S n | A(X) = b}. Note that (y ⋆ , Z ⋆ ) is an optimal solution to (B.4) as (y ⋆ , Z ⋆ ) is feasible in (B.4) and ⟨b, y ⋆ ⟩ ≤ max y,Z (B.4) ≤ d ⋆ = ⟨b, y ⋆ ⟩ by construction. We can write Ω P2 asΩ P2 = X 0 ∩ (∂g) -1 (-Z ⋆ ) = X 0 ∩ (∂δ S n + ) -1 (-Z ⋆ ), where the last equality uses (∂g) -1 (-Z ⋆ ) = (∂δ S n + ) -1 (-Z ⋆ ) in (B.2) as tr(Z ⋆ ) < ρ and Z ⋆ ∈ S n + . On the other hand, we can write Ω P asΩ P = X 0 ∩ (∂δ S n + ) -1 (-Z ⋆ ).It is clear that Ω P2 = Ω P and the proof is complete.Remark B.1 (Dual problem). Note that Proposition B.2 only guarantees the cost value and solution sets of ( 4) and (P) to be the same, while the solution sets of (D) and the dual of (4) may differ, as seen in the proof of Proposition B.2. To fully equate (D) and the dual of ( 4), one can choose the penalty coefficient ρ as ρ > sup (y ⋆ ,Z ⋆ )∈ΩD tr(Z ⋆ ). This choice of ρ can guarantee every optimal solution in (D) is also an optimal solution in (B.4) as the extra constraint in (B.4) (compared with (D)) does not affect the solution set. Combining this with the fact Ω D2 ⊆ Ω D , we conclude that Ω D = Ω D2 .The following proposition showcases the subdifferential calculation of the function l(X) = ρ max{0, λ max (-X)} with ρ ≥ 0. It is a standard result of the subdifferential of the maximal eigenvalue of symmetric matrices and standard subdifferential calculus. Proposition B.3 ([55, Theorem 2] and [45, Theorem 2.87] ). Let ρ ≥ 0 and X ∈ S n with λ max (-X) having t multiplicity . The subdifferential of l(X) = ρ max{0, λ max (-X)} is characterized by∂l(X) =    0 if λ min (X) > 0, {-ρP SP T | S ∈ S t + , tr(S) ≤ 1} if λ min (X) = 0, {-ρP SP T | S ∈ S t + , tr(S) = 1} if λ min (X) < 0, (B.5)where columns of P ∈ R n×t are orthonormal eigenvectors corresponding to λ max (-X).Proposition B.4. Let Z ∈ S n + \ {0} and write Z = [P 1 P 2 ] Λ 1 0 0 0P T 1 P T 2 with Λ 1 ∈ S r ++ . Let l(X) = ρ max{0, λ max (-X)} with ρ > tr(Z). We have (∂l) -1 (0) = S n + , (∂l) -1 (-Z) = (N S n + ) -1 (-Z).Proof. The case (∂l) -1 (0) = S n + can be easily observed from the first two cases in (B.5). We then consider the case Z ∈ S n + \ {0}. Given a X ∈ S n , we use the matrix P X ∈ R n×t to denote the orthonormal eigenvectors corresponding to λ max (-X) where t is the multiplicity of λ max (-X). It follows that(∂l) -1 (-Z) = {X ∈ S n | -Z ∈ ∂l(X)} (a) = {X ∈ S n + \ S n ++ | Z ∈ ρP X SP T X , S ∈ S t + , tr(S) < 1} (b) = [P 1 P 2 ] 0 0 0 B P T 1 P T 2 | 0 ∈ R r×r , B ∈ S n-r + (c) = N S n -(-Z) = (N S n + ) -1 (-Z),The following proof is adapted from [27] . We first prove the primal case. Fix a µ > 0 and X ⋆ ∈ Ω P .As the problem is convex, a pair of primal and dual solutions ( X⋆ , ŷ⋆ , Ẑ⋆ ) solves ( 4) and its dual problem if and only if the following KKT system holdsA( X⋆ ) = b, Ẑ⋆ = C -A * (ŷ ⋆ ), 0 ∈ Ẑ⋆ + ∂g( X⋆ ).Combined with the fact that any primal and dual solution forms a pair, the optimal primal solution Ω P can be characterized asΩ P = X 0 ∩ (∂g) -1 (-Ẑ⋆ ), ∀(ŷ ⋆ , Ẑ⋆ ) ∈ Ω D ,where X 0 = {X ∈ S n | A(X) = b}. Let ( X⋆ , ȳ⋆ , Z⋆ ) be a pair of primal and dual solutions satisfying X⋆ ∈ relint((∂g) -1 (-Z⋆ )) (strict complementarity assumption). There exist α 1 , κ 1 , κ 2 > 0 such that for all X ∈ B(X ⋆ , µ) the following holdsdist 2 (X, Ω P ) = dist 2 (X, X 0 ∩ (∂g) -1 (-Z⋆ )) ≤ α 1 (dist(X, X 0 ) + dist(X, (∂g) -1 (-Z⋆ ))) 2 ≤ κ 1 (dist 2 (X, X 0 ) + dist 2 (X, (∂g) -1 (-Z⋆ ))) ≤ κ 2 (∥A(X) -b∥ 2 + dist 2 (X, (∂g) -1 (-Z⋆ ))), (D.1)where the first inequality applies Lemma A.3, the second inequality applies (A + B) 2 ≤ 2A 2 + 2B 2 for all A, B ≥ 0, the third inequality uses the fact that X 0 is an affine space. On the other hand, we know X⋆ , Z⋆ = 0 for all X⋆ ∈ Ω P naturally, so Lemma 3 can be applied here on Z ⋆ and Z⋆ (theproof of Lemma 3 is provided in Appendix C.2). For all X ∈ B(X ⋆ , µ) it holds that f P (X) = ⟨C, X⟩ + g(X) ≥ ⟨C, X⟩ + g(X ⋆ ) + ⟨A * (ȳ ⋆ ) -C, X -X ⋆ ⟩ + κ • dist 2 (X, (∂g) -1 (-Z⋆ )) ≥ ⟨C, X⟩ + g(X ⋆ ) + ⟨A * (ȳ ⋆ ) -C, X -X ⋆ ⟩ + κ κ 2 dist 2 (X, Ω P ) -κ∥A(X) -b∥ 2 ≥ f P (X ⋆ ) -∥ȳ ⋆ ∥∥A(X) -b∥ -κ∥A(X) -b∥ 2 + κ κ 2 • dist 2 (X, Ω P ) = f P (X ⋆ ) -(∥ȳ ⋆ ∥ + κ∥A(X) -b∥)∥A(X) -b∥ + κ κ 2 • dist 2 (X, Ω P ) ≥ f P (X ⋆ ) -(∥ȳ ⋆ ∥ + γ)∥A(X) -b∥ + κ κ 2 • dist 2 (X, Ω P ),where the first inequality uses the growth property on g for X ⋆ and Z⋆ (12), the second inequality uses (D.1), the third inequality uses the definition of the adjoint operator and Cauchy-Schwarz inequality, and the last inequality uses the fact that X is in a bounded set B(X ⋆ , µ) so there exists some γ ≥ 0 such that κ∥A(X) -b∥ ≤ γ. This completes the proof.We move on to prove the dual case. Similarly, we let (y ⋆ , Z ⋆ ) ∈ Ω D and µ > 0 and characterize the optimal dual solution asΩ D = Z 0 ∩ (R m × (∂h) -1 (-X⋆ )), ∀ X⋆ ∈ Ω P ,whereZ 0 = {(y, Z) ∈ R m × S n | C -A * (y) = Z}.Let ( X⋆ , ȳ⋆ , Z⋆ ) be a pair of primal and dual solution satisfying Z⋆ ∈ relint((∂h) -1 (-X⋆ )). Note thatrelint(R m × (∂h) -1 (-X⋆ )) = R m × relint((∂h) -1 (-X⋆ )).Therefore, the existence of such a pair of strict complementarity solution impliesZ 0 ∩ relint(R m × (∂h) -1 (-X⋆ )) ̸ = ∅.Hence, following the same argument to (D.1), we know there exists a constant κ 3 > 0 such thatdist 2 ((y, Z), Ω D ) ≤ κ 3 (∥C -A * (y) -Z∥ 2 + dist 2 ((y, Z), (∂h) -1 (-X⋆ ))) (D.2)for all (y, Z) ∈ B((y ⋆ , Z ⋆ ), µ). Also, as X⋆ , Z ⋆ = 0, we havef D (y, Z) = -⟨b, y⟩ + h(Z) ≥ -⟨b, y⟩ + h(Z ⋆ ) + ⟨-X ⋆ , Z -Z ⋆ ⟩ + κ • dist 2 ((y, Z), (∂h) -1 (-X⋆ )) = h(Z ⋆ ) + -X⋆ , A * (y) -Z -C + A * (y ⋆ ) + κ • dist 2 ((y, Z), (∂h) -1 (-X⋆ )) ≥ f D (y ⋆ , Z ⋆ ) -∥ X⋆ ∥∥C -A * (y) -Z∥ -κ∥C -A * (y) -Z∥ 2 + κ κ 3 • dist 2 ((y, Z), Ω D ) = f D (y ⋆ , Z ⋆ ) -(∥ X⋆ ∥ + κ∥C -A * (y) -Z∥)∥C -A * (y) -Z∥ + κ κ 3 • dist 2 ((y, Z), Ω D ) ≥ f D (y ⋆ , Z ⋆ ) -(∥ X⋆ ∥ + γ)∥C -A * (y) -Z∥ + κ κ 3 • dist 2 ((y, Z), Ω D ),where the first inequality uses the growth property on h, the second equality rewrites ⟨b, y⟩ = X⋆ , A * (y) and Z ⋆ = C -A * (y ⋆ ), and the last inequality uses the fact that (y, Z) is in a bounded set B((y ⋆ , Z ⋆ ), µ) so there exists a γ ≥ 0 such that κ∥C -A * (y) -Z∥ ≤ γ.In this subsection, we use a simple example to illustrate the quadratic growth property discussed in (9) . In particular, we choose the exact penalty formulation for dual SDP (5) (the proof for the exact penalty function can be found in Appendix B). Moreover, the following example shows that even a simple 2 × 2 SDP can not have sharp growth in the objective function. Example D.1. Consider a SDP (P) and (D) with the problem dataC = 1 -1 -1 1 , A 1 = 1 0 0 0 , A 2 = 0 0 0 1 , and b = 1 1 .It can be verified that both primal and dual SDP have a unique solutionEQUATIONZ ⋆ = 1 -1 -1 1 .Therefore, the optimal cost value is 0. Moreover, it also satisfies strict complementarity as rank(X ⋆ )+ rank(Z ⋆ ) = 1 + 1 = 2 (see Definition A.1). (8b) and (9b) then ensure the following exact penalized formulation having quadratic growth propertyf (y) := -b T y + ρ max{0, λ max (A * (y) -C)},where ρ can be chosen as any number satisfying ρ > tr(Z ⋆ ) = 2. Let S = {(0, 0)} be the optimal dual solution set and f ⋆ = 0 be the optimal cost value. Figure 2a shows the landscape of the function f with ρ = 4 and verifies that the function value f (y) is growing at least quadratically away from the distance to the solution set S = {(0, 0)} with the quadratic constant κ = 0.3. In Figure 2a , the yellow area indicates the part where only the linear component of f (y), i.e. b T y, is active while the nonlinear penalty component ρ max{0, λ max (A * (y) -C)} is 0, and the blue region is the part where both the linear and nonlinear components of f (y) are active. The black line in Figure 2a is the boundary where λ max (A * (y) -C) = 0 which can be characterized by the nonlinear equation y 1 y 2 -y 1 -y 2 = 0 with y 1 < 1. This nonlinear direction also indicates that sharp growth of f is impossible. Indeed, let y 1 ∈ [0, 1) and y 2 = y1 y1-1 . Note that this choice of y satisfies the nonlinear equation y 1 y 2 -y 1 -y 2 = 0 and thus only the linear part -b T y in f (y) is in force. We then havef (y) -f ⋆ = -y 1 -y 2 = -y 1 - y 1 y 1 -1 = -y 2 1 y 1 -1 .On the other hand, the distance to the solution set can be verified asdist(y, S) = y 2 1 + y 2 1 (y 1 -1) 2 = y 1 1 + (y 1 -1) 2 y 1 -1 ≥ y 1 y 1 -1 .It becomes clear that it is impossible to have a constant κ > 0 such that The optimal solution set S = {(0, 0)}. In Figure 2a , the yellow region represents the linear part where only -b T y is active, resulting ρ max{0, λmax(A * (y) -C)} = 0, the blue region encompasses both the linear and the nonlinear parts, and the green surf is the square of the distance to the optimal solution set with κ = 0.3. Figure 2b shows the sectional view of f along the direction y1y2 -y1 -y2 = 0, which can be characterized as the rational functionκ y 1 y 1 -1 ≤ -y 2 1 y 1 -1 = f (y) -f ⋆ , ∀y 1 ∈ [0, 1)f (y1) = -y 2 1 y 1 -1 .as the quadratic therm y 2 1 will dominant when y 1 is small, let alone the sharp growth κ • dist(y, S) ≤ f (y)-f ⋆ . Moreover, the quadratic growth of indicator function formulation -b T y +δ S 2 + (C -A * (y)) has also been verified as we only need to consider the linear component -b T y, which has already been confirmed in the previous case. Lastly, it is worth pointing out that the sublevel sets of the functions f and -b T y + δ S 2 + (C -A * (y)) are different. Indeed, given a finite value β > 0, the sublevel set {y ∈ R 2 | f (y) ≤ β} contains both parts of yellow and blue regions in Figure 2b . In contrast, the sublevel set {y ∈ R 2 | -b T y + δ S 2 + (C -A * (y)) ≤ β} only contains the linear part in Figure 2b .In this section, we complete the missing proof in Section 4 and discuss the ALM applied to (D) with its corresponding convergence properties. This section is divided into three subsections. Appendix E.1 completes the proof of Proposition 2. Appendix E.2 finishes the proof of Theorem 3. Appendix E.3 discusses the ALM applied to (D).The proof of Proposition 2 requires a nice characterization of the ordinal dual function and the augmented dual function defined asg r (w) = inf X∈S n L r (X, w) (E.1)where L r is the augmented Lagrangian function (14) , recall that we write w = (y, Z).Proposition E.1 ([38, Theorem 3.2]). Let r > 0. For all w ∈ R m × S n , it holds that g r (w) = min X∈S n L r (X, w) = max u∈R m ×S n g 0 (u) - 1 2r ∥u -w∥ 2 ,where g 0 is the dual function in (13) .Proposition E.1 not only shows the augmented dual function g r is g 0 with a prior but also shows g r is continuously differentiable. In comparison, the ordinary dual function g 0 can be highly nonsmooth. We are ready to prove Proposition 2.• Part (a) of Proposition 2 comes directly from the PPM convergence Lemma 1 as Lemma 4 and the stopping criteria (A ′ ) naturally imply the dual iterate w k+1 satisfies ∥w k+1 -prox r k ,-g0 (w k )∥ ≤ ϵ k and ∞ k=1 ϵ k < ∞. • The proof of (b) in Proposition 2 is in fact straightforward. Firstly, by Moreau decomposition [49, Exercise 12.22 ] and (15c), we haver k X k+1 -Z k = Π S n + (r k X k+1 -Z k ) -Π S n + (Z k -r k X k+1 ) = Π S n + (r k X k+1 -Z k ) -Z k+1 . Diving both sides by r k , we conclude X k+1 + (Z k+1 -Z k )/r k ∈ S n + . Therefore, it follows that dist(X k+1 , S n + ) ≤ ∥X k+1 -(X k+1 + (Z k+1 -Z k )/r k )∥ = ∥Z k+1 -Z k ∥/r k . Secondly, ∥A(X k+1 ) -b∥ = ∥y k -y k+1 ∥/r k comes directly from the update (15b). Lastly, note that L r k (X k+1 , w k ) = ⟨C, X k+1 ⟩ + 1 2r k (∥w k+1 ∥ 2 -∥w k ∥ 2 ).On the other hand, we havemin X∈S n L r k (X, w k ) = g r k (w k ) = g 0 (u ⋆ ) - 1 2r k ∥u ⋆ -w k ∥ 2 ≤ g 0 (u ⋆ ) ≤ p ⋆ ,where u ⋆ is the point that achieves the maximum in Proposition E.1 and the last inequality uses weakly duality. Therefore, we have⟨C, X k+1 ⟩ -p ⋆ ≤ L r k (X k+1 , w k ) -min X∈S n L r k (X, w k ) - 1 2r k (∥w k+1 ∥ 2 -∥w k ∥ 2 ).Since the convergence of {w k } is guaranteed in (a), the quantities dist(X k+1 , S n + ), ∥A(X k+1 )-b∥, and ⟨C, X k+1 ⟩ -p ⋆ also convergence to zero. • Part (c) is a direct consequence of part (b) and the fact that Ω P is bounded if and only if the set{X ∈ S n | dist(X, S n + ) ≤ γ 1 , ∥A(X) -b∥ ≤ γ 2 , ⟨C, X⟩ -p ⋆ ≤ γ 3 } is bounded for any γ ∈ R 3 [23, page 110].In this subsection, we provide a complete proof of part (a) in Theorem 3. The proof is motivated by [26, Theorem 1] which focuses on dual SDPs only. To facilitate proof, we first introduce a standard result in proximal mapping that upper bounds the step length of the proximal step by the distance to the optimal solution set, which can be found in [42, Proposition 1] by setting z = x and z ′ = Π S (x). We give a simple proof below. Proposition E.2. Let f : R n → R be a convex function. Denote S ⊆ R n as the set of minimizers of f , i.e., S = argmin x∈R n f (x). Suppose S ̸ = 0. Given a point x ∈ R n and a constant α > 0, the proximal mapping holds that∥prox α,f (x) -x∥ ≤ dist(x, S).Proof. From the optimality condition of proximal mapping, we havef (prox α,f (x)) + α 2 ∥prox α,f (x) -x∥ 2 ≤ f (Π S (x)) + α 2 ∥Π S (x) -x∥ 2 =⇒ α 2 ∥prox α,f (x) -x∥ 2 ≤ f (Π S (x)) -f (prox α,f (x)) + α 2 ∥Π S (x) -x∥ 2 =⇒ ∥prox α,f (x) -x∥ ≤ dist(x, S),which completes the proof.Using Proposition E.2 and (B ′ ), we arrive at the following key inequality to show the linear convergence of KKT residuals. Proposition 2. It bounds the step length of the dual update by the current distance to the solution set. Proposition E.3. [26, Lemma 3] Let {X k , w k } be the sequence generated by (15) under (B ′ ). Then for all k ≥ 1 with δ k < 1, it holds that∥w k+1 -w k ∥ ≤ 1 1 -δ k dist(w k , Ω D ).Proof. From the triangle inequality and the stopping criterion (B ′ ), we have∥w k+1 -w k ∥ -∥w k -prox r k ,-g0 (w k )∥ ≤ ∥w k+1 -prox r k ,-g0 (w k )∥ ≤ δ k ∥w k+1 -w k ∥.Rearranging terms and using Proposition E.2 yields(1 -δ k )∥w k+1 -w k ∥ ≤ ∥w k -prox r k ,-g0 (w k )∥ ≤ dist(w k , Ω D ).This completes the proof.We are ready to start the proof of part (a) here. As dual strict complementary holds, the negative of the dual function (13) , i.e., -g 0 , satisfies quadratic growth (9b). Using Lemma 4 and stopping criteria (B ′ ), we have ∥w k+1 -prox r k ,-g0 (w k )∥ ≤ δ k ∥w k+1 -w k ∥. Therefore, the linear reduction on dist(w k , Ω D ) comes directly from the PPM convergence Lemma 1, i.e., there exists a k1 such that for all k ≥ k1 , it holds thatdist(w k+1 , Ω D ) ≤ µ k dist(w k , Ω D ), µ k = θ k + 2δ k 1 -δ k < 1, θ k = 1 2r k µ q +1 < 1.We move to show the bound for residuals dist(X k+1 , S n + ), ∥A(X k+1 ) -b∥, and ⟨C, X k+1 ⟩ -p ⋆ . Specifically, whenδ k < 1, it holds that dist(X k+1 , S n + ) ≤ ∥Z k -Z k+1 ∥ r k ≤ ∥w k -w k+1 ∥ r k ≤ 1 (1 -δ k )r k dist(w k , Ω D ), ∥A(x k+1 ) -b∥ ≤ ∥y k -y k+1 ∥ r k ≤ ∥w k -w k+1 ∥ r k ≤ 1 (1 -δ k )r k dist(w k , Ω D ),where we use part (b) in Proposition 2, ∥y k -y k+1 ∥ ≤ ∥w k -w k+1 ∥, ∥Z k -Z k+1 ∥ ≤ ∥w k -w k+1 ∥,and Proposition E.3. Again, using part (b) in Propositions 2 and E.3, when δ k < 1, we have⟨C, X k+1 ⟩ -p ⋆ ≤ δ 2 k ∥w k+1 -w k ∥ 2 + ∥w k ∥ 2 -∥w k+1 ∥ 2 2r k = δ 2 k ∥w k+1 -w k ∥ 2 + (∥w k ∥ + ∥w k+1 ∥)(∥w k ∥ -∥w k+1 ∥) 2r k ≤ δ 2 k ∥w k+1 -w k ∥ 2 + (∥w k ∥ + ∥w k+1 ∥)(∥w k -w k+1 ∥) 2r k ≤ δ 2 k ∥w k+1 -w k ∥ + ∥w k ∥ + ∥w k+1 ∥ 2r k (1 -δ k ) dist(w k , Ω D ).Since δ k → 0, there exists a k2 such that δ k < 1 for all k ≥ k2 . Taking k = max{ k1 , k2 } completes the proof for part (a) with the constantsµ ′ k = 1 (1 -δ k )r k → µ ′ ∞ = 1 r ∞ , µ ′′ k = δ 2 k ∥w k+1 -w k ∥ + ∥w k ∥ + ∥w k+1 ∥ 2r k (1 -δ k ) → µ ′′ ∞ = ∥w ∞ ∥ r ∞ .We move on to part (b). By Theorem 2, we know that the error bound (7b) holds as dual strict complementary holds, i.e., for any bounded set U ⊆ S n containing any X ⋆ ∈ Ω P , there exist constants α 1 , α 2 , α 3 > 0 such that⟨C, X⟩ -⟨C, X ⋆ ⟩ + α 1 ∥A(X) -b∥ + α 2 • dist(X, S n + ) ≥ α 3 • dist 2 (X, Ω P ), ∀X ∈ U. (E.2) From the assumption that Ω P is bounded, Proposition 2 confirms that the sequence {X k } is bounded. Thus, we can choose a bounded set U ⊇ Ω P ∪ k≥1 {X k }. Combing (E.2) with ( 16), we haveα 3 • dist 2 (X k+1 , Ω P ) ≤ (µ ′′ k + (α 1 + α 2 )µ ′ k ) • dist(w k , Ω D ).Dividing both sides by α 3 leads to the desired result in part (b). This completes the proof.From the definition of the augmented Lagrangian function, we haveL r k (y k+1 , X k ) = ⟨-b, y k+1 ⟩ + 1 2r (∥X k+1 ∥ 2 -∥X k ∥ 2 ).On the other hand, we knowmin y∈R m L r k (y, X k ) = g 0 (U ⋆ ) - 1 2r k ∥U ⋆ -X k ∥ 2 ≤ g 0 (U ⋆ ) ≤ -d ⋆ ,where U ⋆ denoted as the point that achieves the maximum in the identity [38, Theorem 3.2 ]min y∈R m L r k (y, •) = max X∈S n g 0 (X) - 1 2r k ∥X -•∥ 2and the last inequality comes from the definition of the dual problem in (E.3). Thus,d ⋆ -⟨b, y k+1 ⟩ ≤ L r k (y k+1 , X k ) -min y∈R m L r k (y, X k ) - 1 2r (∥X k+1 ∥ 2 -∥X k ∥ 2 ).• Part (c) is a consequence of part (b) and the fact that Ω D is bounded if and only if the set {(y, Z) ∈ R m × S n | d ⋆ -⟨b, y⟩ ≤ γ 1 , dist(Z, S n + ) ≤ γ 2 , ∥C -A * (y) -Z∥ ≤ γ 3 } is bounded for any γ ∈ R 3≥ 0, 0 < µ k < 1 and µ ′ k , µ ′′ k > 0 such that for all k ≥ k, dist(X k+1 , Ω P ) ≤ µ k • dist(X k , Ω P ), dist(Z k+1 , S n + ) ≤ µ ′ k • dist(X k , Ω P ), d ⋆ -⟨b, y k+1 ⟩ ≤ µ ′′ k • dist(X k , Ω P ). (E.5) (b)If Ω D is bounded, then the primal sequence {y k } also converges linearly to Ω D , i.e., there is a constant k ≥ 0 such that for all k ≥ k,dist 2 (y k+1 , Ω P ) ≤ τ k • dist(X k , Ω D ).Proof. Similar to Proposition E.3, if (B ′ D ) is used, we have∥X k+1 -X k ∥ ≤ 1 1 -δ k dist(X k , Ω P ), ∀δ k < 1. (E.6)Therefore, there exists a k ≥ 0 such that ∀k ≥ k, δ k < 1 anddist(Z k+1 , S n + ) ≤ ∥X k+1 -X k ∥ r k ≤ 1 r k (1 -δ k ) dist(X k+1 , Ω P ),where the first inequality uses part (b). Then, once again using (E.6) and part (b), we haved ⋆ -⟨b, y⟩ ≤ δ 2 k ∥X k+1 -X k ∥ 2 + ∥X k ∥ 2 -∥X k+1 ∥ 2 2r k ≤ δ 2 k ∥X k+1 -X k ∥ 2 + (∥X k ∥ -∥X k+1 ∥)(∥X k ∥ + ∥X k+1 ∥) 2r k ≤ δ 2 k ∥X k+1 -X k ∥ 2 + (∥X k -X k+1 ∥)(∥X k ∥ + ∥X k+1 ∥) 2r k ≤ δ 2 k ∥X k+1 -X k ∥ + ∥X k ∥ + ∥X k+1 ∥ 2r k (1 -δ k ) dist(X k+1 , Ω P ).If strict complementarity holds, Theorem 1 (with g in ( 5) as an indicator function) guarantees that -g 0 in (E.3) satisfies quadratic growth in (9b). Thus, the linear convergence of dist(X k , Ω P ) comes from the PPM convergence Lemma 1, i.e., there exists a k1 such that for all k ≥ k1 , it holds thatdist(X k+1 , Ω P ) ≤ µ k dist(X k , Ω P ), µ k = θ k + 2δ k 1 -δ k < 1, θ k = 1 2r k µ q +1 < 1.In Section 5, we consider the classical SDP relaxation of the Mac-Cut problem and the linear SVM.In this section, along with another popular signal processing problem -Lasso, we detail the problem formulation and report the numerical performance of ALM applied to those problems.• The SDP relaxation of Max-Cut: min min x∈R d λ m i=1 max{0, 1 + b i (a T i x)} + 1 2 ∥x∥ 2 ,where a i ∈ R n is the feature of the i-th data point, b i ∈ {-1, 1} is the corresponding label, and λ > 0 is a constant. Equivalently, the problem can reformulated in the following standard conic form minx∈R n ,t∈R m 1 2 ∥x∥ 2 + λ1 T t subject to Diag(b)Ax + 1 ≤ t, 0 ≤ t, where A = [a 1 , • • • , a m ]T ∈ R m×n and Diag(b) ∈ S m denotes the diagonal matrix with the diagonal elements being b.• Lasso: minx∈R n 1 2 ∥Ax -b∥ 2 + λ∥x∥ 1 ,where A ∈ R m×n , b ∈ R m are problem data and λ > 0 is the weighted parameter balancing the sparsity of the solution and the accuracy of the linear solution. Equivalently, the problem can be rewritten in the conic form min All numerical experiments are conducted on a PC with a 12-core Intel i7-12700K CPU@3.61GHz and 32GB RAM. For Max-Cut problem, we select the graph G 1 , G 2 , and G 3 from the website https://web.stanford.edu/~yyye/yyye/Gset/ and only take the first 20 × 20 submatrix as the considered problem data C. For both the linear SVM and Lasso, we randomly generate the problem data with the dimension m = 100 and n = 10, and set the constant λ = 1. We use Mosek [56] to get the optimal cost value. In each application, we consider the following two scenarios 1) fixing the same augmented parameter r k = r for all k for three different problem instances; 2) fixing a problem instance and varying different augmented parameter r. The numerical results are presented in Figures 3 to 5 . For each Figures 3 to 5 , the first row shows the evolution of the primal cost gap, dual cost gap, and KKT residuals for three different instances with a fixed augmented parameter (scenario one), and the second row compares the different numerical behaviors when varying the augmented parameter (scenario two). In the setting of a fixed augmented parameter, the augmented term r is set as 1, 5, 20 for Max-Cut, linear SVM, and Lasso respectively. In the setting of various augmented parameters, the parameter is chosen as r = {1, 5, 10}, r = {1, 5, 10}, and r = {10, 20, 30} for Max-Cut, linear SVM, and Lasso respectively.x∈R n 1 2 ∥y∥ 2 + λ1 T t subject to Ax -b = y, -t ≤ x ≤ t.We observe that, in all cases, ALM enjoys linear convergence in the primal cost value gap, dual cost value gap, and KKT residuals to the accuracy of at least 10 -5 , which is consistent with our theoretical findings in Theorem 3. We believe the oscillated or flattening behavior that appears in the tail (when the iterates are close to the solution set) is due to the inaccuracy of the subproblem solver and computational errors. The numerical result also indicates that when the augmented term r increases, ALM favors the decrease of the feasibility more, leading to faster convergence in the beginning phase. However, a large r may not lead to the best convergence in the long term.Note that the projection term ∥Π S n + (Z -rX)∥ 2 in the subproblem (15a) can not be directly modeled by Yalmip. Therefore, we reformulate the problem as the followingargmin X∈S n ⟨C, X⟩ + 1 2r (∥y + r k (b -A(X))∥ 2 + ∥Π S n + (Z -r k X)∥ 2 -∥y∥ 2 -∥Z∥ 2 ) = argmin X∈S n ⟨C, X⟩ + 1 2r (∥y + r k (b -A(X))∥ 2 + ∥Π S n -(r k X -Z)∥ 2 ) = argmin X∈S n ,U ∈S n + ⟨C, X⟩ + 1 2r (∥y + r k (b -A(X))∥ 2 + ∥r k X -Z -U ∥ 2 ),where the first equality drops two independent terms and uses -S n + = S n -and ∥Π Guidelines:S n + (Y )∥ = ∥ -Π (-S n + ) (-Y )∥ = ∥Π (S n -) (-Y )∥ for all Y ∈ S n ,U ∈S n + ∥Y -U ∥ = ∥Y -Π S n + (Y )∥ = ∥Π S n -(Y )∥ for all Y ∈ S n .• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).This penalty parameter ρ guarantees that (4) and (P) are equivalent. To further ensure the dual problem of (P) is equivalent to the dual of (4), we need to choose ρ > sup (y ⋆ ,Z ⋆ )∈Ω D tr(Z ⋆ ). This subtle point is less emphasized in the literature[30,29]; see Remark B.1 in the appendix for details. 


Decision: This paper introduces Inexact Augmented Lagrangian Methods (ALM) for addressing conic linear optimization problems. Under the assumptions of strict complementarity and strong duality, the authors establish local linear convergence by demonstrating the quadratic growth property within a compact neighborhood of the optimal solution for both the primal and dual problems.

I believe that the paper makes a significant contribution by proving the quadratic growth and error bounds for both primal and dual conic programs (P) and (D) over any compact set containing an optimal solution under standard assumptions, thereby extending existing results. Furthermore, the authors demonstrate that both primal and dual iterates converge linearly, a result that was previously unavailable for primal iterates. Most reviewers support the publication of the paper following the rebuttal. I recommend acceptance.

Reviews: review: paper_summary: paper_summary: The paper addresses the convergence of primal and dual iterates in Augmented Lagrangian Methods (ALMs) for conic optimization, particularly under quadratic growth assumptions. The authors establish that both primal and dual iterates of ALMs demonstrate linear convergence solely based on the strict complementarity assumption and a bounded solution set. This addresses a significant gap in the literature concerning the linear convergence of primal iterates, providing a theoretical foundation that has been previously unresolved.
strength_weakness: strength_weakness: Presentation of Key Contributions: One significant issue with the paper is the placement and treatment of one of its key contributions, Theorem 3, which appears towards the very end of the document. This theorem, which is central to the paper's claims and theoretical framework, is not proven within the main text, and the appendix provided does not sufficiently validate or elaborate on it. This placement and lack of rigorous proof within the main discourse may detract from the impact of the contribution, as it might be overlooked or undervalued by readers. To improve, the authors could consider integrating Theorem 3 more prominently within the main discussion and ensuring that a complete and accessible proof is included either in the main text or more comprehensively in the appendix.

Numerical Validation: Another area where the paper falls short is in its numerical section. The section dedicated to numerical validation of the theoretical results is very brief and lacks depth/sufficient validation through several diverse problems. A more extensive set of numerical experiments is crucial to demonstrate the practical effectiveness and robustness of the proposed methods under varied conditions. The current numerical validation does not sufficiently cover the scope of the potential applications discussed in the paper. Readers are referred to Appendix H, where additional testing is still missing.
questions: questions: Theorem 3 Proof: Can the authors provide a detailed proof of Theorem 3 within the main text or an enhanced appendix to help readers understand its foundational role in the paper's theoretical framework? 

Numerical Experiments: Could the authors expand on the range and depth of the numerical experiments presented? Specifically, how do the proposed methods perform under varying conditions and parameter settings?
limitations: limitations: The paper does not explicitly discuss the limitations or potential negative societal impacts of the research, which is a critical component of scholarly communication.
paper_summary: paper_summary: This paper develops Inexact Augmented Lagrangian methods (ALM) for conic optimization problems with focus on Linear Programming (LP) or the non-negative orthant cone, Second-Order Cone (SOCP) problems and Semidefinite programming (SDP) given a linear objective. Under assumptions of strict complementarity and strong duality, the authors show local linear convergence for these problems by first showing quadratic growth property within a compact subset around the optimal solution for both the primal and dual programs and then leveraging the well-established concept that running ALM for the primal is equivalent to running Proximal Point Method (PPM) for the dual. The experiments show linear convergence for the SDP relaxation for the MaxCut problem, the SDP relaxation for matrix completion, and the moment relaxation of binary quadratic program (BQP) given the following metrics: primal distance, dual cost gap and the KKT-based residuals.
strength_weakness: strength_weakness: One weakness of the paper is the lack of characterization of how inexact evaluation of the proximal operator affects convergence. The authors use the property of linear convergence for Proximal Point Method (PPM) given inexact evaluation of proximal operator and quadratic growth assumption to show similar linear convergence for Inexact ALMs but there are no guarantees based on chosen error tolerance schedule (i.e. choice of $\epsilon_k$ and $\delta_k$ for all k). Another weakness of the paper is the lack of experimental evaluation of conic problems other than SDPs. The work shows theoretical guarantees of local linear convergence under strict complementarity and strong duality for three different types of conic problems: LPs, SOCPs and SDPs but experimental evaluation of LPs and SOCPs are lacking. It maybe because SDPs are a more general class than LPs or SOCPs but it would be good to have a variety of experiments that cover both convex/non-convex constraints as well as different LPs and SOCPs in addition to SDPs. There is also a lack of experimental evaluation to claim that there is local linear convergence given inexact evaluations of the subproblem in Equation (15a).
questions: questions: 1. Why were LPs and SOCPs not evaluated as part of the experimental evaluation but discussed in the theoretical sections and appendix?
2. Have you considered showing the local linear convergence given different random starting points for Inexact ALM? 
3. Did you use inexact evaluation of the subproblem in Equation (15a)?
4. Have you considered showing the local linear convergence given different error tolerance schedules for $\epsilon_k$ and $\delta_k$ for all k?
5. Have you considered choosing the $\mathcal{A}$ operator to hold non-convex constraints in the experimental evaluation? The MaxCut SDP and Matrix Completion SDP both have linear constraints and the BQM has a convex constraint of $x_i^2 = 1$ but your guarantees only only assume that $\mathcal{A}$ is surjective.
limitations: limitations: There were no discussions of limitations in the work or adequate discussion of future directions of work.
paper_summary: paper_summary: The paper presents the convergence rate of the primal iterates of the augmented Lagrangian Methods (ALMs) which are widely employed in solving constrained optimizations. The authors develop new quadratic growth and error bound properties for primal and dual conic programs under the standard strict complementarity condition and then reveal that both primal and dual iterates of the ALMs converge linearly contingent upon the assumption of strict complementarity and a bounded solution set. The specific contributions include:
1. Under the standard strict complementarity assumption, the quadratic growth and error bound for both primal and dual conic programs (P) and (D) over any compact set containing an optimal solution (see Theorems 1 and 2) are established.  
2. A new characterization of the preimage of the subdifferential of the exact penalty functions is unveiled. 
3. They provide new and simple proof for the growth properties in the exact penalty functions and clarify some subtle differences in constructing exact penalty functions.
4. They show the linear convergence for both the primal and dual iterates of  ALM to solve either the primal or dual conic programs.
strength_weakness: strength_weakness: 1. The authors claim in Remark 1 that the results in Theorems 1 and 2 are more general and unified compared with known results since they allow for any compact set $\mathcal{U}$. However, let $\mathcal{U}=\mathcal{U}_1\cap \mathcal{U}_2$ where $\mathcal{U}_1$ and $\mathcal{U}_2$  are compact, and there is not any optimal solution in $\mathcal{U}_1$. If it is known that the error bound is constrained with a pair $\gamma, \kappa$ for $x\in\mathcal{U}_2$. For $x\in\mathcal{U}_1$, it is natural to get a $\kappa$ through the minimizatin of the fraction $$\frac{f(x)-p^*+\gamma\|\mathcal{A}(x)-b\|}{dist^p(x,\Omega)}$$ since $\mathcal{U}_1$ is compact and $dist^p(x,\Omega)>0$. We can just take the minimizer of two $\kappa$(s). The advantages of this error bound form in this paper is doubtable.
2. Aftrer Definition 2, the authors claim that the notion of strict complementarity is not restrictive, and it holds generically for conic programs. After that,  the authors also presented: that it has been revealed that many structured SDPs from practical applications also satisfy strict complementarity. There are contradictions and misunderstandings in these two assertions.
questions: questions: 1. Lines 184-185: If the linear constraints $\mathcal{A}(x)=b$ is empty, how to define the exact penalty function?
2. Line 226: Why is there $\mathbb{F}\times \mathbb{E}$ instead of $\mathbb{F}$?
3. Please consider citing the paper "Rockafellar, R.T. Convergence of Augmented Lagrangian Methods in Extensions Beyond Nonlinear Programming. Math. Program. 199, 375–420 (2023). https://doi.org/10.1007/s10107-022-01832-5," and compare it with your work.

Typos:
1. Line 238: Should (8b) be replaced by (8a)?
2. The notation $\mathbb{R}^n$ should be changed to $\mathbb{R}_{+}^n$.
limitations: limitations: NA
paper_summary: paper_summary: This paper presents new theoretical results on the convergence of primal iterates in inexact augmented Lagrangian methods (ALMs) for conic optimization. The idea is to use strict complementarity (which is a standard assumption in conic optimization) to establish quadratic growth and error bound conditions for the primal and dual programs. These bounds are then used to show linear convergence for both the primal and dual iterates in inexact ALMs. The linear convergence of the primal iterates is shown in (brief) experiments.
strength_weakness: strength_weakness: I found the main weakness of the paper to be in its presentation of results.

* The paper takes too long to reach the main results. Perhaps an informal version of Theorem 3 could be stated in the introduction?

* There is a lot of notation/specific terminology in the paper, which makes it difficult to follow. One suggestion to reduce the complexity would be to focus on a particular problem class (LP, SOCP, or SDP) in the main paper. For example, if focusing on LPs, the authors could move the discussion of strict complementarity of LPs to earlier in the paper, which would give more intuition for the assumptions in the paper. Furthermore, the theorems in the main paper could be simplified to address LPs, which would make the results easier to understand for a wider audience. The general results for LPs, SOCPs, and SDPs could then be presented in the appendix.

* I would have liked the paper to expound upon how their work relates to machine learning (outside of some brief citations in the introduction). Ideally, this could be done by showing linear convergence of primal iterates on a conic program from machine learning. One idea could be to solve an SVM problem (QP, which is a special case of SDP). 

* While Figure 1 suggests that primal iterates are converging linearly, I would like to see more iterations (say 20) in the plots to really verify this claim.

* I found it hard to follow how the author’s results compare to previous convergence results in the literature. I’d suggest providing a more in-depth comparison in lines 341-349.

* The paper takes too long to discuss inexact augmented Lagrangian methods (these are not discussed in-depth until page 7). This makes the flow of the paper confusing — I’d suggest covering inexact ALMs closer to the introduction.

Minor comments: 

* Discussion of scalable first-order methods (line 28) should cite PDLP [1, 2]

* “Lipschitz” is misspelled on lines 100 and 103

[1] Applegate, David, Mateo Diaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan ODonoghue, and Warren Schudy. 2021. “Practical Large-Scale Linear Programming Using Primal-Dual Hybrid Gradient.” In Advances in Neural Information Processing Systems, edited by M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. Wortman Vaughan, 34:20243–57. Curran Associates, Inc.

[2] Applegate, D., Hinder, O., Lu, H. et al. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Math. Program. 201, 133–184 (2023).
questions: questions: * Are there problems for which the dual iterates can converge linearly, but the primal iterates converge sublinearly? If so, could this be demonstrated in an experiment?

* Line 265: What exactly is meant by “nice self-dual structure”?
limitations: limitations: Please see “Weaknesses”

Comments: title: Subproblem solution quality in Mosek
Thanks for the rebuttal
comment: I thank the authors for making the effort to address the comments. I would be happy to increase the score to 6.
Dear Reviewer K87V,

Are you satisfied with the rebuttal? Did the authors adequately address your concerns?

Best,
AC
The authors would like to thank the reviewer for positive feedback and for directing us to the MOSEK documentation. We appreciate the reviewer's understanding of the challenges involved in conducting numerical experiments with varying schedules for $\epsilon_k$ and $\delta_k$.

- Following the reviewer's suggestion, we conducted new numerical simulations to assess the impact of subproblem accuracy by varying the accuracy settings of the MOSEK solver. 
- We ran the inexact ALM on one instance of SVM and one instance of LASSO, adjusting the MOSEK accuracy settings (primal feasibility, dual feasibility, and relative complementarity gap) from $10^{-2}$ to $10^{-8}$. 
- Since we cannot include figures in this response, we present the numerical results in the following tables. The results indicate that higher accuracy in the subproblem solver leads to faster convergence of the residuals. For instance, with an accuracy setting of $10^{-2}$, the inexact ALM fails to converge to a high-accuracy solution after 20 iterations. With an accuracy setting of $10^{-4}$, the residuals converge to the order of $10^{-3}$. At $10^{-6}$ for the subproblem accuracy, the residuals decrease to the order of $10^{-6}$, and at $10^{-8}$, they decrease to around 4.62$\mathrm{e}$-08 after 20 iterations, showing linear convergence as expected by our theoretical analysis. 
- A similar effect of subproblem accuracy was observed in the LASSO experiments.

Some detailed numerical results are shown below. We will add the corresponding figures to the final version of our work. We believe these extra numerical experiments further validate our theoretical analysis. 

> # **SVM - Primal cost value gap**

| **Accuracy/Iteration** | **1**          | **5**          | **10**         | **15**         | **20**         |
|------------------------|----------------|----------------|----------------|----------------|----------------|
| **1.00$\mathrm{e}$-02** | 1.78$\mathrm{e}$-01 | 2.48$\mathrm{e}$-01 | 2.48$\mathrm{e}$-01 | 2.48$\mathrm{e}$-01 | 2.48$\mathrm{e}$-01 |
| **1.00$\mathrm{e}$-04** | 4.29$\mathrm{e}$-01 | 1.58$\mathrm{e}$-02 | 6.07$\mathrm{e}$-03 | 5.98$\mathrm{e}$-03 | 5.97$\mathrm{e}$-03 |
| **1.00$\mathrm{e}$-06** | 4.36$\mathrm{e}$-01 | 1.08$\mathrm{e}$-02 | 1.01$\mathrm{e}$-04 | 2.81$\mathrm{e}$-06 | 1.48$\mathrm{e}$-06 |
| **1.00$\mathrm{e}$-08** | 4.37$\mathrm{e}$-01 | 1.07$\mathrm{e}$-02 | 2.70$\mathrm{e}$-04 | 7.29$\mathrm{e}$-06 | 4.62$\mathrm{e}$-08 |


> # **Lasso - Primal cost value gap**

| **Accuracy/Iteration** | **1**          | **5**          | **10**         | **15**         | **20**         |
|------------------------|----------------|----------------|----------------|----------------|----------------|
| **1.00$\mathrm{e}$-02** | 6.65$\mathrm{e}$+00 | 2.46$\mathrm{e}$-02 | 6.36$\mathrm{e}$-03 | 1.26$\mathrm{e}$-01 | 1.24$\mathrm{e}$-01 |
| **1.00$\mathrm{e}$-04** | 6.78$\mathrm{e}$+00 | 1.13$\mathrm{e}$-03 | 1.27$\mathrm{e}$-03 | 3.37$\mathrm{e}$-03 | 2.14$\mathrm{e}$-03 |
| **1.00$\mathrm{e}$-06** | 6.78$\mathrm{e}$+00 | 3.56$\mathrm{e}$-03 | 5.45$\mathrm{e}$-07 | 4.97$\mathrm{e}$-05 | 4.90$\mathrm{e}$-05 |
| **1.00$\mathrm{e}$-08** | 6.78$\mathrm{e}$+00 | 3.50$\mathrm{e}$-03 | 4.97$\mathrm{e}$-05 | 6.89$\mathrm{e}$-07 | 1.06$\mathrm{e}$-08 |
Thanks to the authors' responses, I have no further questions and will keep my score. However, I agree with the other reviewers that the paper's presentation could be improved.
I would like to thank the authors for their detailed responses to my comments and questions. It is good to see the additional experimental results for linear SVM and Lasso, as this addresses the main concern about inadequate experimental evaluation, particularly with LPs and SOCPs. As far as showing how the error tolerance schedule $\epsilon_k$ and $\delta_k$ propagates to the guarantees, it is still a missing part of the analysis and useful to consider since achieving low error tolerance is difficult and/or costly in some applications. It is good that you will consider adding that analysis. I understand it is difficult to control the subproblem quality using a third-party solver like MOSEK but there are ways to set them. See this as an example for MOSEK: https://docs.mosek.com/latest/cxxfusion/parameters.html. Still, the additional experimental results merits an increase in my rating from 5 to 6.
Thank you for taking the time to address my concerns. I will raise my score from 3 -> 5.