3

Usually I have been asked to write problems in standard form that have inequalities involved. However, this problem has none and I was wondering if anyone had insight on how to go about solving it.

Consider this system:

$$ e_{i} = b_{i} - \sum_{j=1}^na_{i,j}x_{j} \\(i=1,2,...m) $$

where $a_{i,j}$ $(1 \leq i \leq m\,,\ 1 \leq\ j \leq n)$ and $b_{i}$ $(1 \leq i \leq m)$ 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.

So, there are no inequalities and both $i$ and $j$ are both always positive so I don't know where to start introducing new variables.

Alex Chumbley
  • 189

1 Answers1

1

Let $e=\begin{bmatrix}e_1\\\vdots\\ e_m\end{bmatrix}$, $b=\begin{bmatrix}b_1\\\vdots\\ b_m\end{bmatrix}$, $A=\begin{bmatrix}a_{11}&\ldots&a_{1n}\\\vdots\\ a_{m1}&\ldots&a_{mn}\\\end{bmatrix}$, $x=\begin{bmatrix}x_1\\\vdots\\ x_n\end{bmatrix}$

Then you can equivalently right your system as:

$$e=b-Ax$$

Let, scalar $t$ be the value of $\max_j |e_j|$, then you will have:

$$e_j\leq t~~\forall j=1,\ldots,m\\ -e_j\leq t ~~\forall j=1,\ldots,m$$

Now let $\bf{1}= \begin{bmatrix}1\\\vdots\\ 1\end{bmatrix}$ be a vector of $m$ stackes $1$'s, then these constraints can be written as:

$$e\leq t1\\ -e\leq t1$$

where $\leq$ is the element-wise less than/or equal. Equivalently you have:

$$b-Ax\leq t1\\ Ax-b\leq t1$$

the linear program that you are looking for will be:

$$\max_{x,t} ~~t\quad\text{subject to}\\b-Ax\leq t1 \\ Ax-b\leq t1$$

$$\max_{x,t} ~~t\quad\text{subject to}\\-Ax-t1\leq -b \\ Ax-t1\leq b$$

If you want to standardize it further, do the following: let $z=[x^T~~t]^T$, $c=[\underbrace{0\ldots 0}_{n \text{ times}}~~1]^T$, $d=[-b^T~~b^T]^T$, $H=\begin{bmatrix}-A& -1\\A& -1\\\end{bmatrix}$, now it can be written as:

$$\max_{z} ~~c^Tz\quad\text{subject to}\\Hz\leq d$$

Alt
  • 2,592