{"id":"fd303d24-45b5-47d7-a178-352eaef775dd","arxiv_id":"1908.06118","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Levenberg-Marquardt method using inexact feasible projections converges linearly, and superlinearly when projection errors vanish, for constrained nonlinear systems under an error bound condition.","lead":"This paper presents Levenberg-Marquardt algorithms for constrained nonlinear systems that accept approximate, feasible projections instead of exact ones. The methods come with local and global convergence proofs, and numerical tests show large time savings on spectrahedron problems when exact projections are costly.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"G-LMM-IP Step 2 can choose a search direction that points outside the feasible set, so the global convergence proof of Theorem 10 is missing a feasibility invariant.","rationale":"The local LMM-IP analysis in Section 2 appears internally coherent: Proposition 1 controls the inexact-projection error, and Lemma 4 together with Assumptions (A1)-(A2) yields the contraction behind Theorem 7. The reader's concern about (A2) failing on the boundary is a limitation that the paper itself acknowledges, not a defect in the proof. The more serious, load-bearing issue is in the global method. Step 2 flips the projected Levenberg-Marquardt direction whenever its inner product with the gradient has the wrong sign, but dbar_k is the only feasible direction from x_k; its negative is not generally in the tangent cone of a convex set. Since the line search has no feasibility guard and the proof of Theorem 10 never shows x_k + alpha d_k in C, the iterates can leave the feasible set, and the claimed stationarity of accumulation points for the constrained problem is not proven. This is an internal inconsistency in the global algorithm, not a disagreement with prior results. It is fixable by using a one-sided descent test in Step 2, but as written the central global convergence claim is not valid. Therefore the paper should not be accepted in its current form; a corrected version would need to restore the feasibility invariant before Theorem 10 can be trusted.","tokens_in":18706,"tokens_out":25885,"duration_ms":247630,"concrete_test":"Instrument G-LMM-IP with an assertion after Step 4 that x_k + alpha_k d_k is in C, and run the method on C = {x in R^2 : ||x|| <= 1} with x_0 = (1,0) and an F for which the unconstrained Levenberg-Marquardt point has negative radial and positive tangential components, so that Step 2's dbar_k has positive inner product with grad f and the algorithm flips the direction. A direct norm check shows x_0 + alpha d_k leaves the ball for every alpha > 0, confirming the feasibility gap. Running the Section 4 box and spectrahedron tests with the same assertion will reveal whether the sign flip is ever selected; any violation settles that Theorem 10, as stated, is not established.","verdict_should_be":"REJECT","load_bearing_attack":"In the global method (Section 3), Step 2 defines dbar_k = P_C(x_k + dU_k, eps_k) - x_k and, whenever |<grad f(x_k), dbar_k>| > eta1 ||dbar_k||^2, sets d_k = -sgn(<grad f, dbar_k>) dbar_k. For a convex C, only dbar_k is a feasible direction from x_k, since y = P_C(x_k + dU_k, eps_k) belongs to C and x_k + alpha dbar_k is a convex combination of x_k and y for alpha in [0,1]. When <grad f(x_k), dbar_k> is positive, the algorithm takes d_k = -dbar_k, and x_k + alpha d_k = x_k - alpha(y - x_k) is generally outside C for every alpha > 0. For example, with C = {x in R^2 : ||x|| <= 1}, x_k = (1,0), and y = (1 - eps, t) with eps > 0, the point x_k + alpha(y - x_k) has norm greater than 1, while x_k - alpha(y - x_k) leaves the ball for all positive alpha. Step 4 then evaluates f at infeasible points, which may even lie outside the domain Omega, and the proof of Theorem 10 never establishes that x_k + alpha d_k lies in C. The gradient-related inequalities (38)-(39) control only descent and angle, not feasibility of the trial segment. Consequently the invariant x_k in C, which is used in Proposition 1 and in the proof of (39), can be lost, and the assertion that accumulation points are stationary for the constrained problem is not proven. The flaw is repairable by accepting dbar_k only when <grad f(x_k), dbar_k> <= -eta1 ||dbar_k||^2 and otherwise switching to the projected-gradient direction of Step 3, but as written the global method is not a feasible constrained algorithm.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Levenberg-Marquardt methods for constrained nonlinear systems F(x)=0, x∈C, where the projection onto the closed convex set C is allowed to be inexact in the sense of Definition 1. The local method LMM-IP projects x_k+dU_k onto C with tolerance θ_k^2||dU_k||^2 and, under a Lipschitz Jacobian assumption and a local error bound (A2), proves that dist(x_k,C*) converges to zero linearly, superlinearly if θ_k→0, and that the iterates converge to a solution; Theorem 9 adds linear/superlinear rates for the iterates themselves. The global method G-LMM-IP combines the LM step with a nonmonotone line search and safeguarded inexact projected-gradient steps, claiming that every accumulation point is stationary for min_{x∈C} ||F(x)||^2/2. Numerical experiments compare exact and inexact projections on box-constrained systems and on systems over the spectrahedron.","tokens_in":19119,"tokens_out":15127,"duration_ms":142943,"significance":"The local convergence theory is the strongest part of the paper. Definition 1 is a practical and natural notion of inexact projection, Proposition 1 gives a clean Lipschitz-type estimate for it, and Lemmas 4 and 6 correctly propagate the local error-bound estimates. The paper would be a useful extension of the projected Levenberg-Marquardt analyses of Kanzow-Yamashita-Fukushima and others, and the spectrahedron experiments give a concrete setting where inexact projections pay off. However, the global method as stated contains a load-bearing feasibility flaw: Step 2 may select a search direction that points outside C, so the invariant x_k∈C used throughout the proof of Theorem 10 is not maintained. This is a substantive defect in the global convergence claim, though it appears repairable by modifying Step 2.","major_comments":[{"comment":"The global algorithm is not a feasible constrained method as written. In Step 2, dbar_k=PC(x_k+dU_k,ε_k)-x_k is a feasible direction from x_k because x_k∈C and PC(x_k+dU_k,ε_k)∈C, so x_k+α dbar_k∈C for α∈[0,1]. But when ⟨∇f(x_k),dbar_k⟩>0, the algorithm sets d_k=-dbar_k, and x_k+α d_k = x_k-α(y_k-x_k) leaves the convex set C for every α>0 in general. Step 4 evaluates f at x_k+α d_k without any feasibility check. Consequently the invariant x_k∈C, which is used in the proof of (38)-(39) (for example, to assert PC(x_k)=x_k in the lower bound of (39)), can be lost, and the proof of Theorem 10 never establishes that the trial points lie in C. The stationarity conclusion is therefore not proven for the algorithm as stated. This issue occurs even for exact projections θ_k=0. A repair would be to accept dbar_k only when it is a descent direction, e.g. ⟨∇f(x_k),dbar_k⟩≤-η_1||dbar_k||², and otherwise to switch to the projected-gradient step of Step 3; alternatively, the line search must explicitly enforce x_k+α d_k∈C and d_k must be a feasible direction.","section":"Section 3, G-LMM-IP Step 2 and Theorem 10"}],"minor_comments":[{"comment":"The displayed inequality in (32) has α_1 c_1^2 c_3 ||x_k-xbar||, but substituting Lemma 8(b) and Lemma 8(c) gives α_1 c_1^3 c_3 ||x_k-xbar||. As printed, Eq. (32) is inconsistent with the rate constant 4c_1^3(1+α_1)^2/(1-2α_1c_1) stated in Theorem 9; please correct the typo.","section":"Theorem 9, proof, Eq. (32)"},{"comment":"The column header γ denotes the starting-point parameter a∈{0,1/2,1}, not the line-search parameter γ introduced in Step 0 of G-LMM-IP. Rename the column to avoid confusion.","section":"Table 3"},{"comment":"The sentence 'as for these instances we known the rank' contains a grammatical error: it should read 'we know the rank'.","section":"Section 4.2"},{"comment":"The phrase 'Definition (1)' should be 'Definition 1' for consistency with the rest of the paper.","section":"Remark 1(i)"}],"recommendation":"major_revision","confidential_remarks":"The global-convergence flaw in Step 2 is substantial but localized: it concerns the sign of dbar_k and the feasibility of the trial segment, and it can likely be repaired without changing the local analysis, which appears sound. I would not reject on this basis if the authors can implement the fix and update Theorem 10 accordingly. The authors should also correct the Eq. (32) coefficient typo and check the global proof for other places where PC(x_k)=x_k is used implicitly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The local half of this paper is solid; the global half has a load-bearing gap that the authors should fix. The stress-test note is right, and the reader's report missed it.\n\nWhat's actually new: the paper defines a feasible inexact projection via a relaxed variational inequality (Definition 1) and analyzes a Levenberg-Marquardt method that uses it in place of the exact projection. The local convergence analysis under the error bound (A2) follows the Yamashita-Fukushima/Kanzow framework, and the proofs are coherent. I checked the key estimates in Lemma 4 and the invariant-ball argument in Lemma 6; they hold. The numerical experiments, especially the Frank-Wolfe/rank-limited projection on the spectrahedron, give a real practical motivation and the time savings look plausible.\n\nSoft spots, in proportion:\n\n1. The global method (G-LMM-IP) as written is not feasible for convex C. In Step 2, if the gradient inner product with dbar_k is positive, the algorithm sets d_k = -dbar_k. Since dbar_k points into C from x_k, its negative points out. The line search then evaluates f at points outside C, possibly outside the domain Omega, and Theorem 10's proof never establishes the invariant x_k in C. The proof uses that invariant to derive the projected-gradient bound and to apply Proposition 1, so this is not a cosmetic issue. The fix is easy: accept dbar_k only when ⟨∇f(x_k), dbar_k⟩ ≤ -η1||dbar_k||^2, and otherwise fall back to Step 3's projected gradient direction. But as written, the global convergence claim is not proven.\n\n2. The distinction from Behling et al. (2014) on approximate projections is not stated clearly. The reader's report flagged this and I agree.\n\n3. Minor typo/inconsistency in Theorem 9: the displayed rate constant has c1^3 while the inequality just above it suggests c1^2. The qualitative superlinear/linear rates still go through by continuity, but the constant should be corrected.\n\nNo code and only a few numerical runs, but that is minor for this type of paper.\n\nWho gets value: researchers working on projected Levenberg-Marquardt, error-bound conditions, and inexact projections for constrained systems. The local method is a useful extension, and the spectrahedron experiments make a nice case study. The paper deserves a serious referee; the global bug is repairable, and the local part alone is a reasonable contribution. I would send it out with a clear request to fix the global method.\n\nRecommended verdict: revise and resubmit from the reviewer's perspective, with the global method corrected.","headline":"The local method is sound, but the global method has a feasibility bug in Step 2 that leaves Theorem 10 unproven; fixable, but the paper needs revision.","tokens_in":19661,"tokens_out":8314,"would_cite":true,"duration_ms":74916,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65H10","65K05","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that inexact projections preserve Levenberg-Marquardt convergence for constrained nonlinear systems, with linear rates under an error bound and superlinear rates when projection errors vanish.","keywords":["constrained nonlinear systems","Levenberg-Marquardt method","inexact projections","error bound condition","local convergence","global convergence","nonmonotone line search","spectrahedron"],"falsifier":"Construct a smooth $F$ whose zero lies on the boundary of $C$ and for which $\\|F(x)\\|/\\operatorname{dist}(x,C^*)\\to 0$ as $x\\to x^*$, so that (A2) fails, start the LMM-IP at points arbitrarily close to $x^*$, and check whether $\\operatorname{dist}(x_k,C^*)$ still decreases linearly. A direct observable is the ratio $\\|F(x_k)\\|/\\operatorname{dist}(x_k,C^*)$ along iterates: if it tends to zero while the distance to $C^*$ also decreases linearly, the error-bound condition is doing none of the work, and the theorem's stated assumption is not necessary in that case.","tokens_in":18505,"feed_emoji":"📉","tokens_out":8258,"duration_ms":71939,"temperature":0.7,"pith_summary":"This paper attempts to establish that Levenberg-Marquardt methods for constrained nonlinear systems $F(x)=0$, $x\\in C$, remain convergent when the projection onto the feasible set $C$ is computed only approximately. The central device is the feasible $\\varepsilon$-projection of Definition 1: a point of $C$ that satisfies the projection variational inequality up to a tolerance $\\varepsilon$. The authors prove that, under a local error bound weaker than full-rank of the Jacobian, the distance $\\operatorname{dist}(x_k,C^*)$ to the solution set decreases linearly, and superlinearly when the projection tolerances tend to zero (Theorem 7). A globalized version, using a line search that permits occasional increases in the merit function $\\|F(x)\\|^2/2$, is shown to have every accumulation point stationary for that merit function (Theorem 10). The motivation, confirmed by numerical experiments on box-constrained systems and on systems over the spectrahedron, is that exact projections are often the expensive step, and approximate ones can preserve the theory while saving substantial computation time.","feed_headline":"Inexact projections keep Levenberg-Marquardt convergence intact","feed_subtitle":"Constrained nonlinear systems still solve linearly, even superlinearly, when projection errors shrink to zero.","key_machinery":"The load-bearing object is the feasible $\\varepsilon$-projection: for $x\\in\\mathbb{R}^n$ and $\\varepsilon\\ge 0$, a point $P_C(x,\\varepsilon)\\in C$ satisfying $\\langle x-P_C(x,\\varepsilon),\\, y-P_C(x,\\varepsilon)\\rangle\\le\\varepsilon$ for all $y\\in C$. This relaxes the variational characterization of the orthogonal projection while keeping the output feasible, so approximate projection oracles can be used. The method's step is the unconstrained Levenberg-Marquardt direction $d_k^U$ solving $(F'(x_k)^TF'(x_k)+\\mu_k I)d=-F'(x_k)^TF(x_k)$ with $\\mu_k=\\|F(x_k)\\|^2$, followed by an $\\varepsilon_k$-projection with $\\varepsilon_k=\\theta_k^2\\|d_k^U\\|^2$. The proof engine is a one-step estimate (Lemma 4) bounding $\\operatorname{dist}(x_{k+1},C^*)$ by $\\theta_k c_1\\operatorname{dist}(x_k,C^*)$ plus a quadratic term, with constants $c_1,c_2$ coming from the Lipschitz constant and the error-bound constant $\\omega$. This estimate turns the local error bound (A2) into contraction, replacing the usual full-rank assumption.","core_discovery":"The paper's core claim is that the local convergence theory of projected Levenberg-Marquardt extends to a setting where the projection operator is replaced by a feasible $\\varepsilon$-projection $P_C(x,\\varepsilon)$. With $x_0$ sufficiently close to a solution $x_*$, tolerances $\\theta_k\\le\\bar\\theta<1/c_1$, and the local error bound $\\omega\\,\\operatorname{dist}(x,C^*)\\le\\|F(x)\\|$, the iterates satisfy a one-step contraction that gives linear convergence of $\\operatorname{dist}(x_k,C^*)$ to zero; if $\\theta_k\\to 0$, the rate becomes superlinear, and the iterates converge to a point of $C^*$ (Theorem 7). For the global method, the paper claims that every accumulation point is stationary for $\\min_{x\\in C}\\|F(x)\\|^2/2$ (Theorem 10). In both cases the argument runs through the error-bound condition rather than through full-rank Jacobians, so underdetermined and rank-deficient systems are covered as long as the error bound holds.","pith_inferences":["My inference: the $\\theta_k\\to 0$ condition translates into a concrete budget for the inner projection solver—only logarithmically many extra inner iterations should be needed as the outer iterates converge, which is why even fixed modest accuracy was enough in the reported spectrahedron tests.","My inference: the analysis is agnostic to how the $\\varepsilon$-projection is computed, so the same convergence theorems should carry over to randomized or sketching-based projection oracles, as long as the variational inequality of Definition 1 is approximately satisfied.","My inference: the boundary-zero caveat on the error bound suggests that a natural follow-up is an active-set or merit-function correction that restores linear convergence when $C^*$ meets the boundary of $C$."],"forward_implications":["Projected Levenberg-Marquardt works with iterative, approximate projection solvers, so feasible sets whose exact projections are costly become tractable.","The methods solve underdetermined and rank-deficient systems under the local error bound, not only systems with full-rank Jacobians.","When projection tolerances are driven to zero ($\\theta_k\\to 0$), distance-to-solution convergence improves from linear to superlinear, and the iterates themselves converge to a solution.","The globalized method, with a nonmonotone line search, yields stationary points of $\\|F(x)\\|^2/2$ from any starting point whose sublevel set is bounded, giving a practical general solver."],"supporting_citations":[{"why":"It supplies the constrained error-bound framework and the projected Levenberg-Marquardt analysis this paper builds on.","marker":"[1]"},{"why":"It is earlier work on Levenberg-Marquardt with approximate projections, the setting this paper extends.","marker":"[2]"},{"why":"It supplies the local error bound condition (A2) and the projected LM method whose convergence the inexact version generalizes.","marker":"[9]"},{"why":"It gives the unconstrained LM estimates (13)–(14) used as the core step-size bounds in Lemma 4.","marker":"[24]"},{"why":"It describes the conditional-gradient method used to obtain feasible $\\varepsilon$-projections in Definition 1.","marker":"[25]"},{"why":"It provides the nonmonotone line-search technique whose proof structure is adapted for the global convergence theorem.","marker":"[26]"},{"why":"It is the rank-restricted conditional-gradient variant used in the spectrahedron experiments to compute inexact projections efficiently.","marker":"[32]"}],"fun_headline_variants":["Inexact-projection LM converges via error bound, not full rank","LM with inexact projections: linear+superlinear, no full-rank needed","Projected LM: error-bound condition suffices, rank-deficiency OK","Nonmonotone line search gives global convergence for projected LM"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The local-rate results stand on the local error bound $\\omega\\,\\operatorname{dist}(x,C^*)\\le\\|F(x)\\|$ near a solution, and the paper itself notes this bound may fail for solutions on the boundary of $C$; if it fails, the linear and superlinear convergence claims are not established.","fun_headline_variants_meta":{"raw":{"variants":["Inexact-projection LM converges via error bound, not full rank","LM with inexact projections: linear+superlinear, no full-rank needed","Projected LM: error-bound condition suffices, rank-deficiency OK","Nonmonotone line search gives global convergence for projected LM"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000811,"raw_usage":{"total_tokens":3517,"prompt_tokens":867,"completion_tokens":2650,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":483,"completion_tokens_details":{"reasoning_tokens":2572}},"tokens_in":483,"tokens_out":2650,"duration_ms":20795,"temperature":1.0,"reasoning_tokens":2572,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:56:23.073567+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a smooth $F$ whose zero lies on the boundary of $C$ and for which $\\|F(x)\\|/\\operatorname{dist}(x,C^*)\\to 0$ as $x\\to x^*$, so that (A2) fails, start the LMM-IP at points arbitrarily close to $x^*$, and check whether $\\operatorname{dist}(x_k,C^*)$ still decreases linearly. A direct observable is the ratio $\\|F(x_k)\\|/\\operatorname{dist}(x_k,C^*)$ along iterates: if it tends to zero while the distance to $C^*$ also decreases linearly, the error-bound condition is doing none of the work, and the theorem's stated assumption is not necessary in that case.","supporting_citations":[{"cited_title":"Behling, A","cited_arxiv_id":null,"evidence_quote":"It supplies the constrained error-bound framework and the projected Levenberg-Marquardt analysis this paper builds on."},{"cited_title":"Behling, A","cited_arxiv_id":null,"evidence_quote":"It is earlier work on Levenberg-Marquardt with approximate projections, the setting this paper extends."},{"cited_title":"Kanzow, N","cited_arxiv_id":null,"evidence_quote":"It supplies the local error bound condition (A2) and the projected LM method whose convergence the inexact version generalizes."},{"cited_title":"Yamashita, M","cited_arxiv_id":null,"evidence_quote":"It gives the unconstrained LM estimates (13)–(14) used as the core step-size bounds in Lemma 4."},{"cited_title":"Jaggi, Revisiting Frank-Wolfe: Projection-free sparse con vex optimiza- tion, in: Proceedings of the 30th International Conference on Ma chine Learning (ICML-13), Vol","cited_arxiv_id":null,"evidence_quote":"It describes the conditional-gradient method used to obtain feasible $\\varepsilon$-projections in Definition 1."},{"cited_title":"Grippo, F","cited_arxiv_id":null,"evidence_quote":"It provides the nonmonotone line-search technique whose proof structure is adapted for the global convergence theorem."},{"cited_title":"Allen-Zhu, E","cited_arxiv_id":null,"evidence_quote":"It is the rank-restricted conditional-gradient variant used in the spectrahedron experiments to compute inexact projections efficiently."}],"review_version":1}