How to initialise a linear program?

Question

Good morning! I'm absolutely new to linear programing since this year, yet I'm struggling to understand and learn.

I was given during my lecture that to chose the initial vertice we had to determine a vertice of $U$ if it is not empty or to show that this set was empty indeed.

To a set $U=\{v\in\mathbb{R}^+|Av=b\}$ we associate the following linear program: find $(u,\tilde u)$ (I'm not quite sure of what $\tilde u$ is. such that:

\begin{cases} (u,\tilde u)\in \tilde U=\{(v,\tilde v)\in \mathbb{R}^{+^n}\times \mathbb{R}^{+^m}|Av+\tilde v=b\}\\ \min\limits_{(u,\tilde u)\in \tilde U}\sum\limits_{i=1}^{m}\tilde u_i \end{cases}

Tis set is empty iif this $\min$ is negative. We thus had to apply the Simplex algorithm to solve this new linear programming problem. $(0,b)$ is a vertice of $\tilde U$ and we can the initialize this method but I don't understand neither know how.

in practice,

Its a minimizing case: considering the linear program: if we have to find $x_1,x_2$ and $x_3$ such that

\begin{cases} \min_xf(x)=x_1 -3x_2 +2x_3\\ 3x_1 -x_2 +2x_3\le 7\\ -2x_1 + 4x_2\le 12\\ -4x_1 + 3x_2 + 8x_3\le 10\\ x\ge 0 \end{cases}

which can be writen as:

$A=\begin{pmatrix} 3 & -1 & 2 & 1 & 0 & 0 & 0 \\ -2 & 4 & 0 & 0 & 1 & 0\\ -4 & 3 & 8 & 0 & 0 & 1\\ \end{pmatrix}$

$b=\begin{pmatrix} 7\\12\\ 10\\ \end{pmatrix}$

and $c=\begin{pmatrix} 1,-3,2,0,0,0 \end{pmatrix}^T$

We first have $u_0=\begin{pmatrix} 0,0,0,7,12,10 \end{pmatrix}$, okay, I think I understand

Yet, do we find the inital vertice to start from? how do we initialise?

Why do we first have $I_0=(4,5,6)$?

edit:

and what about

\begin{cases} \max_xf(x)=x_1+x_2\\ x_1 +x_2\ge 2\\ x_1 + x_2\le 7\\ 3x_2 -x_1\le 9\\ 3x_1 +2x_2\le 18\\ x\ge 0 \end{cases}

The vertice of the realisable area are

\begin{array}{lll} A=(2,0) \\ B=(0,2) \\ C=(0,3)\\ D=(3,4)\\ E=(4,3)\\ F=(6,0) \end{array}

Here I clearly see that the origin isn't a feasible starting point. I thus have to find a realisable vertice Do I have to solve another program to find it? Why?

Answer 1

you mentioned that $I_0 = (4,5,6)$.

So, did you meant that $(x_1,x_2,x_3)_{initial} = (4,5,6)$ ?

Initialize means that you have to choose a proper "start value"

since you will have to do several iterations to optimize the objective function(al)

There is no FIXED way to choose a start point, but generally, you select your initial value of your variable such that the objective function(al) is relatively close to the target value, which may be measured by $L^2$ or $L^\infty$ norm, etc.

back to your question,

the initial value of variable(s) is NOT UNIQUE,

you can choose some other values, for instance $(3,4,6)$, just avoid too big or small magnitude. In some cases, different initial values lead to different results.