Pith. sign in

REVIEW 4 major objections 6 minor 37 references

Complexity Analysis of Convex Majorization Schemes for Nonconvex Constrained Optimization

T0 review · 4 major / 6 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 This paper claims that nonconvex constrained optimization — even with only Hölderian, non-Lipschitz gradients — is solvable by repeatedly solving convex surrogate subproblems, with $\epsilon$-KKT complexity…

desk verdict Useful complexity framework with a fixable gap in Theorem 1's strict-feasibility handling; the convex and second-order parts are worth the referee's time. read the letter →

arxiv 2506.08506 v2 pith:5WIWNDWV submitted 2025-06-10 math.OC

Nuozhou Wang , Junyu Zhang , Shuzhong Zhang This is my paper
classification math.OC MSC 90C2690C3065K0568Q1752A41
keywords nonconvexoptimizationconvexmajorizationgradientHölderiancontinuityiterationcomplexityKKTconditionsself-concordantbarrierDikinellipsoidcopositiveprogramming
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 tries to establish that nonconvex constrained minimization can be handled by a simple replacement rule: at every iteration, swap the objective and each constraint for a convex function that lies above it and touches it at the current point, solve the resulting convex subproblem, and repeat. Its central result is an iteration-complexity bound for this convex-majorization scheme: after $K$ steps the distance to a KKT point is $O(K^{-\kappa_{\min}/(\kappa+1)})$, so an $\epsilon$-KKT solution costs $O(\epsilon^{-(\kappa+1)/\kappa})$ convex subproblem solves when all Hölder exponents equal some $\kappa$. This matters because the framework needs neither convexity nor gradient Lipschitz continuity, only the weaker and more widely available gradient Hölderian property (gradients that vary like $\|x-y\|^\kappa$ rather than like $\|x-y\|$), and because every iterate is feasible, so the output is never an infeasible artifact of a penalty or Lagrangian scheme. The same machinery yields $O(\epsilon^{-1/\kappa})$ optimality-gap convergence for convex problems, linear convergence under strong convexity, and what the authors put forward as the first complexity guarantee for reaching a second-order stationary point under nonconvex constraints.

What carries the argument

The load-bearing object is the Hölderian convex envelope: for a function with $(L,\kappa)$-Hölderian gradient, $\tilde f(x|y) = f(y) + \langle\nabla f(y), x-y\rangle + \frac{L}{1+\kappa}\|x-y\|^{1+\kappa}$ is a convex function that majorizes $f$ and touches it at $y$, and the same envelope is built for each constraint. This object does three jobs: it makes every subproblem convex, it keeps the iterates strictly feasible, and it yields the sufficient-descent inequality $F(x_{k+1}) \le F(x_k) - \frac{L}{\kappa+1}\|x_{k+1}-x_k\|^{\kappa+1}$, whose telescoping produces the $O(K^{-1/(\kappa+1)})$ residual bound. The transfer from residual decay to KKT error is carried by the Hölder mismatch terms $2L\|d_k\|^\kappa + 2\sum_i \lambda_i L_i \|d_k\|^{\kappa_i}$, which are controlled only if Assumption 3 supplies a uniform multiplier bound. In the second-order variant the key machinery is Brickman's theorem, the statement that the set $\{(x^\top Q_1 x,\, x^\top Q_2 x): \|x\|=1\}$ is convex for $n\ge 3$, which yields an SDP representation of the Dikin-ellipsoid direction subproblem $\min d^\top Q d + \|d\|^3$ subject to $d^\top P d \le 1$; the Dikin ellipsoid, built from the self-concordant barrier of the surrogate constraints, guarantees the step stays feasible.

What would settle it

Build a two-constraint instance whose feasible region pinches to a cusp at the optimum so that the active constraint gradients become linearly dependent there; run CMMA while monitoring both the subproblem multipliers $\|\lambda_k\|_\infty$ and the KKT error $\mathrm{dist}(0, \partial L(x_{k+1},\lambda) + N_X(x_{k+1}))$. If the multipliers grow without bound as the step $\|x_{k+1}-x_k\|$ shrinks to zero, Assumption 3 fails and the KKT error should stop decaying at the promised $O(K^{-\kappa_{\min}/(\kappa+1)})$ rate, so a systematically slower exponent is a direct counterexample. A second check targets the second-order claim: because Brickman's theorem holds only for $n\ge 3$, solving the FOSO direction subproblem on a two-dimensional problem tests whether the $O(1/\epsilon_2)$ guarantee survives outside the SDP regime.

Watch

Extended reading notes

Core claim

The central claim is the convergence-rate theorem for the convex majorization framework: if the Lagrangian multipliers of every surrogate subproblem stay uniformly bounded near the solution (Assumption 3), then after $K \ge (\kappa+1)\Delta/(L\varrho^{\kappa+1})$ iterations there is an iterate whose distance to a KKT point of the original problem is $O(K^{-\kappa_{\min}/(\kappa+1)})$, and any constraint active at that iterate is violated by at most $O(K^{-1/(\kappa+1)})$. On the paper's own terms this is a proof that nonconvex, non-Lipschitz constrained problems are solvable at a provable rate through convex surrogates alone. For the convex case, the same surrogate construction yields a feasible-sequence method that reaches an $\epsilon$-optimal point in $O(\epsilon^{-1/\kappa})$ iterations, and a linear rate $O((L_B/\alpha)\log(1/\epsilon))$ when the objective is strongly convex and $\kappa=1$. The second-order extension, Algorithm FOSO, alternates first-order subproblems ($O(1/\epsilon_1)$ solves) with second-order subproblems over a Dikin ellipsoid ($O(1/\epsilon_2)$ solves), and the paper claims it as the first result of its kind for nonconvex constraints: an $(\epsilon_1,\epsilon_2)$-approximate KKT, i.e. second-order stationary, point is reached in $O(1/\epsilon_1 + 1/\epsilon_2)$ subproblem solves, with the internal cubic direction subproblem solvable exactly as a semidefinite program.

Load-bearing premise

The analysis hinges on Assumption 3: the Lagrange multipliers of every surrogate subproblem must stay bounded by one fixed constant whenever that subproblem's solution lies within a fixed distance of the current point, a fact the authors state cannot be checked before running the algorithm, and whose suggested replacements (a uniform Slater margin or a uniform LICQ condition over the whole level set) are themselves hard to verify in practice.

Editorial extensions

If this is right

  • Problems whose gradients are only Hölder continuous — such as regression with $\ell_p$ losses for $1<p<2$ — acquire a provable $\epsilon$-KKT complexity $O(\epsilon^{-(\kappa+1)/\kappa})$, with strictly feasible iterates throughout.
  • In the convex case the same scheme reaches an $\epsilon$-optimal feasible point in $O(\epsilon^{-1/\kappa})$ iterations, interpolating between the standard $O(\epsilon^{-1})$ Lipschitz rate and slower rates for rougher objectives, and becoming linear, $O((L_B/\alpha)\log(1/\epsilon))$, when the objective is strongly convex and $\kappa=1$.
  • Algorithm FOSO reaches an $(\epsilon_1,\epsilon_2)$-approximate KKT, i.e. second-order stationary, point for nonconvex objectives with nonconvex constraints in $O(1/\epsilon_1 + 1/\epsilon_2)$ subproblem solves, which the authors put forward as the first such guarantee.
  • Each convex subproblem generated by the scheme reduces to a one-dimensional dual equation — the optimal step is $p^\ast_\mu = -\alpha^\ast_\mu (a_0 + A^\top\mu)/\|a_0 + A^\top\mu\|$ with $\alpha^\ast_\mu$ the unique root of $\psi(\alpha)=\|a_0+A^\top\mu\|$ — so the per-iteration cost is a low-dimensional dual optimization, and the barrier and Dikin-ellipsoid variants cut this cost further when the

Reading between the lines

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

  • My inference: because Assumption 3 cannot be verified in advance, the theory doubles as a running diagnostic — monitor $\sup_k\|\lambda_k\|_\infty$ while CMMA runs, and the promised $O(K^{-\kappa_{\min}/(\kappa+1)})$ KKT rate should appear exactly while this running supremum stays bounded.
  • My inference: the complexity depends on the mismatch exponents of the convex envelope one can actually construct, not on the problem's intrinsic smoothness alone, so a problem endowed with a well-structured convex majorant converges provably faster than its raw gradient regularity would suggest.
  • My inference: the SDP reformulation of the second-order direction subproblem relies on Brickman's theorem and hence on $n\ge 3$; whether the $O(1/\epsilon_2)$ guarantee carries over to two-dimensional problems, where the ratio set is an ellipse rather than a spectrahedron, is a natural follow-up check.
  • My inference: the counterexample with constant steps converging to a non-stationary boundary point is a warning about the affine-scaling surrogate: the Dikin-ellipsoid variants, attractive when the number of constraints is very large, are less robust than the other variants, and the diminishing-step requirement is essential rather than a technicality.
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

4 major / 6 minor

Summary. The paper introduces a convex majorization framework (CMMA) for nonconvex constrained optimization, in which convex surrogate functions majorize the objective and the constraints and iterates are kept feasible. Under gradient-Hölderian surrogates, Slater's condition, bounded level sets, and a uniform multiplier bound (Assumption 3), Theorem 1 gives an O(K^{-κ_min/(κ+1)}) bound on the KKT error after K subproblem solves. Explicit surrogates are constructed for Hölderian, difference-of-convex, and nested composite problems. For convex problems, the paper derives an O(1/K^κ) function-value gap for Algorithm GHMA and linear convergence under strong convexity, discusses efficient dual solutions of the convex subproblems, proposes a two-tier second-order algorithm FOSO with claimed O(1/ε1 + 1/ε2) complexity, and analyzes barrier and Dikin-ellipsoid variants. Numerical experiments on copositive programming illustrate the behavior of the methods.

Significance. The proposed framework is attractive because it maintains feasible iterates and covers objective and constraint functions whose gradients are only Hölder continuous, a setting not handled by standard gradient-Lipschitz analyses. The first-order complexity estimates are derived from structural assumptions rather than fitted to data, and the convex-case analysis gives explicit constant dependence. If the proof gaps identified below are repaired, the main first-order results would be a valuable contribution to nonconvex constrained optimization under limited smoothness. The second-order result, if fully proved, would also be the first of its kind for nonconvex constraints, which makes the missing proof of Theorem 14 especially important.

major comments (4)
  1. [§2.1, Theorem 1] The proof invokes Assumption 3 at x_{k*} without establishing that x_{k*} is strictly feasible. Assumption 3 is stated only for centers x that are strictly feasible, and under Assumptions 1–2 alone Algorithm CMMA can produce boundary iterates; the strict-feasibility preservation mentioned in §3.1 relies on taking L_i strictly larger than the minimal Hölder constant, which is not assumed in Theorem 1. Concretely, for min -x subject to x^2 - 1 ≤ 0 with surrogates (4), L = 1, L_1 = 2, and x_0 = 0, CMMA returns x_1 = 1, a boundary point, and after one more step d_1 = 0, so the small-step index selected by (1) can be a non-strictly-feasible center. The theorem needs either an explicit strict-feasibility preservation assumption or an extension of Assumption 3 to all feasible centers.
  2. [§6, Theorem 14] Theorem 14 is stated without proof. No argument is given that bounds the number of first-order subproblem solves (FP_k) or second-order solves (SP_k)', nor is the stopping condition connected to the defined (ε1, ε2)-approximate KKT solution. A proof can likely be supplied from the descent inequalities (each non-terminal first-order step decreases f by at least ε1 and each non-terminal second-order step by at least ε2), but the manuscript must actually provide it, since Theorem 14 is the paper's principal claim for second-order complexity with nonconvex constraints.
  3. [§7.1, Theorem 16 and preceding display] The telescoping argument for Algorithm CEB defines Δ = F(x_0) - F(x_*), where F(x) = f(x) + r(x) - μ Σ_i ln(-c_i(x)) and x_* is an optimal solution of (P). If x_* lies on the boundary c_i(x_*) = 0 for some i, then F(x_*) = +∞, so Δ is not a finite nonnegative quantity and the bound (29) is not justified. The analysis needs to define a finite reference value for the barrier objective, for example the infimum of F over the strict interior, or explicitly assume a strictly feasible optimal solution.
  4. [Appendix, proof of Theorem 17] The proof of Theorem 17 uses LICQ in Branch 9: it states 'by LICQ, {∇c_i(x*)}_i∈A(x*) are linearly independent' and then defines the matrix inverse in (56). However, Theorem 17 and Algorithm CEAS do not state any constraint qualification. Without LICQ, equation (56) and the boundedness of λ_{k,A} are not established. The theorem should either assume LICQ explicitly or provide a separate argument for the degenerate case.
minor comments (6)
  1. [§3.1, inequality (7)] In the sum appearing in (7), the exponent should be κ_j rather than κ_i, since each term involves L_j ϱ^{κ_j} from the bound on ∥d∥^{κ_j}.
  2. [§6, definition of approximate KKT solution] The threshold for the second-order stopping criterion is inconsistent: the text and Algorithm FOSO use v((SP_k)') < -2ε2 for the descent test, while the definition of an (ε1, ε2)-approximate KKT solution requires v((SP_k)') ≥ -ε2. Please choose one convention and use it consistently.
  3. [§6, subproblem (SP_k)'] The Dikin-ellipsoid constraint is written with d^T ∇²B_k(x_k) d ≤ δ < 1 in the derivation, but Algorithm FOSO uses d^T ∇²B_k(x_k) d ≤ 1. Clarify whether the boundary is included and how this affects feasibility of the update.
  4. [§4, Theorem 11] The theorem statement says 'the iteration sequence {x_k}_{k≥0} generated by' but does not name the algorithm; it should say 'generated by GHMA'.
  5. [§6, Proposition 12] The result is called 'Brinkman's theorem' in the running text and 'Brickman's theorem' in the proposition; the standard attribution is Brickman's theorem, and the spelling should be unified.
  6. [§5, dual subproblem analysis] The claim that dual iterates remain in a 2B neighborhood of an optimal dual solution assumes the non-increasing-distance property for 'many convex optimization algorithms'; this is not true for arbitrary algorithms, so the statement should specify which algorithm is used and verify the property.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the iteration complexities are conditional theorems derived from explicit assumptions, with no fitted quantities renamed as predictions and no load-bearing self-citation chain.

full rationale

The central results are conditional complexity bounds. Theorem 1 assumes Assumptions 1, 2, and 3 and then algebraically bounds the KKT residual using the subproblem KKT system, the Holderian majorization inequalities, and the assumed uniform multiplier bound; no target quantity is inserted as an input. Assumption 3 is explicitly acknowledged as not verifiable a priori, but an assumption is not circular reasoning, and Propositions 2 and 3 provide independent sufficient conditions for it. In the convex case, Lemma 7 derives the required multiplier bound from Slater's condition, bounded level sets, and the descent lemma rather than assuming it. The second-order FOSO result counts iterations by the guaranteed per-step objective decrease of at least epsilon_1 or epsilon_2, so the O(1/epsilon_1) and O(1/epsilon_2) bounds follow from a telescoping sum without circularity. The only apparent self-citation is the use of the Sturm-Zhang rank-one decomposition result in Theorem 13, but that is a published external mathematical tool used for an SDP representation and does not assume the paper's target theorem. The skeptic-flagged strict-feasibility issue in the proof of Theorem 1 is a potential correctness gap or missing technical assumption, not a case where a prediction reduces to its own input by construction. Overall, the derivation chain is self-contained relative to its stated assumptions, and no fitted-parameter-as-prediction or definitional equivalence pattern is present.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The paper's central claims rest on standard structural assumptions of nonlinear programming (Slater, bounded level sets, Hölder continuity) and on the existence of convex surrogates. The least-checkable assumption is Assumption 3 on bounded multipliers, which the authors explicitly flag as unverifiable a priori. No invented entities appear. The only free parameters are in the numerical experiments: the relaxation δ and the stepsize schedule.

free parameters (2)
  • relaxation parameter δ = 1e-4
    In the stable set experiments (Section 8.1), the edge constraints X_ij ≤ δ are relaxed to δ=1e-4 to ensure strict feasibility. The claimed 'accurate stable set numbers' depend on this choice, but the paper does not study its effect.
  • diminishing stepsize α_k = e.g., 1/√k in Figure 1; must satisfy Σα_k=∞, Σα_k^2<∞
    Algorithm CEAS requires a diminishing stepsize; the specific schedule is a free design choice not derived from the problem data. The theoretical convergence (Theorem 17) is conditional on x_k converging, and the stepsize schedule is not shown to guarantee convergence.
assumptions (6)
  • domain assumption Assumption 1: existence of convex surrogates f̃,c̃_i that majorize f,c_i and satisfy the gradient Hölderian comparison (Section 2.1)
    This is the core structural assumption of the framework. It is not derived from problem data; the paper provides constructions in Section 3 for Hölderian, DC, and composite functions.
  • domain assumption Assumption 2: existence of an optimal solution and a strictly feasible point x̂ (Slater) with bounded level set (Section 2.1)
    Standard constraint qualification and boundedness; used to guarantee well-posedness and finite Δ.
  • domain assumption Assumption 3: uniform boundedness of subproblem Lagrangian multipliers near optimality (Section 2.1)
    The authors state it cannot be verified a priori. Sufficient conditions are given in Proposition 2 and Proposition 3, but the assumption itself is a load-bearing premise for Theorem 1.
  • domain assumption Assumption 4: gradient Hölderian continuity of f and c_i (Section 3.1)
    Used to construct the quadratic and 1+κ majorants (4). For general nonconvex functions without Hölder gradients, the surrogate construction may fail.
  • domain assumption Self-concordance of the log-barrier (Section 6)
    The Dikin ellipsoid containment relies on the self-concordance of the barrier B_k, a standard result from Nesterov [28].
  • standard math Brickman's theorem (Proposition 12) and Sturm-Zhang rank-one decomposition (Theorem 13)
    External classical results used to show the SDP reformulation of (SP) for n≥3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity Analysis of Convex Majorization Schemes for Nonconvex Constrained Optimization." pith.science (2026). https://pith.science/paper/5WIWNDWV

@misc{pith2026250608506,
  author       = {Pith},
  title        = {Pith review of: Complexity Analysis of Convex Majorization Schemes for Nonconvex Constrained Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5WIWNDWV}},
  note         = {Machine review of arXiv:2506.08506}
}
read the original abstract

In this paper, we introduce and study various algorithms for solving nonconvex minimization with inequality constraints, based on the construction of convex surrogate envelopes that majorize the objective and the constraints. In the case where the objective and constraint functions are gradient H\"{o}lderian continuous, the surrogate functions can be readily constructed and the solution method can be efficiently implemented. The surrogate envelopes are extended to the settings where the second-order information is available, and the convex subproblems are further represented by Dikin ellipsoids using the self-concordance of the convex surrogate constraints. Iteration complexities have been developed for both convex and nonconvex optimization models. The numerical results show promising potential of the proposed approaches.

Figures

Figures reproduced from arXiv: 2506.08506 by the authors.

Figure 1
Figure 1. Graphical illustration of Example 1 8 Numerical Experiments In this section, we test numerical performances of Algorithm GHMA on co-positive programming. 8.1 Copositive relaxation of stable set problem Several NP-hard optimization problems can be written as linear programs over the convex cone of copositive matrices; see e.g. [9]. We consider the completely positive matrices, the dual cone of copositive matrices. Th… view at source ↗
Figure 2
Figure 2. Objective function value gap 8.2 Copositive linear programming We also test Algorithm GHMA on the following basic form of linear programs over completely positive matrices min X,Y ⟨C0, X⟩ s.t. ⟨Ci , X⟩ ≤ bi , i = 1, 2..., m X = Y Y ⊤, Y ≥ 0, where X ∈ R n×n , Y ∈ R n×r and Ci ∈ R n×n , i = 0, 1, 2, ..., m, and C0 ⪰ 0. We set n = 100, r = 60 and m = 200. We tested three randomly generated instances [PITH_FULL_IMAGE:… view at source ↗
Figure 3
Figure 3. Objective function value gap 31 [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: KKT violation (103∥ max(Y k − 10−3 (∇f(Y k ) + Pm i=1 λi∇ci(Y k ), 0) − Y k∥2) 9 Conclusions In this paper, we proposed and studied the iteration complexity properties of a convex majoriza￾tion scheme for nonconvex constrained optimization models. Specific implementati…
Figure 5
Figure 5. Figure 5: Proof sketch for Theorem 17 35 [PITH_FULL_IMAGE:figures/full_fig_p035_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

37 extracted references · 31 canonical work pages

  1. [1]

    Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach

    Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3682–3689, 2022

    work page 2022

  2. [2]

    Antoine Bernigaud, Serge Gratton, Flavia Lenti, Ehouarn Simon, and Oumaima Sohab.l p- norm regularization approaches in variational data assimilation.Quarterly Quarterly Journal of the Royal Meteorological Society, 147:2067–2081, 2021

    work page 2021

  3. [3]

    Projected Newton methods for optimization problems with simple con- straints.SIAM Journal on Control and Optimization, 20(2):221–246, 1982

    Dimitri Bertsekas. Projected Newton methods for optimization problems with simple con- straints.SIAM Journal on Control and Optimization, 20(2):221–246, 1982

    work page 1982

  4. [4]

    Nonlinear programming.Journal of the Operational Research Society, 48(3):334–334, 1997

    Dimitri Bertsekas. Nonlinear programming.Journal of the Operational Research Society, 48(3):334–334, 1997

    work page 1997

  5. [5]

    Academic press, 2014

    Dimitri Bertsekas.Constrained optimization and Lagrange multiplier methods. Academic press, 2014. 32

    work page 2014

  6. [6]

    Stochastic first-order methods for convex and nonconvex functional constrained optimization.Mathematical Programming, 197(1):215–279, 2023

    Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and nonconvex functional constrained optimization.Mathematical Programming, 197(1):215–279, 2023

    work page 2023

  7. [7]

    Cambridge University Press, 2004

    Stephen Boyd and Lieven Vandenberghe.Convex Optimization. Cambridge University Press, 2004

    2004

  8. [8]

    On the field of values of a matrix.Proceedings of the American Mathematical Society, 12:61–66, 1961

    Louis Brickman. On the field of values of a matrix.Proceedings of the American Mathematical Society, 12:61–66, 1961

    work page 1961

Show all 37 references
  1. [9]

    On the copositive representation of binary and continuous nonconvex quadratic programs.Mathematical Programming, 120(2):479–495, 2009

    Samuel Burer. On the copositive representation of binary and continuous nonconvex quadratic programs.Mathematical Programming, 120(2):479–495, 2009

    2009

  2. [10]

    MOS-SIAM Series on Optimization, 2022

    Coralia Cartis, Nicholas Gould, and Philippe Toint.Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation and Perspectives. MOS-SIAM Series on Optimization, 2022

    2022

  3. [11]

    On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming

    Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming. SIAM Journal on Optimization, 21(4):1721–1739, 2011

    2011

  4. [12]

    On the complexity of finding first-order critical points in constrained nonlinear optimization.Mathematical Programming, 144(1):93–106, 2014

    Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the complexity of finding first-order critical points in constrained nonlinear optimization.Mathematical Programming, 144(1):93–106, 2014

    2014

  5. [13]

    A near-optimal primal-dual method for off-policy learning in cmdp.Advances in Neural Information Processing Systems, 35:10521–10532, 2022

    Fan Chen, Junyu Zhang, and Zaiwen Wen. A near-optimal primal-dual method for off-policy learning in cmdp.Advances in Neural Information Processing Systems, 35:10521–10532, 2022

    2022

  6. [14]

    MOS-SIAM Series on Optimization, 2022

    Ying Cui and Jong-Shi Pang.Modern Nonconvex Nondifferentiable Optimization. MOS-SIAM Series on Optimization, 2022

    2022

  7. [15]

    Approximation of the stability number of a graph via copositive programming.SIAM Journal on Optimization, 12(4):875–892, 2002

    Etienne De Klerk and Dmitrii V Pasechnik. Approximation of the stability number of a graph via copositive programming.SIAM Journal on Optimization, 12(4):875–892, 2002

    2002

  8. [16]

    Constrained composite optimization and augmented Lagrangian methods.Mathematical Programming, 201(1):863– 896, 2023

    Alberto De Marchi, Xiaoxi Jia, Christian Kanzow, and Patrick Mehlitz. Constrained composite optimization and augmented Lagrangian methods.Mathematical Programming, 201(1):863– 896, 2023

    2023

  9. [17]

    Copositive programming – a survey

    Mirjam Dur. Copositive programming – a survey. In M. Diehl, F. Glineur, E. Jarlebring, and W. Michiels, editors,Recent Advances in Optimization and its Applications in Engineering, pages 293–298. Springer, Berlin, 2010

    2010

  10. [18]

    Barrier Algorithms for Constrained Non-Convex Optimization.arXiv preprint arXiv:2404.18724, 2024

    Pavel Dvurechensky and Mathias Staudigl. Barrier Algorithms for Constrained Non-Convex Optimization.arXiv preprint arXiv:2404.18724, 2024. 33

    2024 arXiv

  11. [19]

    On the complexity of an augmented Lagrangian method for nonconvex optimization.IMA Journal of Numerical Analysis, 41(2):1546–1568, 2021

    Geovani Nunes Grapiglia and Ya-xiang Yuan. On the complexity of an augmented Lagrangian method for nonconvex optimization.IMA Journal of Numerical Analysis, 41(2):1546–1568, 2021

    2021

  12. [20]

    Safe zeroth- order optimization using quadratic local approximations.arXiv preprint arXiv:2303.16659, 2023

    Baiwei Guo, Yuning Jiang, Giancarlo Ferrari-Trecate, and Maryam Kamgarpour. Safe zeroth- order optimization using quadratic local approximations.arXiv preprint arXiv:2303.16659, 2023

    2023 arXiv

  13. [21]

    Safe zeroth- order convex optimization using quadratic local approximations

    Baiwei Guo, Yuning Jiang, Maryam Kamgarpour, and Giancarlo Ferrari-Trecate. Safe zeroth- order convex optimization using quadratic local approximations. In2023 European Control Conference (ECC), pages 1–8. IEEE, 2023

    2023

  14. [22]

    Safe zeroth-order optimization using linear programs.arXiv preprint arXiv:2304.01797, 2023

    Baiwei Guo, Yang Wang, Yuning Jiang, Maryam Kamgarpour, and Giancarlo Ferrari-Trecate. Safe zeroth-order optimization using linear programs.arXiv preprint arXiv:2304.01797, 2023

    2023 arXiv

  15. [23]

    Chuan He and Zhaosong Lu. A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees.SIAM Journal on Optimization, 33(2):1191–1222, 2023

    2023

  16. [24]

    Rate-improved inex- act augmented Lagrangian method for constrained nonconvex optimization

    Zichong Li, Pin-Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Rate-improved inex- act augmented Lagrangian method for constrained nonconvex optimization. InInternational Conference on Artificial Intelligence and Statistics, pages 2170–2178. PMLR, 2021

    2021

  17. [25]

    Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization.Computational Optimization and Applications, 82(1):175–224, 2022

    Qihang Lin, Runchao Ma, and Yangyang Xu. Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization.Computational Optimization and Applications, 82(1):175–224, 2022

    2022

  18. [26]

    A level-set method for convex opti- mization with a feasible solution path.SIAM Journal on Optimization, 28:3290–3311, 2018

    Qihang Lin, Selvaprabu Nadarajah, and Negar Soheli. A level-set method for convex opti- mization with a feasible solution path.SIAM Journal on Optimization, 28:3290–3311, 2018

    2018

  19. [27]

    On Brickman’s theorem.Journal of Convex Analysis, 12:139– 143, 2005

    Juan Enrique Martinez-Legaz. On Brickman’s theorem.Journal of Convex Analysis, 12:139– 143, 2005

    2005

  20. [28]

    Kluwer Academic Publishers, 2004

    Yurii Nesterov.Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2004

    2004

  21. [29]

    Springer, 2018

    Yurii Nesterov.Lectures on Convex Optimization, volume 137. Springer, 2018

    2018

  22. [30]

    Springer, 1999

    Jorge Nocedal and Stephen J Wright.Numerical Optimization. Springer, 1999

    1999

  23. [31]

    Convergence to second-order station- arity for constrained non-convex optimization.arXiv preprint arXiv:1810.02024, 2018

    Maher Nouiehed, Jason Lee, and Meisam Razaviyayn. Convergence to second-order station- arity for constrained non-convex optimization.arXiv preprint arXiv:1810.02024, 2018. 34

    2018 arXiv

  24. [32]

    Constrained non-convex optimization via stochastic variance reduced approximations

    Mohan Krishna Nutalapati, Muppavaram Sai Krishna, Atanu Samanta, and Ketan Rajawat. Constrained non-convex optimization via stochastic variance reduced approximations. In2019 Sixth Indian Control Conference (ICC), pages 293–298. IEEE, 2019

    2019

  25. [33]

    An inexact augmented lagrangian framework for nonconvex optimization with nonlinear constraints.Ad- vances in Neural Information Processing Systems, 32, 2019

    Mehmet Fatih Sahin, Ahmet Alacaoglu, Fabian Latorre, Volkan Cevher, et al. An inexact augmented lagrangian framework for nonconvex optimization with nonlinear constraints.Ad- vances in Neural Information Processing Systems, 32, 2019

    2019

  26. [34]

    On cones of nonnegative quadratic functions.Mathematics of Operations Research, 28:246–267, 2003

    Jos Sturm and Shuzhong Zhang. On cones of nonnegative quadratic functions.Mathematics of Operations Research, 28:246–267, 2003

    2003

  27. [35]

    Novel opti- mization techniques for parameter estimation.arXiv preprint arXiv:2407.04235, 2024

    Chenyu Wu, Nuozhou Wang, Casey Garner, Kevin Leder, and Shuzhong Zhang. Novel opti- mization techniques for parameter estimation.arXiv preprint arXiv:2407.04235, 2024

    2024 arXiv

  28. [36]

    Solving convex smooth function constrained optimization is as almost easy as unconstrained optimization.arXiv preprint arXiv:2210.05807, 2022

    Zhe Zhang and Guanghui Lan. Solving convex smooth function constrained optimization is as almost easy as unconstrained optimization.arXiv preprint arXiv:2210.05807, 2022

    2022

  29. [37]

    A first-order primal-dual method for nonconvex constrained optimization based on the augmented Lagrangian.Mathematics of Operations Research, 49(1):1–651, 2024

    Daoli Zhu, Lei Zhao, and Shuzhong Zhang. A first-order primal-dual method for nonconvex constrained optimization based on the augmented Lagrangian.Mathematics of Operations Research, 49(1):1–651, 2024. A Proof of Theorem 17 We provide the following roadmap for the proof, for e...

    2024

Pith tools

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