How to solve minimax mixed integer problem with a large high dimensional feasible region? \begin{aligned} \max_{\vec{x}}\min_{\vec{y}} \quad & \vec{r} \cdot \vec{x} + \vec{s} \cdot \vec{y}\\ \textrm{s.t.} \quad & A\vec{x} + B\vec{y} \succcurlyeq \vec{c} \\ \end{aligned} where $A$, $B$, $\vec{r}$, $\vec{s}$, and $\vec{c}$ are constants.
A common trick is to introduce an auxiliary variable $w$ and rewrite the problem as
\begin{aligned} \max_{\vec{x}} \quad & \vec{r} \cdot \vec{x} + w \\ \textrm{s.t.} \quad & A\vec{x} + B\vec{y} \succcurlyeq \vec{c} \\ \quad & \forall \vec{y}: \vec{s} \cdot \vec{y} \ge w \end{aligned}
If $\vec{y}$ only has a few possible values, that can work. However, if $\vec{y}$ has lots of possible values, implementing the constraint $\forall \vec{y}: -\vec{s} \cdot \vec{y} \ge w$ by enumerating all possible $\vec{y}$ is impractical.
I consider optimizing $\vec{x}$ and $\vec{y}$ alternately:
- Randomly choose a feasible pair of $\vec{x}$ and $\vec{y}$
- Fix $\vec{x}$ and minimize over $\vec{y}$
- Fix $\vec{y}$ and maximize over $\vec{x}$
- Repeat steps 2 and 3 till converge.
But I worry the method might get stuck in cycles. For example, a function $q(x, y)$'s values is as follows.
y
^ 1|2
| -+-
| 4|3
+-----> x
Maximizing over $x$ and minimizing over $y$ by the above algorithm would lead to a never-ending cycle.
Moreover, alternately fixing $\vec{x}$ and $\vec{y}$ can make the algorithm get stuck in a local optima due to the constraints. For example, if one of the constraint is $x = y$, then fixing $x$ means fixing $y$ and the algorithm would get stuck at a single point.
I also consider "rewriting" the problem as $\max_{\vec{x}, \vec{y}} \vec{r} \cdot \vec{x} - \vec{s} \cdot \vec{y}$. But I think that is wrong.
Consider a prisoner's dilemma.
A cooperates A defects
B cooperates ( 0, 0) (5, -5)
B defects (-5, 5) (0, 0)
(a, b) means A's score is a and B's score is b.
A prisoner following the minimax strategy would maximize their minimal score over all possible actions of his opponent. For example, if prisoner A choose to cooperate, prisoner A's minimal score over all actions of prisoner B is -5 because prisoner B can choose to defect.
If both prisoners follows the minimax strategy, they would both choose to defect. If I "rewrite" the objective, each prisoner would maximize their maximal score over all possible actions of his opponent. That means everyone cooperates is a global optima.
Bibliography
Ghosh and Boyd. Minimax and Convex-Concave Games. 2004. https://web.stanford.edu/class/ee392o/cvxccv.pdf
- Minimaximizes bilinear objective with separable linear constraints: \begin{aligned} \min_{\vec{x}}\max_{\vec{y}} \quad & \vec{x}^{\intercal} P \vec{y} \\ \textrm{s.t.} \quad & A\vec{x} \preccurlyeq \vec{b} \\ & C\vec{y} \preccurlyeq \vec{d} \\ \end{aligned}
- Uses duality transform to rewrite the problem as a minimization problem solved by linear programming.
- Can rewrite $\max_{\vec{x}}\min_{\vec{y}} \vec{r} \cdot \vec{x}' + \vec{s} \cdot \vec{y}'$ into a bilinear objective with some equality constraints: $$ \begin{bmatrix} {\vec{x}'}^{\intercal} & \vec{s}^{\intercal} \end{bmatrix} I \begin{bmatrix} \vec{r} \\ \vec{y}' \end{bmatrix} $$
- Can I just directly add the non-separable constraints to the transformed problem?
Ahuja. Minimax linear programing problem. Operations research letters. 1985.
- Linear programming. Not mixed. Looks like it is for a $\vec{y}$ with limited number of possible values. Transforming the problem to the paper's form seems not always possible.
Bazaraa and Goode. An algorithm for solving linearly constrained minimax problems. European journal of operational research. 1981.
- Non-linear programming with linear inequality constraint. Not sure if the form of the constraint matches.
