Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables
本文扩展了一类严格凸二次规划的可解性，其Hessian矩阵为三对角或弱拟对角占优时，算法复杂度降至O(n²)，对稀疏变量选择问题有应用价值。
.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 \(\mbox{O}(n^3)\) 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ómez, and S. Küçü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 algorithm reduces to \(\mbox{O}(n^2)\) . Our strongly polynomiality results extend previous works of some strongly polynomially solvable linear complementarity problems with a P-matrix [J. S. Pang and R. Chandrasekaran, 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.Keywordsquadratic programsstrong polynomialitydiagonal dominanceZ-matrixMSC codes90C2090C33