Strong Alternatives


The above lecture is brought to you by Skillshare. In a previous post of mine, we introduced weak alternatives. As a small reminder, consider the following two sets

(1)   \begin{equation*}S = \lbrace f_i(x) \leq 0, i = 1\ldots m ; h_i(x) = 0, i = 1 \ldots p \rbrace\end{equation*}


(2)   \begin{equation*}T = \lbrace \lambda \geq 0 , g(\lambda, \nu) > 0 \rbrace\end{equation*}


(3)   \begin{equation*}g(\lambda,\nu) = \inf_{x\in D} \Big\lbrace\sum\limits_{i=1}^m \lambda_i f_i(x) +\sum\limits_{i=1}^p \nu_i h_i(x) \Big\rbrace\end{equation*}

is the dual function and \mathcal{D} is the domain of the problem. Since we did not impose any convexity assumption on f_i‘s neither did we assume that our h_i‘s are affine, then all we can say about (T) and (S) is that they form weak alternatives. In other words,

  • If (T) is feasible, then (S) is infeasible.
  • If (S) is feasible, then (T) is infeasible.

In this lecture, we assume the following

  • f_i(x) are convex
  • h_i‘s are affine, i.e. h_i(x) = Ax-b
  • \exists x \in \text{relint}(D) such that Ax=b

In that case, we write (S) as

(4)   \begin{equation*}S = \lbrace f_i(x) \leq 0, i = 1\ldots m ; Ax= b \rbrace\end{equation*}

Thanks to the three conditions above, we could strengthen weak alternatives so that they form strong alternatives. That is to say

  • (T) is feasible \iff (S) is infeasible.
  • (S) is feasible \iff (T) is infeasible.

Indeed, strong alternatives are stronger since (unlike weak alternatives) if we know that one of the sets (S) or (T) is infeasible, then the other has to be feasible.

In my YouTube lecture, I give two applications relating to linear inequalities and intersection of ellipsoids.