Get the answer to "Consider this system: e i = b i..."

dikcijom2k

Answered question

2022-07-12

Consider this system:

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

where

a_{i, j}

(

(1 \leq i \leq m, 1 \leq j \leq n)

) and

(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.

Tristin Case

Beginner2022-07-13Added 15 answers

Let

e = [\begin{matrix} e_{1} \\ ⋮ \\ e_{m} \end{matrix}]

e = [\begin{matrix} e_{1} \\ ⋮ \\ e_{m} \end{matrix}]

A = [\begin{matrix} a_{11} & \dots & a_{1 n} \\ ⋮ \\ a_{m 1} & \dots & a_{m n} \end{matrix}]

x = [\begin{matrix} x_{1} \\ ⋮ \\ x_{n} \end{matrix}]

Then you can equivalently right your system as:

e = b - A x

Let, scalar

t

be the value of

max_{j} | e_{j} |

, then you will have:

e_{j} \leq t \forall j = 1, \dots, m - e_{j} \leq t \forall j = 1, \dots, m

Now let

1 = [\begin{matrix} 1 \\ ⋮ \\ 1 \end{matrix}]

be a vector of

m

stackes

1

's, then these constraints can be written as:

e \leq t 1 - e \leq t 1

where

\leq

is the element-wise less than/or equal. Equivalently you have:

b - A x \leq t 1 A x - b \leq t 1

the linear program that you are looking for will be:

max_{x, t} t subject to b - A x \leq t 1 A x - b \leq t 1

max_{x, t} t subject to - A x - t 1 \leq - b A x - t 1 \leq b

If you want to standardize it further, do the following: let

z = [x^{T} t]^{T}

c = [\underset{n times}{\underset{⏟}{0 \dots 0}} 1]^{T}

d = [- b^{T} b^{T}]^{T}

H = [\begin{matrix} - A & - 1 \\ A & - 1 \end{matrix}]

, now it can be written as:

max_{z} c^{T} z subject to H z \leq d

Do you have a similar question?

Recalculate according to your conditions!

Didn't find what you were looking for?