Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables

DOI10.1137/21M1463793MaRDI QIDQ6161304zbMATH OpenOpenAlexFDO

Authors Jong-Shi Pang, Shaoning Han

Publication date 27 June 2023

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.03886

zbMATH Keywords

diagonal dominancequadratic programsstrong polynomialityZ-matrix

Mathematics Subject Classification ID

Quadratic programming (90C20) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Abstract: This paper begins with a class of convex quadratic programs (QPs) with bounded variables solvable by the parametric principal pivoting algorithm with $mathcalO(n^3)$ strongly polynomial complexity, where $n$ is the number of variables of the problem. Extension of the Hessian class is also discussed. Our research is motivated by a recent reference [7] wherein the efficient solution of a quadratic program 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 $mathcalO(n^2)$. Our strongly polynomiality results extend previous works of some strongly polynomially solvable linear complementarity problems with a P-matrix [9]; special cases of the extended results include weakly quasi-diagonally dominant problems in addition to the tridiagonal ones.

Recommendations

• scientific article; zbMATH DE number 1139465
• On the complexity of quadratic programming with two quadratic constraints
• Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm
• A note on the strong polynomiality of convex quadratic programming
• scientific article; zbMATH DE number 3850827

Cites work

• A graph-based decomposition method for convex quadratic optimization with indicators
• A Survey onM-Matrices
• An extension of Karmarkar's projective algorithm for convex quadratic programming
• scientific article; zbMATH DE number 46301 (Why is no real title available?)
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• Linear-step solvability of some folded concave and singly-parametric sparse optimization problems
• Manifestations of the Schur complement
• Some LCPs solvable in strongly polynomial time with Lemke's algorithm
• The Linear Complementarity Problem

Cited in

(3)

• A note on the strong polynomiality of convex quadratic programming
• scientific article; zbMATH DE number 1139465 (Why is no real title available?)
• On the number of pivots of Dantzig's simplex methods for linear and convex quadratic programs

This page was built for publication: Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161304)