  


Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables
JongShi Pang (jongshipusc.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 polynomialtime 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 Pmatrix [9]; special cases of the extended results include weakly quasidiagonally dominant problems in addition to the tridiagonal ones. Keywords: Quadratic programs, strong polynomiality, diagonal dominance, Zmatrix Category 1: Applications  OR and Management Sciences Category 2: Nonlinear Optimization (Quadratic Programming ) Category 3: Nonlinear Optimization Citation: Download: [PDF] Entry Submitted: 12/07/2021 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  