SOME STRONGLY POLYNOMIALLY SOLVABLE CONVEX QUADRATIC PROGRAMS WITH BOUNDED VARIABLES

This paper begins with the review of a class of strictly convex quadratic programs (QPs) with bounded variables solvable by the parametric principal pivoting algorithm with O(n3) strongly polynomial complexity, where n is the number of variables of the problem. Extensions of this Hessian class are the main contributions of this paper, which is motivated by a recent paper [P. Liu, S. Fattahi, A. G\'omez, and S. Ku\\ccu\kyavuz, Math. Program. (2022), https://doi.org/10.1007/s10107-022-01845-0], wherein the efficient solution of a QP with a tridiagonal Hessian matrix in the quadratic objective is needed for the construction of a polynomial-time algorithm for solving an associated sparse variable selection problem. With the tridiagonal structure, the complexity of the QP algo-rithm reduces to O(n2). Our strongly polynomiality results extend previous works of some strongly polynomially solvable linear complementarity problems with a P-matrix [J. S. Pang and R. Chan-drasekaran, Math. Program. Stud., 25 (1985), pp. 13--27]; special cases of the extended results include weakly quasi-diagonally dominant problems in addition to the tridiagonal ones.

Automated summary

This paper reviews a class of strictly convex quadratic programs solvable by the parametric principal pivoting algorithm. The main contribution of this paper is the extension of this Hessian class, motivated by the need to efficiently solve a QP with a tridiagonal Hessian matrix. With the tridiagonal structure, the complexity of the QP algorithm is reduced to O(n2). The strongly polynomiality results of this paper extend previous works on linear complementarity problems.