The basic idea of the KKT conditions as necessary conditions for an optimum is that if they don't hold at a feasible point $\mathbf{x}$, then there exists a direction $\boldsymbol{\delta}$ that will improve the objective $f$ without increasing (and hence possibly violating) the constraints. (If the KKT conditions don't hold at $\mathbf{x}$ then $\mathbf{x}$ can't be an optimum, hence KKT conditions are necessary for a point to be an optimum.)
Imagine you have the optimization problem:
\begin{equation}
\begin{array}{*2{>{\displaystyle}r}}
\mbox{minimize (over $\mathbf{x}$)} & f(\mathbf{x}) \\
\mbox{subject to} & \forall_{j \in \{1\ldots k\}}\; g_j(\mathbf{x}) \leq 0
\end{array}
\end{equation}
Where $\mathbf{x} \in \mathbb{R}^n$ and there are $k$ constraints.
Let $\nabla f(\mathbf{x})$ be a column vector denoting the gradient of $f$ evaluated at $\mathbf{x}$.
Applied to this situation, Farkas Lemma states that for any point $\mathbf{x} \in \mathbb{R}^n$ exactly one of the following statements holds:
- There exists $\boldsymbol{\lambda} \in \mathbb{R}^k$ such that $\sum_{j=1}^k \lambda_j \nabla g_j(\mathbf{x}) = -\nabla f(\mathbf{x})$ and $\boldsymbol{\lambda} \geq \mathbf{0}$
- There exists $\boldsymbol{\delta} \in \mathbb{R}^n$ such that $\forall_j \boldsymbol{\delta}' g_j(\mathbf{x}) \leq 0$ and $ \boldsymbol{\delta}'\nabla f(\mathbf{x}) < 0$
What does this mean? It means that for any feasible point $\mathbf{x}$, either:
- Condition (1) holds and the KKT conditions are satisfied.
- Condition (2) holds and there exists a feasible direction $\boldsymbol{\delta}$ that improves the objective function $f$ without increasing the constraints $g_j$. (eg. you can improve $f$ by moving from $\mathbf{x}$ to $\mathbf{x} + \epsilon \boldsymbol{\delta}$)
Condition (1) states that there exists non-negative multipliers $\boldsymbol{\lambda}$ such that the KKT conditions are satisfied at point $\mathbf{x}$. (Geometrically, it says that the $- \nabla f$ lies in the convex cone defined by the gradients of the constraints.)
Condition (2) states that at the point $\mathbf{x}$, there exists a direction $\boldsymbol{\delta}$ to move (locally) such that:
- Moving in direction $\boldsymbol{\delta}$ reduces the objective function (because the dot product of $\nabla f(\mathbf{x})$ and $\boldsymbol{\delta}$ is less than zero).
- Moving in direction $\boldsymbol{\delta}$ doesn't increase the value of the constraints (because the dot product of $\nabla g_j(\mathbf{x})$ and $\boldsymbol{\delta}$ is less than or equal to zero for all constraints $j$).
(Geometrically, feasible direction $\boldsymbol{\delta}$ defines a separating hyperplane between the vector $-\nabla f(\mathbf{x})$ and the convex cone defined by the vectors $\nabla g_j(\mathbf{x})$.)
(Note: to map this into Farkas Lemma, define matrix $A = \begin{bmatrix} \nabla g_1, \nabla g_2, \ldots, \nabla g_k \end{bmatrix}$)
This argument gives you the necessity (but not sufficiency) of the KKT conditions at an optimum. If KKT conditions aren't satisfied (and the constraint qualifications are satisfied), it's possible to improve the objective without violating the constraints.
The role of constraint qualifications
What can go wrong? You can get degenerate situations where the gradients of the constraints don't accurately describe feasible directions to move in.
There are a multitude of different constraint qualifications to choose from that will allow the above argument to work.
The min, max interpretation (imho the most intuitive)
Form the Lagrangian
$$ \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^k \lambda_jg_j(\mathbf{x})$$
Instead of minimizing $f$ subject to constraints $g_j$, imagine that you're trying to minimize $\mathcal{L}$ while some opponent is trying to maximize it. You can interpret multipliers $\lambda_i$ as penalties (chosen by some opponent) for violating the constraints.
The solution to the original optimization problem is equivalent to:
$$ \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) $$
That is:
- You first pick $\mathbf{x}$ to minimize the Lagrangian $\mathcal{L}$, cognizant that...
- I will then pick $\boldsymbol{\lambda}$ to maximize the Lagrangian (having observed your pick $\mathbf{x}$).
For example, if you violate constraint $g_2$, I can penalize you by setting $\lambda_2$ to infinity!
Weak duality
For any function $f(x, y)$ observe that:
$$ \forall_{\hat{x},\hat{y}} \quad \min_x f(x, \hat{y}) \leq f(\hat{x}, \hat{y}) \leq \max_y f(\hat{x}, y)$$
Since that holds for any $\hat{x}$ and $\hat{y}$ it also holds that:
$$ \max_y \min_x f(x, y) \leq \min_x \max_y f(x, y)$$
In the Langrian setting, this result that $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) \leq \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$ is known as weak duality.
The dual problem $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$ gives you a lower bound on the solution
Strong duality
Under certain special conditions (eg. convex problem where Slater condition holds), you have strong duality (i.e. the saddle point property).
$$\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$$
This beautiful result implies you can reverse the order of the problem.
I first pick penalties $\boldsymbol{\lambda}$ to maximize the Lagrangian.
You then pick $\mathbf{x}$ to minimize the Lagrangian $\mathcal{L}$.
The $\lambda$ set in this process are prices for violating the constraints, and the prices are set such that you will never violate the constraints.
user23658
