Complexity analysis of a linear complementarity algorithm based on a Lyapunov function

DOI10.1007/BF01585708MaRDI QIDQ1184351zbMATH OpenFDO

Authors Paul Tseng

Publication date 28 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/BF01585708

zbMATH Keywords

rate of convergencecomplexity analysispositive semi-definite matriceslinear complementaritypath followingKarmarkar's method

Mathematics Subject Classification ID

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

Recommendations

• Complexity of a noninterior path-following method for the linear complementarity problem
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• Complexity analysis of primaldual algorithms for the semidefinite linear complementarity problem
• Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems
• AN O(n^3L) ALGORITHM USING A SEQUENCE FOR A LINEAR COMPLEMENTARITY PROBLEM

Cites work

• scientific article; zbMATH DE number 4131946 (Why is no real title available?)
• scientific article; zbMATH DE number 3809326 (Why is no real title available?)
• scientific article; zbMATH DE number 3914081 (Why is no real title available?)
• scientific article; zbMATH DE number 3677572 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• scientific article; zbMATH DE number 3466802 (Why is no real title available?)
• scientific article; zbMATH DE number 3516928 (Why is no real title available?)
• scientific article; zbMATH DE number 3385445 (Why is no real title available?)
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• An Algorithm for Convex Quadratic Programming That Requires O(n^3.5L) Arithmetic Operations
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• An O(n^ 3L) primal interior point algorithm for convex quadratic programming
• An interior point potential reduction algorithm for the linear complementarity problem
• Convex Analysis
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• Simple computable bounds for solutions of linear complementarity problems and linear programs

Cited in

(6)

• Complexity of a noninterior path-following method for the linear complementarity problem
• Convergence behavior of interior-point algorithms
• Global linear convergence of a path-following algorithm for some monotone variational inequality problems
• On the convergence of the affine-scaling algorithm
• On the symmetry function of a convex set
• Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp^∗

This page was built for publication: Complexity analysis of a linear complementarity algorithm based on a Lyapunov function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1184351)