{"id":"694b6615-daa0-43e3-a8e2-9649d78d93e8","arxiv_id":"2506.03692","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A two-stage diagonalization and bisection algorithm is proposed for nonconvex QCQP with one equality constraint, claiming global optimality and O(N^3) complexity.","lead":"This paper proposes an algorithm for a class of nonconvex quadratic optimization problems with one equality constraint, claiming global optimality in O(N^3) time. If correct, it would replace much slower semidefinite relaxation solvers in signal processing, finance, and communications subproblems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed unique root of f(λ)=c fails when all b_i at the minimal a_i vanish; Algorithm 1 does not solve such feasible instances, so the global-optimality claim for the standard case is unsupported.","rationale":"The reader identified exactly the load-bearing weakness: the existence of a root of f(λ)=c for every c>0 is asserted from an incorrect endpoint limit. I checked the algebra of Eq. (15) and the KKT derivation: when b_i=0 at the smallest a_i, the formula y_i=b_i/(a_i+λ) gives 0/0 at λ=-min a, and the second-order condition λ≥-min a is not enough to force the boundary solution into the open interval. The counterexample is a legitimate standard-case instance (A1≻0, A0 symmetric) with a feasible set and a finite global minimum. Since the paper's headline claim is for arbitrary problem data, one counterexample invalidates the 'globally optimal' guarantee. The paper's numerical experiments use random b_i, so the failure has probability zero in those tests; this explains why simulations look good without rescuing the theorem. The same f(λ) structure appears in the matrix-format extension (Theorem 4), so the flaw propagates there as well. No further issue is needed: this is a definitive correctness gap. I agree with the reader's verdict and would leave it as REJECT.","tokens_in":18236,"tokens_out":4520,"duration_ms":45119,"concrete_test":"Run Algorithm 1 on N=2 with A0=diag(0,1), A1=I, b0=b1=0, c0=0, c1=-2. In the y coordinates, a=(0,1), b=(0,0), c=2; Step 6 seeks λ>0 with f(λ)=0/(λ)^2+1/(1+λ)^2=2, which has no solution. If the implementation reports failure (or returns the trivial x=-A1^-1 b1=0, which violates the constraint since ||0||^2≠2), the hard-case gap is confirmed. Then the assertion 'for any c>0 there exists a unique root' is false; a correct solver must handle λ=-min a_i with nonzero y_i on the minimal eigenspace, e.g. by checking the boundary KKT system.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of the central claim breaks at the asserted endpoint behavior of f. In Section II-B, after Eq. (15), the paper states that as λ→[−min({a_i})]^+, f(λ)→+∞ and therefore f(λ)=c has a unique root for every c>0. But f(λ)=Σ b_i^2/(a_i+λ)^2: only summands with a_i=min_j a_j and b_i≠0 diverge. If every index attaining the minimum has b_i=0, the limit is the finite value Σ_{a_i>min a} b_i^2/(a_i−min a)^2, so for larger c no root exists. This is not merely a technicality: the KKT formula y_i=b_i/(a_i+λ) degenerates at λ=−min a_i, where non-minimal coordinates are determined but the minimal-block coordinates can be nonzero. A concrete standard-case instance is A0=diag(0,1), A1=I, b0=b1=0, c0=0, c1=−2. The transformed problem is min y_2^2 subject to y_1^2+y_2^2=2, whose global optimum is y=(±√2,0) with value 0; yet f(λ)=1/(1+λ)^2 never equals 2 for λ>0, so Algorithm 1's bisection step cannot find any root. The universal global-optimality claim for the standard case is therefore false as stated, although the method remains valid in the generic case where all minimal b_i are nonzero.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SD-BS, a two-stage algorithm for the nonconvex QCQP with one equality constraint (Eq. (1)). In the standard case A1≻0, the SD stage simultaneously diagonalizes A0 and A1 through an affine change of variables, reducing the problem to the decoupled form (10). The BS stage then finds the Lagrange multiplier λ by solving the equation f(λ)=c, where f is defined in Eq. (15), using monotonicity on the interval (−min_i a_i, +∞). The paper claims that this procedure yields a globally optimal solution in O(N^3) time and extends the approach to rank-deficient A1, indefinite A1, additional linear constraints, and matrix-format variables. Numerical comparisons against SDR and fmincon are reported for randomized instances.","tokens_in":18578,"tokens_out":5795,"duration_ms":57911,"significance":"If the central claim were correct, the SD-BS algorithm would be a valuable contribution, offering O(N^3) complexity and a non-iterative (up to bisection) solution for a problem class typically solved by SDR with much higher complexity. The derivations are clean for generic data, and the reported experiments show excellent performance on randomly generated instances. However, the universal global-optimality guarantee for the standard case is false, because the proof of the endpoint behavior of f(λ) fails when the coefficient b_i vanishes for every index attaining the minimal a_i. In that trust-region hard case the global minimizer lies at λ=−min a_i with nonzero components in the minimal block, which Algorithm 1 cannot find. The numerical experiments generate generic data and therefore do not expose this failure. The contribution is thus significant only under a restrictive assumption that the paper does not state.","major_comments":[{"comment":"The assertion that f(λ) → +∞ as λ → (−min_i a_i)^+ is false when b_i = 0 for every index i attaining the minimum of the a_i. In that case the limit is the finite value Σ_{a_i > min a} b_i^2/(a_i − min a)^2, so for c larger than this limit the equation f(λ)=c has no root in (−min_i a_i, +∞). For example, the standard-case instance min x^2 subject to x^2 = 2 (A0=A1=1, b0=b1=0, c1=−2) yields a=1, b=0, c=2 and f(λ)=0 for all λ; a global minimizer exists (any x=±√2) but no λ in (−1, +∞) satisfies f(λ)=2. This directly disproves the claimed unique-root existence and the universal global-optimality guarantee of Algorithm 1 for the standard case.","section":"Section II-B, Eq. (15) and the paragraph after Eq. (15)"},{"comment":"The KKT solution formula y_i = b_i/(a_i + λ) excludes λ = −min_i a_i because the denominator would vanish. This is not merely a technical edge case: when the minimal-a_i block has b_i=0, the KKT system has solutions at λ=−min_i a_i with arbitrary y_i on that block, constrained only by the norm equation (11), and these solutions can be the global minimizers. Since Algorithm 1 searches only λ ∈ (−min_i a_i, +∞) via bisection, it cannot recover such solutions. Consequently, the claim in Section II-B that the first- and second-order KKT system has a unique KKT point is incorrect in general.","section":"Section II-B, Eqs. (13) and (18)"},{"comment":"The randomized instances in Section VII-A generate b0 and b1 with i.i.d. continuous Gaussian entries, so with probability one every b_i is nonzero. The failure mode described above, in which all b_i at the minimal a_i vanish, is never exercised. The numerical results are therefore consistent with the algorithm's behavior only in the generic case and provide no evidence for the universal claim made in the abstract and in Section II-B.","section":"Section VII-A, experiment generation"}],"minor_comments":[{"comment":"The abstract calls the algorithm 'non-iterative', but the Bisection Search stage in Algorithm 1 is an iterative procedure; the complexity discussion in Section II-C should state the bisection iteration count or clarify that 'non-iterative' refers to the absence of iterative convex-optimization solves.","section":"Abstract and Section II-C"},{"comment":"The phrase 'type pf optimization problem' contains a typo and should read 'type of optimization problem'.","section":"Introduction, first paragraph"},{"comment":"The sentence 'Plugging (40) into (40)' should refer to plugging Eq. (61) into Eq. (60); the current reference is self-referential and unclear.","section":"Appendix C, last paragraph"},{"comment":"The formula arg(y_i) = arg(b_i) is undefined when b_i = 0; the theorem requires a convention or an assumption excluding zero b_i, which is another instance of the zero-coefficient case that the paper does not address.","section":"Theorem 4, Eq. (41)"}],"recommendation":"reject","confidential_remarks":"The counterexample in the major comments is elementary and directly contradicts the central universal claim of the paper. Fixing it would require adding a nontrivial treatment of the hard case (e.g., the trust-region hard-case solution with an additional generalized eigenvalue computation) and revising the scope statement, which is substantial new work beyond a local revision. The paper may be suitable for resubmission after such an addition, but in its current form the main guarantee is invalid."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nYou should know this paper's central claim is false in general. Algorithm 1 (SD-BS) is claimed to globally solve the single-equality QCQP (1) in the standard case A1 ≻ 0 for all feasible instances. That fails in the classical trust-region hard case. After simultaneous diagonalization, if every index i with a_i = min_j a_j has b_i = 0, then f(λ) does not diverge as λ → (−min a_i)^+, and for large enough c the equation f(λ)=c has no root even though the QCQP is feasible. A concrete instance: minimize x2^2 subject to x1^2 + x2^2 = 2 (A0 = diag(0,1), A1 = I, b0 = b1 = 0, c1 = −2). The optimum is (±√2, 0) with value 0, but f(λ) ≡ 0, so bisection cannot proceed. The KKT formula y_i = b_i/(a_i+λ) degenerates to 0/0 in the minimal block. This is not a technicality; it is exactly the hard case studied in the trust-region literature the authors cite but do not address. The paper's assertion that f(λ) → +∞ at the left endpoint is simply wrong when the minimal-coordinate b_i vanishes.\n\nThat said, the paper is not without merit. For generic data (all b_i nonzero at the minimal a_i), the derivation is clean and the two-stage SD-BS procedure is correct and clearly O(N^3). The numerical experiments are thorough and show the method beats SDR and fmincon in speed and often in accuracy on those generic instances. The extensions (rank deficiency, indefiniteness, linear augmentation, matrix variable) are useful engineering, but they inherit the same endpoint issue in their own f(λ) definitions. The citation pattern is acceptable, though the hard case deserves a more prominent discussion given Moré [9] and Conn et al. [30] are both cited.\n\nIn short: the paper is a solid generic-case algorithm with an overbroad global-optimality claim. A serious referee could work with this — the fix is to add an explicit genericity assumption and handle the hard case separately (e.g., solve a reduced trust-region subproblem on the minimal eigenspace). I would not cite it as a universal solver, but the generic-case contribution may be worth salvaging. I'd send it to review, expecting major revision.","headline":"A clean generic-case method whose universal global-optimality claim breaks in the trust-region hard case; reject as is, but fixable.","tokens_in":19082,"tokens_out":4413,"would_cite":false,"duration_ms":43055,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C22","90C20","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that the nonconvex single-equality-constraint QCQP is globally solvable in $O(N^3)$ time by simultaneous diagonalization followed by a bisection search on the KKT equation.","keywords":["nonconvex QCQP","single equality constraint","global optimality","simultaneous diagonalization","bisection search","KKT conditions","semidefinite relaxation","matrix-format QCQP"],"falsifier":"Set $N=2$, $A_0=\\operatorname{diag}(0,1)$, $A_1=I$, $b_0=b_1=0$, $c_0=0$, $c_1=-1$. The constraint becomes $y_1^2+y_2^2=1$ and the objective is $y_2^2$, so the global minimum is $0$, attained at $(\\pm1,0)$. Yet $c=1$ and $f(\\lambda)=0$ for every $\\lambda$, so the bisection stage of Algorithm 1 has no root to find and returns no solution. This instance isolates exactly the missing nonzero-$b$ assumption and would refute the claim that a root exists for every feasible instance.","tokens_in":18026,"feed_emoji":"⚡","tokens_out":16742,"duration_ms":151937,"temperature":0.7,"pith_summary":"This paper tackles a nonconvex quadratically constrained quadratic program (QCQP) with exactly one equality constraint: minimize a quadratic objective subject to a fixed second-order level set. In the standard case where the constraint matrix is positive definite ($A_1\\succ 0$), it claims the global optimum can be found in guaranteed $O(N^3)$ time by a two-stage procedure. First, simultaneous diagonalization turns the two quadratic forms into a decoupled diagonal problem; second, the first- and second-order KKT conditions reduce the search for the optimal Lagrange multiplier to solving a one-dimensional monotone equation $f(\\lambda)=c$ by bisection. The paper also extends the scheme to rank-deficient constraint matrices, indefinite full-rank constraints with a strictly convex objective, extra linear equalities, and matrix-format complex variables. If right, this replaces semidefinite relaxation (SDR) as the standard subproblem solver in applications from portfolio design to hybrid precoding, with far better speed and scalability.","feed_headline":"Nonconvex QCQP solved globally in O(N³) time","feed_subtitle":"One-constraint quadratic programs get a fast global solver instead of a slow semidefinite program.","key_machinery":"The load-bearing object is the pair: simultaneous diagonalization plus the scalar KKT equation. Simultaneous diagonalization finds an invertible $T$ with $A_1=T T^T$ and $A_0=T\\operatorname{diag}(a)T^T$, and the affine map $y=T^T x+T^{-1}b_1$ converts problem (1) into $\\min \\sum_i (a_i y_i^2-2b_i y_i)$ subject to $\\sum_i y_i^2=c$. The bisection stage then solves $f(\\lambda)=\\sum_i b_i^2/(a_i+\\lambda)^2=c$ on the interval $(-\\min_i a_i,+\\infty)$, where the second-order KKT condition forces $\\lambda\\ge -\\min_i a_i$; monotonicity of $f$ makes the root unique, so a simple bisection recovers the globally optimal $y^\\star=b/(a+\\lambda^\\star\\mathbf{1})$ and hence $x^\\star$.","core_discovery":"The central claim is that problem (1) has a unique KKT point that is globally optimal, and that this point can be recovered from the solution of a scalar equation. With $A_1\\succ 0$, the paper proves that for any feasible instance there is an affine map $y=T^T x+T^{-1}b_1$ making the constraint $y^T y=c$ and the objective diagonal; then the first-order condition gives $y_i=b_i/(a_i+\\lambda)$, and the second-order condition restricts $\\lambda$ to $(-\\min_i a_i,+\\infty)$. In that interval $f(\\lambda)=\\sum_i b_i^2/(a_i+\\lambda)^2$ is strictly decreasing, so $f(\\lambda)=c$ has a unique root $\\lambda^\\star$, and the inverse map applied to $y^\\star=b/(a+\\lambda^\\star\\mathbf{1})$ is the global minimizer. The paper further claims that the same two-stage logic, with a modified $f$, handles rank-deficient $A_1$, indefinite $A_1$ under $A_0\\succ 0$, additional linear equalities, and complex matrix variables, and reports numerics showing constraint violations below $10^{-5}$, optimality gaps below $10^{-4}$, and speeds two or more orders of magnitude above SDR.","pith_inferences":["A practical implementation would need a separate fallback for the hard case in which $b_i=0$ at an index attaining $\\min_i a_i$; the paper does not provide that routine, since its proof of the root's existence relies on $b_i\\neq 0$ there.","The column-norm reduction in the matrix extension suggests a general principle: whenever the constraint is a Frobenius-norm equality and the two quadratic forms are simultaneously diagonalizable, only the column norms of the transformed variable enter the multiplier equation, so the effective dimension is the row size, not the full matrix size.","Because single-equality-constraint QCQPs appear inside iterative majorization and block-coordinate outer loops, a fast exact subproblem solver could accelerate those outer algorithms; this follows from the paper's complexity claim but is not spelled out.","A direct stress test would be to run SD-BS on deliberately constructed hard-case instances (zero coefficients at the minimal $a_i$) and compare against a trust-region solver that handles endpoint solutions; the paper's numerical section does not appear to include such instances."],"forward_implications":["For any feasible single-equality-constraint QCQP with $A_1\\succ 0$, global optimality can be certified in $O(N^3)$ time without solving a semidefinite program, making the subproblem affordable at dimension up to $10^3$.","The same two-stage logic, with modified $f(\\lambda)$, covers rank-deficient $A_1$ with a null-space elimination condition, indefinite full-rank $A_1$ when $A_0\\succ 0$, and additional linear equalities via a null-space parametrization.","For complex matrix-format variables, the paper's phase-alignment argument reduces the multiplier equation to the column-norm quantities $b_j=\\sqrt{\\sum_i |b_{i,j}|^2}$, lowering complexity from $O((N_1N_2)^{6.5})$ to $O(N_1^3)$.","Numerical experiments in the paper report constraint violations below $10^{-5}$, optimality gaps below $10^{-4}$, runtime at least two orders of magnitude shorter than the SDR benchmark, and scalability to problem sizes at least ten times larger."],"supporting_citations":[{"why":"Supplies the simultaneous diagonalization lemma (Lemma 1) that decouples the two quadratic forms.","marker":"[44]"},{"why":"Prior O(N^3) eigenvalue-based algorithm for single-inequality-constraint QCQP; the paper adapts and extends the conditions to the equality-constrained case.","marker":"[34]"},{"why":"Supplies the trust-region KKT conditions that underlie the first- and second-order optimality conditions used in the bisection stage.","marker":"[9]"},{"why":"Establishes the semidefinite relaxation benchmark and its O(N^6.5) complexity, which the new algorithm is designed to replace.","marker":"[20]"},{"why":"Provides the KKT conditions, Lagrangian relaxation, and S-procedure background that justify the optimality arguments.","marker":"[13]"},{"why":"Poses the matrix-format complex QCQP subproblem from hybrid precoding that motivates Extension IV.","marker":"[41]"},{"why":"Shows a mean-reverting portfolio application where single-equality-constraint QCQPs appear as majorization-minimization subproblems.","marker":"[40]"}],"fun_headline_variants":["Fast global solution for nonconvex QCQP with one constraint","Global optimum for nonconvex QCQP via two-step algorithm","Fast non-iterative global solver for QCQP with one equality","QCQP global optimum from a scalar equation, no iterations","Nonconvex QCQP's unique KKT point found via bisection"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that every index attaining the smallest diagonal entry $a_i$ has a nonzero coefficient $b_i$, so that $f(\\lambda)\\to+\\infty$ at the left endpoint and $f(\\lambda)=c$ has a root for every $c>0$.","fun_headline_variants_meta":{"raw":{"variants":["Fast global solution for nonconvex QCQP with one constraint","Global optimum for nonconvex QCQP via two-step algorithm","Fast non-iterative global solver for QCQP with one equality","QCQP global optimum from a scalar equation, no iterations","Nonconvex QCQP's unique KKT point found via bisection"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000848,"raw_usage":{"total_tokens":3756,"prompt_tokens":1077,"completion_tokens":2679,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":693,"completion_tokens_details":{"reasoning_tokens":2591}},"tokens_in":693,"tokens_out":2679,"duration_ms":18482,"temperature":1.0,"reasoning_tokens":2591,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:57:53.400727+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $N=2$, $A_0=\\operatorname{diag}(0,1)$, $A_1=I$, $b_0=b_1=0$, $c_0=0$, $c_1=-1$. The constraint becomes $y_1^2+y_2^2=1$ and the objective is $y_2^2$, so the global minimum is $0$, attained at $(\\pm1,0)$. Yet $c=1$ and $f(\\lambda)=0$ for every $\\lambda$, so the bisection stage of Algorithm 1 has no root to find and returns no solution. This instance isolates exactly the missing nonzero-$b$ assumption and would refute the claim that a root exists for every feasible instance.","supporting_citations":[{"cited_title":"Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint,","cited_arxiv_id":null,"evidence_quote":"Prior O(N^3) eigenvalue-based algorithm for single-inequality-constraint QCQP; the paper adapts and extends the conditions to the equality-constrained case."},{"cited_title":"Generalizations of the trust region problem,","cited_arxiv_id":null,"evidence_quote":"Supplies the trust-region KKT conditions that underlie the first- and second-order optimality conditions used in the bisection stage."},{"cited_title":"Semidefinite relaxation of quadratic optimization problems,","cited_arxiv_id":null,"evidence_quote":"Establishes the semidefinite relaxation benchmark and its O(N^6.5) complexity, which the new algorithm is designed to replace."},{"cited_title":"Alternating minimization algorithms for hybrid precoding in millimeter wave MIMO systems,","cited_arxiv_id":null,"evidence_quote":"Poses the matrix-format complex QCQP subproblem from hybrid precoding that motivates Extension IV."},{"cited_title":"Mean-reverting portfolio with budget constraint,","cited_arxiv_id":null,"evidence_quote":"Shows a mean-reverting portfolio application where single-equality-constraint QCQPs appear as majorization-minimization subproblems."}],"review_version":1}