Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems

DOI10.1007/BF02592093zbMath0853.90092OpenAlexW2014663083WikidataQ57392960 ScholiaQ57392960MaRDI QIDQ1919097

Katya Scheinberg, Arkadi Nemirovski

Publication date: 1 August 1996

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

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

zbMATH Keywords

interior point methodlogarithmic barrier functionprojective transformationpotential functionconic formconvex quadratically constrained quadratic problemspolynomial worst-case bound

Mathematics Subject Classification ID

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

Related Items

Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems, A full-step interior-point algorithm for second-order cone optimization based on a simple locally kernel function, Convexification of Queueing Formulas by Mixed-Integer Second-Order Cone Programming: An Application to a Discrete Location Problem with Congestion, Applications of second-order cone programming, Exact computable representation of some second-order cone constrained quadratic programming problems, Two new predictor-corrector algorithms for second-order cone programming, Product-form Cholesky factorization in interior point methods for second-order cone programming, Extension of a projective interior point method for linearly constrained convex programming, Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra, An Introduction to Formally Real Jordan Algebras and Their Applications in Optimization, An Inexact Augmented Lagrangian Method for Second-Order Cone Programming with Applications, A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• Comparative analysis of affine scaling algorithms based on simplifying assumptions
• On the convergence of the method of analytic centers when applied to convex quadratic programs
• An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming
• A Centered Projective Algorithm for Linear Programming
• A method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming