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)
Descent approaches for quadratic bilevel programming. (English) Zbl 0819.90076
Summary: The bilevel programming problem involves two optimization problems where the data of the first one is implicitly determined by the solution of the second. We introduce two descent methods for a special instance of bilevel programs where the inner problem is strictly convex quadratic. The first algorithm is based on pivot steps and may not guarantee local optimality. A modified steepest descent algorithm is presented to overcome this drawback. New rules for computing exact stepsizes are introduced and a hybrid approach that combines both strategies is discussed. It is proved that checking local optimality in bilevel programming is an NP-hard problem.
MSC:
90C26Nonconvex programming, global optimization
90C20Quadratic programming
90C60Abstract computational complexity for mathematical programming problems
References:
[1]Anandalingam, G., andFriesz, T., Editors,Hierarchical Optimization, Annals of Operations Research, Vol. 34, 1992.
[2]Bard, J., andMoore, J.,A Branch-and-Bound Algorithm for the Bilevel Programming Problem, SIAM Journal on Scientific and Statistical Computing, Vol. 11, pp. 281–292, 1990. · Zbl 0702.65060 · doi:10.1137/0911017
[3]Hansen, P., Jaumard, B., andSavard, G.,New Branching-and-Bounding Rules for Linear Bilevel Programming, SIAM Journal on Statistical and Scientific Computing, Vol. 13, pp. 1194–1217, 1992. · Zbl 0760.65063 · doi:10.1137/0913069
[4]Júdice, J., andFaustino, A.,A Sequential LCP Method for Bilevel Linear Programming, Annals of Operations Research, Vol. 34, pp. 89–106, 1992. · Zbl 0749.90049 · doi:10.1007/BF02098174
[5]Al-Khayyal, F., Horst, R., andPardalos, P.,Global, Optimization of Concave Functions Subject of Quadratic Constraints: An Application in Nonlinear Bilevel Programming, Annals of Operations Research, Vol. 34, pp. 125–147, 1992. · Zbl 0751.90066 · doi:10.1007/BF02098176
[6]Bard, J.,Convex Two-Level Programming, Mathematical Programming, Vol. 40, pp. 15–27, 1988. · Zbl 0655.90060 · doi:10.1007/BF01580720
[7]Edmunds, T., andBard, J.,Algorithms for Nonlinear Bilevel Mathematical Programs, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 21, pp. 83–89, 1991. · doi:10.1109/21.101139
[8]Jaumard, B., Savard, G., andXiong, J.,An Exact Algorithm for Convex Bilevel Programming, Optimization Days, Montreal, Canada, 1992.
[9]Aiyoshi, E., andShimizu, K.,Hierarchical Decentralized System and Its New Solution by a Barrier Method, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 11, pp 444–449, 1981. · doi:10.1109/TSMC.1981.4308712
[10]Aiyoshi, E., andShimizu, K.,A Solution Method for the Static Constrained Stackelberg Problem via Penalty Method, IEEE Transactions on Automatic Control, Vol. 29, pp. 1111–1114, 1984. · Zbl 0553.90104 · doi:10.1109/TAC.1984.1103455
[11]Bi, Z., Calamai, P., andConn, A.,An Exact Penalty Function Approach for the Nonlinear Bilevel Programming Problem, Technical Report 180-O-170591, University of Waterloo, 1991.
[12]Ishizuka, Y., andAiyoshi E.,Double Penalty Method for Bilevel Linear Programming, Annals of Operations Research, Vol. 34, pp. 73–88, 1992. · Zbl 0756.90083 · doi:10.1007/BF02098173
[13]Florian, M., andChen, Y.,A Bilevel Programming Approach to Estimating O-D Matrix by Traffic Counts, Report CRT-750, Centre de Recherche sur les Transports, 1991.
[14]Kolstad, C., andLasdon, L.,Derivative Evaluation and Computational Experience with Large Bilevel Mathematical Programs, Journal of Optimization Theory and Applications, Vol. 65, pp. 485–499, 1990. · Zbl 0676.90101 · doi:10.1007/BF00939562
[15]Bard, J.,Optimality Conditions for the Bilevel Programming Problem, Naval Research Logistics Quarterly, Vol. 31, pp. 13–26, 1984. · Zbl 0537.90087 · doi:10.1002/nav.3800310104
[16]Clarke, P., andWesterberg, A.,A Note of the Optimality Conditions for the Bilevel Programming Problem, Naval Research Logistics, Vol. 35, pp. 413–418, 1988. · doi:10.1002/1520-6750(198810)35:5<413::AID-NAV3220350505>3.0.CO;2-6
[17]Chen, Y., andFlorian, M.,The Nonlinear Bilevel Programming Problem: A General Formulation and Optimality Conditions, Report CRT-794, Centre de Recherche sur les Transports, 1991.
[18]Dempe, S.,A Necessary and a Sufficient Optimality Condition for Bilevel Programming Problems, Optimization (to appear).
[19]Gauvin, J., andSavard, G.,The Steepest-Descent Method for the Nonlinear Bilevel Programming Problem, Report G-90-37, GERAD (Groupe d’Études et de Recherche en Analyse des Décisions), 1990.
[20]Júdice, J., andFaustino, A.,The Linear-Quadratic Bilevel Programming Problem, INFOR (to appear).
[21]Al-Khayyal, F.,An Implicit Enumeration Procedure for the General Linear Complementarity Problem, Mathematical Programming Studies, Vol. 31, pp. 1–20, 1987.
[22]Kojima, M., Mizuno, S., andYoshise, A.,A Polynomial-Time Algorithm for a Class of Linear Complementarity Problems, Mathematical Programming, Vol. 50, pp. 331–342, 1991. · Zbl 0738.90077 · doi:10.1007/BF01594942
[23]Murty, K.,Linear Programming, John Wiley and Sons, New York, 1983.
[24]Megiddo, N.,On Finding Primal and Dual Optimal Bases, ORSA Journal on Computing, Vol. 3, pp. 63–65, 1991.
[25]Pardalos, P., andSchnitger, G.,Checking Local Optimality in Constrained Quadratic Programming is NP-Hard, Operations Research Letters, Vol. 7, pp. 33–35, 1988. · Zbl 0644.90067 · doi:10.1016/0167-6377(88)90049-1
[26]Carpenter, T., Lustig, I., Mulvey, J., andShanno, D.,Higher-Order Predictor-Corrector Interior-Point Methods with Application to Quadratic Objectives, RUTCOR Research Report RRR 67-90, Rutgers University, 1990.
[27]Garey, M., andJohnson, D.,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York, New York, 1979.