Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization

Qihang Lin; Runchao Ma; Yangyang Xu

REVIEW 2 major objections 3 minor 1 cited by

Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read An inexact proximal-point penalty method finds epsilon-stationary points of nonconvex constrained problems in O~(epsilon^-5/2) proximal-gradient steps under Slater's condition, and in O~(epsilon^-3) or O~(epsilon^-4) depending on…

desk verdict A sound and genuinely useful complexity paper; the headline nonconvex-constraint rate is real but narrower than advertised because it rests on a global error-bound assumption that simple constraints fail. read the letter →

arxiv 1908.11518 v4 pith:AC6ETWBK submitted 2019-08-30 math.OC cs.CCcs.NAmath.NA

Qihang Lin , Runchao Ma , Yangyang Xu This is my paper · ORCID

classification math.OCcs.CCcs.NAmath.NA MSC 90C2690C30

keywords constrainednonconvexoptimizationproximal-pointmethodquadraticpenaltyweakconvexityepsilon-stationarypointfirst-ordercomplexityadaptiveacceleratedproximalgradient

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 proposes and analyzes a first-order method for constrained nonconvex optimization where both the objective and the constraints may be nonconvex. Each subproblem adds a proximal term and quadratic penalty terms to the original objective, which, under a weak-convexity assumption, makes the subproblem strongly convex and solvable by an adaptive accelerated proximal-gradient routine. The paper claims three complexity results measured in proximal-gradient steps: O~($epsilon^{{-5/2}}$) for weakly convex objectives with convex constraints under Slater's condition, O~($epsilon^{{-3}}$) for nonconvex constraints under a non-singularity condition, and O~($epsilon^{{-4}}$) for weak stationarity when only a feasible initial point is available. The convex-constraint rate is described as the best known first-order complexity for this problem class.

What carries the argument

The load-bearing object is the prox-penalty subproblem phi_k(x)=f_0(x)+g(x)+(gamma_k/2)||x-$xbar^{{(k)}}$||^2+(beta_k/2)(||c(x)||^2+||[f(x)]_+||^2), with g kept as the nonsmooth convex term. The proximal term gamma_k/2||x-$xbar^{{(k)}}$||^2 is chosen above the weak-convexity constant, which converts the possibly nonconvex objective-plus-penalty into a strongly convex composite; the quadratic penalties beta_k/2(||c(x)||^2+||[f(x)]_+||^2) drive the iterates toward feasibility. Inside each subproblem, the adaptive accelerated proximal-gradient routine supplies a complexity bound in terms of the condition number of phi_k, and the outer analysis averages the per-iteration stationarity, feasibility, and complementary-slackness residuals so that selecting the best iterate by maximum residual yields the reported epsilon-stationary rates.

What would settle it

Compute, for the problem class in question, the infimum over the domain of the ratio dist(Jc(x)^T c(x)+Jf(x)^T[f(x)]_+, -N_X(x)) divided by $\sqrt$(||[f(x)]_+||^2+||c(x)||^2). If that infimum is 0, for instance at an infeasible point where the gradient of a violated constraint vanishes, then Assumption 4 cannot hold, so the $epsilon^{{-3}}$ claim does not apply and one must check whether the feasible-initialization result degrades to $epsilon^{{-4}}$ as predicted.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that a proximal-point quadratic-penalty hybrid can be tuned so that every subproblem is strongly convex, even when the original objective and constraints are only weakly convex, and that approximate solutions to these subproblems, output by an adaptive accelerated proximal-gradient routine, carry enough information to certify an epsilon-stationary point of the original problem. The analysis gives matching bounds: feasibility violation shrinks like 1/beta_k and the stationarity of the best iterate is controlled by the subproblem tolerances plus the proximal displacement, so choosing beta_k, gamma_k, and epsilon_k appropriately makes the returned point satisfy the paper's Definition 1. The claimed rates are O~($epsilon^{{-5/2}}$) for convex constraints with Slater's condition, O~($epsilon^{{-3}}$) under a non-singularity condition for nonconvex constraints, and O~($epsilon^{{-4}}$) for weak stationarity when only a feasible initial point is available.

Load-bearing premise

The load-bearing premise for the best nonconvex-constraint rate is Assumption 4: a single uniform margin nu>0 must control every point's constraint violation by a constraint-gradient quantity, including points that are far from feasible; if no such margin exists, the $epsilon^{{-3}}$ guarantee is not claimed and the method's known guarantee drops to weak epsilon-stationarity in $epsilon^{{-4}}$ from a feasible start.

Editorial extensions

If this is right

If the O~(epsilon^{-5/2}) result is correct, first-order methods for weakly convex objectives with convex nonlinear constraints and Slater's condition improve by a factor of about epsilon^{-1/2} over the previous linear-constraint quadratic-penalty result.
For problems with nonconvex constraints satisfying the non-singularity condition, the method certifies a full epsilon-stationary point, including approximate complementary slackness, in O~(epsilon^{-3}) proximal-gradient steps without requiring a feasible starting point.
When no non-singularity condition is known but a feasible starting point is available, the method still guarantees a weak epsilon-stationary point in O~(epsilon^{-4}) steps.
Because the inner subroutine adapts to unknown strong-convexity and smoothness constants, the complexity bounds do not require exact knowledge of those constants, only upper bounds sufficient to set gamma_k.
The stronger stationarity notion in Definition 1 means the returned point satisfies an exact complementarity condition for constraints with f_i(x)<0, not merely for f_i(x)<-epsilon.

Reading between the lines

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

Editorial inference: the balancing of three averaged residuals, namely stationarity, feasibility, and complementarity, looks like a transferable template; stochastic or distributed variants of the method could inherit the same rates if the subsolver's complexity bound survives expectation.
Editorial inference: the epsilon^{-3}-to-epsilon^{-4} gap between the two nonconvex-constraint results suggests that the missing ingredient is a substitute for the uniform non-singularity margin; any constraint-error bound that controls infeasible directions from the normal cone, even a local or averaged one, might close the gap.
Editorial inference: the numerical experiment on Neyman-Pearson classification indicates that growing penalty parameters beat fixed ones; a testable extension is an adaptive schedule for beta_k driven by observed infeasibility, which the theory does not yet cover.

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.

Desk Editor's Note

read the letter

Two things to know. First, the main machinery is sound: the O~(ε^{-5/2}) complexity for nonconvex objectives with convex nonlinear constraints and affine equalities is a real improvement, and the proof, including bounded multipliers under Slater, checks out. Second, the paper's strongest nonconvex-constraint claim, O~(ε^{-3}), is only as good as Assumption 4, and Assumption 4 is stronger than ordinary LICQ. The stress-test example is correct: for c(x)=||x||^2-1 on a Euclidean ball, the ratio in (55) is zero at the center, so that simple constraint is excluded. The appendix verifies the assumption only for the K=2 version of the test problem; it does not cover the K=7 and K=10 datasets used in the experiments. That does not make the theorem false, but it narrows the advertised regime.

What the paper does well: it gives explicit parameter settings, splits convex versus nonconvex constraints cleanly, uses the published AdapAPG theorem as an external input without circularity, and correctly identifies a proof error in Sahin et al. The fallback O~(ε^{-4}) weak-stationarity result under a feasible initial point is a useful safety net and is honestly labeled. The numerics are illustrative only: one run per setting, no error bars, and the stationarity measure is computed by a QP rather than the paper's Definition 1. That is fine for a theory paper, but it is not evidence for the nonconvex-constraint rate.

Soft spots, in proportion. The contribution bullet saying the convex-case rate "remains by far the best" is an overclaim even on the paper's own references: reference [41] is cited as achieving the same O~(ε^{-5/2}) under the same convex-constraint assumptions. That claim needs rewording. Assumption 4 is the load-bearing item; the paper is open that it is global, but a reader will want a clearer statement of where it actually holds, and the appendix's K=2 verification does not cover the reported experiments. Since Corollary 2 is explicitly conditional, I see a scope limitation rather than an internal inconsistency. Corollary 3 returns only weak stationarity, and that weaker guarantee should stay prominent whenever Assumption 4 is dropped.

Bottom line: this deserves serious refereeing. The convex-constraint rate alone is a solid contribution, and the rest is a conditional result with an honest fallback. I would accept a review invitation and push for a revised version that fixes the overclaim and puts the non-singularity assumption front and center.

Referee Report

2 major / 3 minor

Summary. The paper studies an inexact proximal-point penalty (iPPP) method, Algorithm 4, for constrained nonconvex optimization problems of the form (1), where the objective and constraints may be nonconvex and a nonsmooth convex term g with compact domain is present. Each outer iteration adds a proximal term and quadratic penalty terms, making the subproblem strongly convex under weak-convexity assumptions, and the subproblems are solved by the adaptive accelerated proximal gradient method of Lin and Xiao. Complexity results are given in terms of the total number of proximal gradient steps needed to produce an ε-stationary or weak ε-stationary point. For convex constraints with a weakly convex objective and Slater's condition, the paper proves an O~(ε^{-5/2}) rate (Corollary 1). For nonconvex constraints, it proves O~(ε^{-3}) under a global nonsingularity/error-bound condition (Assumption 4, Corollary 2) and O~(ε^{-4}) for a weak ε-stationary point under a feasible initial point (Corollary 3). Numerical experiments compare iPPP with a trust-region penalty method on multi-class Neyman-Pearson classification problems.

Significance. If the results hold, the paper gives a meaningful improvement over prior first-order complexity bounds for constrained nonconvex optimization, particularly the O~(ε^{-5/2}) rate for convex constraints and the conditional O~(ε^{-3}) rate for nonconvex constraints under Assumption 4. The paper is commendably explicit about parameter choices and about the distinction between ε-stationarity and weak ε-stationarity, and the outer-loop analysis is self-contained and does not rely on circular reasoning: the AdapAPG subroutine is an externally proven component. The main limitation is that the flagship nonconvex-constraint rate rests on a strong global condition (Assumption 4) whose scope is not fully delineated in the numerical section; however, the theorems themselves are stated conditionally and their proofs appear essentially sound. The convex-case proof has a fixable but important technical error in the bound leading to the O~(ε^{-5/2}) rate.

major comments (2)

[Section 5.2, Eq. (42)] As written, inequality (42) is not a valid consequence of (41). From (41) and β_k = β√(k+1), multiplying (β_k − β_{k−1}) through the right-hand side gives (√(k+1)−√k) · 4(D+M_y^2+M_λ^2)/β_k, not (√(k+1)−√k) β_k · 4(D+M_y^2+M_λ^2). The displayed version is dimensionally inconsistent and, if summed over k, would grow linearly in K, whereas the subsequent bound (43) is O(1/β). Since (43) is used to define C_1 and hence the O~(ε^{-5/2}) complexity in Corollary 1, this step must be corrected. The repair is local: insert the missing factor 1/β_k in the right-hand side of (42); the rest of the proof then goes through as written.
[Section 6.2, Assumption 4 and Corollary 2; Section 7 and Appendix] The advertised O~(ε^{-3}) rate for nonconvex constraints is conditional on the global nonsingularity inequality (55). This condition is not verified for the K=7 and K=10 datasets used in the numerical experiments; the Appendix verifies only the K=2 model, and that verification itself requires additional conditions (origin feasibility and (87)). Moreover, Assumption 4 is substantially stronger than a feasible-point LICQ: for example, with c(x)=‖x‖²−1 and X=B_2, the ratio in (55) is zero at x=0, so the assumption fails for very simple nonconvex equality constraints. The theorem is correctly stated as conditional, but the paper should explicitly delimit the scope of Corollary 2 in the abstract and introduction, and should either verify (55) for the actual test problems or state that the numerical experiments do not exercise the O~(ε^{-3}) regime.

minor comments (3)

[Section 1.1 and Section 2] The contribution statement that the O~(ε^{-5/2}) convex-constraint complexity 'remains by far the best' is in tension with the discussion in Section 2, which cites [41] and [36] as also achieving the same O~(ε^{-5/2}) order under the same assumptions after the first draft of this paper. Please update the wording to acknowledge these contemporaneous results.
[Section 6.2, Assumption 4 discussion] The paragraph following Assumption 4 says that the condition is inspired by LICQ and can hold on int(X), but the global form (55) is much stronger. It would help readers to state explicitly that Assumption 4 is an error-bound condition over the whole compact domain, including infeasible points, and to give a one-line example showing the difference from feasible-point LICQ.
[Section 7, experimental setup] The numerical comparison reports that the initial iterate x(0)=0 is feasible for (83), but it does not state whether the conditions used in the Appendix to verify Assumption 4 for the K=2 model (nonzero data vectors, pairwise nonnegative inner products, and f(0)≤0) hold for the K=7 and K=10 datasets. Please clarify this in the experimental setup or state explicitly that the verification is not intended to cover those instances.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the iPPP derivation is self-contained, and the only self-citation (AdapAPG, Lin & Xiao 2015) is an externally proven theorem used as a subroutine.

full rationale

The paper's derivation chain is self-contained and does not reduce to its own inputs. Algorithm 4 constructs subproblem (16) by adding a proximal term and quadratic penalty terms to the original objective; Lemma 1 bounds the accumulated proximal and penalty terms using the subproblem accuracy epsilon_k, Lemma 2 bounds the stationarity measure by epsilon_k plus the proximal movement, Lemma 3 bounds the multipliers of the auxiliary convex problem, and Lemma 4 bounds the feasibility violation via the subproblem accuracy and the bounded multipliers. Theorem 2 combines these bounds and then Corollary 1 sets K = O(1/epsilon^2), with parameters gamma_k, beta_k, and epsilon_k chosen explicitly as functions of known constants and epsilon; no fitted parameter is renamed as a prediction. The nonconvex-constraint result is conditional on Assumption 4, which is a regularity/error-bound assumption rather than an assumption of the conclusion; the proof uses it to convert constraint violation into a stationarity bound, and without it the paper explicitly falls back to the O~(epsilon^-4) weak-stationarity result under a feasible initial point. The only self-citation is the AdapAPG complexity theorem, Theorem 1, quoted from Lin and Xiao [44], one of whose authors is a co-author of the present paper. That theorem is a published, independently proven result with its own proof; the paper does not invoke it to assume the main theorem, and it is not a restatement of the present results. The numerical verification of Assumption 4 in the appendix covers only the K=2 case while the experiments use K=7 and K=10; this is a validation limitation for the nonconvex-constraint regime, not a circularity. Overall, the advertised O~(epsilon^-5/2) rate for convex constraints and the conditional O~(epsilon^-3) rate are derived, not assumed, and no equation in the paper is equivalent by construction to an input.

Assumptions & free parameters 1 free parameters · 7 assumptions · 0 invented entities

The theoretical complexity claims introduce no free parameters: the penalty, proximal, and tolerance schedules are explicit functions of the problem's smoothness and weak-convexity constants. The main burden sits on the domain assumptions, especially the global non-singularity condition (Assumption 4) that enables the O~(ε^{-3}) rate, and on the external AdapAPG complexity theorem. The only hand-tuned number appears in the numerical section, where the penalty growth constant β is set per dataset.

free parameters (1)

β (penalty growth constant, experiments only) = 200 (mnist), 500 (covtype)
Selected from a discrete candidate set based on objective value after 10,000 data passes; this tuning affects only the numerics, not the theoretical complexity results.

assumptions (7)

domain assumption Assumption 1: all f_i and c_j are L-smooth, dom(g) is compact, every subgradient of g lies in N_X(x)+B_M, and prox_g is easy to compute.
Used throughout; enables bounded function and gradient values and multiplier bounds in Lemma 3.
domain assumption Assumption 2: f0 is weakly convex, inequality constraints are convex, equality constraints affine, Slater's condition holds with a point in the interior of dom(g).
Needed for KKT conditions and bounded multipliers in Section 5.
domain assumption Assumption 3: objective and all constraint functions are weakly convex.
Defines the setting for Section 6 and guarantees subproblem strong convexity for large γ_k.
ad hoc to paper Assumption 4: global non-singularity/error bound, ν sqrt(||[f]_+||^2+||c||^2) ≤ dist(Jc^T c + Jf^T [f]_+, -N_X) for all x in X.
This strong global condition resembles LICQ over the entire domain, including infeasible points; it is the key enabler of the O~(ε^{-3}) rate and is verified only for the specific mNPC application in the appendix.
domain assumption Assumption 5: initial point is feasible for all constraints.
Used in Theorem 4 and Corollary 3 to avoid Assumption 4 at the cost of a worse rate and only weak stationarity.
standard math Theorem 1 of Lin and Xiao (2015) bounding the iteration count of AdapAPG on strongly convex composite problems.
The total complexity is derived by summing the AdapAPG iteration counts; this is an external published theorem with proof.
standard math Rockafellar's convex analysis theorem on existence of KKT multipliers under Slater's condition for convex programs.
Invoked at the start of Section 5.1 to assert the KKT system (28).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization." pith.science (2026). https://pith.science/paper/AC6ETWBK

@misc{pith2026190811518,
  author       = {Pith},
  title        = {Pith review of: Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AC6ETWBK}},
  note         = {Machine review of arXiv:1908.11518}
}

abstract

In this paper, an inexact proximal-point penalty method is studied for constrained optimization problems, where the objective function is non-convex, and the constraint functions can also be non-convex. The proposed method approximately solves a sequence of subproblems, each of which is formed by adding to the original objective function a proximal term and quadratic penalty terms associated to the constraint functions. Under a weak-convexity assumption, each subproblem is made strongly convex and can be solved effectively to a required accuracy by an optimal gradient-based method. The computational complexity of the proposed method is analyzed separately for the cases of convex constraint and non-convex constraint. For both cases, the complexity results are established in terms of the number of proximal gradient steps needed to find an $\varepsilon$-stationary point. When the constraint functions are convex, we show a complexity result of $\tilde O(\varepsilon^{-5/2})$ to produce an $\varepsilon$-stationary point under the Slater's condition. When the constraint functions are non-convex, the complexity becomes $\tilde O(\varepsilon^{-3})$ if a non-singularity condition holds on constraints and otherwise $\tilde O(\varepsilon^{-4})$ if a feasible initial solution is available.

Figures

Figures reproduced from arXiv: 1908.11518 by the authors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization
math.OC 2026-07 accept novelty 7.0 of 10

SDBPG and its penalty/variance-reduced variants achieve the first explicit (ε_f, ε_g)-stationarity rates for stochastic nonconvex simple bilevel problems by regularizing unbounded dual multipliers.

Reference graph

Works this paper leans on

81 extracted references · 68 canonical work pages · cited by 1 Pith paper

[41]

Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective

Li, Z., Xu, Y.: Augmented lagrangian based ﬁrst-order methods for convex and nonconvex programs: nonergodic convergence and iteration complexity. arXiv preprint arXiv:2003.08880 (2020)

work page Pith review arXiv 2020
[1]

In: Proceedings of the 34th International Conference on Machine Learning (ICML), pp

Allen-Zhu, Z.: Natasha: Faster non-convex stochastic optimization via strongly non-convex parameter. In: Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 89–97 (2017)

2017
[2]

Optimal Convergence for Stochastic Optimization with Multiple Expectation Constraints

Basu, K., Nandy, P.: Optimal convergence for stochastic optimization with multiple expectation constraints. arXiv preprint arXiv:1906.03401 (2019)

work page Pith review arXiv 2019
[3]

In: Large-Scale and Distributed Optimization, pp

Bayandina, A., Dvurechensky, P., Gasnikov, A., Stonyakin, F., Titov, A.: Mirror descent and convex optimization problems with non-smooth inequality constraints. In: Large-Scale and Distributed Optimization, pp. 181–213. Springer (2018)

work page 2018
[4]

Complexity and performance of an Augmented Lagrangian algorithm

Birgin, E., Mart´ ınez, J.: Complexity and performance of an augmented lagrangian algorithm. arXiv preprint arXiv:1907.02401 (2019)

work page Pith review arXiv 2019
[5]

Mathematical Programming 125(1), 139–162 (2010)

Birgin, E.G., Floudas, C.A., Mart´ ınez, J.M.: Global minimization using an augmented lagrangian method with variable lower-level constraints. Mathematical Programming 125(1), 139–162 (2010)

work page 2010
[6]

Computational Optimization and Applications 69(1), 51–75 (2018)

Birgin, E.G., Haeser, G., Ramos, A.: Augmented lagrangians with constrained subproblems and convergence to second-order stationary points. Computational Optimization and Applications 69(1), 51–75 (2018)

work page 2018
[7]

Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization

Boob, D., Deng, Q., Lan, G.: Proximal point methods for optimization with nonconvex functional constraints. arXiv preprint arXiv:1908.02734 (2019)

work page Pith review arXiv 2019

Show all 81 references

[8]

SIAM Journal on control and optimization 29(4), 968–998 (1991)

Burke, J.V.: An exact penalization viewpoint of constrained optimization. SIAM Journal on control and optimization 29(4), 968–998 (1991)

1991
[9]

SIAM Journal on Optimization 16(2), 471–489 (2005)

Byrd, R.H., Gould, N.I., Nocedal, J., Waltz, R.A.: On the convergence of successive linear-quadratic programming algorithms. SIAM Journal on Optimization 16(2), 471–489 (2005)

2005
[10]

SIAM Journal on Optimization 21(4), 1721–1739 (2011)

Cartis, C., Gould, N.I., Toint, P.L.: On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming. SIAM Journal on Optimization 21(4), 1721–1739 (2011)

2011
[11]

Mathematical Programming 144(1-2), 93–106 (2014)

Cartis, C., Gould, N.I., Toint, P.L.: On the complexity of ﬁnding ﬁrst-order critical points in constrained nonlinear optimization. Mathematical Programming 144(1-2), 93–106 (2014)

2014
[12]

Mathematical Programming 161(1-2), 611–626 (2017)

Cartis, C., Gould, N.I., Toint, P.L.: Corrigendum: On the complexity of ﬁnding ﬁrst-order critical points in constrained nonlinear optimization. Mathematical Programming 161(1-2), 611–626 (2017)

2017
[13]

Machine learning 47(2-3), 201–233 (2002)

Crammer, K., Singer, Y.: On the learnability and design of output codes for multiclass problems. Machine learning 47(2-3), 201–233 (2002)

2002
[14]

Optimization Methods and Software 31(1), 157–186 (2016)

Curtis, F.E., Gould, N.I., Jiang, H., Robinson, D.P.: Adaptive augmented lagrangian methods: algorithms and practical numerical experience. Optimization Methods and Software 31(1), 157–186 (2016)

2016
[15]

arXiv preprint arXiv:1803.06523 (2018)

Davis, D., Drusvyatskiy, D.: Stochastic model-based minimization of weakly convex functions. arXiv preprint arXiv:1803.06523 (2018)

2018 arXiv
[16]

arXiv preprint arXiv:1802.02988 (2018) 21

Davis, D., Drusvyatskiy, D.: Stochastic subgradient method converges at the rate o(k−1/4) on weakly convex functions. arXiv preprint arXiv:1802.02988 (2018) 21

2018 arXiv
[17]

arXiv preprint arXiv:1707.03505 (2017)

Davis, D., Grimmer, B.: Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. arXiv preprint arXiv:1707.03505 (2017)

2017 arXiv
[18]

SIAM Journal on Control and Optimization 23(1), 72–84 (1985)

Di Pillo, G., Grippo, L.: A continuously diﬀerentiable exact penalty function for nonlinear programming problems with inequality constraints. SIAM Journal on Control and Optimization 23(1), 72–84 (1985)

1985
[19]

Mathematical Programming 36(1), 1–18 (1986)

Di Pillo, G., Grippo, L.: An exact penalty function method with global convergence properties for nonlinear programming problems. Mathematical Programming 36(1), 1–18 (1986)

1986
[20]

Mathematical Programming (2018)

Drusvyatskiy, D., Paquette, C.: Eﬃciency of minimizing compositions of convex functions and smooth maps. Mathematical Programming (2018)

2018
[21]

SIAM Journal on Optimization 22(2), 384–407 (2012)

Fern´ andez, D., Solodov, M.V.: Local convergence of exact and inexact augmented lagrangian methods under the second-order suﬃcient optimality condition. SIAM Journal on Optimization 22(2), 384–407 (2012)

2012
[22]

In: Mathematical Programming The State of the Art, pp

Fletcher, R.: Penalty functions. In: Mathematical Programming The State of the Art, pp. 87–114. Springer (1983)

1983
[23]

SIAM Journal on Optimization 15(3), 863–897 (2005)

Friedlander, M.P., Saunders, M.A.: A globally convergent linearly constrained lagrangian method for nonlinear optimization. SIAM Journal on Optimization 15(3), 863–897 (2005)

2005
[24]

SIAM Journal on Optimization 23(4), 2341–2368 (2013)

Ghadimi, S., Lan, G.: Stochastic ﬁrst- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization 23(4), 2341–2368 (2013). DOI 10.1137/120880811. URL https: //doi.org/10.1137/120880811

2013 doi
[25]

Ghadimi, S., Lan, G.: Accelerated gradient methods for nonconvex nonlinear and stochastic pro- gramming. Math. Program. 156(1-2), 59–99 (2016). DOI 10.1007/s10107-015-0871-8. URL https://doi.org/10.1007/s10107-015-0871-8

2016 doi
[26]

arXiv preprint arXiv:1702.01850 (2017)

Gon¸ calves, M.L., Melo, J.G., Monteiro, R.D.: Convergence rate bounds for a proximal admm with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems. arXiv preprint arXiv:1702.01850 (2017)

2017 arXiv
[27]

SIAM Journal on Numerical Analysis 26(1), 107–128 (1989)

Gould, N.I.M.: On the convergence of a sequential penalty function method for constrained minimiza- tion. SIAM Journal on Numerical Analysis 26(1), 107–128 (1989)

1989
[28]

arXiv preprint arXiv:1906.05622 (2019)

Grapiglia, G.N., Yuan, Y.x.: On the complexity of an augmented lagrangian method for nonconvex optimization. arXiv preprint arXiv:1906.05622 (2019)

2019 arXiv
[29]

Mathematical Programming178(1-2), 263–299 (2019)

Haeser, G., Liu, H., Ye, Y.: Optimality condition and complexity analysis for linearly-constrained optimization without diﬀerentiability on the boundary. Mathematical Programming178(1-2), 263–299 (2019)

2019
[30]

Mathematical Programming 176(1-2), 207–245 (2019)

Hajinezhad, D., Hong, M.: Perturbed proximal primal–dual algorithm for nonconvex nonsmooth optimization. Mathematical Programming 176(1-2), 207–245 (2019)

2019
[31]

arXiv preprint arXiv:1604.00543 (2016)

Hong, M.: Decomposing linearly constrained nonconvex problems by a proximal primal dual approach: Algorithms, convergence, and applications. arXiv preprint arXiv:1604.00543 (2016)

2016 arXiv
[32]

arXiv preprint arXiv:1802.08941 (2018)

Hong, M., Lee, J.D., Razaviyayn, M.: Gradient primal-dual algorithm converges to second-order stationary solutions for nonconvex distributed optimization. arXiv preprint arXiv:1802.08941 (2018)

2018 arXiv
[33]

Computational Optimization and Applications 72(1), 115–157 (2019)

Jiang, B., Lin, T., Ma, S., Zhang, S.: Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis. Computational Optimization and Applications 72(1), 115–157 (2019)

2019
[34]

arXiv preprint arXiv:1907.12424 (2019)

Jiang, B., Meng, X., Wen, Z., Chen, X.: An exact penalty approach for optimization with nonnegative orthogonality constraints. arXiv preprint arXiv:1907.12424 (2019)

2019 arXiv
[35]

SIAM Journal on Optimization 29(4), 2566–2593 (2019)

Kong, W., Melo, J.G., Monteiro, R.D.: Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. SIAM Journal on Optimization 29(4), 2566–2593 (2019)

2019
[36]

arXiv preprint arXiv:2008.07080 (2020)

Kong, W., Melo, J.G., Monteiro, R.D.: Iteration-complexity of a proximal augmented lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints. arXiv preprint arXiv:2008.07080 (2020)

2020 arXiv
[37]

Mathematical Programming 138(1-2), 115–139 (2013)

Lan, G., Monteiro, R.D.: Iteration-complexity of ﬁrst-order penalty methods for convex programming. Mathematical Programming 138(1-2), 115–139 (2013)

2013
[38]

CoRR abs/1805.05411 (2018)

Lan, G., Yang, Y.: Accelerated stochastic algorithms for nonconvex ﬁnite-sum and multi-block optimization. CoRR abs/1805.05411 (2018)

2018 arXiv
[39]

arXiv preprint arXiv:1604.03887 (2016)

Lan, G., Zhou, Z.: Algorithms for stochastic optimization with expectation constraints. arXiv preprint arXiv:1604.03887 (2016)

2016 arXiv
[40]

arXiv preprint arXiv:2007.01284 (2020) 22

Li, Z., Chen, P.Y., Liu, S., Lu, S., Xu, Y.: Rate-improved inexact augmented lagrangian method for constrained nonconvex optimization. arXiv preprint arXiv:2007.01284 (2020) 22

2020 arXiv
[42]

arXiv preprint arXiv:1908.11518v1 (2019)

Lin, Q., Ma, R., Xu, Y.: Inexact proximal-point penalty methods for non-convex optimization with non-convex constraints. arXiv preprint arXiv:1908.11518v1 (2019)

2019 arXiv
[43]

In: International Conference on Machine Learning, pp

Lin, Q., Ma, R., Yang, T.: Level-set methods for ﬁnite-sum constrained convex optimization. In: International Conference on Machine Learning, pp. 3118–3127 (2018)

2018
[44]

Computational Optimization & Applications 60(3) (2015)

Lin, Q., Xiao, L.: An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization. Computational Optimization & Applications 60(3) (2015)

2015
[45]

arXiv preprint arXiv:1907.04450 (2019)

Lu, S., Razaviyayn, M., Yang, B., Huang, K., Hong, M.: Snap: Finding approximate second- order stationary solutions eﬃciently for non-convex linearly constrained problems. arXiv preprint arXiv:1907.04450 (2019)

2019 arXiv
[46]

arXiv preprint arXiv:1908.01871 (2019)

Ma, R., Lin, Q., Yang, T.: Proximally constrained methods for weakly convex optimization with weakly convex constraints. arXiv preprint arXiv:1908.01871 (2019)

2019 arXiv
[47]

arXiv preprint arXiv:1705.07229 (2017)

Melo, J.G., Monteiro, R.D.: Iteration-complexity of a Jacobi-type non-euclidean ADMM for multi-block linearly constrained nonconvex programs. arXiv preprint arXiv:1705.07229 (2017)

2017 arXiv
[48]

arXiv preprint arXiv:2008.00562 (2020)

Melo, J.G., Monteiro, R.D.: Iteration-complexity of an inner accelerated inexact proximal augmented lagrangian method based on the classical lagrangian function and a full lagrange multiplier update. arXiv preprint arXiv:2008.00562 (2020)

2020 arXiv
[49]

arXiv preprint arXiv:2006.08048 (2020)

Melo, J.G., Monteiro, R.D., Wang, H.: Iteration-complexity of an inexact proximal accelerated aug- mented lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems. arXiv preprint arXiv:2006.08048 (2020)

2020 arXiv
[50]

Optimization Methods and Software 34(2), 305–335 (2019)

Necoara, I., Patrascu, A., Glineur, F.: Complexity of ﬁrst-order inexact lagrangian and penalty methods for conic convex programming. Optimization Methods and Software 34(2), 305–335 (2019)

2019
[51]

Kluwer Academic Publ

Nesterov, Y.: Introductory Lectures on Convex Optimization : a Basic Course. Kluwer Academic Publ. (2004)

2004
[52]

Mathematical programming 127(1), 31–56 (2011)

Nesterov, Y.: Barrier subgradient method. Mathematical programming 127(1), 31–56 (2011)

2011
[53]

Mathematical Programming 140(1), 125–161 (2013)

Nesterov, Y.: Gradient methods for minimizing composite functions. Mathematical Programming 140(1), 125–161 (2013)

2013
[54]

arXiv preprint arXiv:1810.02024 (2018)

Nouiehed, M., Lee, J.D., Razaviyayn, M.: Convergence to second-order stationarity for constrained non-convex optimization. arXiv preprint arXiv:1810.02024 (2018)

2018 arXiv
[55]

arXiv preprint arXiv:1904.03563 (2019)

O’Neill, M., Wright, S.J.: A log-barrier newton-cg method for bound constrained optimization with complexity guarantees. arXiv preprint arXiv:1904.03563 (2019)

2019 arXiv
[56]

Mathematical Programming 35(3), 265–278 (1986)

Powell, M.J., Yuan, Y.: A recursive quadratic programming algorithm that uses diﬀerentiable exact penalty functions. Mathematical Programming 35(3), 265–278 (1986)

1986
[57]

In: Proceedings of the 33rd International Conference on International Conference on Machine Learning (ICML), pp

Reddi, S.J., Hefny, A., Sra, S., P´ ocz´ os, B., Smola, A.: Stochastic variance reduction for nonconvex optimization. In: Proceedings of the 33rd International Conference on International Conference on Machine Learning (ICML), pp. 314–323. JMLR.org (2016)

2016
[58]

Princeton mathematical series

Rockafellar, R.: Convex Analysis. Princeton mathematical series. Princeton University Press (1970)

1970
[59]

In: Advances in Neural Information Processing Systems (2019)

Sahin, M.F., eftekhari, A., Alacaoglu, A., Latorre, F., Cevher, V.: An inexact augmented lagrangian framework for nonconvex optimization with nonlinear constraints. In: Advances in Neural Information Processing Systems (2019)

2019
[60]

Computational Optimization and Applications 72(1), 1–43 (2019)

Tran-Dinh, Q.: Proximal alternating penalty algorithms for nonsmooth constrained convex optimiza- tion. Computational Optimization and Applications 72(1), 1–43 (2019)

2019
[61]

arXiv preprint arXiv:1406.5403 (2014)

Tran-Dinh, Q., Cevher, V.: A primal-dual algorithmic framework for constrained convex minimization. arXiv preprint arXiv:1406.5403 (2014)

2014 arXiv
[62]

arXiv preprint arXiv 1308 (2013)

Tran-Dinh, Q., Kyrillidis, A., Cevher, V.: Composite self-concordant minimization. arXiv preprint arXiv 1308 (2013)

2013
[63]

SIAM Journal on Optimization 24(4), 1718–1745 (2014)

Tran-Dinh, Q., Kyrillidis, A., Cevher, V.: An inexact proximal path-following algorithm for constrained convex minimization. SIAM Journal on Optimization 24(4), 1718–1745 (2014)

2014
[64]

Mathe- matics of Operations Research 43(4), 1326–1347 (2018)

Tran-Dinh, Q., Kyrillidis, A., Cevher, V.: A single-phase, proximal path-following framework. Mathe- matics of Operations Research 43(4), 1326–1347 (2018)

2018
[65]

arXiv preprint arXiv:1410.8625 (2014)

Wang, F., Xu, Z., Xu, H.K.: Convergence of bregman alternating direction method with multipliers for nonconvex composite problems. arXiv preprint arXiv:1410.8625 (2014)

2014 arXiv
[66]

arXiv preprint arXiv:1906.00570 (2019) 23

Wang, S., Chang, T.H., Cui, Y., Pang, J.S.: Clustering by orthogonal nmf model and non-convex penalty optimization. arXiv preprint arXiv:1906.00570 (2019) 23

2019 arXiv
[67]

Mathematics of Computation 86(306), 1793–1820 (2017)

Wang, X., Ma, S., Yuan, Y.x.: Penalty methods with stochastic approximation for stochastic nonlinear programming. Mathematics of Computation 86(306), 1793–1820 (2017)

2017
[68]

Journal of Scientiﬁc Computing 78(1), 29–63 (2019)

Wang, Y., Yin, W., Zeng, J.: Global convergence of admm in nonconvex nonsmooth optimization. Journal of Scientiﬁc Computing 78(1), 29–63 (2019)

2019
[69]

arXiv preprint arXiv:1806.00709 (2018)

Wei, X., Neely, M.J.: Primal-dual frank-wolfe for constrained stochastic programs with convex and non-convex objectives. arXiv preprint arXiv:1806.00709 (2018)

2018 arXiv
[70]

In: Advances in Neural Information Processing Systems, pp

Wei, X., Yu, H., Ling, Q., Neely, M.: Solving non-smooth constrained programs with lower complexity than O(1/ε): A primal-dual homotopy smoothing approach. In: Advances in Neural Information Processing Systems, pp. 3995–4005 (2018)

2018
[71]

Weston, J., Watkins, C.: Multi-class support vector machines. Tech. rep., Citeseer (1998)

1998
[72]

arXiv preprint arXiv:1908.00131 (2019)

Xie, Y., Wright, S.J.: Complexity of proximal augmented lagrangian for nonconvex optimization with nonlinear equality constraints. arXiv preprint arXiv:1908.00131 (2019)

2019 arXiv
[73]

arXiv preprint arXiv:1711.08020 (2017)

Xu, Y.: First-order methods for constrained convex programming based on linearized augmented lagrangian function. arXiv preprint arXiv:1711.08020 (2017)

2017 arXiv
[74]

arXiv preprint arXiv:1802.02724 (2018)

Xu, Y.: Primal-dual stochastic gradient method for convex programs with many functional constraints. arXiv preprint arXiv:1802.02724 (2018)

2018 arXiv
[75]

Mathematical Programming, Series A (online ﬁrst) pp

Xu, Y.: Iteration complexity of inexact augmented lagrangian methods for constrained convex programming. Mathematical Programming, Series A (online ﬁrst) pp. 1–46 (2019)

2019
[76]

In: Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp

Yang, T., Lin, Q., Zhang, L.: A richer theory of convex constrained optimization with reduced projections and improved rates. In: Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 3901–3910. JMLR. org (2017)

2017
[77]

In: Advances in Neural Information Processing Systems, pp

Yu, H., Neely, M., Wei, X.: Online convex optimization with stochastic constraints. In: Advances in Neural Information Processing Systems, pp. 1428–1438 (2017)

2017
[78]

SIAM Journal on Optimization 27(2), 759–783 (2017)

Yu, H., Neely, M.J.: A simple parallel algorithm with an O(1/t) convergence rate for general convex programs. SIAM Journal on Optimization 27(2), 759–783 (2017)

2017
[79]

arXiv preprint arXiv:2006.16440 (2020)

Zhang, J., Luo, Z.: A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization. arXiv preprint arXiv:2006.16440 (2020)

2020 arXiv
[80]

SIAM Journal on Optimization 30(3), 2272–2302 (2020)

Zhang, J., Luo, Z.Q.: A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal on Optimization 30(3), 2272–2302 (2020)

2020
[81]

arXiv preprint arXiv:1806.04781 (2018) Appendix: Discussion on Assumption 4 for application (83) We explain that Assumption 4 can hold for the tested problem (83)

Zhang, S., He, N.: On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv preprint arXiv:1806.04781 (2018) Appendix: Discussion on Assumption 4 for application (83) We explain that Assumption 4 can hold for the tested problem (83). For...

2018 arXiv

Pith tools

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

[1] [41]

Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective

Li, Z., Xu, Y.: Augmented lagrangian based ﬁrst-order methods for convex and nonconvex programs: nonergodic convergence and iteration complexity. arXiv preprint arXiv:2003.08880 (2020)

work page Pith review arXiv 2020

[2] [1]

In: Proceedings of the 34th International Conference on Machine Learning (ICML), pp

Allen-Zhu, Z.: Natasha: Faster non-convex stochastic optimization via strongly non-convex parameter. In: Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 89–97 (2017)

2017

[3] [2]

Optimal Convergence for Stochastic Optimization with Multiple Expectation Constraints

Basu, K., Nandy, P.: Optimal convergence for stochastic optimization with multiple expectation constraints. arXiv preprint arXiv:1906.03401 (2019)

work page Pith review arXiv 2019

[4] [3]

In: Large-Scale and Distributed Optimization, pp

Bayandina, A., Dvurechensky, P., Gasnikov, A., Stonyakin, F., Titov, A.: Mirror descent and convex optimization problems with non-smooth inequality constraints. In: Large-Scale and Distributed Optimization, pp. 181–213. Springer (2018)

work page 2018

[5] [4]

Complexity and performance of an Augmented Lagrangian algorithm

Birgin, E., Mart´ ınez, J.: Complexity and performance of an augmented lagrangian algorithm. arXiv preprint arXiv:1907.02401 (2019)

work page Pith review arXiv 2019

[6] [5]

Mathematical Programming 125(1), 139–162 (2010)

Birgin, E.G., Floudas, C.A., Mart´ ınez, J.M.: Global minimization using an augmented lagrangian method with variable lower-level constraints. Mathematical Programming 125(1), 139–162 (2010)

work page 2010

[7] [6]

Computational Optimization and Applications 69(1), 51–75 (2018)

Birgin, E.G., Haeser, G., Ramos, A.: Augmented lagrangians with constrained subproblems and convergence to second-order stationary points. Computational Optimization and Applications 69(1), 51–75 (2018)

work page 2018

[8] [7]

Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization

Boob, D., Deng, Q., Lan, G.: Proximal point methods for optimization with nonconvex functional constraints. arXiv preprint arXiv:1908.02734 (2019)

work page Pith review arXiv 2019