I was given two linear systems {$2x=1$, $x=1$} and I was told to write the min-max model. Which I hope I did correctly and got

$|| Ax-b||$ = max {$||2x-1||, ||x-1||$} -> min.

now it is asking me to write the min-max model in the standard LP form as defined on-page $152$ of [Forst]

enter image description here

So I am assuming that the form is (P).

I have found these lecture notes online which helped me understand how to change LP into SF. However, I am still unsure of how I can do that with my question. Any help would be really appreciated.

  • $\begingroup$ This linear system is empty $x=1$ do not satisfy $2x=1$. You can use the $||.||_{\infty}$ to minimize the error but, there is no solution. $\endgroup$ – Alexandre Frias Sep 29 '19 at 3:38

Probably, you want to minimize the error of $||Ax-b||_{\infty}$. Let $t=\max\{|2x-1|, |x-1|\}$ the error of the linear system solution.

$$ \begin{align} \min ~ t & \\ &|2x-1|\leq t\\ &|x-1|\leq t\\ & t\geq 0 , ~ x\in \mathbb{R} \end{align} $$

Removing the module

$$ \begin{align} \min ~ t & \\ & 2x-1\leq t\\ & 2x-1\geq t\\ & x-1\leq t\\ & x-1\geq t\\ & t\geq 0 , ~ x\in \mathbb{R} \end{align} $$

Putting in standard form using $x=x_1 - x_2$ and adding $s_1, ...s_4$

$$ \begin{align} \min ~ t & \\ & 2x_1 - 2x_2 -t +s_1 = 1\\ & 2x_1 - 2x_2 -t -s_2 = 1\\ & x_1 - x_2 -t +s_3 = 1\\ & x_1 - x_2-t - s_4 = 1\\ & t\geq 0 , x_i\geq 0, s_j\geq 0 \end{align} $$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.