Computational complexity of LCPs associated with positive definite symmetric matrices

DOI10.1007/BF01588254zbMATH Open0421.90072OpenAlexW1997984350MaRDI QIDQ3854941FDOQ3854941

Publication date: 1979

Published in: Mathematical Programming (Search for Journal in Brave)

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

Gray code Lemke's algorithm linear complementarity P-matrix positive definite symmetric matrices

Analysis of algorithms and problem complexity (68Q25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Cites Work

Title not available (Why is that?)
Complementary pivot theory of mathematical programming
Bimatrix Equilibrium Points and Mathematical Programming
Monotone solutions of the parametric linear complementarity problem
Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
Title not available (Why is that?)
On the number of solutions to the complementarity problem and spanning properties of complementary cones
Computational complexity of complementary pivot methods
Title not available (Why is that?)
On the Alass of Complementary Cones and Lemke’s Algorithm
On a Characterization ofP-Matrices

Cited In (36)

A continuation method for linear complementarity problems with \({P}_{0}\) matrix
A new proof for the criss-cross method for quadratic programming
An improved full-Newton step \(O(n)\) infeasible interior-point method for horizontal linear complementarity problem
A partially smoothing Jacobian method for nonlinear complementarity problems with \(P_0\) function
On solving linear complementarity problems by DC programming and DCA
An interior-point algorithm for \(P_{ast}(kappa)\)-linear complementarity problem based on a new trigonometric kernel function
A feasible directions algorithm for nonlinear complementarity problems and applications in mechanics
On the convergence of an iterative method for solving linear complementarity problem with WGPSBD matrix
A new path-following algorithm for nonlinear \(P_*\) complementarity problems
A new infeasible Mehrotra-type predictor-corrector algorithm for nonlinear complementarity problems over symmetric cones
Infeasible path-following interior point algorithm for Cartesian \(P_\ast(\kappa )\) nonlinear complementarity problems over symmetric cones
The numerical study of a regularized smoothing Newton method for solving \(P_{0}\)-NCP based on the generalized smoothing Fischer-Burmeister function
A new smoothing and regularization Newton method for \(P_{0}\)-NCP
The steepest descent gravitational method for linear programming
On the number of iterations of local improvement algorithms
A polynomial-time algorithm for a class of linear complementarity problems
Generalized Newton method in contact mechanics
A modified feasible semi-smooth asymptotically Newton method for nonlinear complementarity problems
On the computational complexity of piecewise-linear homotopy algorithms
Finite termination of a Newton-type algorithm for a class of affine variational inequality problems
Finite termination of a Newton-type algorithm based on a new class of smoothing functions for the affine variational inequality problem
Convergence of a smoothing-type algorithm for the monotone affine variational inequality problem
An infeasible interior-point algorithm for monotone linear complementarity problem based on a specific kernel function
Verification for existence of solutions of linear complementarity problems
Some LCPs solvable in strongly polynomial time with Lemke's algorithm
A full-Newton step feasible interior-point algorithm for \(P_\ast(\kappa)\)-linear complementarity problems
A new smoothing Broyden-like method for solving nonlinear complementarity problem with a \(P_{0}\)-function
NP-completeness of the linear complementarity problem
A mixed formulation for frictional contact problems prone to Newton like solution methods
Affirmative action algorithms
A non-monotone inexact regularized smoothing Newton method for solving nonlinear complementarity problems
A wide-neighborhood predictor-corrector interior-point algorithm for linear complementarity problems
Low order polynomial bounds on the expected performance of local improvement algorithms
On the finite convergence of Newton-type methods for \(P_{0}\) affine variational inequalities
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
Computational complexity of Van der Heyden's variable dimension algorithm and Dantzig-Cottle's principal pivoting method for solving LCP's

This page was built for publication: Computational complexity of LCPs associated with positive definite symmetric matrices

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