A numerical approach to optimization problems with variational inequality constraints. (English) Zbl 0835.90093

Outrata, Jiří; Zowe, Jochem

Math. Program. 68, No. 1 (A), 105-130 (1995).

Summary: Optimization problems with variational inequality constraints are converted to constrained minimization of a local Lipschitz function. To this minimization a non-differentiable optimization method is used; the required subgradients of the objective are computed by means of a special adjoint equation. Besides tests with some academic examples, the approach is applied to the computation of the Stackelberg-Cournot-Nash equilibria and to the numerical solution of a class of quasi-variational inequalities.

MSC:

90C30	Nonlinear programming
49J40	Variational inequalities
49J52	Nonsmooth analysis
90C33	Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C31	Sensitivity, stability, parametric optimization

Keywords:

sensitivity analysis; generalized Jacobian; optimization; variational inequality constraints; constrained minimization; local Lipschitz function; non-differentiable optimization; subgradients; Stackelberg- Cournot-Nash equilibria

Software:

NLPQL

References:

[1]	W. Alt and I. Kolumbán, ”An implicit function theorem for a class of monotone generalized equations,”Kybernetika 29 (1993) 210–221. · Zbl 0792.49005
[2]	J.-P. Aubin and I. Ekeland,Applied Nonlinear Analysis (Wiley, New York, 1984). · Zbl 0641.47066
[3]	D. Chan and J.S. Pang, ”The generalized quasi-variational inequality problem,”Mathematics of Operations Research 7 (1982) 211–222. · Zbl 0502.90080 · doi:10.1287/moor.7.2.211
[4]	F.H. Clarke,Optimization and Nonsmooth Analysis (Wiley, New York, 1983). · Zbl 0582.49001
[5]	A.H. DeSilva, ”Sensitivity formulas for nonlinear factorable programming and their application to the solution of an implicitly defined optimization model of US crude oil production,” Dissertation, George Washington University (Washington, D.C., 1978).
[6]	B.C. Eaves, ”On the basic theorem of complementarity,”Mathematical Programming 1 (1971) 68–75. · Zbl 0227.90044 · doi:10.1007/BF01584073
[7]	S.D. Flåm, ”Paths to constrained Nash equilibria,” Research Report UTM 345, University of Trento (Trento, 1991). · Zbl 0805.90122
[8]	T.L. Friesz, R.L. Tobin, H.-J. Cho and N.J. Mehta, ”Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints,”Mathematical Programming 48 (1990) 265–284. · Zbl 0723.90070 · doi:10.1007/BF01582259
[9]	T.L. Friesz, H.-J. Cho, N.J. Mehta, R.L. Tobin and G. Anandalingam, ”A simulated annealing approach to the network design problem with variational inequality constraints,”Transportation Science 26 (1992) 18–26. · Zbl 0764.90084 · doi:10.1287/trsc.26.1.18
[10]	P.T. Harker and S.C. Choi, ”A penalty function approach for mathematical programs with variational inequality constraints,” WP 87-08-08, University of Pennsylvania (Pennsylvania, 1987). · Zbl 0732.90075
[11]	P.T. Harker and J.-S. Pang, ”Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,”Mathematical Programming 48 (1990) 161–220. · Zbl 0734.90098 · doi:10.1007/BF01582255
[12]	P.T. Harker, ”Generalized Nash games and quasi-variational inequalities,”European Journal of Operational Research 54 (1991) 81–94. · Zbl 0754.90070 · doi:10.1016/0377-2217(91)90325-P
[13]	J. Haslinger and P. Neittaanmäki,Finite Element Approximation for Optimal Shape Design: Theory and Application (Wiley, Chichester, 1988). · Zbl 0713.73062
[14]	J.M. Henderson and R.E. Quandt,Microeconomic Theory, 3rd ed. (McGraw-Hill, New York, 1980).
[15]	Y. Ishizuka and E. Aiyoshi, ”Double penalty method for bilevel optimization problems,” in: G. Anandalingam and T. Friesz, eds.,Hierarchical Optimization, Annals of Operations Research 34 (1992) 73–88. · Zbl 0756.90083 · doi:10.1007/BF02098173
[16]	M. Kočvara and J.V. Outrata, ”A nondifferentiable approach to the solution of optimum design problems with variational inequalities,” in: P. Kall, ed.,System Modelling and Optimization, Lecture Notes in Control and Information Sciences 180 (Springer, Berlin, 1992) 364–373. · Zbl 0789.49027
[17]	M. Kočvara and J.V. Outrata, ”Shape optimization of elasto-plastic bodies governed by variational inequalities,” in: J.-P. Zolesio, ed.,Boundary Control and Variation, Lecture Notes in Pure and Applied Mathematics 163 (Marcel Dekker, New York, 1994) 261–272. · Zbl 0816.73041
[18]	J. Kyparisis, ”Solution differentiability for variational inequalities,”Mathematical Programming 48 (1990) 285–301. · Zbl 0727.90082 · doi:10.1007/BF01582260
[19]	C. Lemaréchal, J.-J. Strodiot and A. Bihain, ”On a bundle algorithm for nonsmooth optimization,” in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 4 (Academic Press, New York, 1991). · Zbl 0533.49023
[20]	O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969).
[21]	P. Marcotte, ”Network design problem with congestion effects: A case of bilevel programming,”Mathematical Programming 34 (1986) 142–162. · Zbl 0604.90053 · doi:10.1007/BF01580580
[22]	U. Mosco, ”Implicit variational problems and quasi-variational inequalities,” in: A. Dold and B. Eckmann, eds.,Nonlinear Operators and the Calculus of Variations, Lecture Notes in Mathematics, 543 (Springer, Berlin, 1976). · Zbl 0346.49003
[23]	F.H. Murphy, H.D. Sherali and A.L. Soyster, ”A mathematical programming approach for determining oligopolistic market equilibrium,”Mathematical Programming 24 (1982) 92–106. · Zbl 0486.90015 · doi:10.1007/BF01585096
[24]	J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1980). · Zbl 0949.65053
[25]	J.V. Outrata, ”On the numerical solution of a class of Stackelberg problems,”Zeitschrift für Operations Research 4 (1990) 255–278. · Zbl 0714.90077
[26]	J.V. Outrata, ”On necessary optimality conditions for Stackelberg problems,”Journal of Optimization Theory and Applications 76 (1993) 305–320. · Zbl 0802.49007 · doi:10.1007/BF00939610
[27]	J.S. Pang, ”Two characterization theorems in complementarity theory,”Operations Research Letters 7 (1988) 27–31. · Zbl 0643.90087 · doi:10.1016/0167-6377(88)90048-X
[28]	J.S. Pang, S.P. Han and N. Rangaraj, ”Minimization of locally Lipschitz functions,”SIAM Journal on Optimization 1 (1991) 57–82. · Zbl 0752.90070 · doi:10.1137/0801006
[29]	Y. Qiu and T.L. Magnanti, ”Sensitivity analysis for variational inequalities defined on polyhedral sets,”Mathematics of Operations Research 14 (1989) 410–432. · Zbl 0698.90069 · doi:10.1287/moor.14.3.410
[30]	S.M. Robinson, ”Strongly regular generalized equations,”Mathematics of Operations Research 5 (1980) 43–62. · Zbl 0437.90094 · doi:10.1287/moor.5.1.43
[31]	S.M. Robinson, ”An implicit-function theorem for a class of nonsmooth functions,”Mathematics of Operations Research 16 (1991) 282–309. · Zbl 0746.46039 · doi:10.1287/moor.16.2.292
[32]	K. Schittkowski, ”NLPQL: A Fortran subroutine solving constrained nonlinear programming problems,”Annals of Operations Research 5 (1985) 485–500.
[33]	H. Schramm, ”Bundle Trust methods: Fortran codes for nondifferentiable optimization. User’s Guide,” DFG Research Report No. 269, University of Bayreuth (Bayreuth, 1991).
[34]	H. Schramm and J. Zowe, ”A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results,”SIAM Journal on Optimization 2 (1992) 121–152. · Zbl 0761.90090 · doi:10.1137/0802008
[35]	M.J. Smith, ”A decent algorithm for solving monotone variational inequalities and monotone complementarity problems,”Journal of Optimization Theory and Applications 44 (1984) 485–496. · Zbl 0535.49023 · doi:10.1007/BF00935463
[36]	R.L. Tobin, ”Uniqueness results and algorithms for Stackelberg–Cournot–Nash equilibria,” in: G. Anandalingam and T. Friesz, eds.,Hierarchical Optimization, Annals of Operations Research 34 (1992) 21–36. · Zbl 0751.90016 · doi:10.1007/BF02098171