{"id":"c8dac80d-7d4a-4689-ab68-15714773c3db","arxiv_id":"1908.01138","paper_version":4,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"BDCA is generalized to linearly constrained DC programs; cluster points are KKT points and the sequence converges R-linearly for quadratic objectives.","lead":"This paper extends the Boosted DC Algorithm (BDCA), a line-search accelerated variant of the DC Algorithm, to optimization problems with linear constraints. It proves convergence to KKT points under a Slater condition and R-linear convergence for quadratic objectives, with experiments showing substantial speedups over DCA on copositivity testing and trust-region subproblems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's limit passage is unjustified: the KKT multipliers of the subproblems, and the selected subgradients, are passed to the limit without a boundedness argument; the Slater point from the abstract is absent from the theorem statement, so the every-cluster-point-is-KKT claim is not…","rationale":"The reader's weakest-assumption analysis points to exactly the same place: the proof of Theorem 3.1 silently passes KKT multipliers to the limit without a boundedness argument. I agree that this is the single most load-bearing concern. My only refinement is that the missing ingredient is not literally 'Slater point' by itself; one needs a uniform bound on the subproblem multipliers, which requires either bounded subgradients of h or an additional argument. Because the gap is in the main convergence theorem, the verdict should remain CONDITIONAL: the claim is plausible and the fix is standard, but the theorem as stated is not fully proved. The numerical experiments are consistent with the intended statement but do not address this theoretical gap.","tokens_in":14571,"tokens_out":22020,"duration_ms":236454,"concrete_test":"Re-derive the passage from (8) to the KKT system in the proof of Theorem 3.1 with a fixed Slater point x_s in F added. Fix the active set I along a subsubsequence and write the subproblem KKT relation as nabla g(y_j) - u_j + sum_{i in I} mu_i^{(j)} a_i = 0. Attempt to prove sup_j ||mu^{(j)}|| < infinity and sup_j ||u_j|| < infinity using only Assumptions 1-2 and Slater. If either bound cannot be established, or if a concrete sequence satisfying (5) with d_j -> 0 but no convergent multiplier/subgradient subsequence can be exhibited, then Theorem 3.1 must be amended, for example by requiring dom h = R^n (or h differentiable) together with Slater, and the abstract and theorem statements should be aligned.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim is Theorem 3.1(ii): every limit point of the BDCA sequence is a KKT point of (P). In the proof, after extracting a convergent subsequence x_{k_j}->bar{x}, the authors write the subproblem KKT system (8) with multipliers mu_i depending on k_j and then \"take the limit\" to obtain a KKT system at bar{x}. This step requires two boundedness facts that are never proved: (a) the multiplier sequences mu_i^{(k_j)} have a convergent subsequence, and (b) the chosen subgradients u_{k_j} in partial h(x_{k_j}) either converge or can be replaced by some u in partial h(bar{x}). Closedness of the graph of partial h does not help when u_{k_j} is unbounded. The abstract mentions a Slater point, but Theorem 3.1 does not, and the proof never uses it. Slater gives existence of multipliers for each convex subproblem, but it does not automatically bound them uniformly: one also needs the gradients nabla g(y_k) - u_k to be bounded, which can fail when h has unbounded subgradients on the boundary of its domain (for example, h(x) = (rho/2)||x||^2 + iota_{R_+^n}(x) has partial h(0) = (-infinity,0]^n). Since Theorem 3.1(ii) is also the basis for identifying the limit point in Theorem 4.1 as a KKT point, this gap is load-bearing. The likely repair is to add a Slater-type assumption and prove boundedness of the multipliers along the convergent subsequence, or to assume h is finite-valued/differentiable so subgradients are locally bounded.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper extends the Boosted DC Algorithm (BDCA) to difference-of-convex programs with linear inequality constraints. Algorithm 1 performs a classical DCA step by solving a strongly convex quadratic subproblem, then, when the DCA direction is feasible at the new point, takes an extrapolation step with a backtracking line search. The main theoretical claims are Theorem 3.1, which states that the objective values decrease monotonically and that every cluster point of the generated sequence is a KKT point of the constrained problem, and Theorem 4.1, which states that for quadratic objective functions the generated sequence converges R-linearly (geometrically) to a KKT point. The numerical section compares DCA and BDCA on two NP-hard problem classes: testing copositivity of a matrix and solving l_infinity-trust-region subproblems, reporting that BDCA outperforms DCA by a factor of three to fifteen in running time.","tokens_in":14892,"tokens_out":20874,"duration_ms":209154,"significance":"If the convergence claims are valid, this is a practically useful contribution: it provides a simple acceleration of DCA for linearly constrained DC programs with the same theoretical guarantees as DCA, and it gives a self-contained geometric convergence proof in the quadratic case. The paper's descent estimates in Proposition 3.1 and the line-search feasibility check are well motivated, and the numerical tests on challenging NP-hard instances are carefully presented. However, the main convergence theorem has a load-bearing gap: the proof of Theorem 3.1(ii) passes KKT multipliers and subgradients to the limit without proving boundedness, and the theorem statement omits the Slater condition that appears in the abstract. This affects both Theorem 3.1 and, through its final step, Theorem 4.1.","major_comments":[{"comment":"The proof of Theorem 3.1(ii) extracts a convergent subsequence x_{k_j}->x_bar and then 'takes the limit' in the KKT system (8) without proving that the multiplier sequences mu_i^{(k_j)} and the selected subgradients u_{k_j} are bounded. The statement of Theorem 3.1 does not include the Slater condition that appears in the abstract, and the proof never uses it. Slater's condition guarantees existence of multipliers for each convex subproblem (P_k), but it does not by itself give uniform boundedness of those multipliers along the subsequence; one also needs a bound on the vectors nabla g(y_{k_j}) - u_{k_j}, which can fail when h has unbounded subgradients on the boundary of its domain. Closedness of the graph of partial h does not help when u_{k_j} is unbounded, so the conclusion that x_bar is a KKT point is not established. This is load-bearing because Theorem 3.1(ii) is the main convergence claim and is also used at the end of Theorem 4.1.","section":"Section 3"},{"comment":"Theorem 4.1 concludes 'x* is in F*, by Theorem 3.1(ii)' after showing that the sequence is Cauchy. Because Theorem 3.1(ii) is not justified as written, the convergence-to-a-KKT-point conclusion in Theorem 4.1 is also not currently established. Even if Theorem 3.1 is repaired, the proof should state explicitly which additional assumptions are used (for example, finite-valued h, or a Slater-based lemma proving uniform boundedness of the multipliers).","section":"Theorem 4.1, final step"}],"minor_comments":[{"comment":"In the statement of Lemma 3.1, the symbol D(y_k) is used to denote the set of active constraint indices, but D(y_k) was already defined in Section 2 as the cone of feasible directions. The condition should be 'for all i in I(y_k)' rather than 'for all i in D(y_k)'.","section":"Lemma 3.1"},{"comment":"The word 'exits' in the phrase 'there exits a subsequence' should be 'exists'.","section":"Theorem 3.1(ii)"},{"comment":"The supplied abstract states that the convergence result holds 'if the feasible set has a Slater point', but the full-text abstract and Theorem 3.1 omit this condition. These statements should be harmonized, and the theorem should either include the Slater condition or explain why it is not needed.","section":"Abstract versus full text"},{"comment":"Parts (i) and (iii) of Proposition 3.1 are relegated to references without proof. A short derivation or a more detailed reference to the constrained setting would improve the paper's self-containedness.","section":"Proposition 3.1"},{"comment":"The left axes of Figures 2 and 5 use a logarithmic scale, but the displayed objective values can be non-positive or close to zero. The paper should explain how zero and negative values are handled on the log scale.","section":"Figures 2 and 5"}],"recommendation":"major_revision","confidential_remarks":"The main gap in Theorem 3.1 is significant but appears repairable: adding the Slater condition, proving boundedness of the subproblem multipliers along the convergent subsequence, and stating the resulting assumptions on h would likely fix it. I therefore recommend major revision rather than rejection. The discrepancy between the abstract and the theorem statement should be resolved during revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper extends BDCA to linearly constrained DC programs, and the extension is well designed. The feasibility check in Line 7 (comparing active sets) is a real fix over the earlier simplex-only version, and Lemma 3.1 makes it cheap to implement. The R-linear convergence proof for quadratic objectives follows a sensible Luo–Tseng route and is a useful generalization of [29]. The numerical results on copositivity and l_infinity trust-region subproblems show large, consistent speedups over DCA; the experiments are synthetic, but they are appropriate for the algorithms being compared.\n\nThe soft spot is load-bearing. Theorem 3.1 as printed asserts that every limit point is a KKT point with no Slater-type assumption, even though the abstract includes one. The proof writes the subproblem KKT system (8) and passes the multipliers and subgradients to the limit via closedness of the graph of the convex subdifferential. Closedness only works if those objects are bounded along the subsequence, and nothing in the proof supplies that. Slater alone gives existence of multipliers for each subproblem, but it does not uniformly bound them, nor does it bound the selected subgradients u_k in ∂h(x_k). When h is extended-valued, ∂h can be unbounded at the boundary of its domain (e.g., an indicator term added to a quadratic), so the limit passage can genuinely fail. This gap also matters for Theorem 4.1, which uses Theorem 3.1(ii) to identify the Cauchy limit as a KKT point. For the quadratic case the repair is immediate — h is differentiable, so subgradients are locally bounded, and a Slater point would bound the multipliers. For the general theorem, the authors need to state a Slater condition and prove a uniform boundedness argument, or add an assumption that h is finite-valued or has locally bounded subgradients.\n\nThis is not a desk-reject. The algorithmic idea is solid, the proofs are clear where they are complete, and the contribution is likely to be useful after a major revision. I would send it to a serious referee, with a note to focus on the multiplier/subgradient passage in Theorem 3.1.","headline":"A clean extension of BDCA to linearly constrained DC programs, but Theorem 3.1's limit passage is genuinely incomplete and needs a repaired assumption before the main convergence claim can stand.","tokens_in":15442,"tokens_out":3109,"would_cite":false,"duration_ms":34693,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a boosted version of the DC algorithm converges to KKT points for linearly constrained difference-of-convex programs, with geometric convergence when the objective is quadratic.","keywords":["difference of convex functions","boosted difference of convex functions algorithm","global convergence","constrained DC programs","copositivity problem","trust region subproblem","R-linear convergence"],"falsifier":"Inspect the limiting step where the multipliers in the subproblem KKT system are passed to the limit: if the feasible set has no Slater point, those multipliers need not converge, and a cluster point obtained this way may fail the KKT conditions. A concrete search is to run Algorithm 1 on a feasible set with empty interior, such as $F=\\{x\\in\\mathbb{R}^2: x_1\\le 0,\\ -x_1\\le 0,\\ x_2\\le 1\\}$, with a DC objective whose subproblem multipliers diverge along the generated sequence; any convergent run whose limit is not a KKT point would refute Theorem 3.1 as stated in the body.","tokens_in":14352,"feed_emoji":"⚡","tokens_out":7878,"duration_ms":76693,"temperature":0.7,"pith_summary":"The paper gives a version of the Boosted DC Algorithm (BDCA) that handles linear inequality constraints by inserting a line-search extrapolation between classical DCA steps. It claims that from any feasible starting point, either the algorithm stops at a Karush–Kuhn–Tucker (KKT) point or every cluster point of the infinite sequence is a KKT point, provided the feasible set has a Slater point. When the objective is quadratic and a solution exists, the iterates are bounded and converge geometrically to a KKT point. Numerical tests on copositivity detection and $\\ell_\\infty$-trust-region subproblems show the boosted variant is often several times faster than plain DCA and can reach lower objective values. If the claims hold, BDCA can replace DCA in constrained DC programming with at least the same guarantees and better practical speed.","feed_headline":"Boosted DC algorithm gets KKT guarantees for linear constraints","feed_subtitle":"One extrapolation line search preserves convergence—and quadratic objectives converge geometrically.","key_machinery":"The load-bearing mechanism is the active-set feasibility check plus the line-search boost inside DCA. After the DCA subproblem gives $y_k$, the inclusion $I(y_k)\\subseteq I(x_k)$ is shown equivalent to $d_k=y_k-x_k$ being a feasible direction at $y_k$; only then is a backtracking line search along $d_k$ allowed, which prevents infinite loops when $y_k$ lies on the boundary of the feasible set. The descent inequality produced by the strong convexity of $g$ and $h$ yields monotone decrease of $\\varphi$ and $\\|d_k\\|\\to 0$, and a standard local error bound for the projected-gradient residual $\\|x-P_F(x-\\sigma^{-1}(Qx+q))\\|$ converts that decrease into a geometric rate for quadratic objectives.","core_discovery":"The central claim is that the accelerated DCA idea survives the addition of polyhedral constraints. Algorithm 1 solves at each iteration the strongly convex subproblem $\\min_{x\\in F} g(x) - \\langle u_k,x\\rangle$ with $u_k\\in\\partial h(x_k)$, producing $y_k$, then checks whether the active set at $y_k$ is contained in the active set at $x_k$; if so, it performs a backtracking line search along $d_k=y_k-x_k$. The proof shows $\\varphi(x_{k+1})\\le \\varphi(y_k)-\\alpha\\lambda_k^2\\|d_k\\|^2 \\le \\varphi(x_k)-(\\alpha\\lambda_k^2+\\rho)\\|d_k\\|^2$, so the objective decreases monotonically and $\\|d_k\\|\\to 0$. Under the Slater condition, the KKT multipliers of the subproblems stay controlled, and taking limits in the subproblem KKT conditions identifies every cluster point as a KKT point of the original problem. For quadratic objectives the iterates are shown to be a Cauchy sequence via a local error bound, giving R-linear (geometric) convergence.","pith_inferences":["Beyond the paper, the same 'boost then check feasibility' pattern might extend to DC programs with conic or semidefinite constraints if a cheap membership test replaces the active-set inclusion; the paper's own remark on general convex constraints shows the current check breaks there.","If the Slater condition is truly necessary, then linearly constrained DC problems where every feasible point lies on a boundary, such as equality constraints written as two inequalities, need a modified treatment; this is a natural stress test for Theorem 3.1.","The geometric-rate proof for quadratic objectives could be adapted to other norms or regularizers because it only needs the DCA step to behave like a projection and a local error bound to hold; testing this on $\\ell_1$-trust-region or sparse recovery would be a direct extension.","The empirical tendency of BDCA to escape poor local minima, combined with the new constrained version, suggests a practical multi-start heuristic for NP-hard detection problems: run BDCA from several starting points and keep the best objective value, which the paper's experiments already do implicitly."],"forward_implications":["Every cluster point of BDCA on a linearly constrained DC program is a KKT point under the Slater condition, so practitioners can safely use the boosted method wherever DCA was used.","For quadratic objectives with a solution, BDCA converges geometrically without needing the starting point to be close to a solution, and the bound is explicit in terms of the descent constants.","On copositivity testing, a negative objective value at any BDCA iterate certifies non-copositivity, so faster convergence means earlier certificates on hard matrices; the experiments report about 15 times faster on Horn matrices and larger gains on nearly copositive ones.","On $\\ell_\\infty$-trust-region subproblems, BDCA reaches similar objective values roughly three times faster on average, making it a practical drop-in for bound-constrained quadratic subproblems."],"supporting_citations":[{"why":"Introduces BDCA with the line-search boosting step that Algorithm 1 generalizes to linearly constrained problems.","marker":"[3]"},{"why":"Supplies the descent inequalities and convergence proof techniques for the unconstrained accelerated DC method that are adapted here.","marker":"[1]"},{"why":"Provides the linear-convergence technique for nonconvex quadratic programs that Theorem 4.1 extends.","marker":"[29]"},{"why":"Gives the local error bound and the connected-components structure of the KKT set used in the quadratic convergence proof.","marker":"[17]"},{"why":"Formulates copositivity testing as a DC problem and applies DCA as a heuristic, forming the baseline for the numerical comparison.","marker":"[7]"},{"why":"Establishes NP-hardness of copositivity and trust-region subproblems, motivating the need for fast heuristics.","marker":"[20]"},{"why":"Introduces the classical DCA whose iterations BDCA accelerates.","marker":"[25]"}],"fun_headline_variants":["BDCA with linear constraints: faster, convergent","Boosted DC with polyhedral constraints: KKT and faster","Linearly constrained BDCA: KKT limits, geometric speed","DC algorithm boost: linear constraints still reach KKT"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence proof needs a Slater point for the feasible set—a feasible point strictly satisfying every linear inequality—so the Lagrange multipliers of the subproblems cannot blow up when the algorithm's limiting argument is made; the abstract states this condition, while the theorem statement in the paper body does not.","fun_headline_variants_meta":{"raw":{"variants":["BDCA with linear constraints: faster, convergent","Boosted DC with polyhedral constraints: KKT and faster","Linearly constrained BDCA: KKT limits, geometric speed","DC algorithm boost: linear constraints still reach KKT"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000247,"raw_usage":{"total_tokens":1554,"prompt_tokens":967,"completion_tokens":587,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":521}},"tokens_in":583,"tokens_out":587,"duration_ms":5687,"temperature":1.0,"reasoning_tokens":521,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:23:03.230608+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Inspect the limiting step where the multipliers in the subproblem KKT system are passed to the limit: if the feasible set has no Slater point, those multipliers need not converge, and a cluster point obtained this way may fail the KKT conditions. A concrete search is to run Algorithm 1 on a feasible set with empty interior, such as $F=\\{x\\in\\mathbb{R}^2: x_1\\le 0,\\ -x_1\\le 0,\\ x_2\\le 1\\}$, with a DC objective whose subproblem multipliers diverge along the generated sequence; any convergent run whose limit is not a KKT point would refute Theorem 3.1 as stated in the body.","supporting_citations":[{"cited_title":"The Boosted DC Algorithm for nonsmooth functions","cited_arxiv_id":"1812.06070","evidence_quote":"Introduces BDCA with the line-search boosting step that Algorithm 1 generalizes to linearly constrained problems."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the descent inequalities and convergence proof techniques for the unconstrained accelerated DC method that are adapted here."},{"cited_title":"N.: Linear convergence of a type of iterative sequences in nonconvex quadratic programming","cited_arxiv_id":null,"evidence_quote":"Provides the linear-convergence technique for nonconvex quadratic programs that Theorem 4.1 extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the local error bound and the connected-components structure of the KKT set used in the quadratic convergence proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Formulates copositivity testing as a DC problem and applies DCA as a heuristic, forming the baseline for the numerical comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of copositivity and trust-region subproblems, motivating the need for fast heuristics."},{"cited_title":"Acta Math","cited_arxiv_id":null,"evidence_quote":"Introduces the classical DCA whose iterations BDCA accelerates."}],"review_version":1}