An interior point potential reduction algorithm for the linear complementarity problem
From MaRDI portal
Publication:1196718
DOI10.1007/BF01586054zbMath0764.90083MaRDI QIDQ1196718
Kojima, Masakazu, Yinyu Ye, Nimrod Megiddo
Publication date: 16 January 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
linear complementarity; smallest eigenvalue; potential function; \(P\)-matrix; convex quadratic minimization; interior point potential reduction algorithm
90C20: Quadratic programming
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 little theorem of the big \({\mathcal M}\) in interior point algorithms, Interior-point algorithms for global optimization, On total functions, existence theorems and computational complexity, A class of linear complementarity problems solvable in polynomial time, An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems, A unified approach to interior point algorithms for linear complementarity problems: A summary, Comparative analysis of affine scaling algorithms based on simplifying assumptions, Complexity analysis of a linear complementarity algorithm based on a Lyapunov function, A new polynomial time method for a linear complementarity problem, A superlinearly convergent projection algorithm for solving the convex inequality problem, Investigation of path-following algorithms for signomial geometric programming problems, An extension of the potential reduction algorithm for linear complementarity problems with some priority goals, Global convergence in infeasible-interior-point algorithms, Extensions of the potential reduction algorithm for linear programming, Potential-reduction methods in mathematical programming, Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems, 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, Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, Interior-point methods for linear programming: a review
Cites Work
- A new polynomial-time algorithm for linear programming
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- Polynomial affine algorithms for linear programming
- The Jacobian matrix and global univalence of mappings
