Geodesic
The steepest-descent barrier-projection method for linear complementarity problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 45 (2005) no. 5, pp. 792-812 
M. V. Vtyurina; V. G. Zhadan. The steepest-descent barrier-projection method for linear complementarity problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 45 (2005) no. 5, pp. 792-812. http://geodesic.mathdoc.fr/item/ZVMMF_2005_45_5_a3/
@article{ZVMMF_2005_45_5_a3,
     author = {M. V. Vtyurina and V. G. Zhadan},
     title = {The steepest-descent barrier-projection method for linear complementarity problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {792--812},
     year = {2005},
     volume = {45},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2005_45_5_a3/}
}
TY  - JOUR
AU  - M. V. Vtyurina
AU  - V. G. Zhadan
TI  - The steepest-descent barrier-projection method for linear complementarity problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2005
SP  - 792
EP  - 812
VL  - 45
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2005_45_5_a3/
LA  - ru
ID  - ZVMMF_2005_45_5_a3
ER  - 
%0 Journal Article
%A M. V. Vtyurina
%A V. G. Zhadan
%T The steepest-descent barrier-projection method for linear complementarity problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2005
%P 792-812
%V 45
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2005_45_5_a3/
%G ru
%F ZVMMF_2005_45_5_a3

Voir la notice de l'article provenant de la source Math-Net.Ru

The linear complementarity problem with a positive definite matrix is examined. A numerical method for solving this problem is proposed that is an extension of the barrier-projection method originally used for linear and nonlinear programs. The initial approximation and all the subsequent approximations in the proposed method belong to the feasible set. The choice of the step size is based on the idea of the steepest descent. It is shown that the basic variant of the method has additional stationary points apart from the solution of the problem. If a certain nondegeneracy condition is fulfilled, then these stationary points coincide with the vertices of the feasible set. The local convergence of the basic variant is proved, and it is shown that the number of iteration steps does not exceed the dimension of the problem. A modified variant of the method is described in which no additional stationary points appear, and its finite nonlocal convergence is proved.

[1] Cottle R. W., Pang J.-S., Stone R. E., The linear complementarity problem, Acad. Press, Inc., Boston, 1992 | MR | Zbl

[2] Ferris M. C., Pang J.-S., “Engineering and economic applications of complementarity problems”, SIAM Rev., 39 (1997), 669–713 | DOI | MR | Zbl

[3] Berschanskii Ya. M., Meerov M. B., “Teoriya i metody resheniya zadach dopolnitelnosti”, Avtomatika i telemekhan., 1983, no. 6, 5–31

[4] Kojima M., Mizuno Sh., Yoshize A., “A polinomial-time algorithm for a class of linear complementarity problems”, Math. Program., 44 (1989), 1–26 | DOI | MR | Zbl

[5] Mangasarian O. L., “Convergence of iterates of an inexact matrix splitting algorithm for the symmetric monotone linear complementarity problem”, SIAM J. Optimizat., 1991, 114–122 | DOI | MR | Zbl

[6] Monteiro R. D. C., Wright S. J., “Superlinear primal-dual affine scaling algorithms for LCP”, Math. Program., 69 (1995), 311–333 | MR | Zbl

[7] Fischer A., Kanzov Ch., “On finite termination of an iterative method for linear complementarity problems”, Math. Program., 74 (1996), 279–292 | MR | Zbl

[8] Burke J. M., Xu S., “The global linear convergence of non-interior path-following algorithm for linear complementarity problems”, Math. Operat. Res., 23 (1998), 719–734 | DOI | MR | Zbl

[9] Vtyurina M. V., Zhadan V. G., “Barerno-gradientnye metody dlya lineinykh zadach dopolnitelnosti”, Soobsch. po prikl. matem., VTsR AN, M., 2003

[10] Evtushenko Yu. G., Zhadan V. G., “Stable barrier-projection and barrier-Newton methods in linear programming”, Comput. Optimizat. and Applic., 3:4 (1994), 289–304 | DOI | MR

[11] Evtushenko Yu. G., Zhadan V. G., “Barerno-proektivnye metody resheniya zadach nelineinogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 34:5 (1994), 669–684 | MR | Zbl

[12] Zhadan V. G., “Dual barrier-projection and barrier-Newton methods in linear programming”, System Modelling and Optimizat., 1995, 502–510 | MR