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

DOI10.1007/BF01594942zbMath0738.90077OpenAlexW2044061073MaRDI QIDQ1176569

Akiko Yoshise, Shinji Mizuno, Kojima, Masakazu

Publication date: 25 June 1992

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

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

zbMATH Keywords

approximate solutionpotential functioninterior point algorithmKarmarkar's algorithmpositive semi-definite linear complementaritycentral trajectorypotential reductioncentral path following algorithm

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

On the solution and complexity of a generalized linear complementarity problem, New variants of the criss-cross method for linearly constrained convex quadratic programming, 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, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, Determination of optimal vertices from feasible solutions in unimodular linear 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, Interior-point solver for large-scale quadratic programming problems with bound constraints, Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, A modified homogeneous potential reduction algorithm for solving the monotone semidefinite linear complementarity problem, Potential-reduction methods in mathematical programming, On homogeneous and self-dual algorithms for LCP, Some variants of the Todd low-complexity algorithm, A new large-update interior point algorithm for \(P_{*}(\kappa)\) LCPs based on kernel functions, A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem, Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems, 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, A quadratically convergent scaling newton’s method for nonlinear complementarity problems, Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs, EP theorems and linear complementarity problems, A sequential ADMM algorithm to find sparse LCP solutions using a \(l_2-l_1\) regularization technique with application in bimatrix game, Log-domain interior-point methods for convex quadratic programming, A class of linear complementarity problems solvable in polynomial time, A unified approach to interior point algorithms for linear complementarity problems: A summary, On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems, 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, A convergent algorithm for quantile regression with smoothing splines, A path to the Arrow-Debreu competitive market equilibrium, 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, 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, Convergence analysis of an inexact potential reduction method for convex quadratic programming, A new potential reduction algorithm for smooth convex programming, Computational experience with a modified potential reduction algorithm for linear programming, Near boundary behavior of primal-dual potential reduction algorithms for linear programming, The linear complementarity problem, sufficient matrices, and the criss- cross method, Two interior-point methods for nonlinear \(P_*(\tau)\)-complementarity problems., A wide neighborhood interior-point algorithm based on the trigonometric kernel function, An interior point potential reduction method for constrained equations, Average number of iterations of some polynomial interior-point -- algorithms for linear programming, Degeneracy in interior point methods for linear programming: A survey, An interior point algorithm for large scale portfolio optimization, Interior-point algorithms for global optimization, O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming, An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs, Algorithms for the solution of quadratic knapsack problems, An interior point parameterized central path following algorithm for linearly constrained convex programming, Interior point methods for optimal control of discrete time systems, A primal-dual affine-scaling potential-reduction algorithm for linear programming

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