Weak Alternatives


Let us say we are interested in checking whether system (S) hereby defined as

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

is feasible or not. In other words, could we find a vector x that satisfies set (S) ? In many cases, it may turn out to be hard to answer the question by exhaustively searching all possible candidates of x. To crank it up a notch, we formulate an optimization problem that serves us well. To this extent, consider

(2)   \begin{equation*}\begin{aligned}& \underset{x}{\text{minimize}}& & 0 \\& \text{subject to}& & x \in S\end{aligned}\end{equation*}

Yes, that is right. We minimize 0 subject to x being in S. Well, nothing fancy has been done here. As a matter of fact, if one closely looks at the optimal value, that is

(3)   \begin{equation*}p^*=\begin{cases}0 & \text{ if } (S) \text{ is feasible} \\\infty & \text{ if } (S) \text{ is infeasible}\end{cases}\end{equation*}

One could realize that the optimal value acts as an indicator function, i.e. it returns 0 when (S) is feasible, else \infty. That’s awesome. You just wrote down an optimization problem that tells you whether (S) is feasible or not. In other words, you wrote down an optimization problem answering your main question. However, nothing fancy has been done here. All we’re doing is re-writing the problem and hence nothing could be learned from the optimization problem in equation (2). On the other hand, things becomes a whole lot more interesting when taking a look at the dual problem. But for that, we need to pass by the Lagrangian function that is

(4)   \begin{equation*}\mathcal{L}(x,\lambda,\nu)=0 + \sum\limits_{i=1}^m \lambda_i f_i(x)+\sum\limits_{i=1}^p \nu_i h_i(x) \end{equation*}

The dual function is the infimum of \mathcal{L}(x,\lambda,\nu) over \mathcal{D} (domain of the problem), that is

(5)   \begin{equation*}g(\lambda,\nu) = \inf_{x \in \mathcal{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*}

Finally, the dual problem would be to

(6)   \begin{equation*}\begin{aligned}& \underset{\lambda,\nu}{\text{maximize}}& & \inf_{x \in \mathcal{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 \\& \text{subject to}& & \lambda \geq 0\end{aligned}\end{equation*}

As in the primal problem, the optimal value of the dual problem is also an indicator function to another set of inequalities,

(7)   \begin{equation*}d^*=\begin{cases}0 & \text{ if } (T) \text{ is infeasible} \\\infty & \text{ if } (S) \text{ is feasible}\end{cases}\end{equation*}


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

So now the question is ” How does (T) relate to (S) ? “. Applying weak duality that is

(9)   \begin{equation*}d^* \leq p^*\end{equation*}

we can infer two cases.

  • Case 1: If p^* = 0, then d^ has to be 0.
  • Case 2: If d^ = \infty, then p^* has to be \infty.

Using equations (7) and (3) along with the two cases, we get the following:

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

This is what weak alternative is. It is when at most one of the inequalities are feasible.