13
$\begingroup$

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.

enter image description here

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?

enter image description here

Other clarifications

  1. Should f(x) be convex for KKT to apply?
  2. Should g(x) be linear for KKT to apply?
  3. Should λ be necessary in λ*g(X) = 0? Why g(X) = 0 or g(Xi) = 0 is not enough?

References


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?

enter image description here

enter image description here user23658

$\endgroup$
  • 1
    $\begingroup$ This question may garner more attention on the mathematics site; KKT conditions are not necessarily "statistical". Statisticians borrow these and other results from numerical analysis to solve interesting statistical problems, but this is more of a mathematics question. $\endgroup$ – user23658 Jan 13 '17 at 1:54
  • 1
    $\begingroup$ (1) If constraints don't bind, the optimization problem with the constraints has the same solution as the optimization problem without the constraints. (2) Neither $f$ need be convex nor $g$ need be linear for KKT conditions to be necessary at an optimum. (3) You do need special conditions (eg. convex problem where Slater condition holds) for KKT conditions holding to be sufficient conditions for an optimum. $\endgroup$ – Matthew Gunn Jan 14 '17 at 0:11
  • 2
    $\begingroup$ The basic idea of the complementary slackness condition (i.e. $\lambda g(\mathbf{x}) = 0$ where $g(\mathbf{x}) \leq 0$ is a constraint) is that if the constraint is slack (i.e.$g(\mathbf{x}) < 0$) at the optimal $\mathbf{x}$, then the penalty $\lambda$ for tightening the constraint is 0. And if there's a positive penalty $\lambda$ for tightening the constraint, then the constraint must be binding (i.e. $g(\mathbf{x}) = 0$). If traffic is flowing smoothly, the bridge toll $\lambda$ for another car is zero. And if the bridge toll $\lambda > 0$, then the bridge must be at the capacity limit. $\endgroup$ – Matthew Gunn Jan 17 '17 at 0:05
  • 1
    $\begingroup$ The basic KKT theorem says that if the KKT conditions aren't satisfied at a point $\mathbf{x}$, then the point $\mathbf{x}$ isn't optimal. The KKT conditions are necessary for an optimum but not sufficient. (For example, if the function has saddle points, local minima etc... the KKT conditions may be satisfied but the point isn't optimal!) For certain classes of problems (eg. convex problem where Slater's condition holds), the KKT conditions become sufficient conditions. $\endgroup$ – Matthew Gunn Jan 25 '17 at 7:53
7
$\begingroup$

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:

  1. 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}$
  2. 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:

  1. You first pick $\mathbf{x}$ to minimize the Lagrangian $\mathcal{L}$, cognizant that...
  2. 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.

  1. I first pick penalties $\boldsymbol{\lambda}$ to maximize the Lagrangian.

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

$\endgroup$
  • $\begingroup$ Appreciate the information and the links to fill the gaps of understanding. Allow me to confirm. Condition(1) means that KKT says for a point X to be a solution, it needs to satisfy λ*g(X) = 0, λ >=0, and the length of the gradient of g(X) is λ times of that of f(X), otherwise we will find the gradient of f(X) points direction where smaller f(X') can be found? $\endgroup$ – mon Jan 14 '17 at 10:37
  • 3
    $\begingroup$ Slater condition is (just) a constraint qualification which can be applied to convex optimization problems, i.e. makes KKT necessary. Convexity makes KKT sufficient. So Slater condition for convex optimization problem in which objective function and constraints are convex and continuously differentiable makes KKT necessary and sufficient for global minimum. Slater condition is that there is at least one feasible point (i.e., satisfying all constraints) which is in the strict interior of all the nonlinear constraints (anything goes with linear constraints, as long as feasible). $\endgroup$ – Mark L. Stone Jan 14 '17 at 12:33
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.