{"id":"90530f18-45f4-4b35-8b57-6c9c522a93c8","arxiv_id":"2509.02894","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For nonconvex problems with equality and inequality constraints and a known feasible point, an inexact proximal augmented Lagrangian method with adaptive parameter updates reaches an epsilon-KKT point in finitely many iterations.","lead":"This paper presents a proximal augmented Lagrangian method for nonconvex optimization with equality and inequality constraints, and proves that with a feasible starting point it finds an approximate KKT point in finitely many iterations. The new adaptive rules for penalty and proximal parameters can reduce the ill-conditioning that comes from standard linear penalty growth.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.1's upper bound does not follow from Steps 1-2 as written: an ε-stationary subproblem point may have higher augmented Lagrangian value than the warm start, so Theorem 3.1 rests on an unstated descent requirement.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing gap: Step 2's ε-stationarity condition does not imply monotonicity of the augmented Lagrangian value, and Lemma 4.1 silently requires it. An independent check of the proof chain confirms that Theorem 4.2, Lemma 4.3, and Theorem 4.5 all rely on (4.1), so the main ε-KKT termination claim is conditional on repairing this missing descent assumption. I found no equally central flaw elsewhere: the multiplier update identities, the penalty-parameter recursion, and the subsequence arguments are coherent once (4.1) is granted. The numerical experiments are suggestive but cannot substitute for a missing proof step. Since the reader already returned a CONDITIONAL verdict and this concern supports that judgment, no change in verdict is needed; the authors should state the subproblem value descent requirement explicitly or prove Lemma 4.1 by another route.","tokens_in":20853,"tokens_out":7386,"duration_ms":87547,"concrete_test":"Construct a one-dimensional instance satisfying Assumptions I and II: f1(x)=-cos x, f2=0, p=m=0, x0=0, λ0=µ0=0, and choose γ0>π/τ. At k=0, Step 1 sets x̂0=x0 because equality holds in (4.1). The point x1=π satisfies (3.3): |∇L(x1)|=|sin π + (π-x0)/γ0|=π/γ0<τ. But L(x1)+f2(x1) = 1 + π²/(2γ0) > -1 = f(x0)+1/(2γ0)||x0-x0||², contradicting Lemma 4.1. Thus the stated ε-stationarity condition alone permits an execution violating the lemma; run this instance and verify the bound fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 4.1 is the hinge of the proof, but its displayed inequality is not a consequence of the stated algorithm. Step 1 selects a warm start x̂_k, and Step 2 only requires the ε-stationarity residual (3.3). For a nonconvex subproblem, an ε-stationary point can have strictly larger objective value than the starting point; approximate stationarity does not control function value. The bound (4.1) would follow if Step 2 also enforced L(x_{k+1})+f2(x_{k+1}) ≤ L(x̂_k)+f2(x̂_k) (plus a bound at x̂_k), but no such condition appears in (3.2)-(3.3). Moreover, when Step 1 sets x̂_k=x0, even the warm-start value can exceed the right-hand side of (4.1) if the multipliers are positive at the feasible point. Theorem 4.2, Lemma 4.3, Theorem 4.5, and Theorem 3.1 all depend on (4.1), so the finite-time ε-KKT claim is currently unsupported. The same issue affects BALM's analogue (5.4). The paper needs either an explicit descent (or bounded-increase) requirement on the subproblem value in Step 2, or a different proof of Lemma 4.1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes P-BALM, an inexact proximal augmented Lagrangian method for nonconvex optimization with equality and inequality constraints and a possibly nonsmooth convex term f2. Under an initial-feasibility assumption and a growth condition on the parameter sequences, the authors claim that (1/γ_k)||x_{k+1}-x_k||² converges to zero, that scaled multiplier differences vanish along an infinite subsequence, and that an ε-KKT point is obtained in finitely many iterations for any ε>τ. The key step is an upper bound on the augmented Lagrangian along the iterates (Lemma 4.1). The classical ALM is recovered as the limiting case without the proximal term, with analogous guarantees (Corollary 5.2). Numerical experiments on convex QPs and a nonconvex basis-pursuit reformulation compare P-BALM, BALM, and standard ALM.","tokens_in":21190,"tokens_out":13509,"duration_ms":129507,"significance":"If the main theorem is established, the paper is a useful contribution: it gives a unified and relatively simple convergence analysis for an inexact proximal ALM with nonlinear equality and inequality constraints, proposes practical adaptive penalty and proximal-parameter updates that grow sublinearly in the long run, and derives the classical ALM as a by-product. The proof structure is modular (Lemma 4.1 → Theorem 4.2 → Lemma 4.4 → Theorem 4.5 → Theorem 3.1), and the numerical section is supported by reproducible code. The main weakness is an unstated monotonicity requirement on the subproblem solver in Step 2, without which Lemma 4.1 and therefore the main theorem do not follow. This is a correctness issue rather than a stylistic one, but it appears repairable by adding an explicit descent condition or by reworking Lemma 4.1.","major_comments":[{"comment":"The proof of (4.1) implicitly assumes that the subproblem solver returns a point whose augmented Lagrangian value is no larger than the value at the warm start x̂_k. Step 2 only requires the ε-stationarity condition (3.3). For a nonconvex subproblem, an ε-stationary point can have a strictly larger value than the starting point; approximate stationarity does not control function value. Step 1 ensures L(x̂_k)+f2(x̂_k) ≤ f(x0)+1/(2γ_k)||x0-x_k||², but nothing in Steps 1–2 ensures L(x_{k+1})+f2(x_{k+1}) ≤ L(x̂_k)+f2(x̂_k). Thus Lemma 4.1 is not a consequence of the stated algorithm. Since (4.1) is used in Theorem 4.2(i)–(ii), Lemma 4.4, Theorem 4.5, and Theorem 3.1, the central ε-KKT termination claim is currently unsupported. A repair would be to add an explicit condition in Step 2, e.g., L(x_{k+1})+f2(x_{k+1}) ≤ L(x̂_k)+f2(x̂_k), or an equivalent bounded-increase condition. The same issue","section":"Algorithm 1, Step 2; Lemma 4.1 (Eq. (4.1))"},{"comment":"In the paragraph beginning 'Alternatively, if T(k)=k+1', the inequality '||E_{k+1}||∞ ≥ β||E_k||∞' for k+1∉Kν has the wrong direction. From definition (4.7), k+1∉Kν means ||E_{k+1}||∞ ≤ β||E_k||∞. Consequently, the sentence 'showing that lim_{Kν∋k→∞} ||E_k||²=0' is not justified. The claim can be repaired: Lemma 4.4(i) already gives ||E_{k+1}||→0 along Kν, and shifting the subsequence by one yields the required index set. Nevertheless, the proof as written contains a load-bearing error in a central argument and needs correction.","section":"Theorem 4.5, Case 3, second alternative"}],"minor_comments":[{"comment":"The final sentence says the iterates 'converge to an ε-KKT point after a finite number of iterations.' The proof actually establishes an infinite subsequence of ε-KKT iterates, not convergence of the whole sequence. Please rephrase to match the argument; the same wording appears in Corollary 5.2.","section":"Proof of Theorem 3.1"},{"comment":"The notation for γ is inconsistent: (3.4) defines γ_k = max{δ||x0-x_k||², γ0 φ(k)}, while Algorithm 1 Step 7 defines γ_{k+1} = max{δ||x0-x_{k+1}||², γ̂ φ(k+1)}. Please harmonize the indexing and constants (γ0 vs γ̂).","section":"Section 3, Eq. (3.4) vs Algorithm 1 Step 7"},{"comment":"The requirement 'λ0∈R^p_+' is unusual for equality-constraint multipliers, which are not restricted in sign. If nonnegativity is not needed, use λ0∈R^p; if it is intentional, please justify.","section":"Algorithm 1, Require line"},{"comment":"The captions do not describe line styles, colors, or markers. Please add a legend or otherwise make the curves identifiable without relying on the text alone.","section":"Figures 2–5"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of the journal. The main issue is the unstated descent property in the subproblem solve; once added or proved differently, the results are likely sound. The Theorem 4.5 sign error is repairable. I do not see a fundamental novelty problem, and I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nQuick take: this is a genuinely useful extension of ALM/P-ALM convergence analysis to general nonlinear equality and inequality constraints with a nonsmooth convex term, and the adaptive penalty/proximal update rules are practically motivated. The proof chain is clear and mostly correct. But the central theorem rests on an unstated descent assumption on the subproblem solves: Lemma 4.1's upper bound only follows if the value of the augmented Lagrangian at x_{k+1} does not exceed the warm-start value. The algorithm only enforces an ε-stationarity residual (3.3), which for a nonconvex subproblem does not control function value. Without an explicit non-increase (or bounded-increase) condition in Step 2, the multiplier bound (Theorem 4.2) and everything downstream—Lemma 4.4, Theorem 4.5, Theorem 3.1—loses support. This is a real gap, not a minor technicality.\n\nWhat is new and good: the paper extends prior ALM results (Grapiglia-Yuan, Evens et al.) to the proximal variant with general constraints, gives a clean finite-time ε-KKT guarantee, and proposes easily implementable superlinear penalty growth rules that mitigate ill-conditioning. The derivation is direct and the assumptions are mild (initial feasible point, lower bounded objective, smooth constraints). The numerical section on Maros-Mészáros QPs and basis pursuit is suggestive, though limited: few instances, no variance, single solver (PANOC). That's a minor weakness relative to the proof gap.\n\nI checked the stress-test note against the text and I agree with it: Step 1 bounds the value at x̂_k, but Step 2 does not ensure the value at x_{k+1} is no larger. The paper claims Lemma 4.1 is \"a trivial consequence of the initialization,\" but that's only true if the subproblem solver produces descent. The fix is simple—add a value-check or a monotonicity requirement to Step 2—but as written the main theorem is unsupported.\n\nVerdict: worth serious refereeing. The paper is clear, honest, and the core idea is valuable. A referee should ask the authors to state the descent condition explicitly (or prove Lemma 4.1 another way) before the result can be accepted. I'd cite it for the adaptive update rules, but not for the ε-KKT theorem until the gap is closed.\n\nBest, [signed]","headline":"Useful extension of ALM/P-ALM theory with adaptive penalty rules, but the main theorem depends on an unstated descent condition on subproblem solves that the algorithm as written does not guarantee.","tokens_in":21664,"tokens_out":2591,"would_cite":false,"duration_ms":27792,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K05","93-08","49M37","90C06","90C53"],"pacs":[],"model":"deepseek-v4-flash","headline":"An inexact proximal augmented Lagrangian method is shown to reach an approximate KKT point in finitely many iterations for nonconvex problems with equality and inequality constraints, given a feasible starting point and mild growth conditio","keywords":["augmented Lagrangian method","proximal augmented Lagrangian","nonconvex optimization","equality and inequality constraints","adaptive penalty parameters","epsilon-KKT","initial feasible point","inexact optimization"],"falsifier":"Run P-BALM exactly as stated but with an inner solver that stops at an approximately stationary point of subproblem (3.2) without checking whether its objective value exceeds the warm start. On a nonconvex problem where such a point has higher value than x_hat_k, record whether inequality (4.1) holds at that iteration; a single violation, or a consequent failure of the multiplier bound (4.2), would show the stated assumptions are insufficient as written.","tokens_in":20747,"feed_emoji":"🎯","tokens_out":6564,"duration_ms":73625,"temperature":0.7,"pith_summary":"P-BALM is an inexact proximal augmented Lagrangian method designed for nonconvex optimization problems that may include nonlinear equality and inequality constraints plus a convex regularizer. The paper's central claim is that, under standard smoothness and lower-boundedness assumptions, having an initial feasible point lets the method provably return an epsilon-KKT point in finitely many iterations. What makes this useful is that the penalty parameters can grow polynomially—quickly early, slowly later—which mitigates the ill-conditioning associated with traditional linear penalty increases, while the proximal term is adaptively tuned. The same convergence guarantees carry over to the classical non-proximal augmented Lagrangian method as a special case, extending earlier analyses that were limited to equality constraints or required multipliers to vanish.","feed_headline":"Adaptive penalties give nonconvex ALM a finite near-KKT guarantee","feed_subtitle":"Starting from a feasible point, the new rules control the Lagrangian and cover the classical ALM too.","key_machinery":"The central object is the proximal augmented Lagrangian function L_{rho,nu,gamma}(x,lambda,mu;v) = f1(x) + <lambda,h(x)> + (rho/2)||h(x)||^2 + (1/(2 nu))||max{0, nu g(x)+mu}||^2 - (1/(2 nu))||mu||^2 + (1/(2 gamma))||x-v||^2, with the convex term f2 kept separate. Algorithm 1 updates the penalty parameters rho_k and nu_k by increasing them only when the constraint-violation or complementarity surrogate fails to improve by factor beta, using a growth function phi satisfying Assumption II, e.g., phi(k)=(k+1)^alpha with alpha>1. The proximal parameter gamma_k is set to max{delta||x0-x_k||^2, gamma_hat phi(k)}, giving stronger regularization early and a gradual transition toward plain ALM. Lemma","core_discovery":"Theorem 3.1 states that for P-BALM, under Assumptions I and II, three conclusions hold: (i) the scaled primal step (1/gamma_k)||x_{k+1}-x_k||^2 converges to zero; (ii) along an infinite subsequence, the scaled multiplier differences tend to zero; and (iii) an epsilon-KKT point of the original problem is obtained after finitely many iterations for any epsilon > tau. The proof hinges on a simple but central control property: Lemma 4.1 shows that the proximal augmented Lagrangian at each new iterate is bounded above by f(x0) + (1/(2 gamma_k))||x0-x_k||^2, provided the iterates start from a feasible point. This bound feeds a multiplier-control inequality, which forces the primal residual to vani","pith_inferences":["The finite-time epsilon-KKT statement is a termination guarantee, not an iteration-complexity rate; a natural follow-up, which the paper notes as future work, is to bound how many iterations are needed as a function of epsilon, tau, and the constants in Lemma 4.1.","The proof implicitly relies on each subproblem solve not increasing the proximal Lagrangian value relative to its warm start; since Algorithm 1 only asks for an approximately stationary point, a solver that returns a higher-value stationary point may break Lemma 4.1's bound. A testable safeguard is to monitor that value each iteration and restart from x0 if it rises.","Because delta in the gamma_k update can be set very small (e.g., 10^-6 in the basis pursuit experiment), the proximal term can be made nearly inactive on well-behaved problems, suggesting a practical continuum between P-BALM and BALM that could be tuned per problem.","Block-diagonal penalty matrices are noted as an immediate extension; a matrix-valued proximal parameter with its own update rule is left open and is a plausible direction for better conditioning."],"forward_implications":["With phi(k)=(k+1)^alpha for alpha>1, practitioners can grow penalty parameters aggressively in early iterations and only sublinearly later, reducing ill-conditioning while still guaranteeing finite epsilon-KKT termination.","The proximal parameter gamma_k is not fixed: it adapts to the distance from the initial feasible point, so early iterates receive strong regularization and later iterates behave like standard ALM iterates.","The classical non-proximal augmented Lagrangian method (BALM) inherits the same convergence conclusions, covering nonlinear equality and inequality constraints plus a nonsmooth convex term.","A feasible starting point, which the theory requires, can be produced by the phase-I construction in Appendix A, making the method applicable even when no natural feasible point exists.","The practical stopping criterion, max{||h(x_k)||_inf, ||E_k||_inf} <= 10^-5, is directly aligned with the theoretical epsilon-KKT condition."],"supporting_citations":[{"why":"Rockafellar's formulation of ALM as a proximal point method supplies the multiplier update structure in (1.2).","marker":"[20]"},{"why":"Rockafellar's proximal point algorithm underlies the P-ALM iterates written compactly in (2.3).","marker":"[21]"},{"why":"Supplies the inexactness framework of solving subproblems up to a fixed stationarity tolerance, adopted in Step 2.","marker":"[33]"},{"why":"Provides the epsilon-KKT optimality notion and Lemma 4.6's complementarity surrogate, both load-bearing for the termination certificate.","marker":"[34]"},{"why":"Grapiglia and Yuan's nonconvex ALM complexity analysis is a direct precursor, but its multiplier-zero requirement is the limitation this paper resolves.","marker":"[35]"},{"why":"Evens et al.'s equality-constrained ALM analysis is the starting point that this paper generalizes to inequality constraints and the proximal variant.","marker":"[5]"},{"why":"Birgin and Martinez's book supplies the fact that an initial feasible point makes the augmented Lagrangian bounded, supporting Lemma 4.1.","marker":"[36]"}],"fun_headline_variants":["Adaptive penalties give finite near-KKT for nonconvex ALM","Proximal ALM with adaptive updates guarantees finite epsilon-KKT","Finite epsilon-KKT achieved by adaptive proximal ALM","Adaptive ALM: finite near-KKT without ill-conditioning","Finite near-KKT for nonconvex via adaptive proximal ALM"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The proof needs each subproblem solve to return a point whose proximal-Lagrangian value is no larger than the warm start it began from; the algorithm only requires that the point be approximately stationary, and for a nonconvex subproblem such a point can have a higher value. If that happens, the key upper bound on the augmented Lagrangian and the convergence argument built on it no longer follow from the stated assumptions.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive penalties give finite near-KKT for nonconvex ALM","Proximal ALM with adaptive updates guarantees finite epsilon-KKT","Finite epsilon-KKT achieved by adaptive proximal ALM","Adaptive ALM: finite near-KKT without ill-conditioning","Finite near-KKT for nonconvex via adaptive proximal ALM"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000974,"raw_usage":{"total_tokens":3966,"prompt_tokens":724,"completion_tokens":3242,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":468,"completion_tokens_details":{"reasoning_tokens":3151}},"tokens_in":468,"tokens_out":3242,"duration_ms":25570,"temperature":1.0,"reasoning_tokens":3151,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T11:18:06.295748+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run P-BALM exactly as stated but with an inner solver that stops at an approximately stationary point of subproblem (3.2) without checking whether its objective value exceeds the warm start. On a nonconvex problem where such a point has higher value than x_hat_k, record whether inequality (4.1) holds at that iteration; a single violation, or a consequent failure of the multiplier bound (4.2), would show the stated assumptions are insufficient as written.","supporting_citations":[{"cited_title":"Augmented Lagrangians and applications of the proximal point algorithm in convex programming.Mathematics of Operations Research, 1(2):97–116, 1976","cited_arxiv_id":null,"evidence_quote":"Rockafellar's formulation of ALM as a proximal point method supplies the multiplier update structure in (1.2)."},{"cited_title":"Monotone operators and the proximal point algorithm.SIAM Journal on Control and Optimization, 14(5):877–898, 1976","cited_arxiv_id":null,"evidence_quote":"Rockafellar's proximal point algorithm underlies the P-ALM iterates written compactly in (2.3)."},{"cited_title":"Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points.Computational Optimization and Applications, 69(1):51–75, 2018","cited_arxiv_id":null,"evidence_quote":"Supplies the inexactness framework of solving subproblems up to a fixed stationarity tolerance, adopted in Step 2."},{"cited_title":"Complexity and performance of an augmented Lagrangian algorithm","cited_arxiv_id":null,"evidence_quote":"Provides the epsilon-KKT optimality notion and Lemma 4.6's complementarity surrogate, both load-bearing for the termination certificate."},{"cited_title":"On the complexity of an augmented Lagrangian method for nonconvex optimization.IMA Journal of Numerical Analysis, 41(2):1546–1568, 2021","cited_arxiv_id":null,"evidence_quote":"Grapiglia and Yuan's nonconvex ALM complexity analysis is a direct precursor, but its multiplier-zero requirement is the limitation this paper resolves."},{"cited_title":"Neural network training as an optimal control problem—An augmented Lagrangian approach","cited_arxiv_id":null,"evidence_quote":"Evens et al.'s equality-constrained ALM analysis is the starting point that this paper generalizes to inequality constraints and the proximal variant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Birgin and Martinez's book supplies the fact that an initial feasible point makes the augmented Lagrangian bounded, supporting Lemma 4.1."}],"review_version":1}