0
$\begingroup$

Consider the system of linear inequalities: $Ax \preceq b$.

The alternative system of inequalities is: $\lambda \succeq 0, A^T\lambda = 0, b^T \lambda \le 0$

These are strong alternatives since the optimum in the related system (A) below is achieved unless it is unbounded below.

(A) minimize $s$, subject to: $f_i(x) - s \le 0$ for $i=1, \dots, m; Ax=b$.

Can someone explain how these two systems are strong alternatives? I don't see how the unboundedness or optimal value of $A$ implies these two systems are strong alternatives.

$\endgroup$
  • $\begingroup$ I think you intended to write $b^T\lambda < 0$ (with strict inequality). $\endgroup$ – LinAlg Feb 20 at 21:46
1
+50
$\begingroup$

Consider the following two optimization problems: $$\min_{\lambda} \{ b^T\lambda : A^T\lambda=0, \lambda \geq 0\}\text{, and}$$ $$\max_x \{ 0^Tx : Ax \leq b \}. $$ Note that the are duals, let's call the first one the primal problem and the second one the dual.

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 $\lambda$ such that $b^T\lambda < 0$, $A^T\lambda = 0$.

  2. If there is a $\lambda\geq0$ for which $b^T\lambda < 0$ and $A^T\lambda=0$, then the primal problem is unbounded (fill in $t\lambda$ 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.