Weak Alternatives

1

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


where

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

Ahmad Bazzi

Ahmad Bazzi is an Electrical Engineer and YouTuber. Ahmad Bazzi is a signal processing engineer at CEVA DSP. He holds a PhD in Electrical Engineering from EURECOM. Ahmad Bazzi is a EURECOM alumni. Ahmad Bazzi obtained his Master studies (Summa Cum Laude) in Electrical Engineering at SUPELEC, Paris. Ahmad Bazzi has many publications in well-known IEEE conferences, including a nomination award and is a co-inventor in several patents. Ahmad Bazzi dedicates time to publish high level lectures on Mathematics (including convex optimization) and Programming. Ahmad Bazzi also focuses on Machine Learning, Convex Optimization, Linear Algebra, Python, SymPy, NumPy, Pandas, CVXOPT, MATLAB, C++ for firmware systems.

One thought on “Weak Alternatives

  1. Thanks for this helpful article. If anyone wants to transfer playlists/songs between spotify/apple music and more. Then you can use MusConv.com. MusConv – the easiest way to transfer your music data!

Leave a Reply

Your email address will not be published. Required fields are marked *

Next Post

MATPLOTLIB in one video

Thu Dec 10 , 2020
This tutorial is brought to you by DataCamp. The tutorial does the most in rigorously explaining the little bits and pieces of the wonderful Matplotlib. Matplotlib is a comprehensive library for creating static, animated, and interactive visualizations in Python. Matplotlib makes easy things easy and hard things easier. Contents of […]