A modified standard embedding for linear complementarity problems

Sira Allende Allonso; Jürgen Guddat; Dieter Nowack

Kybernetika (2004)

  • Volume: 40, Issue: 5, page [551]-570
  • ISSN: 0023-5954

Abstract

top
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 ∈ [ 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 ∈ [ 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.

How to cite

top

Allonso, Sira Allende, Guddat, Jürgen, and Nowack, Dieter. "A modified standard embedding for linear complementarity problems." Kybernetika 40.5 (2004): [551]-570. <http://eudml.org/doc/33719>.

@article{Allonso2004,
abstract = {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.},
author = {Allonso, Sira Allende, Guddat, Jürgen, Nowack, Dieter},
journal = {Kybernetika},
keywords = {linear complementarity problem; standard embedding; Jongen– Jonker–Twilt regularity; Mangasarian–Fromovitz constraint qualification; pathfollowing methods; linear complementarity problem; Jongen-Jonker-Twilt regularity; Mangasarian-Fromovitz constraint qualification; pathfollowing method},
language = {eng},
number = {5},
pages = {[551]-570},
publisher = {Institute of Information Theory and Automation AS CR},
title = {A modified standard embedding for linear complementarity problems},
url = {http://eudml.org/doc/33719},
volume = {40},
year = {2004},
}

TY - JOUR
AU - Allonso, Sira Allende
AU - Guddat, Jürgen
AU - Nowack, Dieter
TI - A modified standard embedding for linear complementarity problems
JO - Kybernetika
PY - 2004
PB - Institute of Information Theory and Automation AS CR
VL - 40
IS - 5
SP - [551]
EP - 570
AB - 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.
LA - eng
KW - linear complementarity problem; standard embedding; Jongen– Jonker–Twilt regularity; Mangasarian–Fromovitz constraint qualification; pathfollowing methods; linear complementarity problem; Jongen-Jonker-Twilt regularity; Mangasarian-Fromovitz constraint qualification; pathfollowing method
UR - http://eudml.org/doc/33719
ER -

References

top
  1. Allonso S. Allende, Guddat, J., Nowack D., A modified penalty embedding for linear complementarity problems, Investigación Oper. 23 (2002), 1, 37–54 MR1932562
  2. Allgower E., Georg K., Numerical Continuation Methods, An Introduction. Springer–Verlag, Berlin 1990 Zbl1036.65047MR1059455
  3. Bank B., Guddat J., Klatte D., Kummer, B., Tammer K., Non-Linear Parametric Optimization, Akademie–Verlag Berlin, 1982 Zbl0502.49002
  4. Billups S. C., 10.1137/S1052623498337431, SIAM J. Optim. 12 (2002), 583–605 Zbl1056.90132MR1884907DOI10.1137/S1052623498337431
  5. Billups S. C., Watson L. T., 10.1137/S105262340037758X, SIAM J. Optim. 12 (2002), 606–626 MR1884908DOI10.1137/S105262340037758X
  6. Chen, Ch., Mangasarian O. L., 10.1007/BF01592244, Math. Programming 71 (1995), 51–69 (1995) Zbl0855.90124MR1362957DOI10.1007/BF01592244
  7. Pang R. W. Cottle J.-S., Stone R. E., The Linear Complementarity Problem, Academic Press, Boston, MA, 1992 MR1150683
  8. Facchinei F., Pang J.-P., Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol, I and Vol. II. Springer Series in Operations Research, 2003 Zbl1062.90002MR1955648
  9. 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 (1999) MR1751116
  10. Ferris M. C., Pang J.-S., 10.1137/S0036144595285963, SIAM Rev. 39 (1997), 669–713 (1997) MR1491052DOI10.1137/S0036144595285963
  11. Fischer A., 10.1007/BF02192160, J. Optim. Theory Appl. 86 (1995), 3, 585–608 (1995) Zbl0839.90121MR1348771DOI10.1007/BF02192160
  12. Fischer A., Kanzow, CH., 10.1007/BF02592200, Math. Programming 74 (1996), xxx–xxx (1996) Zbl0855.90125MR1407689DOI10.1007/BF02592200
  13. 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 (1985) MR0878586
  14. Gollmer R., Kausmann U., Nowack D., Wendler, K., Estrada J. Bacallao, Computerprogramm PAFO, Humboldt-Universität Berlin, Institut für Mathematik xxxx 
  15. 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 
  16. Guddat J., Guerra, F., Jongen H. Th., Parametric Optimization: Singularities, Pathfollowing and Jumps, BG Teubner, Stuttgart and John Wiley, Chichester 1990 Zbl0718.90056MR1085483
  17. Jongen H. Th., Jonker, P., Twilt F., 10.1007/BF01582234, Math. Programming 34 (1986), 333–353 (1986) Zbl0599.90114MR0839608DOI10.1007/BF01582234
  18. Jongen H. Th., Jonker, P., Twilt F., Nonlinear Optimization in Finite Dimension: Morse Theory, Chebysher Approximation, Transversality, Flows, Parametric Aspects, Kluwer, 2000 MR1794354
  19. Kanzow, Ch., 10.1137/S0895479894273134, SIAM J. Appl. Anal. 17 (1996), 851–868 (1996) MR1410705DOI10.1137/S0895479894273134
  20. Kojima M., Megiddo N., Noma, T., Yoshishe A., A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Springer, Berlin 1991 
  21. Nožička F., 10.1080/02331887208801074, Math. Operationsforschung Statist. 3, (1972), 159–194 (1972) Zbl0247.90037MR0334929DOI10.1080/02331887208801074
  22. Nožička F., Guddat J., Hollatz, H., Bank B., Theorie der linearen parametrischen Optimierung, Akademic–Verlag, Berlin 1974 Zbl0284.90053
  23. Reinholdt W. C., Numerical Analysis of Parametric Nonlinear Equations, John Wiley, New York 1986 
  24. Rückmann J.-J., Tammer K., On linear-quadratic perturbations in one-parametric non-linear optimization, Systems Sci. 18 (1992), 1, 37–48 (1992) MR1222836
  25. Schmid R., Eine modifizierte Standardeinbettung zur Behandlung von Gleichungs- und Ungleichungsrestriktionen, Diplomarbeit, Humboldt-Universitiät zu Berlin, 2000 
  26. Sellami H., Robinson S. M., 10.1007/BF02614398, Math. Programming 76 (1976), 563–578 (1976) MR1433971DOI10.1007/BF02614398
  27. Stoer J., Wechs H., 10.1007/BF02680568, Math. Programming 83 (1998), 407–423 (1998) Zbl0922.90136MR1650309DOI10.1007/BF02680568
  28. Stoer J., Wechs, M., Mizuni S., 10.1287/moor.23.4.832, Math. Oper. Res. 23 (1998), 832–862 (1998) MR1662418DOI10.1287/moor.23.4.832
  29. (ed.), Hj. Wacker, Continuation Methods, Academic Press, New York 1978 Zbl0465.65029MR0483273
  30. Watson T., 10.1137/0317004, SIAM J. Control Appl. 17 (1979), 36–46 (1979) Zbl0407.90083MR0516854DOI10.1137/0317004
  31. 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) (1999) Zbl0978.90097MR1712475

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.