An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming

DOI10.1007/BF01588795zbMath0717.90055OpenAlexW2075023395MaRDI QIDQ2638936

Shucheng Liu, Donald Goldfarb

Publication date: 1991

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01588795

zbMATH Keywords

logarithmic barrier functionconvex quadratic programmingKarmarkar's methodprimal interior point method

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Newton-type methods (49M15) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity, A wide neighborhood arc-search interior-point algorithm for convex quadratic programming, Infinite-dimensional quadratic optimization: Interior-point methods and control applications, Active Set Methods with Reoptimization for Convex Quadratic Integer Programming, The Newton modified barrier method for QP problems, Maximum margin semi-supervised learning with irrelevant data, Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems, Integrating prediction in mean-variance portfolio optimization, Log-domain interior-point methods for convex quadratic programming, Efficient differentiable quadratic programming layers: an ADMM approach, Properties Of Primal Interior Point Methods For QP^∗, Fast quadratic programming for mean-variance portfolio optimisation, Globally maximizing the sum of squares of quadratic forms over the unit sphere, The selection of the optimal parameter in the modulus-based matrix splitting algorithm for linear complementarity problems, Unified complexity analysis for Newton LP methods, Complexity analysis of a linear complementarity algorithm based on a Lyapunov function, An interior point algorithm for convex quadratic programming with strict equilibrium constraints, On affine scaling algorithms for nonconvex quadratic programming, A polynomial method of approximate centers for linear programming, Algorithm for inequality-constrained least squares problems, An interior point algorithm of O\((\sqrt m| \ln\varepsilon |)\) iterations for \(C^ 1\)-convex programming, A long-step barrier method for convex quadratic programming, An unconstrained convex programming approach to solving convex quadratic programming problems, The nearest point problem in a polyhedral set and its extensions, An algorithm for portfolio optimization with variable transaction costs. II: Computational analysis, Identifying superfluous constraints within an interior-point algorithm for convex quadratic programming, An active index algorithm for the nearest point problem in a polyhedral cone, Quadratic Programming and Penalized Regression, A splitting method for quadratic programming problem, Characterization of optimal points in binary convex quadratic programming, An interior point method for quadratic programs based on conjugate projected gradients, Computational schemes for large-scale problems in extended linear- quadratic programming, Long-step primal path-following algorithm for monotone variational inequality problems, A new penalty function algorithm for convex quadratic programming, An exterior point polynomial-time algorithm for convex quadratic programming, On solving the densestk-subgraph problem on large graphs, An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs, Algorithms for the solution of quadratic knapsack problems, Global linear convergence of a path-following algorithm for some monotone variational inequality problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A numerically stable dual method for solving strictly convex quadratic programs
• A new polynomial-time algorithm for linear programming
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• A polynomial-time algorithm, based on Newton's method, for linear programming
• An extension of Karmarkar's projective algorithm for convex quadratic programming
• Interior path following primal-dual algorithms. I: Linear programming
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• A polynomial-time algorithm for a class of linear complementarity problems
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An Algorithm for Convex Quadratic Programming That Requires O(n^3.5L) Arithmetic Operations
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• Matrix factorizations in optimization of nonlinear functions subject to linear constraints
• Methods for Modifying Matrix Factorizations