3.3 Constrained optimization

In constrained optimization, we look to minimize or maximize an objective function only over a set of inputs $\Omega \subseteq X$ that can be written in the following form:

In words, $\Omega$ is a set described by set of equalities and inequalities on $x$ . The constraints $g_i\left(x\right)=0$ are said to be equality constraints , and the constraints $h_i\left(x\right)\le 0$ are said to be inequality constraints .

Example 1 Minimize $f\left(x\right)$ subject to $x_3=0$ , $1\le x_1\le 2$ and $1\le x_2\le 2$ , drawn on [link] .

In this optimization problem, the feasible set $\Omega$ can be written in terms of one equality constraint, $g\left(x\right)=x_3$ , and four inequality constraints:

Definition 1 The points $x\in \Omega$ are called feasible points , and the set $\Omega$ is called the feasible set .

In the sequel, we will assume that $f$ , $g_i$ , $h_i$ are continuous and Fréchet-differentiable (continuous gradients).

We will first consider problems where the feasible set $\Omega$ can be expressed in terms of equality constraints only.

Tangent space

For a given feasible point $x_0\in \Omega$ , the tangent space gives us the set of directions in which one can move from $x_0$ while still staying within the feasible set $\Omega$ . The two examples below show tangent spaces in the cases where the set $\Omega$ correspond to a curve in ${\mathbb{R}}^2$ and a nonlinear manifold in ${\mathbb{R}}^3$ .

The tangent space at $x_0$ can be expressed formally in terms of the derivatives of the equality constraints.

Definition 2 The tangent space to the feasible set $\Omega$ with equality constraints $g_1,...,g_n$ at a feasible point $x_0\in \Omega$ is given by

Requiring all the directional derivatives of the equality constraints to be zero in the direction of the tangent $d-x_0$ guarantees that the value of the equality constraints remains at zero, therefore guaranteeing that $d$ remains a feasible point, i.e., $d\in \Omega$ .

Definition 3 A point $x_0$ satisfying the constraints $g_1\left(x_0\right)=0,g_2\left(x_0\right)=0,...,g_n\left(x_0\right)=0$ is said to be a regular point if the $n$ linear functionals $\delta g_1(x_0;h),\delta g_2(x_0;h),...,\delta g_n(x_0;h)$ (i.e., the derivatives of the equality constraints) are linearly independent on $h$ .

Theorem 1 If $x_0$ is an extremum of $f\left(x\right)$ subject to constraints $g_1\left(x_0\right)=0,g_2\left(x_0\right)=0,...,g_n\left(x_0\right)=0$ and $x_0$ is a regular point of ${\left\{g_i\right\}}_{i=1}^n$ then for any $h\in X$ such that $\delta g_i(x;h)=0$ for all $i=1,2,...,n$ , we must have $\delta f(x_0;h)=0$ .

One can rewrite this theorem in terms of gradients as: if $⟨\nabla g_i\left(x_0\right),h⟩=0$ , then $⟨\nabla f\left(x_0\right),h⟩=0$ . More intuition can be obtained by defining the translated tangent space at $x_0$ as follows:

Thus, the theorem above can be written as: if $h\in {\tilde{T}}_{\Omega }\left(x_0\right)$ , then $⟨\nabla f\left(x_0\right),h⟩=0$ . In words, we expect for the derivative of the objective function $f$ at the constrained extremum $x_0$ to be zero-valued in the directions in which we can move from $x_0$ and remain in the feasible set $\Omega$ — that is, in the directions $h\in {\tilde{T}}_{\Omega }\left(x_0\right)$ . Thus, we can write that the constrained optimum $x_0$ must obey $\nabla f\left(x_0\right)\perp \tilde{T}\left(x_0\right)$ , which implies $\nabla f\left(x_0\right)\perp T_{\Omega }\left(x_0\right)$ .