betaFeedback

WorksMathematics

A Low-Rank Augmented Lagrangian Frank-Wolfe-Based Method for SDPs with Unbounded Feasible Regions

Abstract

In contrast to HALLaR (Monteiro et al. 2026), which is designed for solving problems with a trace-bounding constraint, this work develops a new augmented Lagrangian (AL) method, HALLaR+, for solving large-scale semidefinite programming problems without such constraint. Even though a trace constraint which preserves an optimal solution can always be added, choosing its bound is challenging: a value that is too small may exclude all optimal solutions, whereas one that is too large may substantially increase the computational effort. HALLaR+ is also a low-rank inexact AL method but, in contrast to HALLaR, it doubles the penalty parameter at every AL iteration and its AL subproblems have unbounded feasible regions that are approximately solved by a relaxed unbounded Frank–Wolfe (RUFW) variant. Its analysis relies on a uniform bound on the diameters of the sublevel sets of all generated AL subproblems instead of a bounded feasible set. Assuming that a primal–dual KKT pair exists and the primal optimal set is nonempty and bounded, it is shown that HALLaR+ returns a ε\varepsilon-primal-dual feasible solution in O~(ε−2)\tilde {\mathcal O}(\varepsilon^{-2}) total RUFW iterations. Numerical results suggest that HALLaR+ has very promising competitive performance against current state-of-the-art solvers.

Introduction

This paper develops a hybrid convex–nonconvex augmented Lagrangian (AL) variant of HALLaR of [44], namely HALLaR+, which can solve SDPs, in general standard form, i.e.,

min⁡X∈Sn{⟨C,X⟩:AX=b, X⪰0}(1)\min_{X \in\mathbb{S}^{n}} \{\langle C, X\rangle: \mathcal{A}X=b,\ X \succeq0\} \tag*{(1)}

where Rm\mathbb{R}^{m} is the mm-dimensional Euclidean space equipped with the standard inner product, Sn\mathbb{S}^{n} is the space of n×nn \times n real symmetric matrices equipped with the Frobenius inner product, ⪰0\succeq0 denotes the Löwner partial order on Sn\mathbb{S}^{n}, so that X⪰0X \succeq0 means XX is positive semidefinite (PSD), C∈SnC \in\mathbb{S}^{n}, b∈Rmb \in\mathbb{R}^{m}, and A:Sn→Rm\mathcal{A} : \mathbb{S}^{n} \to\mathbb{R}^{m} is a linear operator with adjoint A∗:Rm→Sn\mathcal{A}^{*} : \mathbb{R}^{m} \to\mathbb{S}^{n}. In contrast, HALLaR can only solve SDPs where one of the constraints in (1) is a bounded trace constraint, i.e., tr⁡(X)≤τ\operatorname{tr}(X) \le\tau for some τ>0\tau> 0. Even though a trace constraint can always be added to (1) with a constant τ\tau that preserves at least one optimal solution, choosing such a τ\tau in practice is challenging: a value that is too small may exclude all optimal solutions, whereas one that is too large may substantially increase the computational effort.

Approach and relation to HALLaR. HALLaR+ is an inexact AL method that generates sequences {Zt}\{Z_t\} and {pt}\{p_t\} according to the recursion

Zt≈arg min⁡X∈Sn{Lβt−1(X;pt−1):=⟨C,X⟩+⟨pt−1,b−AX⟩+βt−12∥b−AX∥2:X⪰0},(2)Z_t \approx\underset{X \in\mathbb{S}^{n}}{\operatorname{arg\,min}}\left\{\mathcal{L}_{\beta_{t-1}}(X;p_{t-1}) := \langle C,X\rangle+ \langle p_{t-1},b-\mathcal{A}X\rangle+ \frac{\beta_{t-1}}{2}\lVert b-\mathcal{A}X\rVert^{2} : X \succeq0\right\}, \tag*{(2)}
pt=pt−1+βt−1(b−AZt),βt=γβt−1,(3)p_t = p_{t-1}+\beta_{t-1}(b-\mathcal{A}Z_t),\qquad\beta_t=\gamma\beta_{t-1}, \tag*{(3)}

with γ=2\gamma= 2. HALLaR differs from the above updates (2a) and (2b) in two aspects. First, as HALLAR solves SDPs over the set {X∈Sn:A(X)=b, tr⁡(X)≤τ, X⪰0}\{X \in\mathbb{S}^{n}: \mathcal{A}(X) = b,\ \operatorname{tr}(X) \le\tau,\ X \succeq0\}, its AL subproblems are obtained by dualizing A(X)=b\mathcal{A}(X) = b, while keeping tr⁡(X)≤τ\operatorname{tr}(X) \le\tau and X⪰0X \succeq0 as constraints. Hence, in contrast to (2a), their feasible regions are bounded. Second, the theoretical analysis of HALLaR assumes γ=1\gamma= 1, and hence that the penalty parameters are kept constant.

Both HALLaR and HALLaR+ use Frank–Wolfe (FW), or conditional-gradient, variants to approximately solve their AL subproblem (2a), initialized at Zt−1Z_{t-1}. However, because the AL subproblems arising in HALLaR+ have an unbounded feasible region, the FW variant used to solve them relies on substantially different techniques from the one used by HALLaR. Both FW variants generate matrices in factored form, i.e., X=UUTX = UU^{\mathsf{T}}, where the number of columns rr of UU varies during the algorithm but is usually much smaller than nn. This low-rank representation reduces memory footprint from O(n2)O(n^2) to O(nr)O(nr) and exploits sparsity in the SDP data [8, 9, 44, 2]. Both XX and UU are viewed as iterates in our discussion, with UU referred to as a factor of XX. For a matrix VV, col⁡(V)\operatorname{col}(V) denotes its number of columns. Starting from a low-rank factor U~∈Rn×r\widetilde{U} \in\mathbb{R}^{n \times r}, an iteration of both FW variants consists of the following two basic steps:

  1. find a factor U∈Rn×rU \in\mathbb{R}^{n \times r} such that col⁡(U)≤col⁡(U~)\operatorname{col}(U) \le\operatorname{col}(\widetilde{U}) and Lβt−1(UUT;pt−1)≤Lβt−1(U~U~T;pt−1)\mathcal{L}_{\beta_{t-1}}(UU^{\mathsf{T}};p_{t-1}) \le\mathcal{L}_{\beta_{t-1}}(\widetilde{U}\widetilde{U}^{\mathsf{T}};p_{t-1});

  1. without forming the associated full matrix, check whether UUTUU^{\mathsf{T}} satisfies the prescribed approximate optimality conditions for (2a). If so, terminate and set Zt=UUTZ_t = UU^{\mathsf{T}}; otherwise, perform an FW-type step based at UUTUU^{\mathsf{T}} to escape from this spurious solution UU to obtain a subsequent low-rank factor U~+\widetilde{U}^{+} satisfying col⁡(U~+)≤col⁡(U)+1\operatorname{col}(\widetilde{U}^{+}) \le\operatorname{col}(U)+1, and hence col⁡(U~+)≤col⁡(U~)+1\operatorname{col}(\widetilde{U}^{+}) \le\operatorname{col}(\widetilde{U})+1.

We now discuss (i) in greater detail. The choice U=U~U = \widetilde{U} trivially satisfies step i) and has been used by methods such as CGAL and T-CGAL [66, 67] (see also the methods in [68, 16, 52] for similar limited memory or reduced storage variants). Such methods can be viewed as essentially pure Frank-Wolfe methods, but have the disadvantage of producing iterates with high number of columns, since steps (i)–(ii) must generally be repeated many times. On the other hand, to implement the second part of (i), HALLaR and HALLaR+ both use the nonlinear solver ADAP-AIPP, initialized at U~\widetilde{U}, to find a near-stationary point UU of min⁡V∈Rn×rLβt−1(VVT;pt−1)\min_{V \in\mathbb{R}^{n \times r}} \mathcal{L}_{\beta_{t-1}}(VV^{\mathsf{T}};p_{t-1}) satisfying the descent condition in step i). Since the objective of this unconstrained subproblem is nonconvex and has only a locally Lipschitz continuous gradient, establishing the required complexity guarantees for ADAP-AIPP in this setting requires a more delicate analysis than the one used in HALLaR. The additional difficulty arises from the fact that, whereas the complexity of HALLaR depends on the diameter of the bounded feasible set, the complexity of HALLaR+ depends on a uniform bound on the diameters of all generated sublevel sets, some of which depend on both βt−1\beta_{t-1} and pt−1p_{t-1}.

We next discuss (ii). Unlike HALLaR, which uses a computable FW gap to estimate whether the primal gap of min⁡X⪰0{Lβt−1(X;pt−1):X⪰0, tr⁡(X)≤1}\min_{X \succeq0}\{\mathcal{L}_{\beta_{t-1}}(X;p_{t-1}): X \succeq0,\ \operatorname{tr}(X) \le1\} at X=UUTX = UU^{\mathsf{T}} is small, HALLaR+ uses approximate optimality conditions tailored to the unbounded subproblem (2). Specifically, with S=∇XLβt−1(UUT;pt−1)S = \nabla_X\mathcal{L}_{\beta_{t-1}}(UU^{\mathsf{T}};p_{t-1}), it checks whether λmin⁡(S)\lambda_{\min}(S) is nearly nonnegative and ⟨S,UUT⟩\langle S, UU^{\mathsf{T}}\rangle is small. If either condition fails, HALLaR+ finds a rank-one matrix y∗(y∗)Ty^*(y^*)^{\mathsf{T}} by solving min⁡X⪰0{⟨S,X⟩:tr⁡(X)≤1}\min_{X \succeq0}\{\langle S,X\rangle:\operatorname{tr}(X) \le1\} and forms the next iterate as a conic combination of this matrix and the current iterate, with the two coefficients of the conic combination chosen by a two-dimensional line search.

This approach for solving each AL subproblem is closely related to those of Laue [35] and Duchi et al. [17, 36], which develop FW variants for the generic static problem of minimizing a convex function ϕ(⋅)\phi(\cdot) over S+n\mathbb{S}^{n}_{+}. The two-dimensional line search for the conic coefficients used in our FW variant is motivated by the scheme of Laue. However, whereas Laue’s convergence analysis is based on a primal-gap criterion that is not directly checkable in practice, our method uses the aforementioned tractable termination criteria. Duchi et al., on the other hand, propose a different unbounded FW variant based on two successive one-dimensional line-searches rather than a single two-dimensional line search. Like our FW variant, their method terminates based on checkable approximate optimality conditions. While closely related to these methods, our FW variant requires a more involved analysis because it must account for the changing AL subproblems in (2) and the dynamics of their associated sublevel sets, a difficulty absent from the static settings considered by Laue and Duchi et al.

Our results and computational impact. Assuming that a primal–dual KKT pair exists and that the set of optimal solutions of (1) is nonempty and bounded, it is shown that HALLaR+ obtains an approximate primal–dual solution of (1) and its dual with provable computational complexity bounds expressed in terms of parameters associated with the SDP instance and user-specified tolerances. In particular, if the tolerances on primal feasibility, dual feasibility, and complementarity are all equal to ϵ∈(0,1]\epsilon\in(0,1], then HALLaR+ performs O(log⁡(1/ϵ))O(\log(1/\epsilon)) AL iterations, O(ϵ−2)O(\epsilon^{-2}) FW iterations/minimum eigenvector computations, and O(ϵ−3)O(\epsilon^{-3}) ADAP-AIPP iterations. Our GPU implementation of HALLaR+ is faster than cuHALLaR [2] on 12 of 14 Hamming and 24 of 28 GSET maximum stable set instances, as well as all 26 matrix completion instances. On a single NVIDIA H200, it reaches 10−510^{-5} relative precision in about 44 seconds on a Hamming SDP (n≈8.4×106n \approx8.4 \times10^{6}, m≈9.7×107m \approx9.7 \times10^{7}) and 31 seconds on a matrix completion SDP (n=2×106n = 2 \times10^{6}, m≈2.6×108m \approx2.6 \times10^{8}). On the other hand, cuLoRADS [23] fails on the Hamming instance and takes about 4,100 seconds on the matrix completion instance. At 10−410^{-4} relative precision, cuHALLaR+ solves 80 of 81 QAPLIB relaxations, compared with 56 for CSDP [5], 17 for HALLaR, and one for cuLoRADS. On the Mittelmann benchmarks [43], cuHALLaR+ solves 27 instances within one hour, cuLoRADS solves 15, and CARDAL [37] solves 14. The final cuHALLaR+ iterate has rank two on every Hamming instance, at most r+1r + 1 on every matrix completion instance with ground-truth rank rr, and 465 on the largest random quadratic assignment instance.

Related works. Interior-point methods are widely used to solve small and medium-scale SDPs to high accuracy. Their applicability to large-scale instances is limited, however, because each Newton-type iteration typically requires solving a large linear system, often through the factorization of a large and potentially dense matrix [5, 3, 45, 59]. We therefore focus below on methods specifically designed for large-scale SDPs.

SDPNAL+ [69, 65] is an augmented Lagrangian (AL) method that approximately solves each AL subproblem using a semismooth Newton–CG method. Spectral bundle methods, and more generally bundle methods, have also been developed for large-scale SDPs (see, for example, [25, 10, 24, 14, 46, 4]). Another substantial line of work applies the alternating direction method of multipliers (ADMM) and related operator-splitting methods to large-scale SDPs (e.g., [47, 20, 13, 40, 70, 33, 12, 63, 48]). Since methods based on nonconvex low-rank (LR) factorizations are most closely related to the approach developed in this paper, we discuss them in greater detail below. We refer the reader to the survey [41] for a broader overview of methods for solving large-scale SDPs.

The nonconvex LR approach introduced in [8, 9] underlies many successful algorithms for solving important classes of SDPs. In particular, the SDPLR method developed in these works applies an AL method to the smooth nonconvex reformulation

min⁡U {C∙UUT : A(UUT)=b,∥U∥F≤1,U∈Rn×r}(4)\min_{U}\ \left\{ C \bullet UU^{T} \ :\ A(UU^{T}) = b,\quad\lVert U\rVert_{F} \le1,\quad U \in\mathbb{R}^{n \times r} \right\} \tag*{(4)}

and approximately solves its AL subproblems using a limited-memory BFGS method. Although SDPLR is designed to handle equality constraints, it can be modified to accommodate inequality constraints (see, for example, [34]).

Several methods solve (Pr)(P_r) without employing an AL framework. For MaxCut SDPs, several specialized algorithms solve (Pr)(P_r) using optimization techniques that preserve feasibility throughout their execution (e.g., [7, 27, 18, 42, 32]). Riemannian optimization methods have also been employed for structured classes of SDPs for which the feasible set of (Pr)(P_r) is a smooth manifold (e.g., [51, 32, 30, 42]). Related feasibility-preserving methods based on manifold-optimization techniques have been developed for more challenging classes of SDPs in which the feasible sets of (Pr)(P_r) are algebraic varieties [55, 56, 57]. Alternative feasibility-preserving strategies have also been explored in [50].

More recently, several low-rank SDP solvers have combined low-rank factorization with augmented-Lagrangian-type schemes [31, 6]. Like SDPLR, LoRADS and its GPU counterpart cuLoRADS [23, 22] use the factorization X=UUTX = UU^{T} in their first phase and apply an inexact AL method to (Pr)(P_r). In their second phase, these methods adopt the bilinear factorization X=UVTX = UV^{T}, penalize the additional constraint U=VU = V, and apply an alternating-minimization scheme to the resulting augmented Lagrangian function. The ALORA method [15] combines gradient descent with a spectral block Frank–Wolfe method to approximately minimize its nonconvex AL subproblems. CARDAL [37] combines rank-adaptive AL iterations with matrix-free L-BFGS and negative-curvature corrections, provides slack-based approximate optimality conditions, and supports distributed GPU execution. SDPF+ [58] combines a feasible low-rank method with an AL phase using a dynamically weighted quadratic penalty. Other low-rank methods focus on specially structured SDPs whose factorized nonconvex AL subproblems take the form arg min⁡U∈MLβt−1(UUT;pt−1)\mathop{\operatorname{arg\,min}}_{U \in\mathcal{M}} \mathcal{L}_{\beta_{t-1}}(UU^{T}; p_{t-1}), where M\mathcal{M} is a Riemannian manifold. Such subproblems are solved using either a Riemannian trust-region method [60, 61] or a Riemannian semismooth Newton method [62]. For SDP-RL and polyhedral-SDP relaxations, respectively, RiNNAL+ and RiNNAL-POP [29, 28] combine low-rank AL iterations with projected-gradient steps in the original matrix variable to adjust the rank and escape spurious factor-space local minima.

Structure of the paper. This paper is organized into five sections and two appendices. Section 2 introduces the pair of primal-dual SDP problems and develops a general AL framework for solving them. Section 3 presents X-AL, an instance of this framework whose iterates are generated in the S+n\mathbb{S}_{+}^{n} space, and establishes its main complexity result for solving the SDP pair. Section 4 introduces HALLaR+, a computationally and memory-efficient variant of X-AL implemented in the UU-space. Theorem 4.1, the main theorem of the paper, establishes the complexity bounds for HALLaR+. Section 5 reports computational experiments comparing HALLaR+ with several existing solvers on a large collection of SDPs. Appendix A provides technical convex-analysis results used throughout the paper and develops the relaxed unbounded Frank–Wolfe (RUFW) framework used by X-AL. Finally, Appendix B presents the convergence analyses of an adaptive version of FISTA and an inexact proximal point method, both implemented in the U-space and used as subroutines within HAllaR+.

Basic definitions and notation

Let E\mathbb{E} be a finite-dimensional inner-product space. We denote its inner product by ⟨X,Y⟩\langle X,Y\rangle and the associated norm by ∥X∥:=⟨X,X⟩\|X\| := \sqrt{\langle X,X\rangle}. When E=Sn\mathbb{E} = \mathbb{S}^{n}, we use the trace inner product ⟨X,Y⟩:=tr⁡(XY)\langle X,Y\rangle:= \operatorname{tr}(XY), whose associated norm is the Frobenius norm. We use the notation

References

  1. [1]J. Aguirre, D. Cifuentes, V. Guigues, R. D. Monteiro, V. H. Nascimento, and A. Sujanani, A user manual for challular: A gpu accelerated low-rank semidefinite programming solver, arXiv preprint arXiv:2508.15951, (2025).
  2. [2]J. M. Aguirre, D. Cifuentes, V. Guigues, R. D. Monteiro, V. H. Nascimento, and A. Sujanani, cuHAL-LaR: A GPU accelerated low-rank augmented lagrangian method for large-scale semidefinite programming, arXiv preprint arXiv:2505.13719, (2025).arxiv.org/abs/2505.13719
  3. [3]F. Alizadeh, J.-P. A. Haeberly, and M. L. Overton, Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM Journal on Optimization, 8 (1998), pp. 746–768.DOI
  4. [4]R. Angell and A. McCallum, Fast, scalable, warm-start semidefinite programming with spectral bundling and sketching, in Proceedings of the 41st International Conference on Machine Learning, vol. 235 of Proceedings of Machine Learning Research, PMLR, 2024, pp. 1579–1615.arxiv.org/abs/2312.11801
  5. [5]B. Borchers, Csdp, an ac library for semidefinite programming, Optimization methods and Software, 11 (1999), pp. 613–623.
  6. [6]D. Brosch, J. Schwinddessen, and A. Wiegele, The augmented mixing method: Computing high-accuracy primal-dual solutions to large-scale SDPs via column updates, Optimization Methods and Software, (2026).DOI
  7. [7]S. Burer and R. D. Monteiro, A projected gradient algorithm for solving the maxcut SDP relaxation, Optimization methods and Software, 15 (2001), pp. 175–200.DOI
  8. [8]———, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical programming, 95 (2003), pp. 329–357.DOI
  9. [9]———, Local minima and convergence in low-rank semidefinite programming, Mathematical programming, 103 (2005), pp. 427–444.DOI
  10. [10]M. O. C. Helmberg and F. Rendl, The spectral bundle method with second-order information, Optimization Methods and Software, 29 (2014), pp. 855–876.DOI
  11. [11]E. Candes and B. Recht, Exact matrix completion via convex optimization, Communications of the ACM, 55 (2012), pp. 111–119.
  12. [12]Q. Deng, Q. Feng, W. Gao, D. Ge, B. Jiang, Y. Jiang, J. Liu, T. Liu, C. Xue, Y. Ye, et al., An enhanced admm-based interior point method for linear and conic optimization, arXiv preprint arXiv:2209.01793, (2022).arxiv.org/abs/2209.01793
  13. [13]—, New developments of admm-based interior point methods for linear programming and conic programming, arXiv preprint arXiv:2209.01793, (2022).
  14. [14]L. Ding and B. Grimmer, Revisiting spectral bundle methods: Primal-dual (sub)linear convergence rates, SIAM Journal on Optimization, 33 (2023), pp. 1305–1332.arxiv.org/abs/2008.07067
  15. [15]L. Ding, H. Lu, and J. Yang, New understandings and computation on augmented lagrangian methods for low-rank semidefinite programming, arXiv preprint arXiv:2505.15775, (2025).arxiv.org/abs/2505.15775
  16. [16]L. Ding, A. Yurtsever, V. Cevher, J. A. Tropp, and M. Udell, An optimal-storage approach to semidefinite programming using approximate complementarity, SIAM Journal on Optimization, 31 (2021), pp. 2695–2725.arxiv.org/abs/1902.03373
  17. [17]J. C. Duchi, O. Hinder, A. Naber, and Y. Ye, Conic descent and its application to memory-efficient optimization over positive semidefinite matrices, in Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 8308–8317.
  18. [18]M. A. Erdogdu, A. Ozd aglar, P. A. Parrilo, and N. D. Vanli, Convergence rate of block-coordinate maximization burer–monteiro method for solving large sdps, Mathematical Programming, 195 (2022), pp. 243–281.arxiv.org/abs/1807.04428
  19. [19]M. Fazel, Matrix rank minimization with applications, PhD thesis, PhD thesis, Stanford University, 2002.
  20. [20]M. Garstka, M. Cannon, and P. Goulart, Cosmo: A conic operator splitting method for convex conic problems, Journal of Optimization Theory and Applications, 190 (2021), pp. 779–810.DOI
  21. [21]M. Grötschel, L. Lovász, and A. Schrijver, Polynomial algorithms for perfect graphs, in North-Holland mathematics studies, vol. 88, Elsevier, 1984, pp. 325–356.DOI
  22. [22]Q. Han, C. Li, Z. Lin, C. Chen, Q. Deng, D. Ge, H. Liu, and Y. Ye, A low-rank admm splitting approach for semidefinite programming, INFORMS Journal on Computing, (2025).arxiv.org/abs/2403.09133
  23. [23]Q. Han, Z. Lin, H. Liu, C. Chen, Q. Deng, D. Ge, and Y. Ye, Accelerating low-rank factorization-based semidefinite programming algorithms on gpu, arXiv preprint arXiv:2407.15049, (2024).arxiv.org/abs/2407.15049
  24. [24]C. Helmberg and K. Kiwiel, A spectral bundle method with bounds, Math. Program., 93 (2002), pp. 173–194.DOI
  25. [25]C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming, SIAM Journal on Optimization, 10 (2000), pp. 673–696.DOI
  26. [26]J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis, Grundlehren Text Editions, Springer, Berlin, Heidelberg, 1 ed., 2001.
  27. [27]S. Homer and M. Peinado, Design and performance of parallel and distributed approximation algorithms for maxcut, Journal of Parallel and Distributed Computing, 46 (1997), pp. 48–61.DOI
  28. [28]D. Hou, T. Tang, and K.-C. Toh, A low-rank augmented Lagrangian method for polyhedral-SDP and moment-SOS relaxations of polynomial optimization, Mathematical Programming, (2026).arxiv.org/abs/2512.06359
  29. [29]—, RiNNAL+: A riemannian ALM solver for SDP-RLT relaxations of mixed-binary quadratic programs, Mathematical Programming Computation, 18 (2026), pp. 679–735.arxiv.org/abs/2507.13776
  30. [30]W. Huang, K. A. Gallivan, and X. Zhang, Solving PhaseLift by low-rank Riemannian optimization methods for complex semidefinite constraints, SIAM Journal on Scientific Computing, 39 (2017), pp. B840–B859.DOI
  31. [31]Y. Huang and D. F. Gleich, Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+, 2024, Version 3, revised 1 June 2026.arxiv.org/abs/2406.10407
  32. [32]M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre, Low-rank optimization on the cone of positive semidefinite matrices, SIAM Journal on Optimization, 20 (2010), pp. 2327–2351.DOI
  33. [33]S. Kang, X. Jiang, and H. Yang, Local linear convergence of the alternating direction method of multipliers for semidefinite programming under strict complementarity, arXiv preprint arXiv:2503.20142, (2025).arxiv.org/abs/2503.20142
  34. [34]B. Kulis, A. C. Surendran, and J. C. Platt, Fast low-rank semidefinite programming for embedding and clustering, in Artificial Intelligence and Statistics, PMLR, 2007, pp. 235–242.
  35. [35]S. Laue, A hybrid algorithm for convex semidefinite optimization, in Proceedings of the 29th International Conference on Machine Learning, 2012, pp. 1083–1090.arxiv.org/abs/1206.4608
  36. [36]B. Li and G. B. Giannakis, Conic descent redux for memory-efficient optimization, in 2023 57th Asilomar Conference on Signals, Systems, and Computers, IEEE, 2023, pp. 594–601.arxiv.org/abs/2308.07343
  37. [37]H. Li, H. Liu, D. Ge, and Y. Ye, A curvature-aware rank-adaptive distributed augmented-lagrangian solver for large-scale sdps, 2026.arxiv.org/abs/2607.17933
  38. [38]Q. Lin and L. Xiao, An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization, Comput. Optim. Appl., 60 (2015), pp. 633–674.DOI
  39. [39]L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information theory, 25 (1979), pp. 1–7.DOI
  40. [40]R. Madani, A. Kalbat, and J. Lavaei, Admm for sparse semidefinite programming with applications to optimal power flow problem, in 2015 54th IEEE Conference on Decision and Control (CDC), IEEE, 2015, pp. 5932–5939.
  41. [41]A. Majumdar, G. Hall, and A. A. Ahmadi, Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics, Annual Review of Control, Robotics, and Autonomous Systems, 3 (2020), pp. 331–360.DOI
  42. [42]S. Mei, T. Misiakiewicz, A. Montanari, and R. I. Oliveira, Solving SDPs for synchronization and MaxCut problems via the G rothendieck inequality, in Conference on learning theory, PMLR, 2017, pp. 1476–1515.arxiv.org/abs/1703.08729
  43. [43]H. D. Mittelmann, An independent benchmarking of sdp and socp solvers, Mathematical Programming, 95 (2003), pp. 407–430.DOI
  44. [44]R. D. C. Monteiro, A. Sujanani, and D. Cifuentes, A low-rank augmented lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach, Mathematical Programming, (2026). Published online 29 April 2026.arxiv.org/abs/2401.12490
  45. [45]R. D. C. Monteiro, Primal–dual path-following algorithms for semidefinite programming, SIAM Journal on Optimization, 7 (1997), pp. 663–678.DOI
  46. [46]F. Oustry, A second-order bundle method to minimize the maximum eigenvalue function, Math. Program., 89 (2000), pp. 1–33.DOI
  47. [47]B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, Conic optimization via operator splitting and homogeneous self-dual embedding, Journal of Optimization Theory and Applications, 169 (2016), pp. 1042–1068.arxiv.org/abs/1312.3039
  48. [48]———, Conic optimization via operator splitting and homogeneous self-dual embedding, Journal of Optimization Theory and Applications, 169 (2016), pp. 1042–1068.arxiv.org/abs/1312.3039
  49. [49]R. T. Rockafellar, Convex Analysis, vol. 28 of Princeton Mathematical Series, Princeton University Press, Princeton, NJ, 1970.
  50. [50]D. M. Rosen, Scalable low-rank semidefinite programming for certifiably correct machine perception, in Algorithmic Foundations of Robotics XIV: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics 14, Springer, 2021, pp. 551–566.DOI
  51. [51]D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard, SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group, The International Journal of Robotics Research, 38 (2019), pp. 95–125.
  52. [52]N. Shinde, V. Narayanan, and J. Saunderson, Memory-efficient structured convex optimization via extreme point sampling, SIAM Journal on Mathematics of Data Science, 3 (2021), pp. 787–814.arxiv.org/abs/2006.10945
  53. [53]A. Sujanani and R. D. C. Monteiro, An adaptive superfast inexact proximal augmented lagrangian method for smooth nonconvex composite optimization problems, Journal of Scientific Computing, 97 (2023), p. 34.arxiv.org/abs/2207.11905
  54. [54]———, Efficient parameter-free restarted accelerated gradient methods for convex and strongly convex optimization, Journal of Optimization Theory and Applications, 206 (2025), p. 52.arxiv.org/abs/2410.04248
  55. [55]T. Tang and K.-C. Toh, A feasible method for general convex low-rank sdp problems, SIAM Journal on Optimization, 34 (2024), pp. 2169–2200.arxiv.org/abs/2312.07908
  56. [56]———, A feasible method for solving an sdp relaxation of the quadratic knapsack problem, Mathematics of Operations Research, 49 (2024), pp. 19–39.arxiv.org/abs/2303.06599
  57. [57]———, Solving graph equipartition sdps on an algebraic variety, Mathematical programming, 204 (2024), pp. 299–347.arxiv.org/abs/2112.04256
  58. [58]———, A preconditioned augmented Lagrangian method for solving semidefinite programming problems, 2026.arxiv.org/abs/2605.17089
  59. [59]M. J. Todd, K. C. Toh, and R. H. Tütüncü, On the nesterov–todd direction in semidefinite programming, SIAM Journal on Optimization, 8 (1998), pp. 769–796.DOI
  60. [60]J. Wang and L. Hu, Solving Low-Rank Semidefinite Programs via Manifold Optimization, Available on arXiv:2303.01722, (2023).arxiv.org/abs/2303.01722
  61. [61]J. Wang, L. Hu, and B. Xia, A dual riemannian admm algorithm for low-rank sdps with unit diagonal, arXiv preprint arXiv:2512.04406, (2025).arxiv.org/abs/2512.04406
  62. [62]Y. Wang, K. Deng, H. Liu, and Z. Wen, A decomposition augmented lagrangian method for low-rank semidefinite programming, SIAM Journal on Optimization, 33 (2023), pp. 1361–1390.arxiv.org/abs/2109.11707
  63. [63]Z. Wen, D. Goldfarb, and W. Yin, Alternating direction augmented lagrangian methods for semidefinite programming, Mathematical Programming Computation, 2 (2010), pp. 203–230.DOI
  64. [64]M. Yamashita, K. Fujisawa, M. Fukuda, K. Kobayashi, K. Nakata, and M. Nakata, Latest Developments in the SDP Family for Solving Large-Scale SDPs, Springer US, New York, NY, 2012, pp. 687–713.
  65. [65]L. Yang, D. Sun, and K.-C. Toh, SDPNAL+: A majorized semismooth Newton-cg augmented lagrangian method for semidefinite programming with nonnegative constraints, Mathematical Programming Computation, 7 (2015), pp. 331–366.arxiv.org/abs/1406.0942
  66. [66]A. Yurtsever, O. Fercoq, and V. Cevher, A conditional-gradient-based augmented lagrangian framework, in International Conference on Machine Learning, PMLR, 2019, pp. 7272–7281.arxiv.org/abs/1901.04013
  67. [67]A. Yurtsever, Y.-P. Hsieh, and V. Cevher, Scalable convex methods for phase retrieval, in 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), IEEE, 2015, pp. 381–384.DOI
  68. [68]A. Yurtsever, J. A. Tropp, O. Fercoq, M. Udell, and V. Cevher, Scalable semidefinite programming, SIAM Journal on Mathematics of Data Science, 3 (2021), pp. 171–200.
  69. [69]X.-Y. Zhao, D. Sun, and K.-C. Toh, A newton-cg augmented lagrangian method for semidefinite programming, SIAM Journal on Optimization, 20 (2010), pp. 1737–1765.
  70. [70]Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. Goulart, and A. Wynn, Fast admm for semidefinite programs with chordal sparsity, in 2017 American Control Conference (ACC), IEEE, 2017, pp. 3335–3340.DOI

Paper details

vlnc:W_9t9xn8sv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents