A modified standard embedding for linear complementarity problems

Allonso, Sira Allende   ; Guddat, Jürgen   ; Nowack, Dieter

Kybernetika, Tome 40 (2004) no. 5, pp. 551-570

Abstract (VO)

We propose a modified standard embedding for solving the linear complementarity problem (LCP). This embedding is a special one-parametric optimization problem $P(t), t \in [0,1]$. Under the conditions (A3) (the Mangasarian–Fromovitz Constraint Qualification is satisfied for the feasible set $M(t)$ depending on the parameter $t$), (A4) ($P(t)$ is Jongen–Jonker– Twilt regular) and two technical assumptions, (A1) and (A2), there exists a path in the set of stationary points connecting the chosen starting point for $P(0)$ with a certain point for $P(1)$ and this point is a solution for the (LCP). This path may include types of singularities, namely points of Type 2 and Type 3 in the class of Jongen–Jonker–Twilt for $t\in [0,1)$. We can follow this path by using pathfollowing procedures (included in the program package PAFO). In case that the condition (A3) is not satisfied, also points of Type 4 and 5 may appear. The assumption (A4) will be justified by a perturbation theorem. Illustrative examples are presented.

Détail

Classification : 68Q25, 90C31, 90C33, 90C51
Keywords: linear complementarity problem; standard embedding; Jongen– Jonker–Twilt regularity; Mangasarian–Fromovitz constraint qualification; pathfollowing methods

Bibliographie

[1] Allonso S. Allende, Guddat, J., Nowack D.: A modified penalty embedding for linear complementarity problems. Investigación Oper. 23 (2002), 1, 37–54 | MR

[2] Allgower E., Georg K.: Numerical Continuation Methods. An Introduction. Springer–Verlag, Berlin 1990 | MR | Zbl

[3] Bank B., Guddat J., Klatte D., Kummer, B., Tammer K.: Non-Linear Parametric Optimization. Akademie–Verlag Berlin, 1982 | Zbl

[4] Billups S. C.: A Homotopy-based algorithm for mixed complementarity problems. SIAM J. Optim. 12 (2002), 583–605 | DOI | MR | Zbl

[5] Billups S. C., Watson L. T.: A probability – one homotopie algorithm for nonsmooth equations and mixed complementarity problems. SIAM J. Optim. 12 (2002), 606–626 | DOI | MR

[7] Chen, Ch., Mangasarian O. L.: Smoothing methods for convex inequalities and linear complementarity problems. Math. Programming 71 (1995), 51–69 | DOI | MR | Zbl

[8] Pang R. W. Cottle J.-S., Stone R. E.: The Linear Complementarity Problem. Academic Press, Boston, MA, 1992 | MR

[9] Facchinei F., Pang J.-P.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. I and Vol. II. Springer Series in Operations Research, 2003 | MR | Zbl

[10] Ferris M. C., Munson, T., Ralph D.: A homotopy method for mixed complementarity problems based on the PATH–solver. In: Numerical Analysis 1999 (D. F. Griffiths and G. A. Watson, eds.), Research Notes in Mathematics, Chapman and Hall, London 2000, pp. 143–167 | MR

[11] Ferris M. C., Pang J.-S.: Engeneering and economic application of complementarity problems. SIAM Rev. 39 (1997), 669–713 | DOI | MR

[12] Fischer A.: A Newton–type method for positive–semidefinite linear complementarity problems. J. Optim. Theory Appl. 86 (1995), 3, 585–608 | DOI | MR | Zbl

[13] Fischer A., Kanzow, CH.: On finite termination of an iterative method for linear complementarity problems. Math. Programming 74 (1996), xxx–xxx | DOI | MR | Zbl

[14] Gfrerer H., Guddat J., Wacker,, Hj., Zulehner W.: Pathfollowing methods for Kuhn–Tucker curves by an active index set strategy. In: Systems and optimization (A. Bagchi and T. Th. Jongen, eds.), (Lecture Notes in Control and Information Sciences 66), Springer–Verlag Berlin, Heidelberg – New York 1985, pp. 111–131 | MR

[15] Gollmer R., Kausmann U., Nowack D., Wendler, K., Estrada J. Bacallao: Computerprogramm PAFO. Humboldt-Universität Berlin, Institut für Mathematik xxxx

[16] Gomez W., Guddat J., Jongen H. Th., Rückmann J.-J., Solano C.: Curvas criticas y saltos en optimizacion nolineal. Electronic Publication: The Electronic Library of Mathematics, http://www.emis.de/monographs/curvas/index.html

[17] Guddat J., Guerra, F., Jongen H. Th.: Parametric Optimization: Singularities, Pathfollowing and Jumps. BG Teubner, Stuttgart and John Wiley, Chichester 1990 | MR | Zbl

[18] Jongen H. Th., Jonker, P., Twilt F.: Critical Sets in Parametric Optimization. Math. Programming 34 (1986), 333–353 | DOI | MR | Zbl

[19] Jongen H. Th., Jonker, P., Twilt F.: Nonlinear Optimization in Finite Dimension: Morse Theory, Chebysher Approximation, Transversality, Flows, Parametric Aspects. Kluwer, 2000 | MR

[20] Kanzow, Ch.: Some boninterior continuation methods for linear complementarity problems. SIAM J. Appl. Anal. 17 (1996), 851–868 | DOI | MR

[21] Kojima M., Megiddo N., Noma, T., Yoshishe A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Springer, Berlin 1991

[22] Nožička F.: Über eine Klasse von linearen einparametrischen Optimierungsproblemen. Math. Operationsforschung Statist. 3, (1972), 159–194 | DOI | MR | Zbl

[23] Nožička F., Guddat J., Hollatz, H., Bank B.: Theorie der linearen parametrischen Optimierung. Akademic–Verlag, Berlin 1974 | Zbl

[24] Reinholdt W. C.: Numerical Analysis of Parametric Nonlinear Equations. John Wiley, New York 1986

[25] Rückmann J.-J., Tammer K.: On linear-quadratic perturbations in one-parametric non-linear optimization. Systems Sci. 18 (1992), 1, 37–48 | MR

[26] Schmid R.: Eine modifizierte Standardeinbettung zur Behandlung von Gleichungs- und Ungleichungsrestriktionen. Diplomarbeit, Humboldt-Universitiät zu Berlin, 2000

[27] Sellami H., Robinson S. M.: Implementation of a continuation method for normal maps. Math. Programming 76 (1976), 563–578 | DOI | MR

[28] Stoer J., Wechs H.: Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity. Math. Programming 83 (1998), 407–423 | DOI | MR | Zbl

[29] Stoer J., Wechs, M., Mizuni S.: High order infeasible-interior-point-method for sufficient linear complementarity problems. Math. Oper. Res. 23 (1998), 832–862 | DOI | MR

[30] (ed.), Hj. Wacker: Continuation Methods. Academic Press, New York 1978 | MR | Zbl

[31] Watson T.: Solving the nonlinear complementarity problem by a homotopy method. SIAM J. Control Appl. 17 (1979), 36–46 | DOI | MR | Zbl

[32] Xu S., Burke J. V.: A polynomial time interior-point path-following algorithm for LCP based on Chen–Harker–Kanzow smoothing techniques. Math. Programming 86 (1999) | MR | Zbl