×

zbMATH — the first resource for mathematics

Robust solution of monotone stochastic linear complementarity problems. (English) Zbl 1165.90012
Summary: We consider the stochastic linear complementarity problem (SLCP) involving a random matrix whose expectation matrix is positive semi-definite. We show that the expected residual minimization (ERM) formulation of this problem has a nonempty and bounded solution set if the expected value (EV) formulation, which reduces to the LCP with the positive semi-definite expectation matrix, has a nonempty and bounded solution set. We give a new error bound for the monotone LCP and use it to show that solutions of the ERM formulation are robust in the sense that they may have a minimum sensitivity with respect to random parameter variations in SLCP. Numerical examples including a stochastic traffic equilibrium problem are given to illustrate the characteristics of the solutions.

MSC:
90C15 Stochastic programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Birge J.R. and Louveaux F. (1997). Introduction to Stochastic Programming. Springer, New York · Zbl 0892.90142
[2] Chen B., Chen X. and Kanzow C. (2000). A penalized Fischer–Burmeister NCP-function. Math. Program. 88: 211–216 · Zbl 0968.90062 · doi:10.1007/PL00011375
[3] Chen X. and Fukushima M. (2005). Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30: 1022–1038 · Zbl 1162.90527 · doi:10.1287/moor.1050.0160
[4] Cottle R.W., Pang J.-S. and Stone R.E. (1992). The Linear Complementarity Problem. Academic, New York · Zbl 0757.90078
[5] Daffermos S. (1980). Traffic equilibrium and variational inequalities. Transportation Sci. 14: 42–54 · doi:10.1287/trsc.14.1.42
[6] Facchinei F. and Pang J.-S. (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems, I and II. Springer, New York · Zbl 1062.90002
[7] Fang, H., Chen, X., Fukushima, M.: Stochastic R 0 matrix linear complementarity problems. SIAM J. Optim. 18, 482–506 (2007) · Zbl 1151.90052
[8] Ferris, M.C.: ftp://ftp.cs.wisc.edu/math-prog/matlab/lemke.m, Department of Computer Science, University of Wisconsin (1998)
[9] Ferris M.C. and Pang J.-S. (1997). Engineering and economic applications of complementarity problems. SIAM Rev. 39: 669–713 · Zbl 0891.90158 · doi:10.1137/S0036144595285963
[10] Frank M. and Wolfe P. (1956). An algorithm for quadratic programming. Nav. Res. Logist. 3: 95–110 · doi:10.1002/nav.3800030109
[11] Gürkan G., Özge A.Y. and Robinson S.M. (1999). Sample-path solution of stochastic variational inequalities. Math. Program. 84: 313–333 · Zbl 0972.90079 · doi:10.1007/s101070050024
[12] Kall P. and Wallace S.W. (1994). Stochastic Programming. Wiley, Chichester
[13] Kanzow C., Yamashita N. and Fukushima M. (1997). New NCP-functions and their properties. J. Optim. Theory Appl. 94: 115–135 · Zbl 0886.90146 · doi:10.1023/A:1022659603268
[14] Kleywegt A.J., Shapiro A. and Homen-De-Mello T. (2001). The sample average approximation method for stochastic disete optimization. SIAM J. Optim. 12: 479–502 · Zbl 0991.90090 · doi:10.1137/S1052623499363220
[15] Lin G.H. and Fukushima M. (2006). New reformulations for stochastic nonlinear complementarity problems. Optim. Methods Softw. 21: 551–564 · Zbl 1113.90110 · doi:10.1080/10556780600627610
[16] Luo Z.-Q. and Tseng P. (1997). A new class of merit functions for the nonlinear complementarity problem. In: Ferris, M.C. and Pang, J.-S. (eds) Complementarity and Variational Problems: State of the Art., pp 204–225. SIAM, Philadelphia · Zbl 0886.90158
[17] Mangasarian O.L. and Ren J. (1994). New improved error bounds for the linear complementarity problem. Math. Program. 66: 241–255 · Zbl 0829.90124 · doi:10.1007/BF01581148
[18] Marti K. (2005). Stochastic Optimization Methods. Springer, Berlin · Zbl 1059.90110
[19] Tseng P. (1996). Growth behavior of a class of merit functions for the nonlinear complementarity problem. J. Optim. Theory Appl. 89: 17–37 · Zbl 0866.90127 · doi:10.1007/BF02192639
[20] Sun D. and Qi L. (1999). On NCP-functions. Comp. Optim. Appl. 13: 201–220 · Zbl 1040.90544 · doi:10.1023/A:1008669226453
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.