×

A purification method for monotone linear complementarity problems. (Une procédure de purification pour les problèmes de complémentarité linéaire, monotones.) (French) Zbl 1092.90051

Summary: We propose a new purification method for monotone linear complementarity problems. This method associates to each iterate of the sequence, generated by an interior point method, one basis which is not necessarily feasible. We show that, under the strict complementarity and non-degeneracy hypoteses, the sequence of bases converges on a finite number of iterations to an optimal basis which gives the exact solution of the problem. The adopted process also serves to preconditioning the conjugate gradient algorithm when computing the Newton direction.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] J.F. Bonnans , J.C. Gilbert , C. Lemarechal and C. Sagastizabal , Optimisation Numérique . Aspects théoriques et pratiques. Springer-Verlag ( 1997 ). MR 1613833 | Zbl 0952.65044 · Zbl 0952.65044
[2] J.F. Bonnans and C.C. Gonzaga , Convergence of interior point algorithms for the monotone linear complementarity problem . Math. Oper. Res. 21 ( 1996 ) 1 - 25 . MR 1385864 | Zbl 0846.90109 · Zbl 0846.90109 · doi:10.1287/moor.21.1.1
[3] R.W. Cottle , J.S. Pang and V. Venkateswaran , Sufficient matrices and the linear complementarity problem . Linear Algebra Appl. 114/ 115 ( 1989 ) 231 - 249 . MR 986877 | Zbl 0674.90092 · Zbl 0674.90092 · doi:10.1016/0024-3795(89)90463-1
[4] F. Facchinei , A. Fischer and C. Kanzow , On the identification of zero variables in a interior-point framework . SIAM J. Optim. 10 ( 2000 ) 1058 - 1078 . MR 1777080 | Zbl 0999.90044 · Zbl 0999.90044 · doi:10.1137/S1052623498339739
[5] C.C. Gonzaga , Path-following methods for linear programming . SIAM Rev. 34 ( 1992 ) 167 - 224 . MR 1166175 | Zbl 0763.90063 · Zbl 0763.90063 · doi:10.1137/1034048
[6] T. Illes , J. Peng , C. Roos and T. Terlaky , A strongly polynomial rounding procedure yielding a maximally complementary solution for \(P_*(\kappa )\) linear complementarity problems . SIAM J. Optim. 11 ( 2000 ) 320 - 340 . MR 1787263 | Zbl 1010.90082 · Zbl 1010.90082 · doi:10.1137/S1052623498336590
[7] J. Ji and A. Potra , Tapia indicators and finite termination of infeasible-interior-point methods for degenerate LCP , edited by J. Renegar, M. Shub and S. Smale. AMS, Providence, RI. Math. Numer. Anal., Lect. Appl. Math. 32 ( 1996 ) 443 - 454 . MR 1421349 | Zbl 0868.90121 · Zbl 0868.90121
[8] J. Ji , A. Potra and S. Huang , Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence . JOTA 85 ( 1995 ) 187 - 199 . MR 1330846 | Zbl 0824.90129 · Zbl 0824.90129 · doi:10.1007/BF02192304
[9] A. Kadiri , Analyse numérique des méthodes de points intérieurs pour les problèmes de complémentarité linéaire et la programmation quadratique convexe . Thèse de Doctorat, INSA de Rouen ( 2001 ).
[10] C.T. Kelley , Iterative methods for linear and nonlinear equations . Frontiers Appl. Math. 16 ( 1995 ). MR 1344684 | Zbl 0832.65046 · Zbl 0832.65046
[11] M. Kojima , S. Mizuno and A. Yoshise , A polynomial-time algorithm for a class of linear complementarity problems . Math. Program. 44 ( 1989 ) 1 - 26 . MR 999720 | Zbl 0676.90087 · Zbl 0676.90087 · doi:10.1007/BF01587074
[12] M. Kojima , Y. Kurita and S. Mizuno , Large-step interior point algorithmsfor linear complementarity problems . SIAM J. Optim. 3 ( 1993 ) 398 - 412 . MR 1215450 | Zbl 0781.90085 · Zbl 0781.90085 · doi:10.1137/0803018
[13] K. Kortanek and J. Zhu , New purification algorithms for linear programming . Naval Res. Logist 35 ( 1988 ) 571 - 583 . MR 952507 | Zbl 0685.90070 · Zbl 0685.90070 · doi:10.1002/1520-6750(198808)35:4<571::AID-NAV3220350410>3.0.CO;2-L
[14] K. Mcshane , Superlineary convergent \(O(\sqrt{n}L)\)-iteration interior-point algorithms for LP and the monotone LCP . SIAM J. Optim. 4 ( 1994 ) 247 - 261 . MR 1273758 | Zbl 0822.90102 · Zbl 0822.90102 · doi:10.1137/0804014
[15] R. Monteiro and I. Adler , Interior path-following primal-dual algorithms, part II\(\!\!\): Convex quadratic programming . Math. Program. 44 ( 1989 ) 43 - 66 . MR 999722 | Zbl 0676.90039 · Zbl 0676.90039 · doi:10.1007/BF01587076
[16] R. Monteiro and S. Wright , Local convergence of interior-point algorithms for degenerate monotone LCP . Comput. Optim. Appl. 3 ( 1994 ) 131 - 155 . MR 1273658 | Zbl 0801.90110 · Zbl 0801.90110 · doi:10.1007/BF01300971
[17] C.R. Papadimitriou and K. Steiglitz , Combinatorial Optimization\(\!\!\): Algorithms and Complexity . Prentice-Hall. Englewood Cliffs, New Jersey ( 1982 ). MR 663728 | Zbl 0503.90060 · Zbl 0503.90060
[18] F.A. Potra and R. Sheng , A superlineary convergent infeasible-interior-point algorithm for degenerate LCP . J. Optim. Theory Appl. 97 ( 1998 ) 249 - 269 . MR 1625072 | Zbl 0907.90261 · Zbl 0907.90261 · doi:10.1023/A:1022670415661
[19] Y. Ye , On the finite convergence of interior point algorithms for linear programming . Math. Program. 57 ( 1992 ) 325 - 335 . MR 1195030 | Zbl 0794.90036 · Zbl 0794.90036 · doi:10.1007/BF01581087
[20] Y. Ye , Interior Point Algorithms\(\!\!\): Theory and Analysis . John Wiley, New York ( 1997 ). MR 1481160 | Zbl 0943.90070 · Zbl 0943.90070
[21] Y. Ye and K.M. Anstreicher , On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP . Math. Program. 62 ( 1993 ) 537 - 551 . MR 1251890 | Zbl 0799.90111 · Zbl 0799.90111 · doi:10.1007/BF01585182
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.