# How are these two systems strong alternatives?

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.

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

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