Optimization Online


Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables

Jong-Shi Pang (jongship***at***usc.edu)
Shaoning Han (shaoning***at***usc.edu)

Abstract: This paper begins with a class of 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. Extension of the Hessian class is also discussed. Our research is motivated by a preprint [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 $\mbox{O}(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.

Keywords: Quadratic programs, strong polynomiality, diagonal dominance, Z-matrix

Category 1: Applications -- OR and Management Sciences

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 12/07/2021
Entry Accepted: 12/07/2021
Entry Last Modified: 12/07/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society