Optimization/Simplex Method, proof of unique solution

[hkcool]

This was on my homework this week. I already turned it in but the professor hasn't posted the solutions yet so I'm genuinely curious what the answer is.

Homework Statement

The LP:
http://i48.tinypic.com/25svp6u.png

The problem:
http://i50.tinypic.com/nnnm2w.png

Homework Equations

c^{T}d = z_{N}^{T}d_{N}

sorry for the non-use of latex! I tried to use the ## $and environments but couldn&#039;t get it to work!<br /> <br /> <h2>The Attempt at a Solution</h2><br /> <br /> Not sure how standard the notation is since we don&#039;t use a textbook, just the professor&#039;s notes. Anyway, I&#039;m taking my first analysis course this semester so I&#039;m getting decent with proofs. He gives us a big hint in the problem statement.<br /> <br /> So suppose there exists an i in the index set N such that$z_{Ni} = 0##. Does this mean that we just let all the remaining components of z_N be strictly positive? I assumed we want to show that if z_N &gt;= 0, we no longer have a unique solution so we require z_N &gt; 0. Optimality occurs when z_N &gt;= 0, but I interpreted the problem as wanting us to show that we need a stronger condition for uniqueness<br /> <br /> From this, I said that d_N must necessarily be the zero vector since we use the convention that:<br /> <br /> d_Nj = 1, if there exists a j0 such that z_Nj0 &lt; 0<br /> d_Nj = 0, otherwise<br /> <br /> Since we clearly have that z_N is non-negative, d_N must be zero. We have the relation<br /> <br /> (c^T)d = (z_N)^T*d_N (since d_N = 0)<br /> <br /> Then this means that we can find a feasible direction d such that (c^T)d = 0, ie we can step down to x&#039; = x + td. The objective function value at x&#039; is:<br /> <br /> (c^T)(x&#039; + td) = (c^T)x&#039; + t*(c^T)d = (c^T)x&#039; + 0<br /> <br /> which is a contradiction since we know x is a unique solution but we find that x&#039; is also a solution.<br /> <br /> My proof-writing is sketchy but I think I understood the main jist. The problem is I don&#039;t get how the hint that we should assume that a single component of z_N is zero helps us. How is this any different than if I assumed for contradiction that z_N was strictly positive for all i? Because for strictly positive z_N, we&#039;d still have d_N = 0.

 

[Ray Vickson]

This was on my homework this week. I already turned it in but the professor hasn't posted the solutions yet so I'm genuinely curious what the answer is.

Homework Statement

The LP:
http://i48.tinypic.com/25svp6u.png

The problem:
http://i50.tinypic.com/nnnm2w.png

Homework Equations

c^{T}d = z_{N}^{T}d_{N}

sorry for the non-use of latex! I tried to use the ## $and environments but couldn&#039;t get it to work!<br /> <br /> <h2>The Attempt at a Solution</h2><br /> <br /> Not sure how standard the notation is since we don&#039;t use a textbook, just the professor&#039;s notes. Anyway, I&#039;m taking my first analysis course this semester so I&#039;m getting decent with proofs. He gives us a big hint in the problem statement.<br /> <br /> So suppose there exists an i in the index set N such that$z_{Ni} = 0##. Does this mean that we just let all the remaining components of z_N be strictly positive? I assumed we want to show that if z_N &gt;= 0, we no longer have a unique solution so we require z_N &gt; 0. Optimality occurs when z_N &gt;= 0, but I interpreted the problem as wanting us to show that we need a stronger condition for uniqueness<br /> <br /> From this, I said that d_N must necessarily be the zero vector since we use the convention that:<br /> <br /> d_Nj = 1, if there exists a j0 such that z_Nj0 &lt; 0<br /> d_Nj = 0, otherwise<br /> <br /> Since we clearly have that z_N is non-negative, d_N must be zero. We have the relation<br /> <br /> (c^T)d = (z_N)^T*d_N (since d_N = 0)<br /> <br /> Then this means that we can find a feasible direction d such that (c^T)d = 0, ie we can step down to x&#039; = x + td. The objective function value at x&#039; is:<br /> <br /> (c^T)(x&#039; + td) = (c^T)x&#039; + t*(c^T)d = (c^T)x&#039; + 0<br /> <br /> which is a contradiction since we know x is a unique solution but we find that x&#039; is also a solution.<br /> <br /> My proof-writing is sketchy but I think I understood the main jist. The problem is I don&#039;t get how the hint that we should assume that a single component of z_N is zero helps us. How is this any different than if I assumed for contradiction that z_N was strictly positive for all i? Because for strictly positive z_N, we&#039;d still have d_N = 0.

<br /> <br /> The hint did not say z_Ni= 0 for a single i; it said z_Ni = 0 for some i, and that could mean one or two or three or ... .<br /> <br /> As to LaTeX: if you use &quot;[t e x] your stuff [/t e x]&quot; (but remove the spaces inside [ and ]) you will get a displayed result, like this:<br /> (c^T)(x&amp;#039; + td) = (c^T)x&amp;#039; + t*(c^T)d = (c^T)x&amp;#039; + 0 If, instead, you say &quot;[i t e x] your stuff [/ i t e x]&quot; (again, no spaces) you will get it in-line, like this: (c^T)(x&amp;#039; + td) = (c^T)x&amp;#039; + t*(c^T)d = (c^T)x&amp;#039; + 0<br /> <br /> RGV

 

[hkcool]

Yes, but I'm not entirely seeing how that initial supposition will help. Is it okay to suppose there exists an i_{0} \in N such that z_{Ni_{0}} = 0 and that for all i \ne i_{0} z_{Ni} &gt; 0? Like I said, I thought the point of the proof was to show that z_{N} \ge 0 is not a strong enough condition to guarantee a unique solution.

For what it's worth, the hint gives so much a way that I understand the direction I should be going but not how to make that initial leap.

[[thanks for the tex tip btw. I have no idea why it wasn't working the first time.]]

 

[Ray Vickson]

Yes, but I'm not entirely seeing how that initial supposition will help. Is it okay to suppose there exists an i_{0} \in N such that z_{Ni_{0}} = 0 and that for all i \ne i_{0} z_{Ni} &gt; 0? Like I said, I thought the point of the proof was to show that z_{N} \ge 0 is not a strong enough condition to guarantee a unique solution.

For what it's worth, the hint gives so much a way that I understand the direction I should be going but not how to make that initial leap.

[[thanks for the tex tip btw. I have no idea why it wasn't working the first time.]]

OK. Let me change the notation a bit, to make it easier to type. By re-labelling the variables if necessary, assume that x₁, ..., x_m are basic and x_m+1,..., x_n are non-basic in the optimal solution. However, let me re-name the non-basic variables as u₁, ..., u_r, where r = n-m. Thus, u = x_N. The final form of the constraint equations are x_B = v - T u, where
v = B^{-1}b, \text{ and } T = B^{-1}N. We have
Z = \sum c_j x_j = V + \sum_j z_j u_j, \\<br /> \text{where } V = c_B v = c_B B^{-1} b, \text{ and } z = c_N - c_B B^{-1}N <br /> = c_N - c_B T. (For simplicity I take c_B and c_N to be row vectors.) In detail, we have:
x_1 = v_1 - t_{11} u_1 - \cdots - t_{1 r} u_r\\<br /> \vdots \\<br /> x_m = v_m - t_{m1} u_1 - \cdots - t_{m r} u_r\\<br /> Z = V + z_1 u_1 + \cdots + z_r u_r<br />
We are assuming two things: (i) this solution is non-degenerate, so that v_i > 0 for i = 1,2, ...,m; and (ii) it is optimal.

Therefore, we need all z_j ≥ 0 (because if some z_p < 0 we can increase the variable u_p a bit and make the value of Z smaller (that is, we can reduce V). The non-degeneracy assumption is crucial here; without it (at a degenerate solution) we might have an optimal solution but a non-optimal basis.

If some z_p = 0, we can increase u_p a bit (i.e., by a truly positive amount) but with no change in Z, because the variable u_p does not actually enter into the expression for Z in this basis. So, if some component of z is zero we can find an optimal solution that is different from the one we started with, and that would contradict the uniqueness.

Note: in applied modelling, we often use this type of argument to tell whether or not a solution is unique: if all the "reduced costs" are non-zero, the solution is unique, but if some reduced costs vanish there are alternative optima (at least in the non-degenerate case).

RGV