{"id":"ccbd2571-095c-4f4f-86fd-652f258302e5","arxiv_id":"2505.21232","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A linear program is solved by minimizing a single convex twice-differentiable function whose zero set equals the primal-dual optimal solution set.","lead":"Linear programs can be rewritten as one smooth unconstrained minimization problem whose minimum is exactly the optimal solution. The paper proves a regularized Newton method reaches that minimum in a bounded number of steps, and tests it on random problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified to the central convergence theorem; a non-central Hessian claim in Section 4.2 is overstated.","rationale":"The reader's principal concern does not land: the bounded-sublevel-set condition follows from a standard convexity fact, so Theorem 3.2's proof is sound. I nevertheless found a real but non-central error in Section 4.2: the modified merit function's Hessian is not always nonsingular. Since Algorithm 2 is explicitly heuristic and still uses a tiny mu I safeguard, this error does not invalidate the main convergence theorem. The verdict can remain CONDITIONAL, but the condition should now include correcting the positive-definiteness claim rather than questioning bounded level sets. The numerical experiments remain limited to one draw per problem with no solver baseline, which is another reason not to upgrade to ACCEPT.","tokens_in":18318,"tokens_out":26156,"duration_ms":330367,"concrete_test":"Symbolically form the Hessian of h_{q,nu} from (HMF) at (x, lambda, s) = (0, 0, 0) with n = 2, m = 1, A = [1 1], c = [1 1], b = 1, and multiply it by d = (1, -1, 0, 0). Verify that the quadratic form is exactly zero for every nu > 0. If it is zero, revise the positive-definiteness assertion in Section 4.2, for example by adding nu||x||^2 + nu||s||^2 terms or by weakening the claim to positive semidefiniteness away from x = s = 0.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Theorem 3.2 is supported. The bounded-level-set step that the reader questions is actually valid: for a convex function on R^{2n+m} whose minimizer set is nonempty and bounded, every sublevel set is bounded. If a sublevel set were unbounded, its recession cone would contain a nonzero direction d; since the minimizer set lies in that sublevel set, convexity along x* + t d forces the function to be constant along that ray, making the minimizer set unbounded. Thus bounded LP optimal set, which equals the argmin of f3 by Theorem 2.1, implies Mishchenko's Assumption 2. The paper should prove this lemma explicitly, but it is not a gap in the argument.\n\nA separate, non-central error: Section 4.2 claims the Hessian of h_{q,nu} in (HMF) is positive definite for all nu > 0. This is false. At x = s = 0, the added nu-terms contribute zero diagonal entries in the x and s blocks. With n = 2, m = 1, A = [1 1], c = [1 1], b = 1, the direction d = (1, -1, 0, 0) satisfies A d = 0 and c^T d = 0 and has zero lambda component, so d^T nabla^2 h_{q,nu}(0,0,0) d = 0. The Hessian is singular. This affects the motivation for Algorithm 2, not Theorem 3.2.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an exact unconstrained reformulation of a primal-dual linear program in standard form, using a convex twice continuously differentiable merit function f_q (Eq. (MF)) that combines a squared duality gap, squared constraint residuals, and smoothed penalties for nonnegativity. Theorem 2.1 establishes that, when the LP has an optimal solution, the minimizers of f_q coincide with the LP optimal solutions and f_q attains zero there; Corollary 2.3 characterizes infeasible or unbounded cases by min f_q > 0. For q = 3 the Hessian is shown to be 1-Lipschitz (Lemma 2.7) but singular at optimal solutions. The main theoretical result (Theorem 3.2) applies Mishchenko's regularized Newton theorem to obtain an O(epsilon^{-3/2}) global iteration bound for reaching approximate primal-dual optimality conditions under the assumption that the LP optimal set is bounded. The paper further introduces a modified merit function h_{q,nu} (Eq. (HMF)) and a homotopy heuristic (Algorithm 2), supported by numerical experiments on random LPs.","tokens_in":18626,"tokens_out":11948,"duration_ms":118296,"significance":"The reformulation is elegant, and the main convergence theorem is a plausible and nontrivial corollary of existing regularized Newton theory, giving a smooth exact unconstrained formulation of LP with a provable global rate for a second-order method. The paper is careful in stating the zero-residual structure and provides a reproducible numerical study with available code. If the missing level-set lemma is supplied and the HMF Hessian claim is corrected, the contribution would be a useful addition to the literature on penalty and smoothing reformulations of LP. The worst-case rate O(epsilon^{-3/2}) is nonstandard and worth highlighting; the numerical experiments honestly show that the adaptive-mu variant is slow while the heuristic variants are faster, which is a useful empirical observation.","major_comments":[{"comment":"The proof asserts without proof that the boundedness of the LP optimal set implies boundedness of the initial sublevel set {f_3 <= f_3(x0, lambda0, s0)} and cites [39]. This implication is load-bearing because it is exactly Theorem 3.1's Assumption 2, and the manuscript does not state or prove the underlying lemma. Please add an explicit lemma: if f is convex and its argmin is nonempty and bounded, then every sublevel set {f <= a} is bounded; provide the proof (e.g., by showing that an unbounded sublevel set contains a nonzero recession direction along which convexity forces f to be constant, contradicting boundedness of the argmin). This will make the proof of Theorem 3.2 self-contained and verify the applicability of [39].","section":"Section 3.2, proof of Theorem 3.2"},{"comment":"The claim that the Hessian of h_{q,nu} is positive definite for all (x, lambda, s) when nu > 0 is false. At x = s = 0, the added terms nu ||lambda||^2 and nu/(q(q-1)) sum(max{x_j,0}^q + max{s_j,0}^q) contribute zero curvature in the x and s blocks. For example, with n = 2, m = 1, A = [1 1], c = [1 1]^T, b = 1, the direction d = (1, -1, 0, 0) at (0,0,0) satisfies A d = 0 and c^T d = 0, so d^T nabla^2 h_{q,nu}(0,0,0) d = 0. Thus the Hessian is singular for every nu > 0. This affects the abstract's claim of nonsingular Hessians and the motivation for Algorithm 2. Please correct the claim (for example, by adding a strong convexity term involving x and s, or by stating the actual positive semidefiniteness and singularity properties) and adjust the discussion of Algorithm 2 accordingly.","section":"Section 4.2, Eq. (HMF)"}],"minor_comments":[{"comment":"The proof uses the same symbol epsilon for the tolerance on f_3 (3.7) and for the tolerances on the optimality constraints (3.2)-(3.6). The iteration counts O(epsilon^{-1}) and O(epsilon^{-3/2}) are derived correctly, but the statement would be clearer if the target accuracy in the merit function were written as a separate parameter, say delta = O(epsilon^2) or O(epsilon^3), to avoid the appearance that O(epsilon^{-1/2}) directly yields all bounds.","section":"Section 3.2, Theorem 3.2"},{"comment":"Algorithms 1b and 2 use q = 2.1, but Lemma 2.7 and Theorem 3.2 are stated only for q = 3. The text should state explicitly that the experiments with q = 2.1 are heuristic and not covered by the theoretical rate.","section":"Table 1 and Section 4.3"},{"comment":"The conclusion that the problem is unbounded from the observed behavior (gradient approaching zero, f_q bounded away from zero, and ||Ax_k - b|| approaching zero) is a heuristic inference from the limit behavior of the iterates; a rigorous certificate would require the homogeneous formulation described in Section 2.1. Please soften the wording or add a remark that this is an empirical observation.","section":"Section 4.4"},{"comment":"The display in the proof of Lemma 2.7 has a small typographical error with double parentheses and a missing closing brace; please clean up the typesetting.","section":"Section 2.2, proof of Lemma 2.7"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is sound in substance, but the missing level-set lemma and the false positive-definiteness claim in Section 4.2 need to be addressed. The false Hessian claim is a clear mathematical error that should not survive in the published version. If the authors fix these points and tighten the presentation, the paper would be a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing before you read it. The central theoretical result is sound; the one false claim is off to the side. The merit function in (MF) is a genuinely new way to get an exact smooth unconstrained formulation of LP, and Theorem 2.1 is exactly what it appears to be. The regularized Newton analysis is imported from Mishchenko, but the import is legitimate: f3 has a 1-Lipschitz Hessian, and the bounded-sublevel-set condition follows for a convex function whose minimizer set is nonempty and bounded. The paper should prove that lemma instead of citing [39], but it is not a gap. I disagree with the reader's worry on that point.\n\nThe real soft spot is Section 4.2. The paper claims the Hessian of h_{q,nu} in (HMF) is positive definite for all nu > 0. That is false. At x = s = 0, the added nu-terms contribute nothing in the x and s blocks; with n = 2, m = 1, A = [1 1], c = [1 1], b = 1, the direction (1, -1, 0, 0) is in the null space. The stress-test counterexample checks out. This does not touch Theorem 3.2, but it does mean the motivation for Algorithm 2 is overstated.\n\nAlgorithm 2 itself is a heuristic: it has no convergence guarantee, and the homotopy parameter theta is tuned by trial and error. The authors admit both points in Section 6. The numerical experiments are one random draw per problem, with no solver baseline, so the speed claims are illustrative only. None of this breaks the paper, but the presentation should separate the proven part from the heuristic part more sharply.\n\nWho gets value from this: people working on exact penalty or smoothing reformulations, and anyone curious about unconstrained approaches to linear programming. It is not competitive with interior-point methods, and the paper does not claim it is. The citation pattern is clean, and the formal equivalence and rate result deserve credit.\n\nRecommendation: send it to peer review. It deserves a serious referee who can ask for the bounded-sublevel-set lemma to be proved, the Section 4.2 claim to be corrected, and the numerical section to be tightened. I would not desk-reject it.","headline":"The central equivalence and the global-rate theorem hold up, but a noncentral Hessian claim in Section 4.2 is false, and the practical claims outrun the evidence.","tokens_in":19152,"tokens_out":2330,"would_cite":false,"duration_ms":27871,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C05","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a primal-dual linear program is equivalent to a single unconstrained minimization of a smooth convex merit function, with a regularized Newton method reaching ε-accuracy in O(ε^{−3/2}) iterations.","keywords":["linear programming","primal-dual optimality","merit function","unconstrained minimization","Levenberg-Marquardt regularization","global convergence","zero residual problem","homotopy method"],"falsifier":"Run Algorithm 1 on a linear program whose optimal set is provably nonempty and bounded, starting from a point with large norm, and record how many iterations are needed to push the residuals below a decreasing sequence of tolerances $\\epsilon$. If the count grows faster than a constant times $\\epsilon^{-3/2}$, or if the iterates escape to infinity, Theorem 3.2's claim fails for that instance. A direct check of the proof mechanism is to test whether the sublevel set $\\{(x,\\lambda,s): f_3(x,\\lambda,s)\\le f_3(x_0,\\lambda_0,s_0)\\}$ is bounded for a family of LPs with bounded optimal sets.","tokens_in":18125,"feed_emoji":"🧮","tokens_out":12302,"duration_ms":112154,"temperature":0.7,"pith_summary":"The paper establishes that solving the primal-dual pair of linear programs is equivalent to one unconstrained minimization problem. The proposed merit function $f_q(x,\\lambda,s)$ is convex, twice continuously differentiable, nonnegative, and reaches zero exactly at primal-dual optimal solutions, so LP solving becomes a zero-residual unconstrained optimization over the whole space. The authors prove that a Newton method with Levenberg-Marquardt regularization attains primal and dual residuals below $\\epsilon$ in $O(\\epsilon^{-3/2})$ iterations whenever the LP optimal set is nonempty and bounded, and that the per-iteration linear system can be solved in $O(m^3+n^3)$ time. A modified merit function with a tunable parameter $\\nu>0$ keeps the Hessian nonsingular and yields a homotopy-style heuristic that converges faster in experiments. This gives an exact reformulation that needs no penalty parameter to be driven to zero and no barrier to keep iterates feasible.","feed_headline":"One unconstrained minimization solves a linear program","feed_subtitle":"A single smooth merit function captures primal-dual solutions, with a global O(ε^{-3/2}) convergence guarantee.","key_machinery":"The load-bearing object is the merit function $f_q$ in (MF): a sum of squared residual terms for the primal-dual optimality conditions, with complementary slackness replaced by the duality gap $c^Tx-b^T\\lambda$ and with nonnegativity enforced by $\\max\\{-x_j,0\\}^q$ and $\\max\\{-s_j,0\\}^q$ for $q>2$. Its convexity and twice continuous differentiability make unconstrained second-order minimization possible, while its zero-level set encodes exactly the LP solutions. The singular Hessian at optimal points is handled by adding $\\mu_k I$ (Levenberg-Marquardt regularization), and the Lipschitz continuity of the Hessian at $q=3$ plugs into an existing regularized-Newton convergence theorem to yield the global rate. A second mechanism is the modified function $h_{q,\\nu}=f_q+\\nu\\|\\lambda\\|_2^2+\\frac{\\nu}{q(q-1)}\\sum_j(\\max\\{x_j,0\\}^q+\\max\\{s_j,0\\}^q)$, whose Hessian is positive definite for $\\nu>0$, so the heuristic can take Newton steps while $\\nu$ decays to zero.","core_discovery":"The central claim is Theorem 2.1: for any fixed $q>2$, $(x^*,\\lambda^*,s^*)$ is optimal for the primal-dual LP pair if and only if it minimizes $f_q$ defined in (MF) and $f_q(x^*,\\lambda^*,s^*)=0$, where $f_q$ sums half the squared duality gap $(c^Tx-b^T\\lambda)^2$, half the squared primal and dual feasibility violations $\\|Ax-b\\|_2^2$ and $\\|A^T\\lambda+s-c\\|_2^2$, and order-$q$ penalty terms $\\max\\{-x_j,0\\}^q + \\max\\{-s_j,0\\}^q$ scaled by $1/(q(q-1))$. Since $f_q\\ge0$, the LP optimal set is exactly the zero-level set of $f_q$, making (MF) a zero-residual problem. Theorem 3.2 then states that Algorithm 1, i.e. Newton's method with Levenberg-Marquardt regularization using $\\mu_k=\\sqrt{\\|\\nabla f(x_k,\\lambda_k,s_k)\\|/2}$ and $\\alpha_k=1$, drives the residuals $\\|c^Tx_k-b^T\\lambda_k\\|$, $\\|Ax_k-b\\|$, $\\|A^T\\lambda_k+s_k-c\\|$ and the violations $x_k,s_k\\ge-\\epsilon$ all below $\\epsilon$ within $O(\\epsilon^{-3/2})$ iterations, under the assumption that the primal-dual optimal set is nonempty and bounded. The paper also introduces a modified merit function $h_{q,\\nu}$ whose Hessian is nonsingular for every $\\nu>0$ and which equals $f_q$ at $\\nu=0$; Algorithm 2 decreases $\\nu$ geometrically while taking Newton steps and is offered as a heuristic that performed faster in the reported experiments, especially in higher dimensions.","pith_inferences":["The same template could be applied to other KKT systems: replacing complementarity by a squared bilinear term such as $(x^T\\lambda)^2$ yields an exact unconstrained reformulation, though the resulting merit function is nonconvex for nonlinear programs.","Adaptive schedules for $\\nu$ rather than the fixed geometric factor $\\theta$ might remove the stalling observed for large-dimensional problems; the paper lists adaptive $\\nu$ updates as future work.","The zero-residual structure suggests that local error bound conditions, if they hold for $f_q$, would upgrade the observed fast practical convergence into a proof of local quadratic convergence, an avenue the paper mentions but does not carry out."],"forward_implications":["Any linear program with a nonempty bounded optimal set can be solved by driving one smooth unconstrained merit function to zero, starting from any point in $\\mathbb{R}^{2n+m}$.","The value of $\\min f_q$ acts as a certificate: if the computed minimum stays strictly above zero, the primal-dual pair has no optimal solution (it is infeasible or unbounded), and the simplified homogeneous formulation can then identify which case holds.","The iteration complexity $O(\\epsilon^{-3/2})$ does not depend on the problem dimension, and with the factored linear-system solve each iteration costs $O(m^3+n^3)$ rather than $O((2n+m)^3)$.","For $q=3$ the Hessian is 1-Lipschitz, giving a concrete regularization choice $\\mu_k=\\sqrt{\\|\\nabla f_k\\|/2}$ that satisfies the conditions of the convergence theorem."],"supporting_citations":[{"why":"Supplies the regularized-Newton global convergence theorem with O(ε^{-1/2}) function-value rate that Theorem 3.2 calls on.","marker":"[32]"},{"why":"Provides the global convergence theory for regularized Newton on convex functions and the cited justification for bounded level sets.","marker":"[39]"},{"why":"Supplies the simplified homogeneous formulation the paper uses to distinguish infeasible from unbounded LPs.","marker":"[49]"},{"why":"Provides the underlying homogeneous self-dual algorithm theory referenced for infeasibility detection.","marker":"[51]"},{"why":"Gives the matrix factorization update used to reduce each Newton-system solve to O(m^3+n^3) time.","marker":"[19]"}],"fun_headline_variants":["LP solved via one unconstrained smooth minimization","One smooth convex function captures all LP solutions","Zero-residual merit function solves LP exactly","Linear programs reduced to unconstrained convex minimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the fast global rate assumes that the set of all points where the merit function is no higher than at the starting point is bounded, and it takes as given that boundedness of the LP optimal set guarantees this; that implication is asserted but not demonstrated, so if it fails the $O(\\epsilon^{-3/2})$ bound has no support.","fun_headline_variants_meta":{"raw":{"variants":["LP solved via one unconstrained smooth minimization","One smooth convex function captures all LP solutions","Zero-residual merit function solves LP exactly","Linear programs reduced to unconstrained convex minimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001545,"raw_usage":{"total_tokens":6303,"prompt_tokens":1194,"completion_tokens":5109,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":810,"completion_tokens_details":{"reasoning_tokens":5054}},"tokens_in":810,"tokens_out":5109,"duration_ms":34998,"temperature":1.0,"reasoning_tokens":5054,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:34:56.471567+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a linear program whose optimal set is provably nonempty and bounded, starting from a point with large norm, and record how many iterations are needed to push the residuals below a decreasing sequence of tolerances $\\epsilon$. If the count grows faster than a constant times $\\epsilon^{-3/2}$, or if the iterates escape to infinity, Theorem 3.2's claim fails for that instance. A direct check of the proof mechanism is to test whether the sublevel set $\\{(x,\\lambda,s): f_3(x,\\lambda,s)\\le f_3(x_0,\\lambda_0,s_0)\\}$ is bounded for a family of LPs with bounded optimal sets.","supporting_citations":[{"cited_title":"Regularized newton method with global ≀(1/k2) convergence","cited_arxiv_id":null,"evidence_quote":"Supplies the regularized-Newton global convergence theorem with O(ε^{-1/2}) function-value rate that Theorem 3.2 calls on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the global convergence theory for regularized Newton on convex functions and the cited justification for bounded level sets."},{"cited_title":"A simplified homogeneous and self-dual linear programming algorithm and its implementation","cited_arxiv_id":null,"evidence_quote":"Supplies the simplified homogeneous formulation the paper uses to distinguish infeasible from unbounded LPs."},{"cited_title":"Todd, and Shinji Mizuno","cited_arxiv_id":null,"evidence_quote":"Provides the underlying homogeneous self-dual algorithm theory referenced for infeasibility detection."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the matrix factorization update used to reduce each Newton-system solve to O(m^3+n^3) time."}],"review_version":1}