# Solving continuous Minimax Optimization problem

I want to solve a linear programming minimax problem here mathematically without using software:

\begin{align*} \text{min}\ \text{max} \quad & \{x_1,x_2,x_3\} \\ \text{s.t.} \quad & x_1 + x_2 + x_3 = 15 \end{align*}

Or it can be written

\begin{align*} \text{min} \quad & Z \\ \text{s.t.} \quad & x_1 + x_2 + x_3 = 15 \\ & Z \ge x_1 \\ & Z \ge x_2 \\ & Z \ge x_3 \\ \end{align*}

I was wondering if someone could help me or provide me with good lecture notes having an explanation with examples? Thanks in advance.

Edited: The above problem seems solvable by inspection method, but if we consider the following problem we can't get the optimal solution by inspection (optimal solution I have obtained using the software is $$x_1=0$$, $$x_2=0.39216$$, $$x_3=0.29412$$, $$x_4=0.31373$$ and $$z=-1.1765$$, but I don't know how to solve it manually/mathematically, as well): \begin{align*} \text{min} \quad & Z \\ \text{s.t.} \quad & x_1 + x_2 + x_3+x_4 = 1 \\ & Z \ge x_1-3x_2 \\ & Z \ge x_1-4x_3 \\ & Z \ge x_1-7x_4 \\ & Z \ge x_2-5x_4 \\ & Z \ge x_3-5x_4 \\ & x_1,x_2,x_3,x_4\ge 0 \\ \end{align*}

• Welcome to OR.SE! I've edited your question to use MathJax instead of code blocks, which is our preferred style. – LarrySnyder610 Feb 4 '20 at 14:26
• Please check your second formulation. I get a different optimal solution $x=(0,20,15,16)/51$, with $z=-20/17$. – RobPratt Feb 4 '20 at 18:11
• @RobPratt Yes, you are right. Edited. Thanks. But do you know how to solve it mathematically without software please? – user123 Feb 4 '20 at 19:01

## 3 Answers

Although this is a linear programming problem, it can really be solved by inspection. Think about how you'd solve the problem if there were only two variables, i.e.:

\begin{align*} \text{min}\ \text{max} \quad & \{x_1,x_2\} \\ \text{s.t.} \quad & x_1 + x_2 = 15 \end{align*}

Now can you extend your approach to handle 3 variables?

• Does it mean for every minmax problem, the inspection method works fine? – user123 Feb 4 '20 at 16:21
• No, definitely not! Only that this is a very simple one. – LarrySnyder610 Feb 4 '20 at 16:59
• Related: or.stackexchange.com/q/143/38 – LarrySnyder610 Feb 4 '20 at 17:00

The optimal solution is 15/3 for the three variables. Any other assignment is such that at least one of the variables takes a value larger than 15/3.

For a proof that the solution $$x=(5,5,5)$$ is optimal, use a dual multiplier $$1/3$$ for each constraint: \begin{align} \frac{1}{3}(x_1 + x_2 + x_3) &= \frac{1}{3}\cdot 15 \\ \frac{1}{3}Z &\ge \frac{1}{3}x_1 \\ \frac{1}{3}Z &\ge \frac{1}{3}x_2 \\ \frac{1}{3}Z &\ge \frac{1}{3}x_3 \\ \end{align} Adding these up yields $$Z \ge 5$$.