On the convergence of the method of analytic centers when applied to convex quadratic programs

DOI10.1007/BF01588796zbMath0725.90076OpenAlexW2044908666MaRDI QIDQ2277366

Florian Jarre

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/bf01588796

zbMATH Keywords

Newton's methodmethod of analytic centerspolynomial time complexityconvex quadratic programsestimation of the speed of convergence

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Utility function programs and optimization over the efficient set in multiple-objective decision making, Infinite-dimensional quadratic optimization: Interior-point methods and control applications, A combined homotopy interior point method for convex nonlinear programming, Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems, A polynomial time dual algorithm for the Euclidean multifacility location problem, A cutting plane algorithm for convex programming that uses analytic centers, A second order affine scaling algorithm for the geometric programming dual with logarithmic barrier, Impproving the rate of convergence of the logarithmic barrier function method, Properties Of Primal Interior Point Methods For QP^∗, Complexity analysis for certain convex programming 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, Interior-point methods for convex programming, On computing the center of a convex quadratically constrained set, On the convergence of the method of analytic centers when applied to convex quadratic programs, Global ellipsoidal approximations and homotopy methods for solving convex analytic programs, Quadratically constrained convex quadratic programmes: Faculty feasible regions, An exterior point polynomial-time algorithm for convex quadratic programming, A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming, An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs, On the classical logarithmic barrier function method for a class of smooth convex programming problems, Interior-point algorithm for quadratically constrained entropy minimization problems

Cites Work

• Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A new continuation method for complementarity problems with uniform P- functions
• A polynomial method of approximate centers for linear programming
• Containing and shrinking ellipsoids in the path-following algorithm
• On the convergence of the method of analytic centers when applied to convex quadratic programs
• La méthode des centres dans un espace topologique
• An Algorithm for Convex Quadratic Programming That Requires O(n^3.5L) Arithmetic Operations
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• A method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item