KKT in a nutshell graphically Objective
Confirm if the understanding of KKT is correct or not. Seek for further explanation and confirmations on KKT.
Background
Trying to understand KKT conditions, especially the complementary one, which always pops up out of blue in SVM articles. I do not need list of abstract formulas but do need a concrete, intuitive, and graphical explanation.
Question
If P, which minimizes the cost function f(X), is inside the constraint (g(P) >= 0), it is the solution. It seems KKT is not relevant in this case.

It seems KKT says if P is not inside the constraint, then the solution X should satisfy below in the picture. Is it KKT all about or do I miss other important aspects?

Other clarifications


*

*Should f(x) be convex for KKT to apply?

*Should g(x) be linear for KKT to apply?

*Should λ be necessary in λ*g(X) = 0? Why g(X) = 0 or g(Xi) = 0 is not enough?


References


*

*Lagrange Multipler KKT condition

*Does every gutter point in SVM have positive multiplier?

*http://fnorio.com/0136Lagrange_method_of_undetermined_multipliers/Lagrange_method_of_undetermined_multipliers.html

Update 1
Thanks for the answers but still struggle to understand. Focus on the necessity only here: 
Is the condition(2) in Matthew Gunn's answer about the non-optimal point (in green circle) and KKT will not be satisfied there? And the point would be identified by looking at Hessian as in the Mark L. Stone's answer?
I suppose another situation is saddle points, but the same applies?


user23658
 A: 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.
KKT conditions and Farkas Lemma
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.
A: f(x) being convex is necessary for KKT to be sufficient for x to be local minimum. If f(x) or -g(x) are not convex, x satisfying KKT could be either local minimum, saddlepoint, or local maximum.
g(x) being linear, together with f(x) being continuously differentiable is sufficient for KKT conditions to be necessary for local minimum. g(x) being linear means that the Linearity constraint qualification for KKT to be nessary for local minimum is satisfied. However, there are other less restrictive constraint qualifications which are sufficient for KKT conditions to be necessary for local minimum.  See the Regularity conditions (or constraint qualifications) section of https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .
If a local minimum has no "active" constraints (so in the case of only an inequality constraint, that constraint is not satisfied with equality), Lagrange multipliers associated with such constraints must be zero, in which case, KKT reduces to the condition that the gradient of the objective = 0.  In such case, there is zero "cost" to the optimal objective value of an epsilon tightening of the constraint.
Further info:
Objective function and constraints are convex and continuously differentiable implies KKT is sufficient for global minimum.
If objective function and constraints are continuously differentiable and constraints satisfy a constraint qualification, KKT is necessary for a local minimum.
If objective function and constraints are continuously differentiable, convex, and constraints satisfy a constraint qualification, KKT is necessary and sufficient for a global minimum.
The above discussion actually pertains only to 1st order KKT conditions. There are also 2nd order KKT conditions, which can be stated as:
A point satisfying 1st order KKT conditions and for which objective function and constraints are twice continuously differentiable is (sufficient for) a local minimum if the the Hessian of the Lagrangian projected into the nullspace of the Jacobian of active constraints is positive semidefinite. (I'll let you look up the terminology used in the preceding sentence.)  Letting $Z$ be a basis for the nullspace of the Jacobian of active constraints, 2nd order KKT condition is that $Z^T H Z$ is positive semi-definite, where $H$ is the Hessian of the Lagrangian.  Active constraints consist of all equality constraints plus all inequality constraints which are satisfied with equality at the point under consideration.  If no constraints are active at the 1st order KKT point under consideration, the identity matrix is a nullspace basis $Z$, and all Lagrange multipliers must be zero, therefore, the 2nd order necessary condition for a local minimum reduces to the familiar condition from unconstrained optimization that the Hessian of the objective function is positive semi-definite.  If all constraints are linear, the Hessian of the Lagrangian = Hessian of objective function because the 2nd derivative of a linear function = 0.
