Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm (Q909582)

\textit{E. Tardos} [Oper. Res. 34, 250-256 (1986; Zbl 0626.90053)] was the first to present a polynomial algorithm for solving LP problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand sides and the cost coefficients. This paper extends Tardos' results to convex quadratic programming problems of the form \[ (P)\quad Max\{c^ Tx-(1/2)x^ TDx:\quad Ax\leq b,\quad x\geq 0\} \] with D being a positive definite matrix. A polynomially bounded algorithm for solving (P) where the number of arithmetic steps is independent of c and b, but depends on the size of the entries of the matrices A and D is developed. The algorithm finds optimal primal and dual solutions to (P), if they exist, by solving a sequence of simple quadratic programming problems using the polynomial algorithm and by checking feasibility of linear system in time independent of the right hand sides.