0
$\begingroup$

From Convex Optimization:

Can someone explain how the proof below shows that $5.87$ and $5.88$ are strong alternatives?

It seems to just list the optimal values of $5.89$ and $5.90$ depending on the feasibility of $5.87$ and $5.88$ and claim that they're equal because of this list.

Is there a feasibility relationship between a linear program and it's dual that would suggest that exactly one of $5.87$ and $5.88$ is feasible?


enter image description here

$\endgroup$
2
$\begingroup$

Is there a feasibility relationship between a linear program and it's dual

Yes, if the primal is infeasible, the dual is infeasible or unbounded. If the primal is unbounded, the dual is infeasible. You can switch primal and dual in these statements. These statements follow from the weak duality theorem.

The two lines of reasoning here are:

  1. If the dual is feasible, the dual has optimal value 0, and therefore the primal also has optimal value 0 (by strong duality), and therefore you cannot have $x$ such that $c^Tx < 0$, $Ax \leq 0$.

  2. If there is an $x$ for which $c^Tx < 0$ and $Ax \leq 0$, then the primal problem is unbounded (fill in $tx$ and let $t\to\infty$), therefore the dual is infeasible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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