Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I have an optimization problem of the form:

$$\min \mathbf{d}^{T}\mathbf{y}$$

subject to

$$\mathbf{M}\mathbf{y} \geq \mathbf{d}, \qquad \mathbf{y} \geq 0$$

If a solution $\mathbf{s}$ which satisfies $\mathbf{M}\mathbf{s} = \mathbf{d}$ and $\mathbf{s} \geq 0$, how can it be shown $\mathbf{s}$ is optimal for the above linear programming problem?

Initial thought was to form the dual:

max p'd

p>=0

p'M<=d

Thus weak duality gives d'y <= p'd

And the constraint of the dual gives p'M<=d

so : p'My<=dy

and thus p'd<=dy

Combining the two equalities shows that p'd must equal dy, and thus with strong duality this means that p'd is the optimal solution.

Where did I go wrong, and how does being symmetric fit into the problem?

share|improve this question
2  
How do $\mathbf{A}$ and $\mathbf{c}$ relate to the original problem? –  Mike Spivey Oct 27 '10 at 3:59
    
Whoops! Sorry I meant Ms = d, not c...typo! –  GBa Oct 27 '10 at 13:35
1  
It isn't the case that $s$ is necessarily optimal. I found a counterexample. Are you missing anything from the problem statement? Maybe that ${\bf M}^T = {\bf M}$? –  Mike Spivey Oct 27 '10 at 22:56
    
Yes actually, M^t = M, but how does this play in to the problem? You are good! –  GBa Oct 28 '10 at 2:17
2  
Thanks. I teach this stuff. :) As with the other question you asked, what are your thoughts so far? (You can just add them as an edit to the end of your original post rather than as a new comment.) –  Mike Spivey Oct 28 '10 at 2:26
add comment

1 Answer

up vote 3 down vote accepted

You can go this route: You know Ms = d. Taking transposes, you have s$^T$ M$^T$ = d$^T$. But (the key step) since M$^T$ = M, this means that s is feasible for the dual problem. Since s is feasible for the primal and for the dual, and since the primal and dual have the same objective function, weak duality shows you that s must be optimal.

If M$^T \neq $ M then s might not be optimal. For example, suppose we have the following linear program.

$$\min x + y$$

subject to

$$\frac{1}{2}x + y \geq 1,$$ $$\frac{1}{2}x + 2y \geq 1,$$ $$x,y \geq 0.$$

The objective and right-hand side coefficient vectors are the same, as in the problem statement. Solving the inequalities at equality gives you $x = 2$, $y=0$. However, this is not optimal. The solution $x = 0$, $y = 1$ yields a smaller objective function value (and is actually the optimal solution).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.