An Algorithm for Convex Quadratic Programming That Requires O(n3.5L) Arithmetic Operations

DOI10.1287/moor.15.2.342zbMath0714.90075OpenAlexW1989097425MaRDI QIDQ3200887

Sanjay Mehrotra, Jie Sun

Publication date: 1990

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.15.2.342

zbMATH Keywords

convex quadratic programminginterior point methodsKarmarkar's algorithmworst case boundapproximate analytic centersequence of nested convex sets

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20)

Related Items (22)

A full-step interior-point algorithm for linear complementarity problem based on a simple function ⋮ An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming ⋮ Active Set Methods with Reoptimization for Convex Quadratic Integer Programming ⋮ Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis ⋮ A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function ⋮ Properties Of Primal Interior Point Methods For QP^∗ ⋮ Complexity analysis of a linear complementarity algorithm based on a Lyapunov function ⋮ On affine scaling algorithms for nonconvex quadratic programming ⋮ An interior point algorithm of O\((\sqrt m| \ln\varepsilon |)\) iterations for \(C^ 1\)-convex programming ⋮ An unconstrained convex programming approach to solving convex quadratic programming problems ⋮ Identifying superfluous constraints within an interior-point algorithm for convex quadratic programming ⋮ Characterization of optimal points in binary convex quadratic programming ⋮ On the convergence of the method of analytic centers when applied to convex quadratic programs ⋮ A new penalty function algorithm for convex quadratic programming ⋮ On uniform consistent estimators for convex regression ⋮ Minimal representation of convex regions defined by analytic functions ⋮ On infeasibility of systems of convex analytic inequalities ⋮ An exterior point polynomial-time algorithm for convex quadratic programming ⋮ An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs ⋮ An \(O(n^ 3L)\) potential reduction algorithm for linear programming ⋮ An interior point parameterized central path following algorithm for linearly constrained convex programming ⋮ Interior-point algorithm for quadratically constrained entropy minimization problems

This page was built for publication: An Algorithm for Convex Quadratic Programming That Requires O(n^3.5L) Arithmetic Operations