2
$\begingroup$

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?

  • 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.)2010-10-28

1 Answers 1

3

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