KKT Condition

Goal

Given a differentiable function $f:M\to \mathbb{R}$, what is the condition for the minimizer of $f$? What if there are constraints? The general answer is the Karush-Kuhn-Tucker (KKT) condition, which is typically written in a coordinate-heavy form.

Is there a high level understanding of KKT condition using the notion of pullback and pushforward?

Karush-Kuhn-Tucker (KKT) Condition

The problem is that we want to

$$\underset{x\in {\mathbb{R}}^n}{\min }E(x)$$

subject to $g_i(x)=0$ for $i=1,\dots ,m$ and $h_j(x)\le 0$ for $j=1,\dots ,\ell$.

The KKT Theorem states that the optimizer $x_0$ of the above problem satisfies

$$\nabla E{|}_{x_0}+\sum _{i=1}^m{\lambda }_i\nabla g_i{|}_{x_0}+\sum _{j=1}^{\ell }{\mu }_j\nabla h_j{|}_{x_0}=0$$ $${\mu }_1,\dots ,{\mu }_{\ell }\ge 0$$ $$\sum _{j=1}^{\ell }{\mu }_j{h}_j(x_0)=0$$

High Level Understanding of KKT Condition

Imagine you are a ball rolling down a 3D hill and you want to minimize your energy function $E(x)$. Reaching the bottom of the hill is the optimal solution. However, there are some constraints on where you can go. Consider when $g_i(x)=0$. This is like saying there are rigid train tracks. The ball must stay exactly on this line. Consider the constraint $h_j(x)\le 0$. These are like fences. The ball can roll freely inside the fenced yard ($h_j(x)<0$) , but cannot cross the boundary ($h_j(x)=0$).

The KKT Theorem states that if the ball is at the optimal solution $x_0$, those three specific conditions must hold.

1. This balances the forces. The gradient $\nabla E{|}_{x_0}$ is gravity pulling the ball down the hill. Without constraints, the ball would stop where gravity is zero ($\nabla E{|}_{x_0}=0$). However, the train tracks and fences exert forces on the ball. It means the track $\nabla g$ and the fence $\nabla h$ are pushing the ball with exact, equal, and opposite forces to balance the gravity. The scalars ${\lambda }_i$ and ${\mu }_j$ are the strength of the forces. The net force must be $0$ for the ball to be at rest.
2. The second condition says the force from the fence must be pushing inward. If ${\mu }_j<0$, the force from the fence is pushing outward, which means the ball is trying to cross the fence. This cannot be optimal because the ball can roll freely inside the fenced yard, so it can always find a better solution by rolling inside the yard.
3. We know ${\mu }_j\ge 0$ from condition 2 and $h_j(x_0)\le 0$ from the constraint. Since every single term in the sum ${\sum }_{j=1}^{\ell }{\mu }_j{h}_j(x_0)$ is non-positive, the only way for the sum to be $0$ is that every single term is $0$. In particular, for ${\mu }_j{h}_j(x_0)$ to equal $0$, one of two must be true.
   1. The ball is far away from the fence, meaning $h_j(x_0)<0$. Because the ball is not touching the fence, there is no force from the fence, so ${\mu }_j=0$. Thus the product is $0$.
   2. The ball is touching the fence, meaning $h_j(x_0)=0$. The product is still $0$. (Note that ${\mu }_j>0$).

Definition (Annihilator Subspace)

The annihilator subspace of a subspace $W\subset U$ is a subspace $W^{\circ }\subset U^{\ast }$ defined by

$$W^{\circ }:=\left\{\lambda \in U^{\ast }\mid ⟨\lambda |\vec{w}⟩=0,\forall \vec{w}\in W\right\}$$

It’s like the dual of the null space.

Definition (Polar Cone)

The polar cone of a subset $S\subset U$ is a subset $S^{\circ }\subset U^{\ast }$ defined by

$$S^{\circ }:=\left\{\lambda \in U^{\ast }\mid ⟨\lambda |\vec{s}⟩\le 0,\forall \vec{s}\in S\right\}$$

Proposition (Convexity of Polar Cone)

The polar cone of any set is a convex cone.

Proposition (Polar Cone of a Subspace)

The polar cone of a subspace is the annihilator space.

Definition (Four Fundamental Subspaces)

The four fundamental subspaces of a linear map $A:U\to V$ are the following four subspaces:

1. Kernel

$$\text{ker}(A):=\left\{\vec{u}\in U\mid A\vec{u}=0\right\}\subset U$$

2. Image

$$\text{im}(A):=\left\{A\vec{u}\in V\mid \vec{u}\in U\right\}\subset V$$

3. Cokernel

$$\text{ker}(A^{\ast }):=\{\lambda \in V^{\ast }\mid A^{\ast }\lambda =0\}\subset V^{\ast }$$

4. Coimage

$$\text{im}(A^{\ast }):=\{A^{\ast }\lambda \in U^{\ast }\mid \lambda \in V^{\ast }\}\subset U^{\ast }$$

Theorem (Fundamental Theorem of Linear Maps)

The four fundamental subspaces of a linear map $A:U\to V$ satisfy the following properties:

1. $\text{ker}(A{)}^{\circ }=\text{im}(A^{\ast })$
   1. The coimage perfectly annihilates the kernel.
2. $\text{ker}(A^{\ast }{)}^{\circ }=\text{im}(A)$
   1. The image perfectly annihilates the cokernel.
3. $\text{im}(A{)}^{\circ }=\text{ker}(A^{\ast })$
   1. The cokernel annihilates the image.
4. $\text{im}(A^{\ast }{)}^{\circ }=\text{ker}(A)$
   1. The kernel annihilates the coimage. Recall that $A^{\ast }$ is the adjoint linear map of $A$, where $A^{\ast }:V^{\ast }\to U^{\ast }$.

Proof: Use the dual pairing.

Let $\lambda \in V^{\ast }$. We have $A^{\ast }\lambda \in \text{im}(A^{\ast })$. Since $A^{\ast }$ is adjoint, then

$$⟨A^{\ast }\lambda |\vec{u}⟩=⟨\lambda |A\vec{u}⟩$$

Let $u$ be some vector. As $Au=0$, we have RHS is $0$ and thus LHS is $0$. In particular, it means $A^{\ast }\lambda \in \text{ker}(A{)}^{\circ }$ as it annihilates the kernel.

The proof is similar for the other three properties.

Unconstrained Optimization

Let $M$ be a domain without boundary (e.g. $M={\mathbb{R}}^n$). Let $E:M\to \mathbb{R}$ be a smooth function. The problem is that we want to minimize $E(x)$ for all $x\in M$. If $x_0$ is a minimizer, then

$$dE{|}_{x_0}[[\mathring{x}]]=0,\forall \mathring{x}\in T_{x_0}M$$

Equivalently, $dE{|}_{x_0}=0$.

Equality Constraints

Here, we discuss the “train tracks” and how they affect the optimality condition.

Let $M$ be an $n$-dimensional domain without boundary (e.g. M = ${\mathbb{R}}^n$). Let $S\subset M$ be a surface without boundary. Typically,

$$S=\left\{x\in M\mid g(x)=0\right\}\text{for some}g:M\to {\mathbb{R}}^m$$

In that case, $S$ is $(n-m)$-dimensional. The problem is that we want to minimize $E(x)$ for all $x\in S$. For an unconstrained problem on $S$, the condition for an optimal $x_0\in S$ is

$$dE{|}_{x_0}[[\mathring{x}]]=0,\forall \mathring{x}\in T_{x_0}S\subset T_{x_0}M$$

Equivalently, $dE{|}_{x_0}\in (T_{x_0}S{)}^{\circ }$.

Now suppose $g:M\to Y$ where $Y$ is a vector space, and $S$ is given by

$$S=g^{-1}\left(\{0_Y\}\right)=\left\{x\in M\mid g(x)=0_Y\right\}$$

What is ${\left(T_{x_0}S\right)}^{\circ }$ in terms of $g$? We observe that

$$T_{x_0}S=\text{ker}(dg{|}_{x_0})$$

Therefore by Theorem (Fundamental Theorem of Linear Maps),

$$\begin{array}{rl}{\left(T_{x_0}S\right)}^{\circ }& ={\left(\text{ker}(dg{|}_{x_0})\right)}^{\circ }\\ & =\text{im}(dg{|}_{x_0}^{\ast })\\ & =\left\{dg{|}_{x_0}^{\ast }[[\lambda ]]\in T_{x_0}{M}^{\ast }\mid \lambda \in Y^{\ast }\right\}\end{array}$$

The optimality condition is that there exists $\lambda \in Y^{\ast }$ such that

$$dE{|}_{x_0}=dg{|}_{x_0}^{\ast }[[\lambda ]]$$

In coordinate form,

$$\frac{\partial E}{\partial x_i}{|}_{x_0}=\sum _{\alpha }{\lambda }_{\alpha }\frac{\partial g_{\alpha }}{\partial x_i}{|}_{x_0}$$

The idea is that if we have found the minimizer point $x_0$ while trapped on a surface $S$, then no matter what direction we take on $S$ from $x_0$ (i.e. the tangent space $T_{x_0}S$), the energy function $E$ does not change (i.e. $dE{|}_{x_0}[[\mathring{x}]]=0$). However, this means that $dE{|}_{x_0}$ is actually in the annihilator subspace of the tangent space. Via the fundamental theorem of linear maps, we get that $dE$ is in the image of $d{g}^{\ast }$, such that there exists covector $\lambda \in Y^{\ast }$ such that $dE{|}_{x_0}=dg{|}_{x_0}^{\ast }[[\lambda ]]$. The resulting equation is the classic Lagrange multiplier form.

Inequality Constraints

Here we discuss the “fences” and how they affect the optimality condition.

Definition (Tangent Cone)

Let $M$ be a domain without boundary (e.g. $M={\mathbb{R}}^n$). Let $S\subset M$ be a surface with boundary. Typically,

$$S=\left\{x\in M\mid h_i(x)\le 0,i=1,\dots ,\ell \right\}$$

The problem is that we want to minimize $E(x)$ for all $x\in S$.

For each $x\in S$, we define the tangent cone of $S$ at $x$ by

$$C_x:=\left\{\mathring{x}\in T_{x}M|\mathring{x}\in \frac{d_{\gamma }(t)}{dt}{|}_{t=0}\text{ for some curve }\gamma :[0,1]\to S\right\}$$

A tangent cone may be a subspace, the entire tangent space $T_{x}M$, or some non-convex cone. If $x$ is the minimizer of $E$, then it means that there is no direction to go that decreases $E$. In particular,

$$dE{|}_{x_0}[[\mathring{x}]]\ge 0$$

or that

$$-dE{|}_{x_0}[[\mathring{x}]]\le 0$$

which by definition of polar cone implies that

$$-dE{|}_{x_0}\in C_{x_0}^{\circ }$$

Physically, the covector $-dE$ points in the “downhill” direction. Since it lives inside the polar cone, then gravity is actively trying to push the ball through the fence, away from the valid yard. The fence stops the ball from falling further.

Translating to KKT via Pullbacks

We can map this back to our constraint functions $h_1,\dots ,h_{\ell }$. Think of $\mathbf{h}=(h_1,\dots ,h_{\ell }):M\to {\mathbb{R}}^{\ell }$ as a map. Since the rule is that $\mathbf{h}(x)\le 0$ for all $x\in S$, we have an “admissible set” in ${\mathbb{R}}^{\ell }$:

$$A:=\left\{\mathbf{z}\in {\mathbb{R}}^{\ell }\mid z_1\le 0,\dots ,z_{\ell }\le 0\right\}$$

• The differential map $d{\mathbf{h}}_x$ pushes the complex tangent cone $C_{S,x}$ forward, flattening it into the simple, negative-quadrant cone $C_{A,h_x}$ in Euclidean space.

$$(d{\mathbf{h}}_x{)}_{\ast }{C}_{S,x}=C_{A,h_x}$$

• To find the polar cone on the manifold $M$, we find the polar cone on the negative quadrant in ${\mathbb{R}}^{\ell }$ and pullback via the adjoint map $(d{\mathbf{h}}_x{)}^{\ast }$.

$$C_{S,x}^{\circ }=(d{\mathbf{h}}_x{)}^{\ast }{C}_{A,h_x}^{\circ }$$

What is the polar cone of the negative quadrant? By definition, it is a strictly positive quadrant. Therefore, any covector living in polar cone $C_{A,h_x}^{\circ }$ must be a vector of positive numbers. Call this positive vector $\vec{\mu }$ where ${\mu }_j\ge 0$ for all $j$. Therefore

$$-dE=(d{\mathbf{h}}_x{)}^{\ast }[[\vec{\mu }]]$$

where ${\mu }_j\ge 0$. So, when we write this in standard coordinate notation, the adjoint $(d{\mathbf{h}}_x{)}^{\ast }$ becomes the sum of the constraint gradients, yielding

$$-dE=\sum _{j=1}^{\ell }{\mu }_{j}d{h}_j$$

Example 1

Consider the following diagram.

$"\\usepackage{amsmath}\n\\usepackage{amssymb}\n\\usepackage{amsfonts}\n\n\\begin{document}\n\\begin{tikzpicture}[>=stealth, scale=1.1]\n\n$

source code

Let the configuration space be all center of mass and rotation.

$$M=\{({\mathbf{c}}_{\text{world}},\theta )\in {\mathbb{R}}^2\times {\mathbb{S}}^1\}$$

Here, ${\mathbf{c}}_{\text{world}}=[c_1,c_2{]}^{\top }$ is the position of the center of mass in the world frame, and $\theta$ is the rotation angle. We see that ${\mathbf{R}}^{\theta }$ is the rotation matrix and ${\mathbf{d}}_{\text{body}}$ is the vector from the center of mass to the corner in the body frame. The corner of the box is

$$\mathbf{x}={\mathbf{c}}_{\text{world}}+{\mathbf{R}}^{\theta }{\mathbf{d}}_{\text{body}}$$

There is an inequality constraint that the corner must be above the ground. When the corner is contact with the ground, what is the polar tangent cone in center of mass and rotation?

So,

$$\begin{array}{rl}\mathbf{x}& ={\mathbf{c}}_{\text{world}}+{\mathbf{R}}^{\theta }{\mathbf{d}}_{\text{body}}\\ {\left[\begin{array}{c}x\\ y\end{array}\right]}_{(c,\theta )}& =\left[\begin{array}{c}{c}_1\\ c_2\end{array}\right]+\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]\left[\begin{array}{c}{d}_1\\ d_2\end{array}\right]\end{array}$$

and so the height of the corner is represented by the following. Note that it must always be non-negative (in the air) and is equal to $0$ at the optimal solution (on the ground).

$$\begin{array}{rl}y(\mathbf{c},\theta )& =d_1\sin \theta +d_2\cos \theta +c_2\\ \left[\begin{array}{ccc}\frac{\partial y}{\partial c_1}& \frac{\partial y}{\partial c_2}& \frac{\partial y}{\partial \theta }\end{array}\right]& =\left[\begin{array}{ccc}0& 1& d_1\cos \theta -d_2\sin \theta \end{array}\right]\end{array}$$

Here we calculated the pushforward which is the Jacobian. The partial derivatives tell us exactly how much the corner moves up or down if we nudge the box horizontally, vertically, or rotatationally.

To find the geometric KKT conditions, we must pull that 1D force $\mu$ backward into our 3D configuration space. We do this by multiplying the transposed ${(}^{\ast })$ Jacobian (the adjoint map!) by $\mu$. Therefore, the polar tangent cone

• in the height space is $\{\mu \le \theta \}$.
• in $(\mathbf{c},\theta )$ space is

$$\left\{\left[\begin{array}{c}0\\ 1\\ d_1\cos \theta -d_2\sin \theta \end{array}\right]\mu |\mu \le 0\right\}$$

This gives the set of vectors

$$\left\{\left[\begin{array}{c}0\\ \mu \\ (d_1\cos \theta -d_2\sin \theta )\mu \end{array}\right]|\mu \le 0\right\}$$

where the horizontal force is $0$. This represents the fact that the ground does not push the box horizontally (i.e. no friction causing it to slide left or right). The vertical force (in the $c_2$ axis) is exactly the normal force $\mu$ from the ground, which is pushing up. It is the equal and exact opposite of the downward gravity force $-dE$. The rotational force is on $\theta$ axis; it is precisely the torque from the ground pushing up on the corner of angle $\theta$ from the ground.

Recall that torque is the cross product of force and distance. The force is $\mu$. The horizontal distance from the center of the mass to the corner is precisely $d_1\cos \theta -d_2\sin \theta$.