Article
Full entry |
PDF
(2.6 MB)
Feedback
PDF
(2.6 MB)
Feedback
Keywords:
linear complementarity problem; standard embedding; Jongen– Jonker–Twilt regularity; Mangasarian–Fromovitz constraint qualification; pathfollowing methods
linear complementarity problem; standard embedding; Jongen– Jonker–Twilt regularity; Mangasarian–Fromovitz constraint qualification; pathfollowing methods
Summary:
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.
References:
[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 1932562
[2] Allgower E., Georg K.: Numerical Continuation Methods. An Introduction. Springer–Verlag, Berlin 1990 MR 1059455 | Zbl 1036.65047
[3] Bank B., Guddat J., Klatte D., Kummer, B., Tammer K.: Non-Linear Parametric Optimization. Akademie–Verlag Berlin, 1982 Zbl 0502.49002
[4] Billups S. C.: A Homotopy-based algorithm for mixed complementarity problems. SIAM J. Optim. 12 (2002), 583–605 DOI 10.1137/S1052623498337431 | MR 1884907 | Zbl 1056.90132
[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 10.1137/S105262340037758X | MR 1884908
[7] Chen, Ch., Mangasarian O. L.: Smoothing methods for convex inequalities and linear complementarity problems. Math. Programming 71 (1995), 51–69 DOI 10.1007/BF01592244 | MR 1362957 | Zbl 0855.90124
[8] Pang R. W. Cottle J.-S., Stone R. E.: The Linear Complementarity Problem. Academic Press, Boston, MA, 1992 MR 1150683
[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 1955648 | Zbl 1062.90002
[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 1751116
[11] Ferris M. C., Pang J.-S.: Engeneering and economic application of complementarity problems. SIAM Rev. 39 (1997), 669–713 DOI 10.1137/S0036144595285963 | MR 1491052
[12] Fischer A.: A Newton–type method for positive–semidefinite linear complementarity problems. J. Optim. Theory Appl. 86 (1995), 3, 585–608 DOI 10.1007/BF02192160 | MR 1348771 | Zbl 0839.90121
[13] Fischer A., Kanzow, CH.: On finite termination of an iterative method for linear complementarity problems. Math. Programming 74 (1996), xxx–xxx DOI 10.1007/BF02592200 | MR 1407689 | Zbl 0855.90125
[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 0878586
[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 1085483 | Zbl 0718.90056
[18] Jongen H. Th., Jonker, P., Twilt F.: Critical Sets in Parametric Optimization. Math. Programming 34 (1986), 333–353 DOI 10.1007/BF01582234 | MR 0839608 | Zbl 0599.90114
[19] Jongen H. Th., Jonker, P., Twilt F.: Nonlinear Optimization in Finite Dimension: Morse Theory, Chebysher Approximation, Transversality, Flows, Parametric Aspects. Kluwer, 2000 MR 1794354
[20] Kanzow, Ch.: Some boninterior continuation methods for linear complementarity problems. SIAM J. Appl. Anal. 17 (1996), 851–868 DOI 10.1137/S0895479894273134 | MR 1410705
[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 10.1080/02331887208801074 | MR 0334929 | Zbl 0247.90037
[23] Nožička F., Guddat J., Hollatz, H., Bank B.: Theorie der linearen parametrischen Optimierung. Akademic–Verlag, Berlin 1974 Zbl 0284.90053
[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 1222836
[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 10.1007/BF02614398 | MR 1433971
[28] Stoer J., Wechs H.: Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity. Math. Programming 83 (1998), 407–423 DOI 10.1007/BF02680568 | MR 1650309 | Zbl 0922.90136
[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 10.1287/moor.23.4.832 | MR 1662418
[30] (ed.), Hj. Wacker: Continuation Methods. Academic Press, New York 1978 MR 0483273 | Zbl 0465.65029
[31] Watson T.: Solving the nonlinear complementarity problem by a homotopy method. SIAM J. Control Appl. 17 (1979), 36–46 DOI 10.1137/0317004 | MR 0516854 | Zbl 0407.90083
[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 1712475 | Zbl 0978.90097
Search
Partner of
