What is the relationship between minimax problems and bilevel optimization problems?

Question

Is there (ever) a way to phrase a minimax problem as a bilevel optimization problem, or vice versa? Can one be seen as a limiting case of another?

Answer 1

A minimax problem can be seen as a simple bilevel problem.

A general bilevel problem can be written

$$\max_x f(x,y) \quad \mbox{s.t.} \quad y\in\arg\min g(x,y).$$

If $g(x,y) = f(x,y)$ then this is equivalent to

$$\max_x \min_y f(x,y).$$

So you can see a minimax problem as the bilevel optimization problem:

$$\max_x f(x,y)\quad\mbox{s.t.}\quad y\in\arg\min f(x,y).$$

On the other hand, not every bilevel problem can necessarily be written as a minmax problem.

Answer 2

In [1], the authors proposed a bilevel optimization problem: $$ \min z_1(x) = x_1 \vee x_2 \vee \cdots \vee x_n \tag{1} $$ $$ \text{s.t. } A \circ x^T \geq b^T, \tag{2} $$ $$ \min z_2(x) = \|x\|_0 \tag{3} $$ $$ \text{s.t. } x \in X_1(A, b), \tag{4} $$ where $x \vee y := \max(x, y)$, $A = (a_{ij})_{m \times n} \in [0, 1]^{m \times n}$, $x = (x_1, x_2, ..., x_n) \in [0, 1]^n$, $b = (b_1, b_2, ..., b_m) \in [0, 1]^m$ and $\circ$ represents the max-product composition. The zero norm of $x$, denoted by $\|x\|_0$, is the number of nonzero components in $x$, i.e., $$ \|x\|_0 = | \{ i \mid x_i \neq 0, 1 \leq i \leq n \} |. \tag{5} $$ $X_1(A, b)$ represents the complete optimal solution set of Problem (1). In Problem (1)-(4), the first level objective is to minimize the intensity of electromagnetic radiation, while the second level objective is to minimize the operation cost of the base stations. Please see [1] for details.

We can see that (1) is a minimax problem and (1)-(4) is a bilevel optimization problem. Therefore, a minimax problem can be the first level objective of a bilevel optimization problem.

Reference

[1] J. Qiu, H. Xue, G. Li, and X. Yang, "Fuzzy Relation Bilevel Optimization Model in the Wireless Communication Station System," IEEE Access, vol. 8, pp. 60811-60823, 2020.