Optimality conditions for the bilevel programming problem.

*(English)*Zbl 0537.90087The bilevel programming problem (BLPP) is a sequence of two optimization problems where the constraint region of the first is determined implicitly by the solution to the second. Consider two decision-makers or competitive players who must find vectors x and y, respectively, to optimize their individual objective functions F(x,y) and f(x,y). It will be assumed that player 1 has the first choice and selects \(x\in X\), followed by player 2 who selects \(y\in Y\), where X and Y are nonempty subsets of \({\mathbb{R}}^{n^ 1}\) and \({\mathbb{R}}^{n^ 2}\). In addition, the choice made by player 1 may affect the set of feasible strategies, S, open to player 2, implying the existence of jointly dependent constraints.

Letting \(S=\{(x,y):\) g(x,y)\(\geq 0\}\) the above situation can be compactly stated as follows: \[ \max_{x\in X}F(x,y),\quad where\quad y\quad solves\quad \max_{y\in Y}f(x,y),\quad subject\quad to\quad G(x,y)\geq 0. \] It is first shown that the linear BLPP is equivalent to maximizing a linear function over a feasible region comprised of connected faces and edges of the original polyhedral constraint set. The solution is shown to occur at a vertex of that set. Next, under assumptions of differentiability, first-order necessary optimality conditions are developed for the more general BLPP, and a potentially equivalent mathematical program is formulated. Finally, the relationship between the solution to this problem and Pareto optimality is discussed and a number of examples given.

Letting \(S=\{(x,y):\) g(x,y)\(\geq 0\}\) the above situation can be compactly stated as follows: \[ \max_{x\in X}F(x,y),\quad where\quad y\quad solves\quad \max_{y\in Y}f(x,y),\quad subject\quad to\quad G(x,y)\geq 0. \] It is first shown that the linear BLPP is equivalent to maximizing a linear function over a feasible region comprised of connected faces and edges of the original polyhedral constraint set. The solution is shown to occur at a vertex of that set. Next, under assumptions of differentiability, first-order necessary optimality conditions are developed for the more general BLPP, and a potentially equivalent mathematical program is formulated. Finally, the relationship between the solution to this problem and Pareto optimality is discussed and a number of examples given.

##### MSC:

90C31 | Sensitivity, stability, parametric optimization |

49K35 | Optimality conditions for minimax problems |

91A05 | 2-person games |

90B50 | Management decision making, including multiple objectives |

93A13 | Hierarchical systems |

49J35 | Existence of solutions for minimax problems |

49K30 | Optimality conditions for solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) |

49J30 | Existence of optimal solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) |

##### Keywords:

bilevel programming; competitive players; jointly dependent constraints; first-order necessary optimality conditions; Pareto optimality
Full Text:
DOI

##### References:

[1] | Bard, Computers and Operations Research 9 pp 77– (1982) |

[2] | Bard, Proceedings of the 14th Annual Meeting of the American Institute for Decision Science 2 pp 256– (1982) |

[3] | and , Dynamic Noncooperative Games, Academic, New York, 1982. |

[4] | Bialas, IEEE Transactions of Automatic Control AC-27 pp 211– (1982) |

[5] | Candler, Computers and Operations Reseurch 9 pp 59– (1982) |

[6] | Danskin, Journal of SIAM Applied Mathematics 14 pp 641– (1966) · Zbl 0144.43301 |

[7] | and , ”Two Optimizer Situations with a Solution Algorithm Based on Sensitivity Analysis,” Spring, TIMS/ORSA Conference, New Orleans (1978). |

[8] | Falk, Mathematical Programming 5 pp 169– (1973) |

[9] | and , Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968. |

[10] | Gallo, Mathematical Programming 12 pp 173– (1977) |

[11] | Gehner, SIAM Journal of Control 12 pp 140– (1974) |

[12] | ”Program MOGG–A Code for Solving Separable Nonconvex Optimization Problems,” The Institute for Defense Analyses, Arlington, VA, 1976, P-1318. |

[13] | ”Extreme Problems with Inequalities as Subsidiary Conditions,” Studies and Essays, Current Anniversary Edition, Wiley, New York, 1948, pp. 187–204. |

[14] | Konno, Mathematical Programming 11 pp 14– (1976) |

[15] | Schmitendorf, Journal of Mathematical Analysis and Applications 57 pp 683– (1977) · Zbl 0354.49012 |

[16] | Simaan, Journal of Optimization Theory and Applications 11 pp 533– (1973) · Zbl 0261.65023 |

[17] | Wallenius, Management Science 21 pp 1387– (1975) |

[18] | Linear Multiobjective Programming, Springer-Verlag, New York, 1974. · Zbl 0325.90033 · doi:10.1007/978-3-642-80808-1 |

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.