Complexity of a noninterior path-following method for the linear complementarity problem

DOI10.1023/A:1013040428127zbMath1049.90097MaRDI QIDQ5959900

James V. Burke, Song Xu

Publication date: 11 April 2002

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

zbMATH Keywords

Linear complementarity, noninterior path-following methods, complexity of algorithms

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) Interior-point methods (90C51)

Related Items (7)

A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem ⋮ An entire space polynomial-time algorithm for linear programming ⋮ Some non-interior path-following methods based on a scaled central path for linear complementarity problems ⋮ A general class of penalty/barrier path-following Newton methods for nonlinear programming ⋮ Interior hybrid proximal extragradient methods for the linear monotone complementarity problem ⋮ An exterior point polynomial-time algorithm for convex quadratic programming ⋮ An interior point parameterized central path following algorithm for linearly constrained convex programming

Cites Work

• Unnamed Item
• On a global projection-type error bound for the linear complementarity problem
• Error bounds for the linear complementarity problem with a P-matrix
• Some interlacing properties of the Schur complement of a Hermitian matrix
• New improved error bounds for the linear complementarity problem
• The global linear convergence of an infeasible non-interior path-following algorithm for complementarity problems with uniform \(P\)-functions
• A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques
• Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems
• A class of smoothing functions for nonlinear and mixed complementarity problems
• A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints
• A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems
• A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities
• A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem
• Growth behavior of a class of merit functions for the nonlinear complementarity problem
• The Global Linear Convergence of a Noninterior Path-Following Algorithm for Linear Complementarity Problems
• A Non-Interior-Point Continuation Method for Linear Complementarity Problems
• On Homotopy-Smoothing Methods for Box-Constrained Variational Inequalities
• Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities
• Improving the convergence of non-interior point algorithms for nonlinear complementarity problems
• A Global Linear and Local Quadratic Noninterior Continuation Method for Nonlinear Complementarity Problems Based on Chen--Mangasarian Smoothing Functions
• Some Noninterior Continuation Methods for Linear Complementarity Problems
• Global Convergence Analysis of the Generalized Newton and Gauss-Newton Methods of the Fischer-Burmeister Equation for the Complementarity Problem

This page was built for publication: Complexity of a noninterior path-following method for the linear complementarity problem