# Continuous minimax with linear objective and constraints

How to solve the following minimax problem quickly? The variables are all continuous.

$$\max_{x_{1}, x_{4}, x_{5}} \min_{x_2,x_3} \vec{c}^{\intercal} \vec{x}$$

subject to the following constraints: $$A\vec{x} \ge \vec{b}$$ $$\vec{x} \ge 0$$

where

$$A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 0 & 0 \\ 0 & -1 & 0 & 0.4 & 0 \\ 0 & 0 & -1 & 0 & 0.4 \\ 1 & 0 & 0 & -1 & -1 \\ 0 & -0.6 & 0 & 1 & 0 \\ 0 & 0 & -0.6 & 0 & 1 \end{bmatrix}$$

$$\vec{b}^{\intercal} = \begin{bmatrix} 1 & -1 & 2 & -2 & 1 & 1 & -1 & 0.6 & 0.6 \end{bmatrix}$$

$$\vec{c}^{\intercal} = \begin{bmatrix} 1 & -0.6 & -0.6 & 0 & 0 \end{bmatrix}$$

I tried to split the variables into two groups $$x_1, x_4, x_5$$ and $$x_2, x_3$$. And replace the inner minimization by its dual, which is a maximization. But that makes the objective function quadratic instead of linear:

$$\max_{x_1, x_4, x_5} \left( \max_{x_2, x_3} \vec{b}^{\intercal} \vec{y} - \vec{x}^{\intercal}A_{1,4,5}^{\intercal} \vec{y} \right)$$ where $$A_{1,4,5}$$ is same as $$A$$ except columns 2 and 3 are all zeros.

• Are you sure the problem is stated correctly? This is maximin instead of minimax. Also, the first two constraints imply that $x_1=1$, so you can eliminate that variable. Aug 21, 2021 at 20:18
• Yes. $x_1 = 1$, $x_2 + x_3 = 2$ Exchanging the order of max and min should be fine in this case because it is a zero-sum game: en.wikipedia.org/wiki/Minimax_theorem Aug 21, 2021 at 20:28
• Maybe there is no deterministic answer: blogs.cornell.edu/info2040/2015/10/19/… But a probabilistic approximation is good enough for me. Probably I can start from a random feasible point and then alternate the maximization and minimization steps. Stop when I reach a cycle of solutions. Then try another random initial point again to find all cycles of solutions. Aug 21, 2021 at 20:58
• @QuriousCube There is no feasible point. Please see my answer. Aug 22, 2021 at 9:33
• That is nice. That gets rid of one branch of the search tree. Aug 22, 2021 at 16:42

## 1 Answer

The problem is infeasible:

$$(c_1,c_2) \Rightarrow x_1=1$$

$$(c_3,c_4) \Rightarrow x_2+x_3=2$$

$$(c_1,c_2,c_7) \Rightarrow x_4 + x_5 \le 2$$

$$(c_5,c_6) \Rightarrow -(x_2+x_3)+0.4(x_4+x_5) \ge 2 \text{ and so } (c_3,c_4,c_5,c_6)\Rightarrow x_4 + x_5 \ge 10$$

The last two lines are not consistent. Note that we also obtain a conflict with $$(c_8,c_9)$$:

$$(c_8,c_9) \Rightarrow -0.6(x_2+x_3)+(x_4+x_5) \ge 1.2 \text{ and so } (c_3,c_4,c_8,c_9)\Rightarrow x_4 + x_5 \ge 2.4$$

• How can a computer know that the problem is infeasible? Aug 22, 2021 at 16:50
• Never mind. Just have add slack and surplus variables and then solve the system of equality Aug 22, 2021 at 16:53
• @QuriousCube Once the problem is infeasible, you can use a feature of linear solvers called conflict refiner that gives you a minimal set of conflicting constraints. Gurobi calls this minimal set an Irreducible Inconsistent Subsystem (IIS). I haven't used a solver for this problem though. I started to characterize the basic feasible solutions of the minimization part (which only has two variables $x_2$ and $x_3$) to subsequently solve the original problem, and then realized that it is infeasible. Aug 22, 2021 at 17:30