Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem
This paper deals with the LCP (linear complementarity problem) with a positive semi-definite matrix. Assuming that a strictly positive feasible solution of the LCP is available, we propose ellipsoids each of which contains all the solutions of the LCP. We use such an ellipsoid for computing a lower bound and an upper bound for each coordinate of the solutions of the LCP. We can apply the lower bound to test whether a given variable is positive over the solution set of the LCP. That is, if the lower bound is positive, we know that the variable is positive over the solution set of the LCP; hence, by the complementarity condition, its complement is zero. In this case we can eliminate the variable and its complement from the LCP. We also show how we efficiently combine the ellipsoid method for computing bounds for the solution set with the path- following algorithm proposed by the authors for the LCP [ibid., Ser. A 44, No.1, 1-26 (1989; Zbl 0676.90087)]. If the LCP has a unique non- degenerate solution, the lower bound and the upper bound for the solution, computed at each iteration of the path-following algorithm, both converge to the solution of the LCP.
- Bounds for the solution set of linear complementarity problems
- AN O(n^3L) ALGORITHM USING A SEQUENCE FOR A LINEAR COMPLEMENTARITY PROBLEM
- scientific article; zbMATH DE number 432996
- A polynomial-time algorithm for a class of linear complementarity problems
- scientific article; zbMATH DE number 6020688
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- A polynomial-time algorithm, based on Newton's method, for linear programming
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- Bimatrix Equilibrium Points and Mathematical Programming
- Characterizations of bounded solutions of linear complementarity problems
- Containing and shrinking ellipsoids in the path-following algorithm
- Determining basic variables of optimal solutions in Karmarkar's new LP algorithm
- Equilibrium Points of Bimatrix Games
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 4164543 (Why is no real title available?)
- scientific article; zbMATH DE number 4041641 (Why is no real title available?)
- scientific article; zbMATH DE number 3562788 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- scientific article; zbMATH DE number 3284926 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
- Interior path following primal-dual algorithms. I: Linear programming
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- Karmarkar's algorithm and the ellipsoid method
- On the solution of some (parametric) linear complementarity problems with applications to portfolio selection, structural engineering and actuarial graduation
- Simple computable bounds for solutions of linear complementarity problems and linear programs
This page was built for publication: Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2276889)
