| Title:
|
A modified standard embedding for linear complementarity problems (English) |
| Author:
|
Allonso, Sira Allende |
| Author:
|
Guddat, Jürgen |
| Author:
|
Nowack, Dieter |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
40 |
| Issue:
|
5 |
| Year:
|
2004 |
| Pages:
|
[551]-570 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
linear complementarity problem |
| Keyword:
|
standard embedding |
| Keyword:
|
Jongen– Jonker–Twilt regularity |
| Keyword:
|
Mangasarian–Fromovitz constraint qualification |
| Keyword:
|
pathfollowing methods |
| MSC:
|
68Q25 |
| MSC:
|
90C31 |
| MSC:
|
90C33 |
| MSC:
|
90C51 |
| idZBL:
|
Zbl 1249.90273 |
| idMR:
|
MR2120996 |
| . |
| Date available:
|
2009-09-24T20:03:45Z |
| Last updated:
|
2015-03-23 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135616 |
| . |
| Reference:
|
[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 |
| Reference:
|
[2] Allgower E., Georg K.: Numerical Continuation Methods.An Introduction. Springer–Verlag, Berlin 1990 Zbl 1036.65047, MR 1059455 |
| Reference:
|
[3] Bank B., Guddat J., Klatte D., Kummer, B., Tammer K.: Non-Linear Parametric Optimization.Akademie–Verlag Berlin, 1982 Zbl 0502.49002 |
| Reference:
|
[4] Billups S. C.: A Homotopy-based algorithm for mixed complementarity problems.SIAM J. Optim. 12 (2002), 583–605 Zbl 1056.90132, MR 1884907, 10.1137/S1052623498337431 |
| Reference:
|
[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 MR 1884908, 10.1137/S105262340037758X |
| Reference:
|
[7] Chen, Ch., Mangasarian O. L.: Smoothing methods for convex inequalities and linear complementarity problems.Math. Programming 71 (1995), 51–69 Zbl 0855.90124, MR 1362957, 10.1007/BF01592244 |
| Reference:
|
[8] Pang R. W. Cottle J.-S., Stone R. E.: The Linear Complementarity Problem.Academic Press, Boston, MA, 1992 MR 1150683 |
| Reference:
|
[9] Facchinei F., Pang J.-P.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol.I and Vol. II. Springer Series in Operations Research, 2003 Zbl 1062.90002, MR 1955648 |
| Reference:
|
[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 |
| Reference:
|
[11] Ferris M. C., Pang J.-S.: Engeneering and economic application of complementarity problems.SIAM Rev. 39 (1997), 669–713 MR 1491052, 10.1137/S0036144595285963 |
| Reference:
|
[12] Fischer A.: A Newton–type method for positive–semidefinite linear complementarity problems.J. Optim. Theory Appl. 86 (1995), 3, 585–608 Zbl 0839.90121, MR 1348771, 10.1007/BF02192160 |
| Reference:
|
[13] Fischer A., Kanzow, CH.: On finite termination of an iterative method for linear complementarity problems.Math. Programming 74 (1996), xxx–xxx Zbl 0855.90125, MR 1407689, 10.1007/BF02592200 |
| Reference:
|
[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 |
| Reference:
|
[15] Gollmer R., Kausmann U., Nowack D., Wendler, K., Estrada J. Bacallao: Computerprogramm PAFO.Humboldt-Universität Berlin, Institut für Mathematik xxxx |
| Reference:
|
[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 |
| Reference:
|
[17] Guddat J., Guerra, F., Jongen H. Th.: Parametric Optimization: Singularities, Pathfollowing and Jumps.BG Teubner, Stuttgart and John Wiley, Chichester 1990 Zbl 0718.90056, MR 1085483 |
| Reference:
|
[18] Jongen H. Th., Jonker, P., Twilt F.: Critical Sets in Parametric Optimization.Math. Programming 34 (1986), 333–353 Zbl 0599.90114, MR 0839608, 10.1007/BF01582234 |
| Reference:
|
[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 |
| Reference:
|
[20] Kanzow, Ch.: Some boninterior continuation methods for linear complementarity problems.SIAM J. Appl. Anal. 17 (1996), 851–868 MR 1410705, 10.1137/S0895479894273134 |
| Reference:
|
[21] Kojima M., Megiddo N., Noma, T., Yoshishe A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems.Springer, Berlin 1991 |
| Reference:
|
[22] Nožička F.: Über eine Klasse von linearen einparametrischen Optimierungsproblemen.Math. Operationsforschung Statist. 3, (1972), 159–194 Zbl 0247.90037, MR 0334929, 10.1080/02331887208801074 |
| Reference:
|
[23] Nožička F., Guddat J., Hollatz, H., Bank B.: Theorie der linearen parametrischen Optimierung.Akademic–Verlag, Berlin 1974 Zbl 0284.90053 |
| Reference:
|
[24] Reinholdt W. C.: Numerical Analysis of Parametric Nonlinear Equations.John Wiley, New York 1986 |
| Reference:
|
[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 |
| Reference:
|
[26] Schmid R.: Eine modifizierte Standardeinbettung zur Behandlung von Gleichungs- und Ungleichungsrestriktionen.Diplomarbeit, Humboldt-Universitiät zu Berlin, 2000 |
| Reference:
|
[27] Sellami H., Robinson S. M.: Implementation of a continuation method for normal maps.Math. Programming 76 (1976), 563–578 MR 1433971, 10.1007/BF02614398 |
| Reference:
|
[28] Stoer J., Wechs H.: Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity.Math. Programming 83 (1998), 407–423 Zbl 0922.90136, MR 1650309, 10.1007/BF02680568 |
| Reference:
|
[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 MR 1662418, 10.1287/moor.23.4.832 |
| Reference:
|
[30] (ed.), Hj. Wacker: Continuation Methods.Academic Press, New York 1978 Zbl 0465.65029, MR 0483273 |
| Reference:
|
[31] Watson T.: Solving the nonlinear complementarity problem by a homotopy method.SIAM J. Control Appl. 17 (1979), 36–46 Zbl 0407.90083, MR 0516854, 10.1137/0317004 |
| Reference:
|
[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) Zbl 0978.90097, MR 1712475 |
| . |
