Pith. sign in

REVIEW 1 major objections 5 minor 67 references

Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-{\L}ojasiewicz Inequality

T0 review · 1 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read The greedy Frank-Wolfe algorithm provably converges to a critical point when the objective satisfies the Kurdyka-Łojasiewicz inequality.

desk verdict The KL-based last-iterate convergence proof for greedy FW is sound; the paper's real warts are a missing factor 1/2 in a constant and a mismatch between the theory and the Max-Cut pseudocode. read the letter →

arxiv 2505.00221 v1 pith:W5X35ODI submitted 2025-04-30 math.OC

Fatih Selim Aktas , Christian Kroer This is my paper · ORCID
classification math.OC MSC 90C2690C3049M3765K05
keywords Frank-WolfealgorithmconditionalgradientconvexmaximizationKurdyka-Łojasiewiczinequalitylast-iterateconvergencesparsePCAreweightedl1minimizationMax-CutSDP
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

The paper studies the greedy Frank-Wolfe algorithm with a unit step size, applied to maximizing a smooth and strongly convex function over a compact feasible set that is not assumed convex. The central claim is that, once the objective-plus-indicator function $F=-g+I_X$ satisfies the Kurdyka-Łojasiewicz (KL) inequality, the full iterate sequence converges to a critical point of $F$, with finite, linear, or sublinear rates depending on the KL exponent. If correct, this is the first last-iterate convergence guarantee for this linear-oracle algorithm beyond polyhedral feasible sets. The result is then applied to prove convergence of a sparse PCA method, to construct a reweighted $\ell_1$ compressed-sensing algorithm whose guarantees survive noisy constraints, and to design a parallel GFW algorithm for the Max-Cut semidefinite relaxation.

What carries the argument

The mechanism is the reformulation $F=-g+I_X$ together with the gradient-like descent sequence verification. Strong convexity gives sufficient decrease $f(x_k)-f(x_{k+1})\ge (\alpha/2)\|x_{k+1}-x_k\|^2$; smoothness lets $w_{k+1}=\nabla f(x_{k+1})-\nabla f(x_k)$ serve as a subgradient of $F$ at $x_{k+1}$ with $\|w_{k+1}\|\le L\|x_{k+1}-x_k\|$; and continuity supplies the limit-point energy condition. The KL property—a concave desingularizing function $\varphi$ controlling $F(x)-F(x^*)$ by $\mathrm{dist}(0,\partial F(x))$—then forces finite length of the iterates and convergence to a critical point.

What would settle it

Take $g(x,y)=x^2+y^2$ and $X=\{(t,|t|):t\in[-1,1]\}$, a compact semialgebraic set. Starting from $(0.5,0.5)$, GFW jumps to $(1,1)$ and repeats it, but $-\nabla g(1,1)=(-2,-2)$ is not in the normal cone of $X$ at $(1,1)$, so $(1,1)\notin\mathrm{crit}\,F$; this instance satisfies all stated assumptions, including KL.

Watch

Extended reading notes

Core claim

The paper's strongest assertion is Theorem 3.2: under smoothness and strong convexity of $g$, compactness of $X$, and the KL property of $F=-g+I_X$, the sequence $x_{k+1}\in\arg\max\{\nabla g(x_k)^T x:x\in X\}$ converges to some $x^*\in\mathrm{crit}\,F$. The proof shows the GFW sequence is a gradient-like descent sequence for $F$, so standard KL theory applies; Theorem 3.3 attaches rates from the desingularizing exponent $\theta$. Replacing $X$ by its convex hull only sharpens the limit to an extreme point, and the stationarity condition becomes a normal-cone condition for $\mathrm{conv}(X)$.

Load-bearing premise

The proof relies on the chosen maximizer of the linear step counting as a stationary candidate through the normal cone of the feasible set; that is automatic for convex or smooth feasible sets, but not for every compact set.

Editorial extensions

If this is right

  • The sparse PCA GFW algorithm converges in the last iterate under the sphere-plus-cardinality constraint, where previously only subsequential stationarity was known.
  • The proposed RWL1 Split reweighted $\ell_1$ algorithm keeps a convergence guarantee even when the linear equality constraint is replaced by a noisy norm-ball constraint, a case where polyhedral finite convergence fails.
  • The Max-Cut SDP algorithm updates all rows of $B$ in parallel and still converges to a first-order stationary point; the reported experiments show it overtakes block-coordinate and Riemannian-gradient methods in wall-clock time.
  • When the KL desingularizing exponent $\theta$ is known, the GFW convergence rate is finite for $\theta=0$, linear for $\theta\le 1/2$, and sublinear for $\theta>1/2$.

Reading between the lines

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

  • An implicit requirement in Lemma 3.1 is that the maximizer $x_{k+1}$ of the linear subproblem satisfy the normal-cone optimality condition for $F$; this holds for prox-regular, convex, or smooth-manifold feasible sets, and a repaired theorem would need to state such regularity explicitly.
  • The $\sigma I$ shift used to force strong convexity in the sparse PCA and Max-Cut applications is a general modeling trick: any smooth convex maximization over a compact semialgebraic set can be shifted to satisfy Assumption 1.1, so the same KL convergence template should extend to other low-rank and sparsity-constrained models.
  • A natural testable extension replaces the exact linear oracle by an approximate one: if the linear maximization is solved only to tolerance $\epsilon_k$, the gradient-like descent inequalities should hold with a slack term, and KL arguments should yield convergence whenever $\sum\epsilon_k<\infty$.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. This paper studies the greedy Frank-Wolfe (GFW) algorithm with unit step size for maximizing a smooth, strongly convex function g over a compact set X that is not assumed convex. The authors reformulate the problem as the minimization of F = -g + I_X and prove that the GFW iterates form a gradient-like descent sequence in the sense of Bolte et al. [30]. Their main result (Theorem 3.2) states that if F satisfies the Kurdyka-Łojasiewicz property, then the whole sequence converges to a critical point of F; Theorem 3.3 gives convergence rates depending on the desingularizing exponent. The paper also contributes three applications: a split reweighted ℓ1 minimization algorithm for compressed sensing with a convergence guarantee that survives noisy constraints, a sparse PCA convergence result, and a parallel GFW algorithm for the Max-Cut SDP relaxation, accompanied by numerical experiments on Gaussian data.

Significance. If correct, the main theorem provides the first last-iterate convergence guarantee for this unit-step greedy Frank-Wolfe variant outside the polyhedral setting, which is a meaningful advance for the algorithm and for the applications considered. The proof is a clean verification of the three conditions of the gradient-like descent framework; the subgradient lower bound (C2) is verified directly from the subproblem optimality and smoothness, and the KL machinery is imported from existing nonconvex optimization theory. The paper is careful to acknowledge the limitations of the rates (unknown constants) and to note which numerical experiments fall outside the assumptions. The applications are relevant, and the numerical studies support the theoretical results without overclaiming. The central objection raised in the review process about the validity of the optimality condition in Lemma 3.1 does not survive scrutiny: the limiting normal cone is the appropriate object for arbitrary closed sets, and the condition is valid.

major comments (1)
  1. [§3, Lemma 3.1, Eq. (26)] A natural concern is that Eq. (26) uses an optimality condition for a global maximizer over a nonconvex set. This concern does not hold: for any closed set X, if x_{k+1} is a global minimizer of y ↦ ∇f(x_k)^T y on X, then -∇f(x_k) lies in the regular normal cone \hat N_X(x_{k+1}), and since \hat N_X(x) ⊆ N_X(x) = ∂I_X(x), the inclusion 0 ∈ ∇f(x_k) + ∂I_X(x_{k+1}) follows. Equivalently, Fermat's rule applied to the lsc function ∇f(x_k)^T(·) + I_X(·) at its global minimizer gives the same condition. The V-shaped counterexample proposed in the review process does not produce a non-critical limit: for g(x,y)=x^2+y^2 on X = {(t,|t|): |t|≤1}, the limit (1,1) satisfies ∇g(1,1)=(2,2) ∈ N_X(1,1) = {w : w_1+w_2 ≥ 0}, so 0 ∈ ∂F(1,1). The proof of Lemma 3.1 is sound.
minor comments (5)
  1. [§3, Lemma 3.1] In verifying (C1), the inequality (24) carries a factor 1/2 from strong convexity, so the correct constant is ρ1 = α/2, not ρ1 = α as written. The claim remains true with this correction, but the text should be made consistent.
  2. [§2.1, Proposition 2.2] The statement that the GFW algorithm applied to X and to conv(X) 'produces identical iterates' is not justified under arbitrary tie-breaking: when the linear subproblem has multiple maxima, a chosen maximizer in conv(X) may not belong to X, and the subsequent iterates can diverge. Please rephrase to assert existence of a selection of extreme-point maximizers for which the iterates coincide, or restrict the claim to cases where the linearized subproblem has a unique maximizer.
  3. [§2.2, Theorem 2.4, Eq. (11)] In the sum in (11), the index k appears inside the summand; it should be i. Also, the phrase 'Every limit point of the sequence converges to a stationary point' should be 'Every limit point of the sequence is a stationary point.'
  4. [§4.1] The bounded reformulation of the RWL1 Split model uses an unspecified constant M. It would help the reader to state explicitly that a sufficiently large M exists because the objective value is monotonically nondecreasing and its superlevel sets on X are bounded, and to note that the linear subproblem over the original unbounded polyhedron has a finite optimum since the weights in (38) are positive.
  5. [§4.3, Algorithm 3] Algorithm 3 computes B_{k+1} by normalizing each row of G_{k+1}; if a row of G_{k+1} is zero, the update is undefined. A short remark on this degenerate case would make the algorithm well-posed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence proof imports the KL/gradient-like-descent theorems from external references and verifies the three descent conditions independently.

full rationale

The paper's central result, Theorem 3.2, is obtained by verifying that the GFW sequence is a gradient-like descent sequence for F = -g + I_X (Definition 2.5) and then invoking Theorem 2.7 from Bolte et al. [30], an external reference with no author overlap. The verification in Lemma 3.1 is independent: condition (C1) follows from strong convexity, condition (C2) from the first-order optimality condition of the linear subproblem together with smoothness, and condition (C3) from continuity and compactness. No parameter is fitted to the target conclusion, and no quantity predicted by the convergence theorems is already an input to Assumption 1.1. The self-citations that appear, [7] and [29], are used for application context and literature background, not as load-bearing support for the convergence machinery. The convergence rates in Theorem 3.3 are inherited from the external KL theory rather than newly derived, but importing an externally established theorem is not circular. The numerical experiments compare algorithms and explicitly acknowledge when chosen sigma values do not guarantee strong convexity, so no fitted value is relabeled as a prediction. The only substantive objection in the reader's take concerns whether Eq. (26) is valid for arbitrary compact sets, which is a correctness question, not a circularity question; even if that step were flawed, it would not make the derivation circular. No step can be identified, under the required quote-and-reduction standard, where the paper's conclusion is equivalent by construction to its inputs or where a load-bearing premise is justified only by the authors' own prior work.

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

The central claim rests on strong convexity, smoothness, compactness, and the KL property, which are standard assumptions. The hidden regularity of X (needed for the normal cone optimality condition) is not stated and is the main fragility. The free parameters are user-chosen algorithmic constants, not fitted to data, but the Max-Cut sigma choice in experiments is outside the theoretically justified regime.

free parameters (4)
  • sigma (Max-Cut experiments) = 25e-4
    Chosen by hand in the experiments; does not satisfy the theoretical condition sigma > -lambda_min(A) that guarantees strong convexity, so the convergence guarantee is not active for the best-performing reported choice.
  • sigma (SPCA shift) = positive constant, unspecified
    Added to the data matrix to ensure strong convexity; the value does not affect the optimum but must be positive, and no specific choice rule is given.
  • epsilon (RWL1 Split) = 0.1
    Fixed in the numerical experiments as the regularization parameter in log(epsilon + x); its choice is standard from Candes et al. (2008) but is still a user-selected constant.
  • M (RWL1 Split bounding constant) = not explicit; sufficiently large
    The paper argues a non-binding bound ||x|| <= M can be added because iterates stay bounded, but M is never computed and the algorithm as stated does not include it in the subproblem.
assumptions (5)
  • domain assumption g is strongly convex and smooth with L-Lipschitz gradient (Assumption 1.1).
    The blanket assumption of the paper, used throughout Lemmas 2.3, 3.1 and Theorem 2.4.
  • domain assumption X is compact.
    Ensures that the FW gap is well-defined, that every subsequence has a convergent subsequence, and that the objective is bounded above.
  • domain assumption F = -g + I_X satisfies the KL property at the limit point.
    Explicitly assumed in Theorem 3.2 and verified in applications via semialgebraicity or definability.
  • ad hoc to paper The optimality condition 0 in ∇f(x_k) + ∂I_X(x_{k+1}) holds at each GFW iterate.
    Used in Lemma 3.1 equation (26). This is not true for arbitrary compact sets and is the load-bearing hidden regularity assumption; it requires X to be regular (convex, prox-regular, or a smooth manifold union).
  • domain assumption In applications, F is semialgebraic or definable in the log-exp structure, so the desingularizing function has the form phi(s) = c s^{1-theta}.
    Used to apply the global convergence and rate theorems. The paper cites Bolte et al. for these facts.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-{\L}ojasiewicz Inequality." pith.science (2026). https://pith.science/paper/W5X35ODI

@misc{pith2026250500221,
  author       = {Pith},
  title        = {Pith review of: Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-\Lojasiewicz Inequality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W5X35ODI}},
  note         = {Machine review of arXiv:2505.00221}
}
abstract

We study the convergence properties of the 'greedy' Frank-Wolfe algorithm with a unit step size, for a convex maximization problem over a compact set. We assume the function satisfies smoothness and strong convexity. These assumptions together with the Kurdyka-{\L}ojasiewicz (KL) property, allow us to derive global asymptotic convergence for the sequence generated by the algorithm. Furthermore, we also derive a convergence rate that depends on the geometric properties of the problem. To illustrate the implications of the convergence result obtained, we prove a new convergence result for a sparse principal component analysis algorithm, propose a convergent reweighted $\ell_1$ minimization algorithm for compressed sensing, and design a new algorithm for the semidefinite relaxation of the Max-Cut problem.

Figures

Figures reproduced from arXiv: 2505.00221 by the authors.

Figure 1
Figure 1. Illustration of a single iteration of the GFW algorithm on two nonconvex [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Empirical comparison of the RWL1, RWL1 Prox, and RWL1 Split [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. Empirical comparison of the RWL1, RWL1 Prox, and RWL1 Split [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Empirical comparison of various algorithms for solving the Max-Cut [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]
Figure 5
Figure 5. Figure 5: Empirical performance of the GFW algorithm for varying shifting [PITH_FULL_IMAGE:figures/full_fig_p023_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

67 extracted references · 60 canonical work pages

  1. [30]

    First order methods beyond convexity and lipschitz gradient continuity with applications to quadratic inverse problems,

    J. Bolte, S. Sabach, M. Teboulle, and Y. Vaisbourd, “First order methods beyond convexity and lipschitz gradient continuity with applications to quadratic inverse problems,”SIAM Journal on Optimization, vol. 28, no. 3, pp. 2131–2151, 2018

    work page 2018

  2. [1]

    Global maximization of a convex function with linear inequality constraints,

    P. B. Zwart, “Global maximization of a convex function with linear inequality constraints,” Operations Research, vol. 22, no. 3, pp. 602–609, 1974

    work page 1974

  3. [2]

    Machine learning via polyhedral concave minimization,

    O. L. Mangasarian, “Machine learning via polyhedral concave minimization,” in Applied Mathematics and Parallel Computing: Festschrift for Klaus Ritter, pp. 175–188, Springer, 1996

    work page 1996

  4. [3]

    A direct formu- lation for sparse pca using semidefinite programming,

    A. d’Aspremont, L. Ghaoui, M. Jordan, and G. Lanckriet, “A direct formu- lation for sparse pca using semidefinite programming,”Advances in neural information processing systems, vol. 17, 2004

    work page 2004

  5. [4]

    Nonnegative sparse pca,

    R. Zass and A. Shashua, “Nonnegative sparse pca,”Advances in neural information processing systems, vol. 19, 2006

    work page 2006

  6. [5]

    Enhancing sparsity by reweightedℓ1 minimization,

    E. J. Candes, M. B. Wakin, and S. P. Boyd, “Enhancing sparsity by reweightedℓ1 minimization,” Journal of Fourier analysis and applications, vol. 14, pp. 877–905, 2008. 23

    work page 2008

  7. [6]

    Reweighted nuclear norm minimization with application to system identification,

    K. Mohan and M. Fazel, “Reweighted nuclear norm minimization with application to system identification,” inProceedings of the 2010 American Control Conference, pp. 2953–2959, IEEE, 2010

    work page 2010

  8. [7]

    Pca sparsified,

    F. S. Aktaş and M. Ç. Pinar, “Pca sparsified,”SIAM Journal on Optimiza- tion, vol. 33, no. 3, pp. 2089–2117, 2023

    work page 2023

Show all 67 references
  1. [8]

    Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite program- ming,

    M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite program- ming,” Journal of the ACM (JACM), vol. 42, no. 6, pp. 1115–1145, 1995

    1995

  2. [9]

    Concave minimization: theory, applications and algorithms,

    H. P. Benson, “Concave minimization: theory, applications and algorithms,” in Handbook of global optimization, pp. 43–148, Springer, 1995

    1995

  3. [10]

    Convex maximiza- tion via adjustable robust optimization,

    A. Selvi, A. Ben-Tal, R. Brekelmans, and D. den Hertog, “Convex maximiza- tion via adjustable robust optimization,”INFORMS Journal on Computing, vol. 34, no. 4, pp. 2091–2105, 2022

    2022

  4. [11]

    An algorithm for maximizing a convex function based on its minimum,

    A. Ben-Tal and E. Roos, “An algorithm for maximizing a convex function based on its minimum,”INFORMS journal on computing, vol. 34, no. 6, pp. 3200–3214, 2022

    2022

  5. [12]

    Variations and extension of the convex–concave procedure,

    T. Lipp and S. Boyd, “Variations and extension of the convex–concave procedure,” Optimization and Engineering, vol. 17, pp. 263–287, 2016

    2016

  6. [13]

    Cccp is frank-wolfe in disguise,

    A. Yurtsever and S. Sra, “Cccp is frank-wolfe in disguise,”Advances in Neural Information Processing Systems, vol. 35, pp. 35352–35364, 2022

    2022

  7. [14]

    Checking local optimality in constrained quadratic programming is np-hard,

    P. M. Pardalos and G. Schnitger, “Checking local optimality in constrained quadratic programming is np-hard,”Operations Research Letters, vol. 7, no. 1, pp. 33–35, 1988

    1988

  8. [15]

    Methods for global concave minimization: A bibliographic survey,

    P. M. Pardalos and J. B. Rosen, “Methods for global concave minimization: A bibliographic survey,”Siam Review, vol. 28, no. 3, pp. 367–379, 1986

    1986

  9. [16]

    Audet, P

    C. Audet, P. Hansen, and G. Savard,Essays and surveys in global optimiza- tion, vol. 7. Springer Science & Business Media, 2005

    2005

  10. [17]

    One algorithm for branch and bound method for solving concave optimization problem,

    A. Andrianova, A. Korepanova, and I. Halilova, “One algorithm for branch and bound method for solving concave optimization problem,” inIOP Conference Series: Materials Science and Engineering, vol. 158, p. 012005, IOP Publishing, 2016

    2016

  11. [18]

    Conditional gradient algorithmsfor rank-one matrix approximations with a sparsity constraint,

    R. Luss and M. Teboulle, “Conditional gradient algorithmsfor rank-one matrix approximations with a sparsity constraint,”siam REVIEW, vol. 55, no. 1, pp. 65–98, 2013

    2013

  12. [19]

    Nonlinear programming,

    D. P. Bertsekas, “Nonlinear programming,” Journal of the Operational Research Society, vol. 48, no. 3, pp. 334–334, 1997. 24

    1997

  13. [20]

    An algorithm for quadratic programming,

    M. Frank, P. Wolfe,et al., “An algorithm for quadratic programming,”Naval research logistics quarterly, vol. 3, no. 1-2, pp. 95–110, 1956

    1956

  14. [21]

    Constrained minimization methods,

    E. S. Levitin and B. T. Polyak, “Constrained minimization methods,”USSR Computational mathematics and mathematical physics, vol. 6, no. 5, pp. 1–50, 1966

    1966

  15. [22]

    Convergence rates for conditional gradient sequences generated by implicit step length rules,

    J. C. Dunn, “Convergence rates for conditional gradient sequences generated by implicit step length rules,”SIAM Journal on Control and Optimization, vol. 18, no. 5, pp. 473–487, 1980

    1980

  16. [23]

    Projection-free online learning,

    E. Hazan and S. Kale, “Projection-free online learning,”arXiv preprint arXiv:1206.4657, 2012

    2012 arXiv

  17. [24]

    Revisiting frank-wolfe: Projection-free sparse convex optimiza- tion,

    M. Jaggi, “Revisiting frank-wolfe: Projection-free sparse convex optimiza- tion,” inInternational conference on machine learning, pp. 427–435, PMLR, 2013

    2013

  18. [25]

    A conditional gradient framework for composite convex minimization with applications to semidefinite programming,

    A. Yurtsever, O. Fercoq, F. Locatello, and V. Cevher, “A conditional gradient framework for composite convex minimization with applications to semidefinite programming,” in International Conference on Machine Learning, pp. 5727–5736, PMLR, 2018

    2018

  19. [26]

    A conditional-gradient-based augmented lagrangian framework,

    A. Yurtsever, O. Fercoq, and V. Cevher, “A conditional-gradient-based augmented lagrangian framework,” inInternational Conference on Machine Learning, pp. 7272–7281, PMLR, 2019

    2019

  20. [27]

    Kerdreux,Accelerating conditional gradient methods

    T. Kerdreux,Accelerating conditional gradient methods. PhD thesis, Uni- versité Paris sciences et lettres, 2020

    2020

  21. [28]

    Generalized power method for sparse principal component analysis,

    M. Journée, Y. Nesterov, P. Richtárik, and R. Sepulchre, “Generalized power method for sparse principal component analysis,”Journal of Machine Learning Research, vol. 11, p. 517–553, Mar. 2010

    2010

  22. [29]

    Competitive equilibrium for chores: from dual eisenberg-gale to a fast, greedy, lp-based algorithm,

    B. R. Chaudhury, C. Kroer, R. Mehta, and T. Nan, “Competitive equilibrium for chores: from dual eisenberg-gale to a fast, greedy, lp-based algorithm,” 2024

    2024

  23. [31]

    Novel proximal gradient methods for non- negative matrix factorization with sparsity constraints,

    M. Teboulle and Y. Vaisbourd, “Novel proximal gradient methods for non- negative matrix factorization with sparsity constraints,”SIAM Journal on Imaging Sciences, vol. 13, no. 1, pp. 381–421, 2020

    2020

  24. [32]

    Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-łojasiewicz inequality,

    H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, “Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-łojasiewicz inequality,”Mathematics of operations research, vol. 35, no. 2, pp. 438–457, 2010. 25

    2010

  25. [33]

    Proximal alternating linearized minimization for nonconvex and nonsmooth problems,

    J. Bolte, S. Sabach, and M. Teboulle, “Proximal alternating linearized minimization for nonconvex and nonsmooth problems,”Mathematical Pro- gramming, vol. 146, no. 1, pp. 459–494, 2014

    2014

  26. [34]

    Convergence rate of frank-wolfe for non-convex objec- tives,

    S. Lacoste-Julien, “Convergence rate of frank-wolfe for non-convex objec- tives,” arXiv preprint arXiv:1607.00345, 2016

    2016 arXiv

  27. [35]

    Sketchy decisions: Convex low-rank matrix optimization with optimal storage,

    A. Yurtsever, M. Udell, J. Tropp, and V. Cevher, “Sketchy decisions: Convex low-rank matrix optimization with optimal storage,” inArtificial intelligence and statistics, pp. 1188–1196, PMLR, 2017

    2017

  28. [36]

    R. T. Rockafellar,Convex Analysis. Princeton University Press, 1970

    1970

  29. [37]

    Conic optimization-based algorithms for nonnegative matrix factorization,

    V. Leplat, Y. Nesterov, N. Gillis, and F. Glineur, “Conic optimization-based algorithms for nonnegative matrix factorization,”Optimization Methods and Software, vol. 38, no. 4, pp. 837–859, 2023

    2023

  30. [38]

    Low-rank optimization on the cone of positive semidefinite matrices,

    M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre, “Low-rank optimization on the cone of positive semidefinite matrices,”SIAM Journal on Optimiza- tion, vol. 20, no. 5, pp. 2327–2351, 2010

    2010

  31. [39]

    R. T. Rockafellar and R. J.-B. Wets,Variational analysis, vol. 317. Springer Science & Business Media, 2009

    2009

  32. [40]

    On the convergence of the proximal algorithm for nonsmooth functions involving analytic features,

    H. Attouch and J. Bolte, “On the convergence of the proximal algorithm for nonsmooth functions involving analytic features,”Mathematical Program- ming, vol. 116, pp. 5–16, 2009

    2009

  33. [41]

    A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications,

    H. H. Bauschke, J. Bolte, and M. Teboulle, “A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications,” Mathematics of Operations Research, vol. 42, no. 2, pp. 330–348, 2017

    2017

  34. [42]

    The łojasiewicz inequality for nons- mooth subanalytic functions with applications to subgradient dynamical systems,

    J. Bolte, A. Daniilidis, and A. Lewis, “The łojasiewicz inequality for nons- mooth subanalytic functions with applications to subgradient dynamical systems,” SIAM Journal on Optimization, vol. 17, no. 4, pp. 1205–1223, 2007

    2007

  35. [43]

    Clarke subgradients of stratifiable functions,

    J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota, “Clarke subgradients of stratifiable functions,” SIAM Journal on Optimization, vol. 18, no. 2, pp. 556–572, 2007

    2007

  36. [44]

    Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods,

    H. Attouch, J. Bolte, and B. F. Svaiter, “Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods,”Mathematical Program- ming, vol. 137, no. 1, pp. 91–129, 2013

    2013

  37. [45]

    Compressed sensing,

    D. L. Donoho, “Compressed sensing,”IEEE Transactions on information theory, vol. 52, no. 4, pp. 1289–1306, 2006. 26

    2006

  38. [46]

    From sparse solutions of systems of equations to sparse modeling of signals and images,

    A. M. Bruckstein, D. L. Donoho, and M. Elad, “From sparse solutions of systems of equations to sparse modeling of signals and images,”SIAM review, vol. 51, no. 1, pp. 34–81, 2009

    2009

  39. [47]

    ApS,MOSEK Optimizer API for Python 11.0.12, 2025

    M. ApS,MOSEK Optimizer API for Python 11.0.12, 2025

    2025

  40. [48]

    CVXPY: A Python-embedded modeling language for convex optimization,

    S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,”Journal of Machine Learning Research, vol. 17, no. 83, pp. 1–5, 2016

    2016

  41. [49]

    Clarabel: An interior-point solver for conic programs with quadratic objectives,

    P. J. Goulart and Y. Chen, “Clarabel: An interior-point solver for conic programs with quadratic objectives,” 2024

    2024

  42. [50]

    Interior point methods in semidefinite programming with applications to combinatorial optimization,

    F. Alizadeh, “Interior point methods in semidefinite programming with applications to combinatorial optimization,”SIAM journal on Optimization, vol. 5, no. 1, pp. 13–51, 1995

    1995

  43. [51]

    Cones of matrices and set-functions and 0–1 optimization,

    L. Lovász and A. Schrijver, “Cones of matrices and set-functions and 0–1 optimization,” SIAM journal on optimization, vol. 1, no. 2, pp. 166–190, 1991

    1991

  44. [52]

    Inference in graphical models via semidefinite programming hierarchies,

    M. A. Erdogdu, Y. Deshpande, and A. Montanari, “Inference in graphical models via semidefinite programming hierarchies,” Advances in Neural Information Processing Systems, vol. 30, 2017

    2017

  45. [53]

    Onthelow-rankapproachfor semidefinite programs arising in synchronization and community detection,

    A.S.Bandeira, N.Boumal, andV.Voroninski, “Onthelow-rankapproachfor semidefinite programs arising in synchronization and community detection,” in Conference on learning theory, pp. 361–382, PMLR, 2016

    2016

  46. [54]

    Solving sdps for synchronization and maxcut problems via the grothendieck inequality,

    S. Mei, T. Misiakiewicz, A. Montanari, and R. I. Oliveira, “Solving sdps for synchronization and maxcut problems via the grothendieck inequality,” in Conference on learning theory, pp. 1476–1515, PMLR, 2017

    2017

  47. [55]

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

    S. Burer and R. D. Monteiro, “A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization,”Mathematical programming, vol. 95, no. 2, pp. 329–357, 2003

    2003

  48. [56]

    Phase transitions in semidefinite relaxations,

    A. Javanmard, A. Montanari, and F. Ricci-Tersenghi, “Phase transitions in semidefinite relaxations,” Proceedings of the National Academy of Sciences, vol. 113, no. 16, pp. E2218–E2223, 2016

    2016

  49. [57]

    The mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints,

    P.-W. Wang, W.-C. Chang, and J. Z. Kolter, “The mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints,” arXiv preprint arXiv:1706.00476, 2017

    2017 arXiv

  50. [58]

    Convergence rate of block-coordinate maximization burer–monteiro method for solving large sdps,

    M. A. Erdogdu, A. Ozdaglar, P. A. Parrilo, and N. D. Vanli, “Convergence rate of block-coordinate maximization burer–monteiro method for solving large sdps,” Mathematical Programming, vol. 195, no. 1, pp. 243–281, 2022. 27

    2022

  51. [59]

    Trust-region methods on riemannian manifolds,

    P.-A. Absil, C. G. Baker, and K. A. Gallivan, “Trust-region methods on riemannian manifolds,” Foundations of Computational Mathematics, vol. 7, pp. 303–330, 2007

    2007

  52. [60]

    Thenon-convexburer-monteiro approach works on smooth semidefinite programs,

    N.Boumal, V.Voroninski, andA.Bandeira, “Thenon-convexburer-monteiro approach works on smooth semidefinite programs,”Advances in Neural Information Processing Systems, vol. 29, 2016

    2016

  53. [61]

    R. A. Horn and C. R. Johnson,Topics in matrix analysis. Cambridge university press, 1994

    1994

  54. [62]

    Local minima and convergence in low-rank semidefinite programming,

    S. Burer and R. D. Monteiro, “Local minima and convergence in low-rank semidefinite programming,” Mathematical programming, vol. 103, no. 3, pp. 427–444, 2005

    2005

  55. [63]

    Manopt, a matlab toolbox for optimization on manifolds,

    N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre, “Manopt, a matlab toolbox for optimization on manifolds,”The Journal of Machine Learning Research, vol. 15, no. 1, pp. 1455–1459, 2014

    2014

  56. [64]

    Cupy: A numpy- compatible library for nvidia gpu calculations,

    R. Okuta, Y. Unno, D. Nishino, S. Hido, and C. Loomis, “Cupy: A numpy- compatible library for nvidia gpu calculations,” inProceedings of Workshop on Machine Learning Systems (LearningSys) in The Thirty-first Annual Conference on Neural Information Processing Systems (NIPS), 2017

    2017

  57. [65]

    JAX: composable transformations of Python+NumPy programs,

    J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang, “JAX: composable transformations of Python+NumPy programs,” 2018

    2018

  58. [66]

    Pymanopt: A python toolbox for optimization on manifolds using automatic differentiation,

    J. Townsend, N. Koep, and S. Weichwald, “Pymanopt: A python toolbox for optimization on manifolds using automatic differentiation,”Journal of Machine Learning Research, vol. 17, no. 137, p. 1–5, 2016

    2016

  59. [67]

    First and second-order necessary and sufficient optimalityconditionsforinfinite-dimensionalprogrammingproblems,

    H. Maurer and J. Zowe, “First and second-order necessary and sufficient optimalityconditionsforinfinite-dimensionalprogrammingproblems,” Math- ematical programming, vol. 16, pp. 98–110, 1979. A Convergence to a Strict Local Minimum over Polyhedra In this section, we show that ...

    1979

Pith tools

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