2
$\begingroup$

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.
$\endgroup$
4
  • $\begingroup$ Do I really have to write my own solver? That doesn't sound easy. $\endgroup$ Jun 29 at 16:22
  • $\begingroup$ What variables are integral? $\endgroup$ Jun 29 at 19:32
  • $\begingroup$ 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. $\endgroup$ Jun 29 at 19:35
  • $\begingroup$ There is no tag for bilinear optimization. $\endgroup$ Jun 29 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.