Optimality conditions

Let $\mathcal{C}\subset {\mathbf{R}}^d$ be closed, and $f_0:{\mathbf{R}}^d\to \mathbf{R}$ be a continuously differentiable function. Consider the (possibly non-convex) general optimization problem

Intuitively, if a point $x_{\ast }$ is a (local) minimum, then

If $x_{\ast }$ is in the interior of $\mathcal{C}$, then the set of “feasible directions” is ${\mathbf{R}}^d$, and we recover the usual zero-gradient (necessary) optimality condition:

If $x_{\ast }$ is on the boundary of $\mathcal{C}$, then the set of “feasible directions” is intuitively the set of all directions that point “inward” from $x_{\ast }$. As we shall see, this is the set of tangent vectors.

Tangent vectors

At first blush, we consider defining tangent vectors at $x\in \mathcal{C}$ as directions $v$ such that $x+\eta d\in \mathcal{C}$ for all small enough step sizes $\eta$. Although this definition works well for $\cC$ defined by linear constraints, it is too restrictive for $\cC$ with curved boundaries. For example, if $\mathcal{C}$ is curve in ${\mathbf{R}}^2$, then it may not be possible to move in any direction and remain in $\mathcal{C}$.

Tangent vectors: A vector $v\in {\mathbf{R}}^d$ is tangent to $\mathcal{C}$ at $x\in \mathcal{C}$ iff there are sequences $(x_n)\subset \mathcal{C}$, $(x_n)\to x$ and $({\eta }_n)\searrow 0$ such that

$\frac{1}{{\eta }_n}(x_n-x)\to v$ or $x_n-x={\eta }_{n}v+o({\eta }_n)$.

Intuitively, $(x_n)$ traces out a curve passing thru $x$, and the line segment $x+\eta v$ is tangent to this curve. Compared to the initial (overly restrictive) definition of tangent vector, this definition adds a $o({\eta }_n)$ fudge factor.

We note that any direction $v$ such that $x+\eta v\in \mathcal{C}$ for all small enough $\eta$ is a tangent vector. Indeed, let ${\eta }_n$ be a sequence of small enough step sizes that converges to zero and $x_n\triangleq x+{\eta }_{n}v$. The assumption $x+\eta v\in \mathcal{C}$ for all small enough $\eta$ ensures $x_n$ is in $\mathcal{C}$. We have $x_n-x={\eta }_{n}v$.

We also note that this definition of tangent vector is coincides with the tangent space of a smooth manifold. Recall the tangent space of a smooth manifold $\mathcal{M}$ at $x\in \mathcal{M}$ consists of the derivatives (at $x$) of all smooth curves in $\mathcal{M}$ passing thru $x$. Let $\gamma :[-\delta ,\delta ]\to \mathcal{C}$ be a curve in $\mathcal{C}$ such that $x=\gamma (0)$. To see that $\dot{\gamma }(0)$ is a tangent vector, let ${\eta }_n\searrow 0$ and $x_n\triangleq \gamma ({\eta }_n)$. We have

where we used the definition of the derivative in the second step.

Finally, we claim that the set of all tangent vectors at $x\in \mathcal{C}$ is a closed cone called the tangent cone $T_{\mathcal{C}}(x)$. Recall a subset of ${\mathbf{R}}^d$ is a cone iff it is closed under non-negative scalar multiplication: if $x\in \mathcal{C}$, then $\alpha x\in \mathcal{C}$ for any $\alpha \ge 0$. The proof of this claim is elementary, and we leave the details as an exercise to the reader.

Optimality conditions for the general optimization problem

The normal vectors at a point $x\in \mathcal{C}$ are the vectors that make an obtuse angle with all tangent vectors: $⟨u,v⟩\le 0$ for all $v\in T_{\mathcal{C}}(x)$. It is not hard to check that the set of all normal vectors at a point is a closed convex cone. We note that the tangent cone of a non-convex set may not the convex, but the normal cone is generally convex.

Optimality conditions for the general optimization problem. If $x_{\ast }$ is a local minimum, then $-\partial f_0(x_{\ast })\in N_{\mathcal{C}}(x_{\ast })$. This is equivalent to

To see this, let $v\in T_{\mathcal{C}}(x_{\ast })$ be an arbitrary tangent vector. There are $(x_n)\in \mathcal{C}$, $x_n\to x$ and ${\eta }_n\searrow 0$ such that $\frac{1}{{\eta }_n}(x_n-x_{\ast })\to v$. We have

where the first step is the (local) optimality of $x_{\ast }$, the second step is the smoothness of continuously differentiable functions, and the third step is the definition of tangent vector. We divide both sides by ${\eta }_n$ and take limits to obtain

This optimality condition is intuitive: if $x_{\ast }$ is a local minimum, then there is no direction $v$ that is (i) tangent to the feasible set and (ii) a (strict) descent direction.

Optimality conditions for convex problems. The main results here are

1. $T_{\mathcal{C}}(x)=\mathrm{cone}(\mathcal{C}-x_{\ast })$, where $\mathrm{cone}$ is the conic hull;
2. $N_{\mathcal{C}}(x)=\{u\in {\mathbf{R}}^d\mid ⟨u,x^{\prime }-x⟩\le 0\text{ for all }{x}^{\prime }\in \mathcal{C}\}$;
3. The optimality condition $-\partial f_0(x_{\ast })\in N_{\mathcal{C}}(x_{\ast })$ is necessary and sufficient.

At a high-level, the KKT conditions are an instance of the (necessary) optimality condition for the general optimization problem to non-linear optimization problems in standard form. To keep things simple, we consider a non-linear optimization with only inequality constraints:

Tangent vectors of optimization problems in “standard” form

To keep things simple, we consider a non-linear optimization with only inequality constraints:

Let $\mathcal{C}$ be the feasible set of the preceding optimization problem:

At first blush, we guess that the tangent cone at $x\in \mathcal{C}$ is

where $\mathcal{A}\triangleq \{i\in [m]\mid f_i(x)=0\}$ is the set of indicies of the active constraints at $x$. This guess is motivated by the observation that we must have $⟨\partial f_i(x),v⟩\le 0⟩$ for all $i\in \mathcal{A}$ or moving in the direction $v$ will violate an active inequality constraint. Unfortunately, this guess is not restrictive enough: there are pathological cases in which there are $v$’s that satisfy the preceding guess, but are not tangent vectors.

Consider the set $\mathcal{C}\triangleq \{x\in {\mathbf{R}}^2\mid \frac{1}{2}\Vert x+e_1{\Vert }_2^2\le \frac{1}{2},\frac{1}{2}\Vert x-e_1{\Vert }_2^2\le \frac{1}{2}\}$, where $e_1\triangleq (1,0)$. This is the intersection of two disks of radius 1: one centered at $e_1$ and another centered at $-e_1$. The two disks only intersect at the origin. Thus $\mathcal{C}=\{0\}$, and $T_{\mathcal{C}}(0)=\{0\}$. On the other hand, the preceding guess is

To rule out such pathological cases, we impose constraint qualification (CQ). The standard CQ that we impose in this class is Slater’s CQ, but there are many alternatives.

The KKT conditions

Recall the optimality condition of the general optimization problem: if $x_{\ast }$ is a local minimum, then $⟨\partial f_0(x_{\ast }),v⟩\ge 0$ for all $v\in T_{\mathcal{C}}(x_{\ast })$. In light of the preceding characterization of $T_{\mathcal{C}}(x_{\ast })$, this is equivalent to there is no $v\in {\mathbf{R}}^d$ such that

Consider the $v$ in the preceding system of inequalities as (the normal vector) of a hyperplane thru the origin. The optimality condition has a geometric interpretation: there is no hyperplane (thru the origin) that separates $-\partial f_0(x_{\ast })$ from $\{\partial f_i(x_{\ast }){\}}_{i\in \mathcal{A}}$. This implies $\partial f_0(x_{\ast })$ is in the conic hull of $\{\partial f_i(x_{\ast }){\}}_{i\in \mathcal{A}}$: i.e. there is $\lambda \in {\mathbf{R}}_{+}^m$ such that

This is almost the stationarity condition in the KKT conditions. We pad $\lambda$ with zero entries for the constraints that are inactive to get

to get the stationarity condition. The complementary slackness and dual feasibility conditions follows from the construction of $\lambda$. Finally, the primal feasibility condition is a consequence of the fact that $x_{\ast }$ is a local minimum (hence it’s feasible).

Posted on February 17, 2025 from Ann Arbor, MI.