An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems

DOI10.1007/BF01594942zbMath0738.90077MaRDI QIDQ1176569

Kojima, Masakazu, Shinji Mizuno, Akiko Yoshise

Publication date: 25 June 1992

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

zbMATH Keywords

approximate solution; potential function; interior point algorithm; Karmarkar's algorithm; positive semi-definite linear complementarity; central trajectory; potential reduction; central path following algorithm

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

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

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

A quadratically convergent scaling newton’s method for nonlinear complementarity problems, A new potential reduction algorithm for smooth convex programming, A convergent algorithm for quantile regression with smoothing splines, A little theorem of the big \({\mathcal M}\) in interior point algorithms, On the finite convergence of interior-point algorithms for linear programming, A long-step barrier method for convex quadratic programming, Convergence behavior of interior-point algorithms, Interior-point algorithms for global optimization, O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming, Algorithms for the solution of quadratic knapsack problems, A new large-update interior point algorithm for \(P_{*}(\kappa)\) LCPs based on kernel functions, A class of linear complementarity problems solvable in polynomial time, A unified approach to interior point algorithms for linear complementarity problems: A summary, Comparative analysis of affine scaling algorithms based on simplifying assumptions, On lower bound updates in primal potential reduction methods for linear programming, A survey of search directions in interior point methods for linear programming, On the complexity of following the central path of linear programs by linear extrapolation. II, An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem, Complexity analysis of a linear complementarity algorithm based on a Lyapunov function, A note on a potential reduction algorithm for LP with simultaneous primal-dual updating, On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise, A new polynomial time method for a linear complementarity problem, The linear complementarity problem, sufficient matrices, and the criss- cross method, Degeneracy in interior point methods for linear programming: A survey, An interior point algorithm for large scale portfolio optimization, An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs, Interior point methods for optimal control of discrete time systems, A primal-dual affine-scaling potential-reduction algorithm for linear programming, On the solution and complexity of a generalized linear complementarity problem, A globally convergent primal-dual interior point algorithm for convex programming, Descent approaches for quadratic bilevel programming, Global convergence in infeasible-interior-point algorithms, Interior-point algorithms for semi-infinite programming, Primal-dual algorithms for linear programming based on the logarithmic barrier method, Limiting behavior of weighted central paths in linear programming, Interior-point algorithms for monotone affine variational inequalities, Potential-reduction methods in mathematical programming, On homogeneous and self-dual algorithms for LCP, Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems, Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs, EP theorems and linear complementarity problems, Average number of iterations of some polynomial interior-point -- algorithms for linear programming, Near boundary behavior of primal-dual potential reduction algorithms for linear programming, Two interior-point methods for nonlinear \(P_*(\tau)\)-complementarity problems., An interior point potential reduction method for constrained equations, New variants of the criss-cross method for linearly constrained convex quadratic programming, Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, Some variants of the Todd low-complexity algorithm, A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem, Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs, A lower bound on the number of iterations of long-step primal-dual linear programming algorithms, Interior-point methods for nonlinear complementarity problems, A superquadratic infeasible-interior-point method for linear complementarity problems, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, Determination of optimal vertices from feasible solutions in unimodular linear programming, Interior-point solver for large-scale quadratic programming problems with bound constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global ellipsoidal approximations and homotopy methods for solving convex analytic 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
• An extension of Karmarkar's algorithm for linear programming using dual variables
• 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 interior point potential reduction algorithm for the linear complementarity problem
• An implementation of Karmarkar's algorithm for linear programming
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A Centered Projective Algorithm for Linear Programming
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
• Homotopy Continuation Methods for Nonlinear Complementarity Problems