Convergence behavior of interior-point algorithms

DOI10.1007/BF01580610zbMath0803.90087OpenAlexW2050897335MaRDI QIDQ689124

Osman Güler, Yinyu Ye

Publication date: 6 December 1993

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

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

zbMATH Keywords

interior point algorithmsstrict complementarity condition

Mathematics Subject Classification ID

Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

Conic convex programming and self-dual embedding, A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming, Constant potential primal-dual algorithms: A framework, Recovering an optimal LP basis from an interior point solution, Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, Unnamed Item, On homogeneous and self-dual algorithms for LCP, Initialization in semidefinite programming via a self-dual skew-symmetric embedding, A primal-dual interior-point method for linear programming based on a weighted barrier function, ON THE PROPERTIES OF ∊-SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING, Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming, Theory of semidefinite programming for sensor network localization, A Mehrotra-type predictor-corrector algorithm with polynomiality and \(Q\)-subquadratic convergence, Identifying an optimal basis in linear programming, Interior-point methods for nonlinear complementarity problems, A general parametric analysis approach and its implication to sensitivity analysis in interior point methods, Input design for discrimination between classes of LTI models, Primal-Dual Path-Following Methods and the Trust-Region Updating Strategy for Linear Programming with Noisy Data, A superlinearly convergent wide-neighborhood predictor-corrector interior-point algorithm for linear programming, An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints, Dynamic non-diagonal regularization in interior point methods for linear and convex quadratic programming, A step-truncated method in a wide neighborhood interior-point algorithm for linear programming, A polynomial arc-search interior-point algorithm for convex quadratic programming, A quadratically convergent polynomial long-step algorithm for A class of nonlinear monotone complementarity problems^*, Quadratic regularizations in an interior-point method for primal block-angular problems, Identifying the optimal partition in convex quadratic programming, On the uniqueness of optimal strategies in symmetric matrix games, On the behavior of Lagrange multipliers in convex and nonconvex infeasible interior point methods, Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization, A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion, On interior algorithms for linear programming with no regularity assumptions, On the finite convergence of interior-point algorithms for linear programming, A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties, On the probabilistic complexity of finding an approximate solution for linear programming, Necessary and sufficient conditions of solution uniqueness in 1-norm minimization, On self-regular IPMs (with comments and rejoinder), Stabilization of Mehrotra's primal-dual algorithm and its implementation, A new algorithm for solving convex parametric quadratic programs based on graphical derivatives of solution mappings, General central path and the largest step general central path following algorithm for linear programming, A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks, Characterizing the universal rigidity of generic frameworks, On the convergence of primal-dual interior-point methods with wide neighborhoods, On the convergence rate of Newton interior-point methods in the absence of strict complementarity, Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming, On parametric semidefinite programming, A STUDY ON SENSITIVITY ANALYSIS FOR CONVEX QUADRATIC PROGRAMS, Analytic centers and repelling inequalities, Finding an interior point in the optimal face of linear programs, On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP, On the convergence of a predictor-corrector variant algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A modification of Karmarkar's linear programming algorithm
• A long-step barrier method for convex quadratic programming
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction 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
• 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
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• Complexity analysis of a linear complementarity algorithm based on a Lyapunov function
• Long steps in an \(O(n^ 3L)\) algorithm for linear programming
• A polynomial method of approximate centers for linear programming
• An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem
• Near boundary behavior of primal-dual potential reduction algorithms for linear programming
• Theoretical convergence of large-step primal-dual interior point algorithms for linear programming
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An Extension of Karmarkar Type Algorithm to a Class of Convex Separable Programming Problems with Global Linear Rate of Convergence
• Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method
• Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
• On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
• An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
• An Implementation of a Primal-Dual Interior Point Method for Linear Programming
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Existence of Interior Points and Interior Paths in Nonlinear Monotone Complementarity Problems
• Large-Step Interior Point Algorithms for Linear Complementarity Problems