dikcijom2k

2022-07-12

Consider this system:
${e}_{i}={b}_{i}-\sum _{j=1}^{n}{a}_{i,j}{x}_{j}\phantom{\rule{0ex}{0ex}}\left(i=1,2,...m\right)$
where ${a}_{i,j}$ () and $\left(1\le i\le m\right)$ are given. The problem is to find an assignment of values to the variables ${x}_{1},...,{x}_{n}$ that minimizes max $|{e}_{j}|$. Express this problem as a linear program in the standard form.

Tristin Case

Let $e=\left[\begin{array}{c}{e}_{1}\\ ⋮\\ {e}_{m}\end{array}\right]$, $e=\left[\begin{array}{c}{e}_{1}\\ ⋮\\ {e}_{m}\end{array}\right]$, $A=\left[\begin{array}{ccc}{a}_{11}& \dots & {a}_{1n}\\ ⋮\\ {a}_{m1}& \dots & {a}_{mn}\end{array}\right]$, $x=\left[\begin{array}{c}{x}_{1}\\ ⋮\\ {x}_{n}\end{array}\right]$
Then you can equivalently right your system as:
$e=b-Ax$
Let, scalar $t$ be the value of $\underset{j}{max}|{e}_{j}|$, then you will have:

Now let $\mathbf{1}\mathbf{=}\left[\begin{array}{c}1\\ ⋮\\ 1\end{array}\right]$ be a vector of $m$ stackes $1$'s, then these constraints can be written as:
$e\le t1\phantom{\rule{0ex}{0ex}}-e\le t1$
where $\le$ is the element-wise less than/or equal. Equivalently you have:
$b-Ax\le t1\phantom{\rule{0ex}{0ex}}Ax-b\le t1$
the linear program that you are looking for will be:

If you want to standardize it further, do the following: let
, , , $H=\left[\begin{array}{cc}-A& -1\\ A& -1\end{array}\right]$, now it can be written as:

Do you have a similar question?