Determining the handicap of a sufficient matrix
It is known that \(A\in\mathbb{R}^{n\times n}\) is sufficient if and only if there is a \(k\geq 0\) auch that (1) \((1+4k) \sum_{i\in I_+(x)} x_iy_i+ \sum_{i\in I_-(x)} x_iy_i\geq 0\) for all \(x\in\mathbb{R}^n\), where \(y=Ax\) and \(I_+(x)= \{i\mid x_iy_i>0\}\) and \(I_-(x)= \{i\mid x_iy_i<0\}\), and any sufficient linear complementarity problem can be solved by means of the unified interior point method. The smaller \(k\) in (1) can be chosen, the better the complexity bound of the method. This value is called the handicap of sufficient matrix \(A\). After some preliminaries the author derives a general expression for the handicap of a sufficient indefinite matrix of order two and determines the handicaps of P-matrices (the class of matrices with positive principal minors). Further, he shows that, for \(n\geq 3\), determining the handicap of a sufficient matrix \(A\in\mathbb{R}^{n\times n}\), not in P, can be reduced to determining handicaps of P-matrices of order less than \(n\) and those of sufficient matrices of order two. Finally, he indicates that the handicaps of a sufficient matrix and its transpose are equal.
- \(P_ *\)-matrices are just sufficient
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- scientific article; zbMATH DE number 53115 (Why is no real title available?)
- On a subclass of \(P_ 0\)
- On inverting partitioned matrices
- On Nonlinear Fractional Programming
- Sufficient matrices and the linear complementarity problem
- The principal pivoting method revisited
- d-orientation sequences for continuous functions and nonlinear complementarity problems
- Two interior-point methods for nonlinear P_*()-complementarity problems.
- Feasible corrector-predictor interior-point algorithm for \(P_* (\kappa)\)-linear complementarity problems based on a new search direction
- Predictor–corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path
- On the complexity of computing the handicap of a sufficient matrix
- Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation
- A New full-newton step infeasible interior-point method for P_*(\kappa )-linear Complementarity problem
- A new Ai-Zhang type interior point algorithm for sufficient linear complementarity problems
- Sufficient matrices: properties, generating and testing
- Polynomial convergence of two higher order interior-point methods for \(P_*(\kappa)\)-LCP in a wide neighborhood of the central path
- Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation
- A polynomial path-following interior point algorithm for general linear complementarity problems
This page was built for publication: Determining the handicap of a sufficient matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q677143)
