# Simplex method - infeasible

1. ### liquidFuzz

63
Simplex method - infeasible

I'm looking at some linear optimization problems. In one example I must be missing something, maybe someone can point it out. Here's the example:

\begin{align*} \textrm{max } f(\textbf{x}) = & 2x_1 + x_2 \\ \textrm{subject to} & x_1 + x_2 \leq 5 \\ & -x_1 + x_2 \geq 1 \\ & \textbf{x} \geq 0 \end{align*}

When I try to perform iterations of the simplex method I get funky results, not feasible stuff. I suspect that it is due to how I set up my slack variables, ##x_3## and ##x_4##. My starting point ##x=(0,0)## is not in the feasible set, but that shouldn't matter, right?

\begin{align*} \textrm{min } f(\textbf{x}) = & -2x_1 - x_2 \\ \textrm{subject to} & x_1 + x_2 + x_3 = 5 \\ & x_1 - x_2 + x_4 = - 1 \\ & \textbf{x} \geq 0 \end{align*}

Are my slack variables wrong..? Or is it something else causing me to end up in infeasible points in my iterations?

2. ### elegysix

376
Have you tried a starting point that is in your set? like, x1 = 1, x2 = 2?

I am not familiar with the method you're talking about, but whenever I get crazy results or errors in matlab from fitting, it's usually because of the starting point I've chosen.

3. ### MrAnchovy

550
Of course it matters - the trial solution blindly heads off down the line of steepest descent, how do you expect it is going to find its way into the feasible set?

4. ### liquidFuzz

63
Eh could you refresh my memory. Where do you calculate the steepest descent direction in the simplex algorithm..?

5. ### liquidFuzz

63
I haven't tinkered with this in matlab. Is the optimixation tool kit good? I'll try different starting points and see what I get.

6. ### liquidFuzz

63
Maybe it's how I chose pivoting element..?

I'll post some iterations, maybe you can comment on them.

Tableau
\begin{matrix}
& x_1 & x_2 & s_1 & s_2 & f(x) & \hat{x} \\
r1 & 1 & 1 & 1 & 0 & 0 & 5 \\
r2 & 1 & -1 & 0 & 1 & 0 & -1 \\
obj & -2 & -1 & 0 & 0 & 1 & 0 \\
\end{matrix}

If I chose column ##x_1## as pivoting column the ratio test gives pivoting element ##r_1,x_1##. The updated tableau is then:
\begin{matrix}
& x_1 & x_2 & s_1 & s_2 & f(x) & \hat{x} \\
r1 & 1 & 1 & 1 & 0 & 0 & 5 \\
r2 & 0 & -2 & -1 & 1 & 0 & -6 \\
obj & 0 & 1 & 2 & 0 & 1 & 10 \\
\end{matrix}
This would imply that there are no descent direction, so no further optimization is possible. The current solution however is ##x =(5,0)## which isn't feasible.

If I instead chose starting pivoting element ##r2,x1## I end up in the point ##x=(2,3)## after a couple of iterations with ##f(2,3) = 7##. This suggests that I don't have a clue on how to chose pivoting elements. Pointers would be appreciated...

7. ### liquidFuzz

63
Sigh, I got now. I just needed to iterate until I had the solution...

8. ### MrAnchovy

550
I could have put that better, but it would have taken more words. At each vertex (the initial vertex in particular) you have a number of choices of which variable to vary. An efficient implementation generally chooses the variable that descends most steeply (or possibly the one which achieves the greatest descent when reaching the next extremum).

This is not really relevant to the point though, which is that the simplex method works by traversing (a subset of) the extrema of the feasible set. If you start outside the feasible set you are only going to end up inside it by luck.

9. ### MrAnchovy

550
No, it demonstrates that unless you are at an extremum the choice of reaching the solution is purely down to luck. Now you have struck lucky and found your way to x = (2,3) which is clearly an extremum, the algorithm starts to work and...

Bingo!

10. ### liquidFuzz

63
Could you, or someone else, show me ho to start in, lets say x =(0,1)..?

11. ### MrAnchovy

550
Set the slack variables to 0 and solve the simultaneous equations.