Are Slack Variables Causing Infeasible Points in Simplex Method?

[liquidFuzz]

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?

 

[elegysix]

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.

 

[pbuk]

My starting point $x=(0,0)$ is not in the feasible set, but that shouldn't matter, right?

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?

 

[liquidFuzz]

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?

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

 

[liquidFuzz]

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.

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.

 

[liquidFuzz]

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

 

[liquidFuzz]

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

 

[pbuk]

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

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.

 

[pbuk]

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

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

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

Bingo!

 

[liquidFuzz]

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

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

 

[pbuk]

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