1

Here is an example of $\min \max $ that should be converted to a linear program. $$\min_{x \in \mathbb{R}^n} \,\,\,\max_{i = 1, \cdots, m} a_i^{\top}x \tag{1}$$

We know the standard primal linear program is defined as follows: $$ \min \,\,\,\,\,\,c^{\top}x \,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\, (P)\\ s.t. \,\,\,\, Ax = b\,\, , x \geq 0 $$ Also, the dual of $(P)$ is defined as $$ \max_{y \in \mathbb{R}^n} \,\,\,\,\,\,\,\,b^{\top}y \,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\, (D)\\ s.t. \,\,\,\, A^{\top}y \leq c \,\,\,\,\,\ $$

My try: I tried to convert $(1)$ to $(D)$, then it would be easy to convert $(D)$ to $(P)$. Let $t= \max_{i = 1, \cdots, m} a_i^{\top}x$, then

$$ \min_{x \in \mathbb{R}^n} t \\ t \geq a_i^{\top}x \,\,\,\,\,\,\forall i = 1, \cdots, m $$

Now we can write

$$ \max_{x \in \mathbb{R}^n} -t \\ a_i^{\top}x-t \leq 0 \,\,\,\,\,\,\forall i = 1, \cdots, m $$ or in the matrix form

$$ \max_{x \in \mathbb{R}^n} \begin{bmatrix} \textbf{0}\\ -1 \end{bmatrix}^{\top} \begin{bmatrix} x\\ t \end{bmatrix} \\ \begin{bmatrix} a_1^{\top} & -1 \\ a_2^{\top} & -1 \\ \vdots\\ a_m^{\top} & -1 \end{bmatrix} \begin{bmatrix} x\\ t \end{bmatrix} \leq \textbf{0} \tag{2} $$

Question: I cannot convert $(2)$ to $(P)$ because $c= \textbf{0}$. What am I missing and mistaken?

Please complete my answer and do not provide other solutions

2 Answers2

1

The original program (1) as written is always at least feasible no matter the choice of $a_1,\ldots, a_m$, with $x \in \mathbb{R}^n = 0$ a feasible solution, with an objective value of 0. Furthermore, either the optimum objective value of (1) is either 0 or $-\infty$. [Make sure you see why.]

Thus your linear program (2) has either an optimum objective value of either 0 or $\infty$ i.e., unboundedness.

Thus (2)'s dual which is in the form of (P) either has an an optimum objective value of either 0 or is infeasible. Which in fact is precisely what you get w $c=0$.

Mike
  • 20,434
1

You need some slack variables.

Note that $a_i^T x \le t$ is equivalent to $a_i^Tx-t +s_i = 0$ and $s_i \ge 0$.

Let $x_k = x_{k,+} - x_{k,-} $, $t=t_+-t_-$, $x_{k,+}, x_{k,-},t_+t_-\ge 0$.

copper.hat
  • 172,524
  • if I do what you are suggesting, I should convert $(1)$ to $(P)$ where I need all the decision variables bigger than zero ($x$ and $t$). How would you take care of them? –  Jan 21 '20 at 22:33
  • can you tell me how to do so. I know I can write $x= x_{+} - x_{-}$ where $x_+=\max(x,0)$ and $x_-=\max(-x,0)$. –  Jan 21 '20 at 22:43
  • I thought you wanted someone to complete your answer and provide no other solutions? (I don't care about the points, just wondering what you meant?) – copper.hat Jan 22 '20 at 01:06
  • completing my solution was using $(D)$ to finish my argument. But you tried to use equality constraint which is using $(P)$ to find the answer. You convert inequality constraint to equality one which forces us to use $(P)$. –  Jan 22 '20 at 02:28