Efficient algorithm solves specific quadratic programming problems quickly
A Tardos-Type Algorithm for Separable Convex Quadratic Programming
Data Structures and Algorithms
Summary
Some math problems ask you to find the best solution under certain rules, using curved shapes called quadratic functions. This paper gives a new exact method that can solve a type of these problems much faster and more reliably, especially when the rules involve whole numbers arranged in a matrix. The method keeps all calculations manageable and doesn’t get slower when certain parts of the problem change. This advance also works for related problems where the function has many curved pieces, useful in real-world settings like managing multiple network flows at once without exceeding shared limits.
What this means in practice
- •For network engineers: Optimize flows through networks with shared capacity limits and complex congestion costs using a guaranteed fast algorithm.
- •For operations researchers: Solve large-scale convex quadratic programming problems involving piecewise costs and integer constraints with bounded computational steps.
Authors
Hanqing Li
Abstract
We give an exact algorithm for continuous separable convex quadratic programming with an integer equality matrix and nonnegative variables. The number of rational arithmetic operations and comparisons is polynomial in the dimensions and the encoding length of the constraint matrix, independently of the right-hand side, linear costs, and all nonnegative quadratic weights. Intermediate rational encodings are polynomial in the complete input. This yields a strongly polynomial algorithm for every integer matrix class with polynomially bounded entry encodings, including arbitrary matrices with entries in $\{0,\pm1\}$. The local solver compresses a quadratic objective on an integer box and solves only the compressed continuous problem. Two-sided proximity on boxes with rational bounds transfers its solution to a nearby original optimum; integer optima are used only in the proof. A single linear program supplies an error bound and a dual potential, while tight-coordinate revelation and fixed feasible anchors ensure termination and control encoding lengths. An explicit lifting extends the result to convex piecewise quadratic functions of signed integer affine features, with operation counts independent of breakpoints and objective coefficients. Applications include continuous multicommodity flow with shared capacities and piecewise quadratic costs of aggregate congestion.