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)  

and

(2)  

where

(3)  

is the dual function and is the domain of the problem. Since we did not impose any convexity assumption on ‘s neither did we assume that our ‘s are affine, then all we can say about and is that they form weak alternatives. In other words,

• If is feasible, then is infeasible.
• If is feasible, then is infeasible.

In this lecture, we assume the following

• are convex
• ‘s are affine, i.e.
• such that

In that case, we write as

(4)  

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

• is feasible is infeasible.
• is feasible is infeasible.

Indeed, strong alternatives are stronger since (unlike weak alternatives) if we know that one of the sets or 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.