# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints. (English) Zbl 0723.90070
The authors consider some algorithms for the bilevel programming problem of minimizing F(x,y) subject to $L\le y\le U$, $x\in K(y)$, and Z(x,y)(z- x)$\ge 0$ for all $z\in K(y)$ [cf. {\it P. Marcotte}, Math. Program. 34, 142-162 (1986; Zbl 0604.90053)]. For many applications the preceding variational inequality constraint defines x as a relatively smooth function of y. After presenting some results about sensitivity analysis of variational inequalities formal statements of three heuristic algorithms for the bilevel programming problem are given. The first two of them are descent algorithms and they differ from one another in the manner in which stepsizes are determined, either according to the Armijo rule or a priori. The third one is a generalization of the equilibrium decomposition optimization algorithm proposed by {\it C. Suwansirikul, T. L. Friesz} and {\it R. L. Tobin} [Transp. Sci. 21, 254-263 (1987; Zbl 0638.90097)]. Finally some numerical examples drawn from equilibrium network design, hierarchical mathematical programming, and game theory are discussed.

##### MSC:
 90C30 Nonlinear programming 49J40 Variational methods including variational inequalities 65K10 Optimization techniques (numerical methods) 65K05 Mathematical programming (numerical methods) 90-08 Computational methods (optimization) 90C99 Mathematical programming 49K40 Sensitivity, stability, well-posedness of optimal solutions 91A65 Hierarchical games 90C35 Programming involving graphs or networks
Full Text:
##### References:
 [1] M. Abdulaal and L.J. LeBlanc, ”Continuous equilibrium network design models,”Transportation Research 13B (1979) 19--32. · Zbl 0398.90042 [2] D.P. Bertsekas, ”Projected Newton methods for optimization problems with simple constraints,”SIAM J. Control and Optimization 20(2) (1982a) 221--246. · Zbl 0507.49018 · doi:10.1137/0320018 [3] D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982b). · Zbl 0572.90067 [4] A.H. De Silva, ”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). [5] T.L. Friesz, T. Miller and R.L. Tobin, ”Algorithms for spatially competitive network facility-location,”Environment and Planning B 15 (1988) 191--203. · doi:10.1068/b150191 [6] P.T. Harker and J.-S. Pang, ”Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of the theory, algorithms and applications,”Mathematical Programming (Series B) 48 (1990) 161--220, this issue. · Zbl 0734.90098 · doi:10.1007/BF01582255 [7] P.T. Harker and S.-C. Choi, ”A penalty function approach for mathematical programs with variational inequality constraints,” Decision Science Working Paper 87-09-08, University of Pennsylvania (Philadelphia, PA, 1987). [8] J.M. Henderson and R.E. Quandt,Microeconomic Theory (McGraw-Hill, New York, 1980, 3rd ed.). [9] C.D. Kolstad, ”A review of the literature on bi-level mathematical programming,” Los Alamos National Laboratory Report, LA-10284-MS (Los Alamos, 1985). [10] C.D. Kolstad and L.S. Lasdon, ”Derivative evaluation and computational experience with large bi-level mathematical programs,” BEBR Faculty Working Paper No. 1266, University of Illinois (Urbana-Champaign, IL, 1986). · Zbl 0676.90101 [11] J. Kyparisis, ”Sensitivity analysis framework for variational inequalities,”Mathematical Programming 38 (1987) 203--213. · doi:10.1007/BF02604641 [12] J. Kyparisis, ”Solution differentiability for variational inequalities and nonlinear programming problems,” Department of Decision Sciences and Information Systems, College of Business Administration, Florida International University (Miami, FL, 1989). [13] T.L. Magnanti and R.T. Wong, ”Network design and transportation planning: models and algorithms,”Transportation Science 18(1) (1984) 1--55. · doi:10.1287/trsc.18.1.1 [14] 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 [15] J.-S. Pang, ”Solution differentiability and continuation of Newton’s method for variational inequality problems over polyhedral sets,” Department of Mathematical Sciences, The Johns Hopkins University (Baltimore, MD, 1988). [16] R.T. Rockafellar,The Theory of Subgradients and its Applications to Problems of Optimization: Convex and Nonconvex Functions (Heldermann, Berlin, 1981). · Zbl 0462.90052 [17] C. Suwansirikul, T.L. Friesz and R.L. Tobin, ”Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem,”Transportation Science 21(4) (1987) 254--263. · Zbl 0638.90097 · doi:10.1287/trsc.21.4.254 [18] H.N. Tan, S.B. Gershwin and M. Athaus, ”Hybrid optimization in urban traffic networks,” Report No. DOT-TSC-RSPA-79-7, Laboratory for Information and Decision System, M.I.T. (Cambridge, MA, 1979). [19] R.L. Tobin, ”Sensitivity analysis for variational inequalities,”Journal of Optimization Theory and Applications 48 (1986) 191--204. · Zbl 0557.49004 [20] R.L. Tobin and T.L. Friesz, ”Sensitivity analysis for equilibrium network flow,”Transportation Science 22(4) (1988) 242--250. · Zbl 0665.90031 · doi:10.1287/trsc.22.4.242