Weak and strong alternatives

Weak alternatives

• Two systems of inequalities are called weak alternatives if at most one of the two is feasible.
• This is true whether or not the inequalities of system 1 are convex (i.e. $f_i$ convex, $h_i$ affine)
• System 2 is always convex ($g$ concave and $\lambda_i\ge 0$ are convex)

Lagrange duality theory can be applied to the problem of determining feasibility of a system of inequalities and equalities
$$\begin{equation}f_i(x) \leq 0, \; i=1,\cdots,m,\quad h_i(x)=0,\; i=1,\cdots,p \end{equation}$$
The above can be posed as the standard problem with objective $f_0=0$:
$$\begin{align*} \text{minimize} \quad &0\\ \text{subject to}\quad &f_i(x) \leq 0, \quad i=1,\cdots,m \\ &h_i(x) = 0, \quad i=1,\cdots,p \end{align*}$$
This problem has optimal value
$$p^* = \begin{cases}                   0\quad &\text{if system is feasible}\\                  \infty\quad &\text{if system is infeasible}               \end{cases}$$
We associate with the inequality system the dual function
$$g(\lambda,\nu)= \inf_{x\in\mathcal{D}} \left(\sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \right)$$
Note that the dual function has is positive homogeneous, i.e. that for $\alpha > 0, \; g(\alpha\lambda,\alpha\nu) = \alpha g(\lambda,\nu)$.   The dual problem of maximizing $g(\lambda,\nu) \; s.t. \; \lambda \succeq 0$ has the optimal value
$$d^* = \begin{cases}            \infty \quad &\lambda \succeq 0, \; g(\lambda,\nu) \gt 0 \text{ is feasible}\\             0       \quad &\lambda \succeq 0, \; g(\lambda,\nu) \gt 0 \text{ is infeasible}           \end{cases}$$
From weak duality $d^*\leq p^*$ and the above facts, we can conclude that the inequality system
$$\begin{equation} \lambda\succeq 0, \quad g(\lambda,\nu) \gt 0\end{equation}$$ is feasible $d^*=\infty$, then the inequality system is infeasible (since $p^* = \infty$)

A solution to the dual function is a certificate of infeasibility of the system.  To summarize:

• feasibility of system 2 implies infeasibility of system 1
• feasibility of system 1 implies infeasibility of system 2

Strong alternatives

When the original inequality system is convex, and some type of constraint qualification holds, then the pairs of weak alternatives becomes strong alternatives, which means exactly one of the two alternatives holds.

If system 1 is convex, it can be expressed as
$$f_i(x) \leq 0, \; i=1,\dotsm,m,\quad Ax=b, \; A\in \mathbf{R}^{p\times n}$$
This system and its alternative
$$\lambda\succeq 0,\quad g(\lambda,\nu) \gt 0$$
are strong alternatives provided there exists an $x\in \text{relint } \mathcal{D}$ with $Ax=b$ and the optimal value $p^*$ is attained.  [More on that later...]

See Farkas' lemma