# Weak Alternatives

1

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

(1)

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

(2)

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

(3)

One could realize that the optimal value acts as an indicator function, i.e. it returns when is feasible, else . That’s awesome. You just wrote down an optimization problem that tells you whether 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)

The dual function is the infimum of over (domain of the problem), that is

(5)

Finally, the dual problem would be to

(6)

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

(7)

where

(8)

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

(9)

we can infer two cases.

• Case 1: If , then has to be .
• Case 2: If , then has to be .

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

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

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