Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

A Bundle-based Augmented Lagrangian Framework: Algorithm, Convergence, and Primal-dual Principles

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A bundle-based augmented Lagrangian method (BALA) solves a constrained convex problem in a single loop with no inner subroutine, achieving sublinear convergence rates and linear convergence for semidefinite programs with rank-one…

desk verdict A genuinely new single-loop ALM-PBM link, but the advertised ρ=ε speedups and Theorem 6's parameter condition are wrong as printed; the corrected fixed-ρ rates are solid. read the letter →

arxiv 2502.08835 v1 pith:MPCHSJTF submitted 2025-02-12 math.OC cs.SYeess.SY

Feng-Yi Liao , Yang Zheng This is my paper · ORCID
classification math.OCcs.SYeess.SY MSC 90C2590C22
keywords bundlemethodaugmentedLagrangianconvexoptimizationsemidefiniteprogrammingconvergenceratessingle-loopalgorithmproximalprimal-dual
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes a bundle-based augmented Lagrangian framework (BALA) for constrained convex problems of the form $\min\{\langle c, x\rangle : Ax = b, x \in \Omega\}$. The claim is that replacing the exact inner solve of classical ALM by an exact solve over a simple inner approximation $\Omega_k \subset \Omega$, built from a bundle of past primal and dual iterates, yields a single-loop algorithm whose dual iterates converge at rate $O(\epsilon^{-3})$ and whose primal residuals converge at rate $O(\epsilon^{-6})$, with $\rho = \epsilon$ improving these to $O(\epsilon^{-2})$ and $O(\epsilon^{-4})$. Under quadratic growth of the dual function and quadratic closeness of the approximations, every iteration is a descent step and the method converges linearly, including for semidefinite programs with rank-one optimal solutions. If correct, this gives a projection-free, subroutine-free ALM with provable rates and a per-iteration cost that can be as low as a one-dimensional line search. The proof works by showing BALA is exactly the proximal bundle method applied to the dual problem, in analogy with the classical equivalence between ALM and the proximal point method.

What carries the argument

The load-bearing object is the inner approximation set $\Omega_k$, chosen as a line segment (or a small convex hull) spanned by two points: $v_k$, the point where the Lagrangian realizes the current dual function value, and $w_k$, the previous approximate primal solution. This set satisfies Assumption 3.1 (proper, inner, containing $v_{k+1}$, and containing $w_{k+1}$ on null steps), and the induced dual function $g_k$ is a valid bundle model. Solving the quadratic subproblem over such a line segment reduces to a scalar saturation formula, so each iteration is a closed-form computation; the descent test (15) decides whether to accept or reject the candidate, exactly as in a proximal bundle method.

What would settle it

Take an SDP with a rank-one optimal solution that satisfies quadratic growth (18) and quadratic closeness (19) with known constants $\alpha, \gamma$, and run BALA with $\beta = 1/2$ and $\rho \ge 1/\gamma$ from a point satisfying the hypotheses. If any null step occurs after the iteration $T$ where (19) is guaranteed, then the claim that every iteration is a descent step is false. Alternatively, implement BALA with line-segment approximations on a general compact polytope $\Omega$ in dimension $n \ge 100$, counting the cost of the exact dual evaluations; if the total observed work scales worse than a conventional inexact ALM with an accelerated-gradient inner loop, then the single-loop efficiency advantage is limited to structured $\Omega$, exactly as the weakest assumption suggests.

Watch

Extended reading notes

Core claim

The central discovery is that a bundle of past iterates can define a sequence of inner approximations $\Omega_k \subset \Omega$ whose induced approximate dual functions $g_k(y) = -\min_{x \in \Omega_k} L(x,y)$ satisfy exactly the three requirements of a proximal bundle model: they stay below the true dual function, they carry the subgradient of $g$ at the candidate point, and they aggregate the previous model's subgradient. Consequently the BALA update $z_{k+1} = y_k + \rho(b - A w_{k+1})$ is precisely a proximal step on $g_k$, and the descent test $g(y_k) - g(z_{k+1}) \ge \beta\bigl(g(y_k) - g_k(z_{k+1})\bigr)$ is the bundle method's test. This equivalence lets the authors transfer the convergence machinery of proximal bundle methods to ALM: null steps are bounded by $O(\epsilon^{-2})$, giving the $O(\epsilon^{-3})$ dual rate, and the inexact-ALM interpretation gives the primal average-iterate rate $O(\epsilon^{-3})$. Under the additional regularity conditions (18) and (19), a proximal-point contraction in the distance to the dual optimal set shows that every iteration is a descent step and the method converges linearly, a regime that includes SDPs with rank-one solutions.

Load-bearing premise

The convergence rates assume that at every iteration the algorithm can evaluate the true dual function exactly and can find the exact point in $\Omega$ where the Lagrangian attains the dual value; for a general compact convex set this is itself a convex optimization problem, so the advertised cheap per-iteration cost holds only for structured sets such as the nonnegative orthant, second-order cone, and positive semidefinite cone with a trace bound.

Editorial extensions

If this is right

  • BALA reaches a dual gap $g(y_k) - g^\star \le \epsilon$ in $O(\epsilon^{-3})$ iterations, and primal feasibility and cost gap $\le \epsilon$ in $O(\epsilon^{-6})$ iterations; setting $\rho = \epsilon$ improves both to $O(\epsilon^{-2})$ and $O(\epsilon^{-4})$.
  • Averaging the primal iterates over descent steps yields $O(\epsilon^{-3})$ for both primal residuals, giving the first average-iterate convergence result for the proximal bundle method.
  • Under quadratic growth (18) and quadratic closeness (19), every iteration is a descent step and the dual distance to optimality contracts by a constant factor; the same linear rate transfers to primal feasibility and cost gap.
  • When applied to SDPs with rank-one optimal solutions, BALA enjoys these linear rates while each subproblem over the line-segment approximation is solved in closed form, matching the structure of spectral bundle methods.
  • BALA matches the convergence behavior of classical inexact ALM, so subsequent iALM developments can be adapted to a single-loop scheme without an inner solver.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The efficiency claim is strongest for the three symmetric cones with trace bounds; for a general compact convex $\Omega$, the exact dual-oracle step in Assumption 3.1 is itself an optimization problem, so the practical single-loop advantage is an oracle property rather than a property of the bundle framework alone.
  • The equivalence with the proximal bundle method means that any improvement to bundle methods (better models, adaptive step sizes, second-order information) automatically yields an improved BALA; conversely, the average-iterate result proven for BALA transfers to PBM, which the paper notes is new.
  • The linear convergence for rank-one SDPs hints at a practical two-phase protocol: a coarse solver reaches a moderately accurate solution, then BALA refines it to high accuracy cheaply — the paper's experiments reach a $10^{-11}$ dual gap, beyond typical interior-point precision, though this use is only implicit.
  • The line-segment inner approximation gives BALA a Frank-Wolfe-like flavor with a safeguard test; connecting the two families, e.g. through momentum or weak-proximal oracles, is a natural next step that the paper only sketches.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes a bundle-based augmented Lagrangian algorithm (BALA) for constrained convex problems of the form (P). At each iteration, BALA solves a subproblem over an inner approximation Ω_k ⊂ Ω, computes a dual candidate via a proximal-type update, tests a sufficient descent criterion (15), and updates Ω_k using both primal and dual information (Assumption 3.1). The authors show that BALA is equivalent to a proximal bundle method applied to the dual (Lemmas 5 and Theorem 7), and exploit this connection to prove sublinear convergence of dual iterates, primal feasibility, and primal cost (Theorems 3 and 4), an average-iterate result (Theorem 5), and, under quadratic growth and quadratic closeness, linear convergence with every iteration being a descent step (Theorem 6). The main application is to semidefinite programs with trace-bounded PSD cones, where the subproblems and dual-function evaluations have closed forms.

Significance. If the results are correct, BALA is a potentially valuable single-loop alternative to inexact ALM for structured convex problems. The primal-dual PBM connection is a clean and useful observation, and the paper is generally well written. The fixed-ρ sublinear rates are plausible and the experiments show encouraging performance on SDPs. However, two load-bearing points—the claimed improved rates with ρ=ε in Theorem 4 and the penalty condition in Theorem 6—contain inconsistencies that need correction before the main claims are fully reliable.

major comments (3)
  1. [Theorem 4, Appendix D.5] The claim that choosing ρ=ε improves the dual and primal iteration complexities to O(ε^-2) and O(ε^-4) is unsupported and, as stated, false. Lemma 5 shows that the dual candidate z_{k+1} is the proximal point of the model g_k with parameter α=ρ (since the quadratic term is (1/(2ρ))||y-y_k||^2). Theorem 2's accelerated bound O(ε^-2) applies only when α=1/ε, i.e., ρ=1/ε, not ρ=ε. Moreover, to turn a dual gap of δ into a primal residual ||Ax_{k+1}-b|| ≤ ε, Lemma 2 (17b) requires δ ≤ ρβ ε^2/2; with ρ=ε this forces δ=O(ε^3), and the generic PBM bound then gives at best O(δ^-3)=O(ε^-9) iterations, not O(ε^-4). The proof in Appendix D.5 simply asserts that the O(ε^-4) bound 'follows from Lemmas 2 and 3' without performing the substitution. The fixed-ρ rates O(ε^-3) and O(ε^-6) appear consistent, but the improved rates should be removed or corrected.
  2. [Theorem 6, Appendix D.7] The condition ρ ≥ 1/γ stated in Theorem 6 contradicts the inequality 1/ρ ≥ γ used in the proof. In Appendix D.7, the descent argument applies Theorem 8, which requires the proximal parameter θ=1/ρ to satisfy θ ≥ α, where α corresponds to the quadratic-closeness constant γ in (19). The proof explicitly states '1/ρ ≥ γ where γ is the constant in (19)'. The theorem statement requires the opposite inequality, so a user who follows the stated condition ρ ≥ 1/γ may choose a penalty for which the proof's key step (descent at every iteration) is no longer guaranteed. The theorem condition must be changed to ρ ≤ 1/γ (or to 1/ρ ≥ γ) or the proof amended.
  3. [Assumption 3.1, Appendix A.2] The single-loop efficiency claim rests on Assumption 3.1 item 3, which requires at every iteration an exact point v_{k+1} ∈ Ω with g(z_{k+1}) = -L(v_{k+1}, z_{k+1}), plus exact evaluations of g(y_k) and g(z_{k+1}) in the descent test (15). For a general compact convex Ω these are convex optimization problems potentially as hard as the original problem, and the closed-form constructions in Appendix A.2 are available only for the nonnegative orthant, second-order cone, and PSD cone with a trace bound. The paper should state in the main text that the per-iteration cost is low only for such structured sets, and that the iteration-complexity guarantees do not account for the oracle cost when Ω is arbitrary. Otherwise the headline 'single-loop' advantage is overstated.
minor comments (5)
  1. [Theorem 2] In Theorem 2, the Lipschitz constant M is not defined in the theorem statement; it is first identified as ‖b‖+‖A‖D in Appendix D.5, which should be stated earlier.
  2. [Lemma 4] In Lemma 4, the bound O(ε^-2) on null steps between consecutive descent steps should specify the dependence of ε (the target accuracy) rather than an undefined 'sub-optimality measure'.
  3. [Appendix D.5] In Appendix D.5, the phrase 'viewing the reciprocal relationship between the penalty parameter ρ and the proximal mapping parameter in Lemma 5' should explicitly state that the proximal parameter is α=ρ.
  4. [Appendix D.7] In Appendix D.7, the expression for µ2 contains unclear parentheses in the term involving ρ^4 E^2; the formula should be typeset and grouped carefully.
  5. [Section 5] In Section 5, the text refers to 'Figure 3' when discussing the main experiments, but the first main-text figure is Figure 1; the cross-reference appears to be a typo.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: BALA's convergence proofs reduce to external PBM/PPM theory and explicitly stated regularity conditions; self-citations are redundant rather than load-bearing.

full rationale

The derivation chain is self-contained. The dual sublinear rate in Theorem 4 is obtained by proving BALA is a realization of the proximal bundle method (Lemma 5, Theorem 7, Appendix B.1) and then invoking the external PBM result [38, Theorem 2.1]; the primal feasibility and cost bounds are derived from Lemmas 2 and 3, not imported from the conclusion. Theorem 6 is a conditional statement whose hypotheses (quadratic growth (18) and quadratic closeness (19)) are explicitly assumed; the proof uses a standard PPM contraction (Theorem 8) and does not assume the conclusion. The SDP applicability claim is supported by the external result [5] (Ding & Grimmer); the same-author citations [4,22] are contextual/redundant and do not carry the load. Assumption 3.1's exact evaluation of g and exact construction of v_{k+1} is an oracle requirement common to PPM/PBM complexity analyses; it does not make the iteration counts circular. Separately, the claimed rho=epsilon improvement in Theorem 4 appears inconsistent with Lemma 5 (which makes the proximal parameter alpha=rho, so the O(epsilon^{-2}) regime of Theorem 2 requires rho=1/epsilon), and the proof of Theorem 6 uses 1/rho >= gamma while the statement requires rho >= 1/gamma; these are internal correctness risks, not circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The algorithm introduces no new physical or formal entities; it introduces inner approximation sets Ω_k, which are algorithmic constructions rather than postulated objects. The core claims rest on standard convex-analysis assumptions (Slater, compactness, Lipschitzness) plus user-chosen hyperparameters ρ and β. The linear convergence result rests on the quadratic growth and quadratic closeness assumptions, which are imported from prior work and not verified for the general case.

free parameters (3)
  • ρ (augmented Lagrangian penalty)
    Algorithm hyperparameter; Theorem 4 requires ρ = ε for improved rates and Theorem 6 (as intended) requires ρ ≤ 1/γ. It is user-selected, not fitted to data.
  • β (descent test ratio)
    Constant in (0,1) in the testing criterion (15); Theorem 6 further requires β ∈ (0,1/2]. It affects convergence bounds but is not fitted to data.
  • r (subspace dimension in SDP inner sets)
    User-chosen rank parameter in the SDP construction (Appendix F); it controls approximation quality and subproblem cost.
assumptions (4)
  • domain assumption Slater's condition holds for both (P) and (D), and Ω is compact
    Stated in Section 4; ensures strong duality, solvability of both problems, Lipschitzness of the dual function, and applicability of Theorems 1 and 2.
  • domain assumption An oracle exists to evaluate g(y) and to construct a point v ∈ Ω with g(z) = -L(v,z) at each iteration (Assumption 3.1 item 3)
    Required for the descent test (15) and the update of Ω_{k+1}; for generic Ω this is itself a convex optimization, so the efficiency claim depends on this oracle being cheap.
  • ad hoc to paper Quadratic growth (18) and quadratic closeness (19) hold for all k ≥ T
    Sufficient conditions imported from prior work [4,5] to obtain the linear rate in Theorem 6; they are assumed, not proved, for the general problem class.
  • standard math Rockafellar's inexact ALM convergence (Theorem 1) and Díaz-Grimmer's PBM convergence (Theorem 2)
    Borrowed external results that Theorems 3-5 rely on; the paper references them explicitly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Bundle-based Augmented Lagrangian Framework: Algorithm, Convergence, and Primal-dual Principles." pith.science (2026). https://pith.science/paper/MPCHSJTF

@misc{pith2026250208835,
  author       = {Pith},
  title        = {Pith review of: A Bundle-based Augmented Lagrangian Framework: Algorithm, Convergence, and Primal-dual Principles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MPCHSJTF}},
  note         = {Machine review of arXiv:2502.08835}
}
abstract

We propose a new bundle-based augmented Lagrangian framework for solving constrained convex problems. Unlike the classical (inexact) augmented Lagrangian method (ALM) that has a nested double-loop structure, our framework features a $\textit{single-loop}$ process. Motivated by the proximal bundle method (PBM), we use a $\textit{bundle}$ of past iterates to approximate the subproblem in ALM to get a computationally efficient update at each iteration. We establish sub-linear convergences for primal feasibility, primal cost values, and dual iterates under mild assumptions. With further regularity conditions, such as quadratic growth, our algorithm enjoys $\textit{linear}$ convergences. Importantly, this linear convergence can happen for a class of conic optimization problems, including semidefinite programs. Our proof techniques leverage deep connections with inexact ALM and primal-dual principles with PBM.

Figures

Figures reproduced from arXiv: 2502.08835 by the authors.

Figure 1
Figure 1. Comparison between our proposed BALA (Algorithm 3) and CGAL[6, 25]. design a scalable solver for SDPs [6]. The details of applying BALA to SDPs are given in Appendix F. More extensive numerical results are provided in Appendix G. We here consider two SDPs of the form min X∈Sn {tr(CX) : AX = b, tr(X) ≤ a, X ∈ S n +}, where C ∈ S n , A : S n → R m and a ≥ 0 are the problem data. This type of SDP is in the form of (P) … view at source ↗
Figure 2
Figure 2. Numerical experiment for a simple linear program (15), which serves as a safeguard to determine whether the current iterate should be accepted. Unlike BALA, the Frank-Wolfe algorithm always accepts new iterates, without assessing their quality before updating. Convex hull with three points. Despite the simplicity and the convergence guarantee of using the line segment approximation, the convergence can be slow when … view at source ↗
Figure 3
Figure 3. Linear convergence for SDPs. where the fourth equality uses the definition of an adjoint map, i.e., hA∗y, Xi = hy, AXi, ∀y ∈ R m, X ∈ S n, and the last inequality is due to C − A∗y ⋆ is positive semidefinite and a > tr(X⋆ ) ≥ λ1, which implies 0 = minX∈S n +,tr(X)≤a hC − A∗y ⋆ , Xi. Thus, the generated SDP does contain a rank-one solution X⋆ . Aside from the description of the problem generation, this subsection als… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Additional numerical experiments. The blue curves are from BALA, and the red curves are from CGAL [6]. 36 [PITH_FULL_IMAGE:figures/full_fig_p036_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Proximal Descent Method for Minimizing Weakly Convex Optimization

    math.OC 2025-09 conditional novelty 6.0 of 10

    A bundle-based proximal descent method achieves O(1/delta^4) for Moreau stationarity on weakly convex functions and adapts to O(1/delta^2) under smoothness and linear convergence under quadratic growth.

Reference graph

Works this paper leans on

63 extracted references · 56 canonical work pages · cited by 1 Pith paper

  1. [1]

    Convex optimization

    Stephen P Boyd and Lieven Vandenberghe. Convex optimization . Cambridge university press, 2004. 13

    work page 2004

  2. [2]

    Handbook of semidefinite programming: theory, algorithms, and applications , volume 27

    Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. Handbook of semidefinite programming: theory, algorithms, and applications , volume 27. Springer Science & Business Media, 2012

    work page 2012

  3. [3]

    A primal-dual Frank-Wolf e algorithm for linear programming

    Matthew Hough and Stephen A Vavasis. A primal-dual Frank-Wolf e algorithm for linear programming. arXiv preprint arXiv:2402.18514 , 2024

    arXiv 2024

  4. [4]

    An overview and compa rison of spectral bundle methods for primal and dual semidefinite programs

    Feng-Yi Liao, Lijun Ding, and Yang Zheng. An overview and compa rison of spectral bundle methods for primal and dual semidefinite programs. arXiv preprint arXiv:2307.07651 , 2023

    arXiv 2023

  5. [5]

    Revisiting spectral bundle metho ds: Primal-dual (sub) linear convergence rates

    Lijun Ding and Benjamin Grimmer. Revisiting spectral bundle metho ds: Primal-dual (sub) linear convergence rates. SIAM Journal on Optimization , 33(2):1305–1332, 2023

    work page 2023

  6. [6]

    Scalable semidefinite programming

    Alp Yurtsever, Joel A Tropp, Olivier Fercoq, Madeleine Udell, and V olkan Cevher. Scalable semidefinite programming. SIAM Journal on Mathematics of Data Science , 3(1):171–200, 2021

    work page 2021

  7. [7]

    Chordal and factor-width decompo- sitions for scalable semidefinite and polynomial optimization

    Yang Zheng, Giovanni Fantuzzi, and Antonis Papachristodoulou . Chordal and factor-width decompo- sitions for scalable semidefinite and polynomial optimization. Annual Reviews in Control , 52:243–279, 2021

    work page 2021

  8. [8]

    Improved approximation alg orithms for maximum cut and satisfiability problems using semidefinite programming

    Michel X Goemans and David P Williamson. Improved approximation alg orithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM) , 42(6):1115–1145, 1995

    work page 1995

Show all 63 references
  1. [9]

    On the constr uction of Lyapunov functions using the sum of squares decomposition

    Antonis Papachristodoulou and Stephen Prajna. On the constr uction of Lyapunov functions using the sum of squares decomposition. In Proceedings of the 41st IEEE Conference on Decision and Cont rol, 2002., volume 3, pages 3482–3487. IEEE, 2002

    2002

  2. [10]

    Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery

    Emmanuel Abbe, Afonso S Bandeira, Annina Bracher, and Amit S inger. Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. IEEE Transactions on Network Science and Engineering , 1(1):10–22, 2014

    2014

  3. [11]

    Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming

    Emmanuel J Candes, Thomas Strohmer, and Vladislav Voroninsk i. Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Communications on Pure and Applied Mathematics, 66(8):1241–1274, 2013

    2013

  4. [12]

    Low-rank matrix recovery from errors and erasures

    Yudong Chen, Ali Jalali, Sujay Sanghavi, and Constantine Caram anis. Low-rank matrix recovery from errors and erasures. IEEE Transactions on Information Theory , 59(7):4324–4337, 2013

    2013

  5. [13]

    PEPit: computer-assisted worst-case analyses of fir st-order optimization methods in Python

    Baptiste Goujaud, C´ eline Moucer, Fran¸ cois Glineur, Julien M Hendrickx, Adrien B Taylor, and Aymeric Dieuleveut. PEPit: computer-assisted worst-case analyses of fir st-order optimization methods in Python. Mathematical Programming Computation , 16(3):337–367, 2024

    2024

  6. [14]

    On the scalability and memory efficiency of semidefinite programs for L ipschitz constant estimation of neural networks

    Zi Wang, Bin Hu, Aaron J Havens, Alexandre Araujo, Yang Zhen g, Yudong Chen, and Somesh Jha. On the scalability and memory efficiency of semidefinite programs for L ipschitz constant estimation of neural networks. In The Twelfth International Conference on Learning Represen tations, 2024

    2024

  7. [15]

    Augmented Lagrangians and applications of the proximal point algorithm in convex programming

    R Tyrrell Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of operations research , 1(2):97–116, 1976

    1976

  8. [16]

    Multiplier and gradient methods

    Magnus R Hestenes. Multiplier and gradient methods. Journal of optimization theory and applications , 4(5):303–320, 1969

    1969

  9. [17]

    A method for nonlinear constraints in minimizatio n problems

    Michael JD Powell. A method for nonlinear constraints in minimizatio n problems. Optimization, pages 283–298, 1969

    1969

  10. [18]

    Monotone operators and the proximal p oint algorithm

    R Tyrrell Rockafellar. Monotone operators and the proximal p oint algorithm. SIAM journal on control and optimization , 14(5):877–898, 1976

    1976

  11. [19]

    Asymptotic convergence analysis of t he proximal point algorithm

    Fernando Javier Luque. Asymptotic convergence analysis of t he proximal point algorithm. SIAM Journal on Control and Optimization , 22(2):277–293, 1984

    1984

  12. [20]

    On the R-superlinear c onvergence of the KKT residuals generated by the augmented Lagrangian method for convex comp osite conic programming

    Ying Cui, Defeng Sun, and Kim-Chuan Toh. On the R-superlinear c onvergence of the KKT residuals generated by the augmented Lagrangian method for convex comp osite conic programming. Math. Program., 178:381–415, 2019. 14

    2019

  13. [21]

    Iteration complexity of inexact augmented Lagr angian methods for constrained convex programming

    Yangyang Xu. Iteration complexity of inexact augmented Lagr angian methods for constrained convex programming. Mathematical Programming, 185:199–244, 2021

    2021

  14. [22]

    Inexact augmented Lagrangian methods for conic opti- mization: Quadratic growth and linear convergence

    Feng-Yi Liao, Lijun Ding, and Yang Zheng. Inexact augmented Lagrangian methods for conic opti- mization: Quadratic growth and linear convergence. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024

    2024

  15. [23]

    A se mismooth Newton-CG based dual PPA for matrix spectral norm approximation problems

    Caihua Chen, Yong-Jin Liu, Defeng Sun, and Kim-Chuan Toh. A se mismooth Newton-CG based dual PPA for matrix spectral norm approximation problems. Math. Program., 155(1):435–470, 2016

    2016

  16. [24]

    Sdpnal+: A matlab software for semidefinite programming with bound constraints (version 1.0)

    Defeng Sun, Kim-Chuan Toh, Yancheng Yuan, and Xin-Yuan Zha o. Sdpnal+: A matlab software for semidefinite programming with bound constraints (version 1.0). Optimization Methods and Software , 35(1):87–115, 2020

    2020

  17. [25]

    A conditional- gradient-based augmented Lagrangian framework

    Alp Yurtsever, Olivier Fercoq, and Volkan Cevher. A conditional- gradient-based augmented Lagrangian framework. In International Conference on Machine Learning , pages 7272–7281. PMLR, 2019

    2019

  18. [26]

    A fast iterative shrinkage-thresh olding algorithm for linear inverse problems

    Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresh olding algorithm for linear inverse problems. SIAM journal on imaging sciences , 2(1):183–202, 2009

    2009

  19. [27]

    An algorithm for quadratic p rogramming

    Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic p rogramming. Naval research logistics quarterly, 3(1-2):95–110, 1956

    1956

  20. [28]

    Sdpnal+: a majoriz ed semismooth Newton-CG aug- mented Lagrangian method for semidefinite programming with nonne gative constraints

    Liuqin Yang, Defeng Sun, and Kim-Chuan Toh. Sdpnal+: a majoriz ed semismooth Newton-CG aug- mented Lagrangian method for semidefinite programming with nonne gative constraints. Math. Program. Computation, 7(3):331–366, 2015

    2015

  21. [29]

    A Newton-CG a ugmented Lagrangian method for semidefinite programming

    Xin-Yuan Zhao, Defeng Sun, and Kim-Chuan Toh. A Newton-CG a ugmented Lagrangian method for semidefinite programming. SIAM Journal on Optimization , 20(4):1737–1765, 2010

    2010

  22. [30]

    Iteration-complexity o f first-order augmented Lagrangian methods for convex programming

    Guanghui Lan and Renato DC Monteiro. Iteration-complexity o f first-order augmented Lagrangian methods for convex programming. Mathematical Programming, 155(1):511–547, 2016

    2016

  23. [31]

    Sum of squares basis pursuit wit h linear and second order cone programming

    Amir Ali Ahmadi and Georgina Hall. Sum of squares basis pursuit wit h linear and second order cone programming. Algebraic and geometric methods in discrete mathematics , 685:27–53, 2017

    2017

  24. [32]

    Bloc k factor-width-two matrices and their applications to semidefinite and sum-of-squares optimization

    Yang Zheng, Aivar Sootla, and Antonis Papachristodoulou. Bloc k factor-width-two matrices and their applications to semidefinite and sum-of-squares optimization. IEEE Transactions on Automatic Control, 68(2):943–958, 2022

    2022

  25. [33]

    Iterative inner/outer approxim ations for scalable semidefinite programs using block factor-width-two matrices

    Feng-Yi Liao and Yang Zheng. Iterative inner/outer approxim ations for scalable semidefinite programs using block factor-width-two matrices. In 2022 IEEE 61st Conference on Decision and Control (CDC) , pages 7591–7597. IEEE, 2022

    2022

  26. [34]

    A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

    Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program., 95(2):329–357, 2003

    2003

  27. [35]

    A lo w-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex- nonconvex approach

    Renato DC Monteiro, Arnesh Sujanani, and Diego Cifuentes. A lo w-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex- nonconvex approach. arXiv preprint arXiv:2401.12490, 2024

    2024 arXiv

  28. [36]

    A feasible method for general convex low-rank SDP problems

    Tianyun Tang and Kim-Chuan Toh. A feasible method for general convex low-rank SDP problems. SIAM Journal on Optimization , 34(3):2169–2200, 2024

    2024

  29. [37]

    A dec omposition augmented lagrangian method for low-rank semidefinite programming

    Yifei Wang, Kangkang Deng, Haoyang Liu, and Zaiwen Wen. A dec omposition augmented lagrangian method for low-rank semidefinite programming. SIAM Journal on Optimization , 33(3):1361–1390, 2023

    2023

  30. [38]

    Optimal convergence ratesfor the proximal bundle method

    Mateo D ´ ıaz and Benjamin Grimmer. Optimal convergence ratesfor the proximal bundle method. SIAM Journal on Optimization , 33(2):424–454, 2023

    2023

  31. [39]

    Faster projec tion-free augmented Lagrangian methods via weak proximal oracle

    Dan Garber, Tsur Livney, and Shoham Sabach. Faster projec tion-free augmented Lagrangian methods via weak proximal oracle. In International Conference on Artificial Intelligence and St atistics, pages 7213–7238. PMLR, 2023. 15

    2023

  32. [40]

    On the nonergodic converge nce rate of an inexact aug- mented Lagrangian framework for composite convex programming

    Ya-Feng Liu, Xin Liu, and Shiqian Ma. On the nonergodic converge nce rate of an inexact aug- mented Lagrangian framework for composite convex programming . Mathematics of Operations Research, 44(2):632–650, 2019

    2019

  33. [41]

    Practical augmented Lagrangian methods for constrained optimization

    Ernesto G Birgin and Jos´ e Mario Mart ´ ınez. Practical augmented Lagrangian methods for constrained optimization. SIAM, 2014

    2014

  34. [42]

    Metric subregularity and the proximal point metho d

    D Leventhal. Metric subregularity and the proximal point metho d. Journal of Mathematical Analysis and Applications, 360(2):681–688, 2009

    2009

  35. [43]

    First-order methods in optimization

    Amir Beck. First-order methods in optimization . SIAM, 2017

    2017

  36. [44]

    A condensed introductio n to bundle methods in nonsmooth optimization

    Claude Lemarechal and Jochem Zowe. A condensed introductio n to bundle methods in nonsmooth optimization. In Algorithms for continuous optimization: the state of the ar t, pages 357–382. Springer, 1994

    1994

  37. [45]

    Learning the kernel matrix with semidefinite programming

    Gert RG Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine learning research , 5(Jan):27–72, 2004

    2004

  38. [46]

    On approximations of the psd c one by a polynomial number of smaller-sized psd cones

    Dogyoon Song and Pablo A Parrilo. On approximations of the psd c one by a polynomial number of smaller-sized psd cones. Mathematical Programming, 198(1):733–785, 2023

    2023

  39. [47]

    Nonlinear optimization

    Andrzej Ruszczynski. Nonlinear optimization. Princeton university press, 2011

    2011

  40. [48]

    Error bounds, pl co ndition, and quadratic growth for weakly convex functions, and linear convergences of proximal poin t methods

    Feng-Yi Liao, Lijun Ding, and Yang Zheng. Error bounds, pl co ndition, and quadratic growth for weakly convex functions, and linear convergences of proximal poin t methods. In 6th Annual Learning for Dynamics & Control Conference , pages 993–1005. PMLR, 2024

    2024

  41. [49]

    A spectral bundle method for semidefinite programming

    Christoph Helmberg and Franz Rendl. A spectral bundle method for semidefinite programming. SIAM Journal on Optimization , 10(3):673–696, 2000

    2000

  42. [50]

    Quadratic growth conditio ns for convex matrix optimization problems associated with spectral functions

    Ying Cui, Chao Ding, and Xinyuan Zhao. Quadratic growth conditio ns for convex matrix optimization problems associated with spectral functions. SIAM Journal on Optimization , 27(4):2332–2355, 2017

    2017

  43. [51]

    Exact matrix completion via convex optimization

    Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communi- cations of the ACM , 55(6):111–119, 2012

    2012

  44. [52]

    Second-order cone progra mming

    Farid Alizadeh and Donald Goldfarb. Second-order cone progra mming. Mathematical programming, 95(1):3–51, 2003

    2003

  45. [53]

    Convex analysis , volume 11

    R Tyrrell Rockafellar. Convex analysis , volume 11. Princeton university press, 1997

    1997

  46. [54]

    Gradient methods for minimizing composite functio ns

    Yu Nesterov. Gradient methods for minimizing composite functio ns. Mathematical programming , 140(1):125–161, 2013

    2013

  47. [55]

    Revisiting frank-wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International conference on machine learning , pages 427–435. PMLR, 2013

    2013

  48. [56]

    Spectr al frank-wolfe algorithm: Strict complementarity and linear convergence

    Lijun Ding, Yingjie Fei, Qiantong Xu, and Chengrun Yang. Spectr al frank-wolfe algorithm: Strict complementarity and linear convergence. In International conference on machine learning , pages 2535–

  49. [57]

    On the asymptotic sup erlinear convergence of the aug- mented Lagrangian method for semidefinite programming with multiple solutions

    Ying Cui, Defeng Sun, and Kim-Chuan Toh. On the asymptotic sup erlinear convergence of the aug- mented Lagrangian method for semidefinite programming with multiple solutions. arXiv preprint arXiv:1610.00875, 2016

    2016 arXiv

  50. [58]

    The MOSEK optimization toolbox for MATLAB manual

    MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 9 .0., 2019

    2019

  51. [59]

    On the simplicity and conditioning of low rank semidefinite programs

    Lijun Ding and Madeleine Udell. On the simplicity and conditioning of low rank semidefinite programs. SIAM Journal on Optimization , 31(4):2614–2637, 2021

    2021

  52. [60]

    Global optimization with polynomials and the pro blem of moments

    Jean B Lasserre. Global optimization with polynomials and the pro blem of moments. SIAM Journal on optimization , 11(3):796–817, 2001. 16 Appendix Organization In this appendix, we provide extra discussions, proof details, and f urther computational results. In particular, we ...

    2001

  53. [61]

    In particular, as we will see in ( B.1), it holds that − min x∈ Ω k Lρ(x, yk) = min y∈ Rm gk(y) + 1 2ρ ‖y − yk‖2

    is solved. In particular, as we will see in ( B.1), it holds that − min x∈ Ω k Lρ(x, yk) = min y∈ Rm gk(y) + 1 2ρ ‖y − yk‖2. Thus, once wk+1 ∈ minx∈ Ω k Lρ(x, yk) and zk+1 = yk + ρ(b − A wk+1) are constructed, gk(zk+1) can be recovered as gk(zk+1) = −Lρ(wk+1, yk) − 1 2ρ ‖zk+1 ...

  54. [62]

    Finally, our bundle -based Augmented Lagrangian framework also complements the viewpoints of interior-point and penalty m ethods [1, Chapter 11] in addressing Ω

    and Frank-Wolfe-type algorithms [ 27, 55], though establishing an exact connection requires furthe r in- vestigation and is left for future work. Finally, our bundle -based Augmented Lagrangian framework also complements the viewpoints of interior-point and penalty m ethods [1...

  55. [63]

    The convex hull app roximation with three points always contains the line approximation

    convex hull approximation with three points. The convex hull app roximation with three points always contains the line approximation. In both constructions, the subpr oblem admits an analytical solution. As discussed in Appendix A.2 , at iteration k, the dual information vk+1 ...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.