Strong Alternatives - Free Online Courses

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*}$

and

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

where

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

On December 14, 2020 By Ahmad Bazzi

Convex Optimization

Leave a Reply Cancel reply

You may also like

But why isn't Markowitz Working ?

Log Barrier Minimization: An Intuitive Approach

Markowitz Portfolio Optimization in Stock Market Analysis

Introduction of Convex Optimization