# Linear optimization constrained by cost function

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?

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

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

-