Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming

Alberto Del Pia

REVIEW 1 major objections 4 minor 18 references

Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming

T0 review · 1 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that MIQP with fixed numbers of integer variables and negative Hessian eigenvalues admits polynomial-time epsilon-approximation on a Turing machine, and that both restrictions are necessary unless P=NP.

desk verdict Strong, publishable complexity paper with new rational Jacobi machinery and one easily patched gap in Proposition 4; worth refereeing. read the letter →

arxiv 2607.29386 v1 pith:KPS6ZADR submitted 2026-07-31 math.OC cs.DM

Alberto Del Pia This is my paper · ORCID

classification math.OCcs.DM MSC 90C2090C1068Q2565F15

keywords mixedintegerquadraticprogrammingapproximationalgorithmrationalJacobirotationssimultaneousdiagonalizationinertiaofHessiancomputationalcomplexityTuringmachinefixedparameter

topics P versus NP

open problems P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a sharp complexity boundary for approximating mixed integer quadratic programming (MIQP). Its main theorem gives an algorithm that, whenever the number p of integer variables and the number k_- of negative eigenvalues of the objective's Hessian are fixed, either detects infeasibility or returns an epsilon-approximate solution, running in polynomial time on a Turing machine. The same theorem shows that neither restriction can be removed without collapsing to NP-hardness, assuming P is not NP. The result matters because it converts a class of nonconvex, integer-constrained problems that previously had no provable Turing-machine approximation into one with a concrete worst-case guarantee; it is new even in the continuous case, where earlier polynomial-time approximations relied on a real-RAM model.

What carries the argument

The engine is the rational Jacobi rotation: an exactly orthogonal rational matrix, built via the Weierstrass parametrization c=(1-u^2)/(1+u^2), s=2u/(1+u^2), that approximately annihilates a chosen off-diagonal entry of a symmetric matrix. Iterating these rotations drives the off-diagonal Frobenius norm below any prescribed tolerance; a classical lower bound on the size of nonzero eigenvalues of integer symmetric matrices then guarantees that zeroing tiny entries cannot change inertia. Composing this with a standard ellipsoid rounding algorithm yields a simultaneous diagonalization that maps the feasible polytope to spherical form while making the objective separable up to an arbitrarily sma

What would settle it

Take a small instance with p=2 and one negative Hessian eigenvalue, run the recursive algorithm, and compare its returned feasible solution against a brute-force optimum; returning a solution whose objective gap exceeds epsilon(f_sup - f_inf) would refute Theorem 1. More directly, search for a rational lattice and a radius-1/4 ball with no lattice point such that every admissible dual direction has width larger than p 2^{p(p-1)/4}; such a ball would falsify the flatness lemma on which the recursion depends.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for any instance of MIQP whose objective is bounded below on the feasible region and any rational epsilon in (0,1], there is a Turing-machine algorithm that either proves infeasibility or finds an epsilon-approximate solution in time polynomial in the instance size, size(epsilon), and 1/epsilon, provided p and k_- are fixed. The paper also proves that, unless P=NP, fixing both p and k_- is necessary: allowing p to grow would decide integer feasibility in polynomial time, and allowing k_- to grow would solve 3SAT in polynomial time already with p=0. The algorithmic novelty is a rational simultaneous diagonalization: a rational nonsingular change of basis that m

Load-bearing premise

The recursion relies on a flatness lemma for mixed-integer lattices that bounds the width of any radius-1/4 ball with no lattice point by p 2^{p(p-1)/4}, independent of the lattice basis; if that bound fails, the partition into subproblems with fewer integer variables—and with it the polynomial-time guarantee—collapses.

Editorial extensions

If this is right

For fixed p and k_-, epsilon-approximate solutions to MIQP can be found in polynomial time on a Turing machine, including detection of infeasibility.
The result is new already for purely continuous quadratic programming (p=0); earlier polynomial-time approximations of that case required a real-RAM computation model.
Both fixed-parameter assumptions are necessary: dropping either one makes the approximation problem NP-hard, assuming P is not NP.
The dependence on 1/epsilon cannot be reduced to a purely logarithmic dependence without solving an NP-hard problem.
The recursion tree has depth at most p and polynomially many leaves for fixed p, so the algorithm terminates with the promised running time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extension: the rational Jacobi rotations give a polynomial-time approximate spectral decomposition over the rationals, so they may transfer to other settings where exact diagonalization blocks Turing-machine algorithms, such as generalized eigenvalue problems or trust-region subproblems.
Extension: the inertia-preserving rounding recipe—drive the off-diagonal norm below an eigenvalue gap, then round small entries to zero—could be adapted to yield rational approximation guarantees for other structured nonconvex optimization problems.
Extension: a natural testable next step is an implementation study, since the paper is algorithmic and contains no computational experiments; measuring practical runtimes and approximation quality on small MIQP instances would reveal how the polynomial bounds behave in practice.
Manuscript note: the proof of Proposition 4 omits the branch in which the second application of the flatness lemma returns a flat direction instead of a lattice point; the text states the repair is immediate using the same width argument, but that case is not written out.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear X,

The headline: this is a real result, and the main theorem looks right to me. If the proof is correct, Del Pia completes the complexity characterization for approximating MIQP, and the new rational Jacobi rotation machinery is a genuine contribution, not a repackaging. The continuous case (p=0) being new on a Turing machine is significant.

What's actually new: Theorem 1 gives a Turing-machine algorithm for epsilon-approximation with p and k_- fixed — this subsumes Vavasis's real-RAM work and Del Pia's earlier fixed-rank results. The rational simultaneous diagonalization (Theorem 4) and the rational Jacobi rotations are new technical tools, with careful size and running-time bounds. The eigenvalue-gap argument (Lemmas 9–13) is clean, and the rounding to zero without changing inertia is well executed. The reliance on Lenstra's rounding and flatness theorem is appropriate; those are external published results, not contrived for this paper.

Soft spots: the proof of Proposition 4 has a genuine gap. After the first call to Lemma 18 returns a lattice point y+, the second call to the same lemma is said, 'symmetrically,' to return a lattice point y-. But that call could return a flat direction u. The missing branch is harmless: setting v=2u gives the required integer direction with the same width bound, and the paper's conclusion still holds. But as written, the case is omitted, and the proof needs a patch. This is minor — the repair is immediate and the central argument doesn't depend on it. Also, several load-bearing subroutines come from Del Pia's own earlier papers. That's a citation-pattern smell only if the results are questionable; these are published, and the target theorem is new, so I don't see a circularity problem. The paper has no experiments, which is fine for a complexity result.

Who it's for: anyone working on algorithms for nonconvex QP or MIQP, and complexity theorists interested in rational orthogonal transformations. The paper deserves a serious referee. If I were the editor, I'd send it out with a request that the referee check the Prop 4 repair and the recursion depth carefully.

Recommendation: engage with it — referee it, and expect a small revision, not a rejection.

Referee Report

1 major / 4 minor

Summary. The paper claims a polynomial-time Turing-machine approximation algorithm for mixed integer quadratic programming (MIQP) when the number p of integer variables and the number k_- of negative eigenvalues of the Hessian are fixed. The algorithm either detects infeasibility or returns an epsilon-approximate solution for any rational epsilon in (0,1], in time polynomial in the instance size, size(epsilon), and 1/epsilon. The main technical engine is a rational version of Jacobi rotations that nearly diagonalizes a symmetric matrix while exactly preserving inertia, leading to a simultaneous diagonalization/rounding procedure for ellipsoids and polytopes. This is combined with mesh partitioning and linear underestimators for spherical-form MIQP, plus a recursion driven by a flatness theorem for mixed integer lattices. The paper also argues that both restrictions are necessary unless P=NP, and that the result is new already in the purely continuous case in the Turing model.

Significance. If correct, this completes the complexity characterization for approximating MIQP in terms of p and k_-, subsuming earlier results for concave and fixed-rank cases, and giving the first Turing-machine polynomial-time approximation algorithm for continuous quadratic programming with fixed k_-. The rational Jacobi rotations and the inertia-preserving near-diagonalization theorems are potentially useful independent tools. The proofs are generally careful and quantitative, with explicit size bounds and running-time analyses; the reliance on the author's own prior lemmas is substantial but not circular. However, one proof branch is missing in Proposition 4, as detailed below; the gap is local and has an immediate repair, but it must be fixed before the proof is complete.

major comments (1)

[§4.4, Proposition 4] After the first application of Lemma 18 returns y+, the proof says 'Symmetrically, we can assume that Lemma 18 finds a vector y-' when Lemma 18 is applied to B(-3e_1/4,1/4). This ignores the branch where the second application returns a nonzero flat direction u instead of a lattice point. The repair is immediate: set v=2u. Then u^T(2b_i) ∈ Z for i≤p and u^T(2b_i)=0 for i>p imply v^T b_i ∈ Z for i≤p and v^T b_i=0 for i>p, and width_v(B(0,n^{3/2})) = 8n^{3/2} width_u(B(-3e_1/4,1/4)) ≤ 8p 2^{p(p-1)/4} n^{3/2}. Thus the proposition's conclusion remains true, but the proof as written is incomplete. Since Proposition 4 is used in Proposition 5 and then in Theorem 1, this is a load-bearing gap, though a readily fixable one.

minor comments (4)

[Theorem 2, statement] The running-time expression 'O(n^4(log(1/δ)+logn+log(max(1,∥A∥_F)))^2)' is easy to misread as O(n^4) times a squared parenthesis; clarify the exponent placement.
[References] Reference [11] says '4rd edition'; should be '4th edition'.
[Funding line] The funding statement starts with 'F unding:' rather than 'Funding:'; fix the typo.
[§1, lower-bound discussion] The necessity of fixing p and k_- is argued in the introduction via reductions to previously known NP-hard problems. This is convincing, but since these are central to the 'complete characterization' claim, a formal statement of the reductions (or precise pointers to the exact theorems used) would strengthen the paper.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main algorithm is derived in-paper, and the self-citations are to independent published lemmas, not to the target theorem.

full rationale

The claimed contribution — rational Jacobi rotations, the near-diagonalization algorithm, the inertia-preserving simultaneous diagonalization Theorems 3–5, the reduction to spherical form, and the recursive partition scheme — is proved inside the manuscript from first principles (Sections 2–4). The central Theorem 1 is not assumed or hidden in any input: the algorithm is constructive, and the approximation guarantee is obtained from explicit perturbation bounds (Lemma 15), the spherical-form reduction (Proposition 2), mesh partitioning (Proposition 3), and the two theorems of the alternative (Propositions 4 and 5). The paper does rely on several results from the author's own prior work: Lemma 16 from [8] to solve convex mixed-integer quadratic programs, Lemma 18 from [9] for the mixed-integer flatness direction, Lemma 21 from [10] for the bound on an optimal solution, Lemma 22 from [8] for the affine decomposition with p' ≤ p−1, Lemma 23 from [7] for exact symmetric diagonalization, and Lemma 24 from [9] for combining approximate solutions over a partition. Under the stated review rules these are not circularity: each is a published, parameter-free supporting theorem whose hypotheses do not include the MIQP approximation theorem of this paper, and each is used as a black box with its own polynomial-time guarantee. Self-citation alone is not load-bearing circularity when the cited result is independent evidence of this kind. The only substantive weakness in the written derivation is the one identified by the reader: in Proposition 4, after the first application of Lemma 18 to B(3e_1/4,1/4) returns a lattice point y^+, the proof says 'Symmetrically, we can assume that Lemma 18 finds a vector y^−', but the second application to B(−3e_1/4,1/4) could instead return a flat direction. This is a genuine omitted case in the proof as written, but it is a correctness/patching issue, not circularity: the repair is immediate (take v = 2u and use the same width argument as in the first branch), and it does not identify a prediction with an input or make the theorem's content an assumption. Accordingly, no circular step is exhibited, and the score is 0 rather than a positive value.

Assumptions & free parameters 0 free parameters · 11 assumptions · 0 invented entities

No free parameters are fitted to data; the absolute constant kappa=3/16 in the approximation analysis is a fixed universal constant, and mesh sizes are computed from epsilon. The paper relies on a set of external published results, several from the same author, which are treated as axioms here because their proofs are not reproduced. The factored-form restriction on M is an admitted domain restriction.

assumptions (11)

standard math Lemma 10 (Cauchy's root bound): roots of a polynomial q(t) with coefficients b_i satisfy |lambda| >= |b0|/(|b0| + max_{i>=1}|b_i|).
Used in Lemma 11 to lower-bound nonzero eigenvalues of integer symmetric matrices.
standard math Lemma 12 (Weyl's perturbation bound): |lambda_i(B)-lambda_i(C)| <= ||B-C||_2 for symmetric B,C.
Used in Lemma 13 to bound eigenvalue movement after rounding.
standard math Sylvester's law of inertia: congruence transformations preserve inertia.
Used throughout to transfer inertia between matrices.
domain assumption Lemma 14 (Lenstra's ellipsoid rounding) produces rational nonsingular C with E(a,C) subset P subset E(a,C/n^{3/2}).
Bridges the polytope to a factored ellipsoid; the rest of the reduction depends on it.
domain assumption Lemma 16 (from Del Pia [8]): MICQP with fixed p and bounded feasible region is polynomially solvable on a Turing machine.
Used to solve the convex subproblems in Proposition 3 and the convex case in the main recursion.
domain assumption Lemma 18 (from Del Pia [9]): flatness theorem for mixed integer lattices with bound p^2^{p(p-1)/4}.
Load-bearing for the partition alternatives in Propositions 4 and 5.
domain assumption Lemma 21 (from Del Pia-Dey-Molinaro [10]): if MIQP is feasible and bounded below, an optimal solution of size bounded by a polynomial-size integer exists.
Used to bound the feasible region in Initialization step 1.
domain assumption Lemma 22 (from Del Pia [8]): affine reformulation of mixed integer linear sets.
Used to make polyhedra full-dimensional and to reduce the number of integer variables in the recursion.
domain assumption Lemma 23 (from Del Pia [7]): rational symmetric decomposition L^T H L = D.
Used to check positive semidefiniteness in the recursion.
domain assumption The input matrix M comes in factored form M = C^T C with rational nonsingular C.
Explicitly flagged by the authors as a genuine restriction; necessary for rational simultaneous diagonalization (Example 3).
domain assumption The objective function of Problem MIQP is bounded below on the feasible region, and p and k_- are fixed.
Stated assumptions of Theorem 1; boundedness is NP-hard to check and imposed rather than verified.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming." pith.science (2026). https://pith.science/paper/KPS6ZADR

@misc{pith2026260729386,
  author       = {Pith},
  title        = {Pith review of: Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KPS6ZADR}},
  note         = {Machine review of arXiv:2607.29386}
}

read the original abstract

We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective function are fixed. Unless P=NP, both restrictions are necessary, so this completes the characterization of the complexity of approximating MIQP in terms of the number of integer variables and the inertia of the Hessian; the result is new already in the purely continuous case. The main ingredient is a polynomial-time simultaneous diagonalization algorithm: it computes a rational change of basis that maps a given ellipsoid, presented in factored form, exactly to a ball, while making the objective function separable up to an arbitrarily small perturbation and preserving the inertia of its Hessian. The classical construction, in which the objective function is made exactly separable, requires a change of basis that is in general irrational, and cannot be carried out on a Turing machine; ours rests instead on rational Jacobi rotations, which we believe to be of independent interest.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references

[1]

The complexity of approximating a nonlinear program.Mathe- matical Programming, 69:429–441, 1995

Mihir Bellare and Phillip Rogaway. The complexity of approximating a nonlinear program.Mathe- matical Programming, 69:429–441, 1995

1995
[2]

Biblioth` eque Nationale, Paris, 1829

Augustin Cauchy.Exercises de Mathematiques, Quatri` eme Ann´ ee. Biblioth` eque Nationale, Paris, 1829
[3]

Dax and S

A. Dax and S. Kaniel. Pivoting techniques for symmetric Gaussian elimination.Numerische Math- ematik, 28:221–241, 1977

1977
[4]

Etienne de Klerk, Monique Laurent, and Pablo A. Parrilo. A PTAS for the minimization of polyno- mials of fixed degree over the simplex.Theoretical Computer Science, 361:210–225, 2006

2006
[5]

On approximation algorithms for concave mixed-integer quadratic programming

Alberto Del Pia. On approximation algorithms for concave mixed-integer quadratic programming. In Proceedings of IPCO 2016, volume 9682 ofLecture Notes in Computer Science, pages 1–13. Springer, 2016

2016
[6]

On approximation algorithms for concave mixed-integer quadratic programming

Alberto Del Pia. On approximation algorithms for concave mixed-integer quadratic programming. Mathematical Programming, Series B, 172(1–2):3–16, 2018

2018
[7]

An approximation algorithm for indefinite mixed integer quadratic programming

Alberto Del Pia. An approximation algorithm for indefinite mixed integer quadratic programming. Mathematical Programming, Series A, 201:263–293, 2023

2023
[8]

Convex quadratic sets and the complexity of mixed integer convex quadratic programming.SIAM Journal on Optimization, 35(3):1822–1845, 2025

Alberto Del Pia. Convex quadratic sets and the complexity of mixed integer convex quadratic programming.SIAM Journal on Optimization, 35(3):1822–1845, 2025. 34

2025

Show all 18 references

[9]

The mixed integer trust region problem.Mathematical Programming, Series A, 213:699–736, 2025

Alberto Del Pia. The mixed integer trust region problem.Mathematical Programming, Series A, 213:699–736, 2025

2025
[10]

Dey, and Marco Molinaro

Alberto Del Pia, Santanu S. Dey, and Marco Molinaro. Mixed-integer quadratic programming is in NP.Mathematical Programming, Series A, 162(1):225–240, 2017

2017
[11]

Golub and C.F

G.H. Golub and C.F. Van Loan.Matrix Computations, 4rd edition. Johns Hopkins University Press, Baltimore, MD, USA, 2013

2013
[12]

Hendrik W. Jr. Lenstra. Integer programming with a fixed number of variables.Mathematics of Operations Research, 8(4):538–548, 1983

1983
[13]

Mignotte

M. Mignotte. Some useful bounds. In B. Buchberger, G.E. Collins, and R. Loos, editors,Computer Algebra: Symbolic and Algebraic Computation, pages 259–263. Springer, Verlag, Wien, 1982

1982
[14]

Nemirovski and David Berkovich Yudin.Problem Complexity and Method Efficiency in Optimization

Arkadi S. Nemirovski and David Berkovich Yudin.Problem Complexity and Method Efficiency in Optimization. Wiley, Chichester, 1983. Translated by E.R. Dawson from Slozhnost’ Zadach i Effektivnost’ Metodov Optimizatsii (1979)

1983
[15]

Pardalos and Stephen A

Panos M. Pardalos and Stephen A. Vavasis. Quadratic programming with one negative eigenvalue is NP-hard.Journal of Global Optimization, 1(1):15–22, 1991

1991
[16]

Wiley, Chichester, 1986

Alexander Schrijver.Theory of Linear and Integer Programming. Wiley, Chichester, 1986

1986
[17]

Stephen A. Vavasis. Approximation algorithms for indefinite quadratic programming.Mathematical Programming, 57:279–311, 1992

1992
[18]

Stephen A. Vavasis. On approximation algorithms for concave quadratic programming. In C.A. Floudas and Panos M. Pardalos, editors,Recent Advances in Global Optimization, pages 3–18. Princeton University Press, Princeton, NJ, 1992. 35

1992

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

The complexity of approximating a nonlinear program.Mathe- matical Programming, 69:429–441, 1995

Mihir Bellare and Phillip Rogaway. The complexity of approximating a nonlinear program.Mathe- matical Programming, 69:429–441, 1995

1995

[2] [2]

Biblioth` eque Nationale, Paris, 1829

Augustin Cauchy.Exercises de Mathematiques, Quatri` eme Ann´ ee. Biblioth` eque Nationale, Paris, 1829

[3] [3]

Dax and S

A. Dax and S. Kaniel. Pivoting techniques for symmetric Gaussian elimination.Numerische Math- ematik, 28:221–241, 1977

1977

[4] [4]

Etienne de Klerk, Monique Laurent, and Pablo A. Parrilo. A PTAS for the minimization of polyno- mials of fixed degree over the simplex.Theoretical Computer Science, 361:210–225, 2006

2006

[5] [5]

On approximation algorithms for concave mixed-integer quadratic programming

Alberto Del Pia. On approximation algorithms for concave mixed-integer quadratic programming. In Proceedings of IPCO 2016, volume 9682 ofLecture Notes in Computer Science, pages 1–13. Springer, 2016

2016

[6] [6]

On approximation algorithms for concave mixed-integer quadratic programming

Alberto Del Pia. On approximation algorithms for concave mixed-integer quadratic programming. Mathematical Programming, Series B, 172(1–2):3–16, 2018

2018

[7] [7]

An approximation algorithm for indefinite mixed integer quadratic programming

Alberto Del Pia. An approximation algorithm for indefinite mixed integer quadratic programming. Mathematical Programming, Series A, 201:263–293, 2023

2023

[8] [8]

Convex quadratic sets and the complexity of mixed integer convex quadratic programming.SIAM Journal on Optimization, 35(3):1822–1845, 2025

Alberto Del Pia. Convex quadratic sets and the complexity of mixed integer convex quadratic programming.SIAM Journal on Optimization, 35(3):1822–1845, 2025. 34

2025