- #1

hkcool

- 11

- 0

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.

The LP:

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

The problem:

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

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

sorry for the non-use of latex! I tried to use the ## ## and [itex] environments but couldn't get it to work!

Not sure how standard the notation is since we don't use a textbook, just the professor's notes. Anyway, I'm taking my first analysis course this semester so I'm getting decent with proofs. He gives us a big hint in the problem statement.

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 >= 0, we no longer have a unique solution so we require z_N > 0. Optimality occurs when z_N >= 0, but I interpreted the problem as wanting us to show that we need a stronger condition for uniqueness

From this, I said that d_N must necessarily be the zero vector since we use the convention that:

d_Nj = 1, if there exists a j0 such that z_Nj0 < 0

d_Nj = 0, otherwise

Since we clearly have that z_N is non-negative, d_N must be zero. We have the relation

(c^T)d = (z_N)^T*d_N (since d_N = 0)

Then this means that we can find a feasible direction d such that (c^T)d = 0, ie we can step down to x' = x + td. The objective function value at x' is:

(c^T)(x' + td) = (c^T)x' + t*(c^T)d = (c^T)x' + 0

which is a contradiction since we know x is a unique solution but we find that x' is also a solution.

My proof-writing is sketchy but I think I understood the main jist. The problem is I don'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'd still have d_N = 0.

## 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 [itex] environments but couldn't get it to work!

## The Attempt at a Solution

Not sure how standard the notation is since we don't use a textbook, just the professor's notes. Anyway, I'm taking my first analysis course this semester so I'm getting decent with proofs. He gives us a big hint in the problem statement.

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 >= 0, we no longer have a unique solution so we require z_N > 0. Optimality occurs when z_N >= 0, but I interpreted the problem as wanting us to show that we need a stronger condition for uniqueness

From this, I said that d_N must necessarily be the zero vector since we use the convention that:

d_Nj = 1, if there exists a j0 such that z_Nj0 < 0

d_Nj = 0, otherwise

Since we clearly have that z_N is non-negative, d_N must be zero. We have the relation

(c^T)d = (z_N)^T*d_N (since d_N = 0)

Then this means that we can find a feasible direction d such that (c^T)d = 0, ie we can step down to x' = x + td. The objective function value at x' is:

(c^T)(x' + td) = (c^T)x' + t*(c^T)d = (c^T)x' + 0

which is a contradiction since we know x is a unique solution but we find that x' is also a solution.

My proof-writing is sketchy but I think I understood the main jist. The problem is I don'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'd still have d_N = 0.

Last edited: