zbMATH — the first resource for mathematics

Foundations of bilevel programming. (English) Zbl 1038.90097
Nonconvex Optimization and Its Applications 61. Dordrecht: Kluwer Academic Publishers (ISBN 1-4020-0631-4). viii, 306 p. (2002).
Bilevel programming (BP in brief) deals with optimization problems of the form \[ \begin{aligned} (P) \text{``min''}\quad & f(x,y)\\ \text{s.t.}\quad & g_i(x,y) \leq 0,\;i\in I\\ \quad & x\in\Psi(y),\;y\in\mathbb{R}^m,\end{aligned} \] where \(| I |<\infty\) and \(\Psi(y)\subset\mathbb{R}^n\) denotes the optimal set of a certain optimization problem, \((P_y)\), depending on the parameter \(y\). Accordingly, \((P_y)\) and \((P)\) are called lower level and upper level problems, respectively. If \((P_y)\) is uniquely solvable for all \(y\in \mathbb{R}^m\), then \((P)\) is a mathematical program whose objective function is implicitly defined. Otherwise, given \(y\in\mathbb{R}^m\), the set \[ \bigl\{f(x,y)\mid x\in\Psi(y),\;g_i(x,y)\leq 0,\;i\in I\bigr\} \subset \mathbb{R} \] is not necessarily a singleton and the task “min” can be interpreted in different ways, for instance, as \(\min_{y\in\mathbb{R}^m} \min_{x\in F(y)} f(x,y)\) \((\min_{y\in\mathbb{R}^m} \max_{x\in F(y)} f(x, y))\), corresponding to the optimistic perspective (pessimistic perspective, respectively). As the applications collected in Chapter 2 show, BP problems naturally arise in economy, engineering, chemistry, data analysis and many other fields.
The book is mainly focussed on BP theory (specially optimality conditions), and its main novelties (in comparison with previous monographs) are the elimination of the strong uniqueness assumption on \((P_y)\) and the discussion of discrete BP problems. This is a valuable expository text for graduate and advanced undergraduate students which provides detailed information on the wide BP literature, and can be read with different purposes:
1. A short introduction to BP (Chapters 1–3, preferably complemented with Section 5.1).
2. An introduction to parametric optimization (Chapter 4), which is the key tool in BP theory.
3. An overview of BP (Chapters 1–5 and 5–7, skipping the proofs, which have been conveniently concentrated at the end of each chapter).
4. A thorough course on BP. The many illustrative examples contained in the book will help these readers who could miss complementary exercises and problems.

90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C31 Sensitivity, stability, parametric optimization
90C46 Optimality conditions and duality in mathematical programming
90C27 Combinatorial optimization
49J52 Nonsmooth analysis