# Minimax problem with a large high dimensional feasible region

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:

1. Randomly choose a feasible pair of $$\vec{x}$$ and $$\vec{y}$$
2. Fix $$\vec{x}$$ and minimize over $$\vec{y}$$
3. Fix $$\vec{y}$$ and maximize over $$\vec{x}$$
4. 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.
• Do I really have to write my own solver? That doesn't sound easy. Jun 29 at 16:22
• What variables are integral? Jun 29 at 19:32
• hmm. Some of the x and some of the y are integral. The full problem is here: or.stackexchange.com/questions/6443/… But that one is very long. Jun 29 at 19:35
• There is no tag for bilinear optimization. Jun 29 at 22:01