.md .pdf

repository open issue

Contents

9.5. Constrained Optimization I

In this section, we focus on objective functions of type $f:{\mathbb{R}}^n\to \mathbb{R}$ which are convex and differentiable. Our goal is to minimize $f$ over a convex set $C\subseteq \mathrm{dom}f$.

We also concern ourselves with functions of type $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ where $\mathbb{V}$ is a Euclidean space and $f$ is Fréchet differentiable over some open set $C\subseteq \mathrm{dom}f$. For those results which concern with Fréchet differentiable functions, we request the readers to revise the concepts of Gateaux and Fréchet differentiability in Differentiation in Banach Spaces.

Main references for this section are [5, 10].

9.5.1. Stationary Points

We first look at functions which are differentiable over a convex set. Here, we don’t require that the function itself be convex. Thus, we may not characterize the global optimality of a point. However, we can still characterize the local optimality of a point.

In Definition 7.6, we defined stationary points for a real valued function as points where the gradient vanishes; i.e. $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$.

In this section, we wish to restrict the domain of feasible points to a convex set $C$ and consider the problem

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C\end{array}$$

where $f$ is differentiable over the convex set $C$.

We now introduce the notion of stationary points for the given optimization problem of minimizing $f$ over $C$.

Definition 9.21 (Stationary point for an optimization problem)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a real valued function which is differentiable over a convex set $C$.

Then, $\mathbf{a}\in C$ is called a stationary point of the problem of minimizing $f$ over $C$ if

$$\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})\ge 0\mathrm{\forall }\mathbf{x}\in C.$$

If $C={\mathbb{R}}^n$, then the condition will reduce to $\mathrm{\nabla }f(\mathbf{a})=\mathbf{0}$.

Theorem 9.45 (Local minimum points are stationary points)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a real valued function which is differentiable over a convex set $C$. Consider the optimization problem

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C.\end{array}$$

If $\mathbf{a}\in C$ is a local minimum, then $\mathbf{a}$ must be a stationary point.

Proof. Let $\mathbf{a}$ be a local minimum and for contradiction assume that it is not a stationary point.

1. Then, there exists $\mathbf{x}\in C$ such that $\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})<0$.

2. Let $t\in [0,1]$ be a parameter.

3. Let ${\mathbf{z}}_t=t\mathbf{x}+(1-t)\mathbf{a}$.

4. Since $C$ is convex, hence ${\mathbf{z}}_t\in C$.

5. Differentiating $f({\mathbf{z}}_t)$ w.r.t. $t$ at $t=0$, we obtain

   $${\frac{d}{dt}f({\mathbf{z}}_t)|}_{t=0}=\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})<0.$$

6. Thus, for small enough $t$, $f({\mathbf{z}}_t)<f(\mathbf{a})$.

7. This contradicts the hypothesis that $\mathbf{a}$ is a local minimum.

8. Thus, all local minimum points must be stationary points.

Example 9.6 (Unconstrained minimization)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a real valued function which is differentiable. Consider the unconstrained optimization problem

$$\text{minimize }f(\mathbf{x}).$$

In this case, the feasible set is $C={\mathbb{R}}^n$.

1. If $\mathbf{a}$ is a stationary point for this problem, then

   $$\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})\ge 0\mathrm{\forall }\mathbf{x}\in {\mathbb{R}}^n.$$

2. In particular, if we choose $\mathbf{x}=\mathbf{a}-\mathrm{\nabla }f(\mathbf{a})$, we get

   $$\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})=\mathrm{\nabla }f(\mathbf{a}{)}^T(-\mathrm{\nabla }f(\mathbf{a}))=-\Vert \mathrm{\nabla }f(\mathbf{a}){\Vert }^2\ge 0.$$

3. This is true only if $\mathrm{\nabla }f(\mathbf{a})=\mathbf{0}$.

4. Thus, for unconstrained minimization, the gradient vanishes at stationary points.

Theorem 9.46 (Stationary point as an orthogonal projection)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a real valued function which is differentiable over a convex set $C$. Consider the optimization problem

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C.\end{array}$$

Let $s>0$. Then $\mathbf{a}\in C$ is a stationary point of the optimization problem if and only if

$$\mathbf{a}=P_C(\mathbf{a}-s\mathrm{\nabla }f(\mathbf{a})).$$

Proof. Recall from Theorem 9.7 that $\mathbf{z}\in C$ is the projection of $\mathbf{x}$ if and only if

$$⟨\mathbf{y}-\mathbf{z},\mathbf{x}-\mathbf{z}⟩\le 0\mathrm{\forall }\mathbf{y}\in C.$$

1. Replace $\mathbf{z}=\mathbf{a}$ and $\mathbf{x}=\mathbf{a}-s\mathrm{\nabla }f(\mathbf{a})$. We get

   $$\begin{array}{rl}& ⟨\mathbf{y}-\mathbf{a},\mathbf{a}-s\mathrm{\nabla }f(\mathbf{a})-\mathbf{a}⟩\le 0\mathrm{\forall }\mathbf{y}\in C\\ & ⟺s⟨\mathbf{y}-\mathbf{a},\mathrm{\nabla }f(\mathbf{a})⟩\ge 0\mathrm{\forall }\mathbf{y}\in C\\ & ⟺\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{y}-\mathbf{a})\ge 0\mathrm{\forall }\mathbf{y}\in C.\end{array}$$

2. But this is the same condition as the definition for a stationary point.

9.5.2. First Order Optimality Criteria

We now pay our attention to the case where $f$ is convex as well as differentiable. In this case, a point is a global optimal point if and only if it is a stationary point.

Theorem 9.47 (Optimality criterion for differentiable objective function)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a differentiable convex function. Let $C\subseteq \mathrm{dom}f$ be a convex set. Consider the minimization problem

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C.\end{array}$$

Then, $\mathbf{x}\in C$ is an optimal point if and only if

(9.8)$$\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})\ge 0\mathrm{\forall }\mathbf{y}\in C.$$

In other words, $\mathbf{x}$ is optimal if and only if it is a stationary point.

Proof. By Theorem 8.98

$$f(\mathbf{y})\ge f(\mathbf{x})+\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})$$

for every $\mathbf{x},\mathbf{y}\in \mathrm{dom}f$.

Assume that some $\mathbf{x}\in C$ satisfies the optimality criterion in (9.8).

1. Let $\mathbf{y}\in C$.

2. Then, by differentiability

   $$f(\mathbf{y})\ge f(\mathbf{x})+\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x}).$$

3. By hypothesis $\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})\ge 0$.

4. Thus, $f(\mathbf{y})\ge f(\mathbf{x})$.

5. Since this is true for every $\mathbf{y}\in C$, hence $\mathbf{x}$ is an optimal point for the minimization problem.

Now for the converse, assume that $\mathbf{x}\in C$ is an optimal point.

1. For contradiction, assume that (9.8) doesn’t hold.

2. Then, there exists $\mathbf{y}\in C$ such that

   $$\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})<0.$$

3. Let $t\in [0,1]$ be a parameter.

4. Let $\mathbf{z}(t)=t\mathbf{y}+(1-t)\mathbf{x}$.

5. Since $C$ is convex, hence $\mathbf{z}(t)\in C$.

6. Differentiating $f(\mathbf{z}(t))$ w.r.t. $t$ at $t=0$, we obtain

   $${\frac{d}{dt}f(\mathbf{z}(t))|}_{t=0}=\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})<0.$$

7. Thus, for small enough $t$, $f(\mathbf{z}(t))<f(\mathbf{x})$.

8. Thus, $\mathbf{x}$ cannot be an optimal point for the minimization problem.

9. This contradicts our hypothesis that $\mathbf{x}$ is an optimal point.

10. Hence, (9.8) must hold for every $\mathbf{y}\in C$.

Theorem 9.48 (Optimality criterion for unconstrained problem with differentiable objective function)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a differentiable convex function. Consider the unconstrained minimization problem

$$\text{minimize }f(\mathbf{x})$$

Then, $\mathbf{x}\in {\mathbb{R}}^n$ is an optimal point if and only if $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$.

Proof. In this case, the set of feasible points is $C=\mathrm{dom}f$.

1. Since $f$ is differentiable, hence $C$ is an open set.

2. By Theorem 9.47, $\mathbf{x}$ is an optimal point if and only if

   $$\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})\ge 0\mathrm{\forall }\mathbf{y}\in C.$$

3. If $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$, then this inequality is satisfied. Hence, $\mathbf{x}$ must be an optimal point.

4. Now, assume that $\mathbf{x}$ is an optimal point.

5. Since $\mathbf{x}\in C$ and $C$ is open, hence there exists a closed ball $B[\mathbf{x},r]\subseteq C$.

6. Let $\mathbf{y}=\mathbf{x}-t\mathrm{\nabla }f(\mathbf{x})$.

7. For sufficiently small $t>0$, $\mathbf{y}\in B[\mathbf{x},r]\subseteq C$.

8. Then,

   $$\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})=\mathrm{\nabla }f(\mathbf{x}{)}^T(-t\mathrm{\nabla }f(\mathbf{x}))=-t\Vert \mathrm{\nabla }f(\mathbf{x}){\Vert }_2^2\ge 0$$

   must hold true for $t>0$.

9. This means that $\Vert \mathrm{\nabla }f(\mathbf{x}){\Vert }_2\le 0$ must be true.

10. Thus $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$ must be true.

9.5.2.1. Nondifferentiability at the Boundary

There are some specific results available for the unconstrained minimization of a convex function $f$ is not differentiable everywhere in its domain. If $\mathrm{dom}f$ is not open, then $f$ may be differentiable at $\mathrm{int}\mathrm{dom}f$ but is not differentiable at the boundary points $(\mathrm{dom}f)\setminus (\mathrm{int}domf)$. The key questions are

1. Under what conditions, the minimizer of $f$ is a point of differentiability.

2. Under what conditions, the minimizer of $f$ may be at a point of nondifferentiability.

Theorem 9.49 (Zero gradient implies minimizer)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ with $S=\mathrm{dom}f$ be a proper convex function which is differentiable over some open set $U\subseteq S$. If $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$ at some $\mathbf{x}\in U$, then $\mathbf{x}$ is one of the minimizers for $f$.

Proof. Recall from Theorem 8.220 that $f$ is differentiable at $\mathbf{x}$ if and only if

$$\partial f(\mathbf{x})=\{\mathrm{\nabla }f(\mathbf{x})\}.$$

1. Assume that $f$ is differentiable at $\mathbf{x}\in U$ and $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$.

2. Then $\mathrm{\nabla }f(\mathbf{x})$ is the one and only subgradient of $f$ at $\mathbf{x}$.

3. Due to subgradient inequality

   $$f(\mathbf{y})\ge f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩\mathrm{\forall }\mathbf{y}\in \mathbb{V}.$$

4. Since $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$, hence

   $$f(\mathbf{y})\ge f(\mathbf{x})\mathrm{\forall }\mathbf{y}\in \mathbb{V}.$$

5. Thus $f$ attains a minimum at $\mathbf{x}$ and $\mathbf{x}$ is one of its minimizers.

Next we consider the special case of the minimization of a convex function $f$ which is differentiable in the interior of its domain but the gradient never vanishes. In this case, if a minimizer for $f$ exists, it must be at the boundary of its domain.

Theorem 9.50 (Minimizers at points of nondifferentiability)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ with $S=\mathrm{dom}f$ be a proper convex function which is differentiable over some open set $U\subseteq S$ and not differentiable over $S\setminus U$. Assume that $f$ attains its minimum value at some $\mathbf{a}\in S$; i.e., a minimizer of $f$ exists. If $\mathrm{\nabla }f(\mathbf{x})\ne \mathbf{0}$ at every $\mathbf{x}\in U$, then the minimizer must be at some point of nondifferentiability. In other words, $\mathbf{a}\in S\setminus U$.

Proof. We are given that there exists a is a minimizer of $f$ and for every $\mathbf{x}\in U$, $\mathrm{\nabla }f(\mathbf{x})\ne \mathbf{0}$.

1. Pick any $\mathbf{x}\in U$.

2. We need to show that $\mathbf{x}$ cannot be a minimizer.

3. For contradiction, assume that $\mathbf{x}$ is a minimizer.

4. By subgradient inequality

   $$f(\mathbf{y})\ge f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩\mathrm{\forall }\mathbf{y}\in \mathbb{V}.$$

5. Since $\mathbf{x}$ is a minimizer, hence we must have

   $$⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩\ge 0\mathrm{\forall }\mathbf{y}\in \mathbb{V}.$$

6. Let $\mathbf{y}=\mathbf{x}-\mathrm{\nabla }f(\mathbf{x})$.

7. Then

   $$⟨\mathbf{y}-\mathbf{x},\mathrm{\nabla }f(\mathbf{x})⟩=⟨-\mathrm{\nabla }f(\mathbf{x}),\mathrm{\nabla }f(\mathbf{x})⟩=-\Vert \mathrm{\nabla }f(\mathbf{x}){\Vert }^2<0.$$

8. This contradicts our assumption that $\mathbf{x}$ is a minimizer.

9. Hence if $\mathbf{a}$ is a minimizer of $f$ then $\mathbf{a}\in S\setminus U$.

We next show how the condition in (9.8) simplifies for specific optimization problem structures.

9.5.2.2. Equality Constraints

Theorem 9.51 (Differentiable objective minimization with equality constraints)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a differentiable convex function with $\mathrm{dom}f={\mathbb{R}}^n$. Consider the minimization problem:

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{A}\mathbf{x}=\mathbf{b}\end{array}$$

where $\mathbf{A}\in {\mathbb{R}}^{p\times n}$ and $\mathbf{b}\in {\mathbb{R}}^p$ represent $p$ linear equality constraints. Assume that the problem is feasible.

Then, $\mathbf{x}$ is an optimal point for the minimization problem if and only if there exists a vector $\mathbf{v}\in {\mathbb{R}}^p$ such that

$$\mathrm{\nabla }f(\mathbf{x})+{\mathbf{A}}^T\mathbf{v}=\mathbf{0}.$$

Proof. The feasible set is given by $C=\{\mathbf{x}|\mathbf{A}\mathbf{x}=\mathbf{b}\}$. We recall from Theorem 9.47, that $\mathbf{x}$ is an optimal point if and only if $\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})\ge 0\mathrm{\forall }\mathbf{y}\in C$.

1. Thus, $\mathbf{x}$ is feasible if and only if $\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})\ge 0$ for every $\mathbf{y}$ satisfying $\mathbf{A}\mathbf{y}=\mathbf{b}$.

2. Since both $\mathbf{x}$ and $\mathbf{y}$ are feasible, hence $\mathbf{A}(\mathbf{y}-\mathbf{x})=\mathbf{0}$.

3. Thus, $\mathbf{z}=\mathbf{y}-\mathbf{x}\in \mathcal{N}(\mathbf{A})$.

4. In fact, $\mathbf{y}\in C$ if and only if $\mathbf{y}=\mathbf{x}+\mathbf{z}$ for some $\mathbf{z}\in \mathcal{N}(\mathbf{A})$.

5. Thus, the optimality criteria reduces to $\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{z}\ge 0$ for every $\mathbf{z}\in \mathcal{N}(\mathbf{A})$.

6. Note that $\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{z}$ is a linear function of $\mathbf{z}$ as $\mathrm{\nabla }f(\mathbf{x})$ is a fixed vector.

7. If a linear function is nonnegative on a subspace, then it must be identically zero on the subspace.

8. Thus, $\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{z}=0$ for every $\mathbf{z}\in \mathcal{N}(\mathbf{A})$.

9. In other words, $\mathbf{x}$ is optimal if and only if $\mathrm{\nabla }f(\mathbf{x})\perp \mathcal{N}(\mathbf{A})$.

10. Recall that $\mathcal{N}(\mathbf{A}{)}^{\perp }=\mathcal{C}({\mathbf{A}}^T)$; i.e., the null space of $\mathbf{A}$ is orthogonal complement of the column space (range) of ${\mathbf{A}}^T$.

11. Thus, $\mathbf{x}$ is optimal if and only if $\mathrm{\nabla }f(\mathbf{x})\in \mathcal{C}({\mathbf{A}}^T)$.

12. In other words, $\mathbf{x}$ is optimal if and only if there exists a vector $\mathbf{v}\in {\mathbb{R}}^p$ such that

    $$\mathrm{\nabla }f(\mathbf{x})+{\mathbf{A}}^T\mathbf{v}=\mathbf{0}.$$

This result is a Lagrange multiplier optimality condition to be discussed in more detail in later sections.

9.5.2.3. Nonnegative Orthant Constraints

Example 9.7 (Differentiable objective minimization over nonnegative orthant)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a differentiable convex function with $\mathrm{dom}f={\mathbb{R}}^n$. Consider the minimization problem:

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}⪰\mathbf{0}.\end{array}$$

1. The feasible set is the nonnegative orthant ${\mathbb{R}}_{+}^n$.

2. $\mathbf{x}$ is optimal if and only if $\mathbf{x}⪰\mathbf{0}$ and $\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})\ge 0$ for every $\mathbf{y}⪰\mathbf{0}$.

3. The term $\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{y}$ is unbounded below on $\mathbf{y}\in {\mathbb{R}}_{+}^n$ unless $\mathrm{\nabla }f(\mathbf{x})\in {\mathbb{R}}_{+}^n$.

4. Thus, $\mathrm{\nabla }f(\mathbf{x})$ must be nonnegative.

5. Then, the minimum value for $\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{y}$ is 0.

6. Consequently, the optimality condition reduces to $-\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{x}\ge 0$ or $\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{x}\le 0$.

7. But $\mathbf{x}⪰\mathbf{0}$ and $\mathrm{\nabla }f(\mathbf{x})⪰\mathbf{0}$.

8. Thus, we must have $\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{x}=0$.`

9. We note that

   $$\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{x}=\sum _{i=1}^n(\mathrm{\nabla }f(\mathbf{x}){)}_i{x}_i.$$

10. Thus, it is a sum of products of nonnegative numbers.

11. So each term in the sum must be 0.

12. Thus, $(\mathrm{\nabla }f(\mathbf{x}){)}_i{x}_i=0$ must hold true for every $i=1,\dots ,n$.

13. Thus, the optimality condition can be rephrased as

    $$\mathbf{x}⪰\mathbf{0}\text{ and }\mathrm{\nabla }f(\mathbf{x})⪰\mathbf{0}\text{ and }(\mathrm{\nabla }f(\mathbf{x}){)}_i{x}_i=0\mathrm{\forall }i=1,\dots ,n.$$

The condition $(\mathrm{\nabla }f(\mathbf{x}){)}_i{x}_i=0$ for every $i$ is known as complementarity. It means that for every $i$ either $x_i$ or $(\mathrm{\nabla }f(\mathbf{x}){)}_i$ or both must be 0. In other words, both $x_i$ and $(\mathrm{\nabla }f(\mathbf{x}){)}_i$ cannot be nonzero at the same time.

Thus, the sparsity patterns of $\mathbf{x}$ and $\mathrm{\nabla }f(\mathbf{x})$ are complementary. In other words,

$$\mathrm{supp}(\mathbf{x})\cap \mathrm{supp}(\mathrm{\nabla }f(\mathbf{x}))=\varnothing$$

where $\mathrm{supp}(\mathbf{x})$ denotes the index set of nonzero entries of $\mathbf{x}$.

9.5.2.4. Unit Sum Set Constraint

Example 9.8 (Minimization over unit sum set)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a differentiable convex function with $\mathrm{dom}f={\mathbb{R}}^n$. Consider the minimization problem:

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & {\mathbf{1}}^T\mathbf{x}=1.\end{array}$$

1. The feasible set is given by

   $$C=\{\mathbf{x}\in {\mathbb{R}}^n|{\mathbf{1}}^T\mathbf{x}=1\}=\{\mathbf{x}\in {\mathbb{R}}^n|\sum _{i=1}^n{x}_i=1\}.$$

2. This set is also known as the unit sum set.

3. A point $\mathbf{a}\in C$ is optimal if and only if

   $$\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})\ge 0\mathrm{\forall }\mathbf{x}\in C.$$

   Let us call this condition (I).

4. This is equivalent to the condition:

   $$\frac{\partial f}{\partial x_1}(\mathbf{a})=\frac{\partial f}{\partial x_2}(\mathbf{a})=\cdots =\frac{\partial f}{\partial x_n}(\mathbf{a}).$$

   Let us call this condition (II).

5. We shall show that (I) and (II) are equivalent.

We first show that (II) implies (I).

1. Assume that some $\mathbf{a}\in C$ satisfies (II) with

   $$\alpha =\frac{\partial f}{\partial x_1}(\mathbf{a})=\frac{\partial f}{\partial x_2}(\mathbf{a})=\cdots =\frac{\partial f}{\partial x_n}(\mathbf{a}).$$

2. Then, for any $\mathbf{x}\in C$,

   $$\begin{array}{rl}\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})& =\sum _{i=1}^n\frac{\partial f}{\partial x_i}(\mathbf{a})(x_i-a_i)\\ & =\alpha \sum _{i=1}^n(x_i-a_i)\\ & =\alpha (\sum _{i=1}^n{x}_i-\sum _{i=1}^n{a}_i)\\ & =\alpha (1-1)=0.\end{array}$$

3. Thus, we see that $\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})\ge 0$ indeed and (I) is satisfied.

Now, assume that (I) is satisfied for some $\mathbf{a}\in C$.

1. For contradiction, assume that $\mathbf{a}$ doesn’t satisfy (II).

2. Then, their exist $i,j\in [1,\dots ,n]$ such that

   $$\frac{\partial f}{\partial x_i}(\mathbf{a})>\frac{\partial f}{\partial x_j}(\mathbf{a}).$$

3. Pick a vector $\mathbf{x}\in C$ with following definition

   $$\begin{array}{r}{x}_k=\{\begin{array}{ll}{a}_k& k\notin \{i,j\}\\ a_k-1& k=i\\ a_k+1& k=j.\end{array}\end{array}$$

4. Note that

   $$\sum _{i=1}^n{x}_k=\sum _{i=1}^n{a}_k=1.$$

   Thus, $\mathbf{x}\in C$ holds.

5. Now,

   $$\begin{array}{rl}\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})& =\sum _{k=1}^n\frac{\partial f}{\partial x_k}(\mathbf{a})(x_k-a_k)\\ \mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})& =\frac{\partial f}{\partial x_i}(\mathbf{a})(x_i-a_i)+\frac{\partial f}{\partial x_j}(\mathbf{a})(x_j-a_j)\\ & =-\frac{\partial f}{\partial x_i}(\mathbf{a})+\frac{\partial f}{\partial x_j}(\mathbf{a})\\ <0.\end{array}$$

6. This violates the hypothesis that (I) holds true.

7. Thus, (II) must be true.

8. Thus, (I) implies (II).

9.5.2.5. Unit Ball Constraint

Example 9.9 (Minimization over unit ball)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a convex function which is differentiable over $B[\mathbf{0},1]$. Consider the minimization problem:

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \Vert \mathbf{x}\Vert \le 1.\end{array}$$

1. The feasible set is given by

   $$C=B[\mathbf{0},1]=\{\mathbf{x}|\Vert \mathbf{x}\Vert \le 1\}.$$

2. A point $\mathbf{a}\in B[\mathbf{0},1]$ is an optimal point if and only if

   $$\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})\ge 0\mathrm{\forall }\mathbf{x}\in B[\mathbf{0},1].$$

3. This is equivalent to saying that

   $$\underset{\Vert \mathbf{x}\Vert \le 1}{inf}(\mathrm{\nabla }f(\mathbf{a}{)}^T\mathbf{x}-\mathrm{\nabla }f(\mathbf{a}{)}^T\mathbf{a})\ge 0.$$

4. Recall from Theorem 7.11 that for any $\mathbf{v}\in {\mathbb{R}}^n$, the optimal value of the problem

   $$inf\{{\mathbf{v}}^T\mathbf{x}|\Vert \mathbf{x}\Vert \le 1\}$$

   is $-\Vert \mathbf{v}\Vert$.

5. Thus,

   $$\underset{\Vert \mathbf{x}\Vert \le 1}{inf}\mathrm{\nabla }f(\mathbf{a}{)}^T\mathbf{x}=-\Vert \mathrm{\nabla }f(\mathbf{a})\Vert .$$

6. Thus, the inequality simplifies to

   $$-\mathrm{\nabla }f(\mathbf{a}{)}^T\mathbf{a}\ge \Vert \mathrm{\nabla }f(\mathbf{a})\Vert .$$

7. At the same time, by Cauchy Schwartz inequality,

   $$-\mathrm{\nabla }f(\mathbf{a}{)}^T\mathbf{a}\le \Vert \mathrm{\nabla }f(\mathbf{a})\Vert \Vert \mathbf{a}\Vert \le \Vert \mathrm{\nabla }f(\mathbf{a})\Vert$$

   since $\mathbf{a}\in B[\mathbf{0},1]$.

8. Thus, the inequality must be an equality, giving us, $\mathbf{a}$ is an optimal point

   $$-\mathrm{\nabla }f(\mathbf{a}{)}^T\mathbf{a}=\Vert \mathrm{\nabla }f(\mathbf{a})\Vert .$$

We now have following possibilities for this condition.

1. If $\mathrm{\nabla }f(\mathbf{a})=\mathbf{0}$, then the condition holds and $\mathbf{a}$ is indeed an optimal point.

2. Otherwise, if $\mathrm{\nabla }f(\mathbf{a})\ne \mathbf{0}$, then $\Vert \mathbf{a}\Vert =1$ must be true.

   1. For contradiction, if we assume that $\Vert \mathbf{a}\Vert <1$.

   2. Then, by Cauchy Schwartz inequality

      $$-\mathrm{\nabla }f(\mathbf{a}{)}^T\mathbf{a}\le \Vert \mathrm{\nabla }f(\mathbf{a})\Vert \Vert \mathbf{a}\Vert <\Vert \mathrm{\nabla }f(\mathbf{a})\Vert ,$$

      a contradiction.

3. Thus, if $\mathrm{\nabla }f(\mathbf{a})\ne \mathbf{0}$, then $\mathbf{a}$ is an optimal point if and only if $\Vert \mathbf{a}\Vert =1$ and

   $$-\mathrm{\nabla }f(\mathbf{a}{)}^T\mathbf{a}=\Vert \mathrm{\nabla }f(\mathbf{a})\Vert =\Vert \mathrm{\nabla }f(\mathbf{a})\Vert \Vert \mathbf{a}\Vert .$$

4. But this is possible only when there exists $t\le 0$ such that

   $$\mathrm{\nabla }f(\mathbf{a})=t\mathbf{a}.$$

5. Thus, if $\mathrm{\nabla }f(\mathbf{a})\ne \mathbf{0}$, then $\mathbf{a}$ is an optimal point if and only if $\Vert \mathbf{a}\Vert =1$ and there exists $t\le 0$ such that $\mathrm{\nabla }f(\mathbf{a})=t\mathbf{a}$.

9.5.3. Descent Directions Method

We first consider the problem of unconstrained minimization of a continuously differentiable function $f$.

Typical iterative algorithms which aim to find the solution $\mathbf{x}$ for the minimization problem start with an initial guess ${\mathbf{x}}_0$ and perform a step of the form

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k+t_k{\mathbf{d}}_k$$

where ${\mathbf{x}}_k$ is the current guess (starting from ${\mathbf{x}}_0$), ${\mathbf{d}}_k$ is a direction in which we move to make the next guess and $t_k$ is a step size in that direction. ${\mathbf{x}}_{k+1}$ is the next guess obtained from current guess. We say that an algorithm has made progress if $f({\mathbf{x}}_{k+1})<f({\mathbf{x}}_k)$.

This brings us to the notion of a descent direction.

Definition 9.22 (Descent direction)

Let $f:\mathbb{V}\to \mathbb{R}$ be a continuously differentiable function over $\mathbb{V}$. A nonzero vector $\mathbf{d}$ is called a descent direction of $f$ at $\mathbf{x}$ if the directional derivative $f^{\prime }(\mathbf{x};\mathbf{d})$ is negative.

In other words,

$$f^{\prime }(\mathbf{x};\mathbf{d})=⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩<0.$$

If the directional derivative is negative, then it is clear that for a small enough step in this direction, the value of $f$ will decrease.

Lemma 9.4 (Descent property of descent direction)

Let $f:\mathbb{V}\to \mathbb{R}$ be a continuously differentiable function over $\mathbb{V}$. Let $\mathbf{x}\in \mathbb{V}$. Assume that $\mathbf{d}$ is a descent direction for $f$. Then, there exists $ϵ>0$ such that

$$f(\mathbf{x}+t\mathbf{d})<f(\mathbf{x})$$

for any $t\in (0,ϵ]$.

Proof. This follows from the negativity of the directional derivative.

1. Recall from Definition 8.70 that

   $$f^{\prime }(\mathbf{x};\mathbf{d})=\underset{t\to 0^{+}}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}.$$

2. Since $\mathbf{d}$ is a descent direction, hence $f^{\prime }(\mathbf{x};\mathbf{d})<0$.

3. Thus,

   $$\underset{t\to 0^{+}}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}<0.$$

4. Thus, there exists $ϵ>0$ such that

   $$\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}<0$$

   for every $t\in (0,ϵ]$.

9.5.3.1. Descent Directions Method

Algorithm 9.1 (The descent directions method)

Initialization

1. Pick ${\mathbf{x}}_0\in \mathbb{V}$ arbitrarily as initial solution.

General iteration: for $k=0,1,2,\dots$, execute the following steps

1. Pick a descent direction ${\mathbf{d}}_k$.

2. Pick a step size $t_k$ satisfying $f(\mathbf{x}+t_k{\mathbf{d}}_k)<f({\mathbf{x}}_k)$.

3. Update: ${\mathbf{x}}_{k+1}\leftarrow {\mathbf{x}}_k+t_k{\mathbf{d}}_k$.

4. Check for convergence: If converged, then STOP.

Return ${\mathbf{x}}_{k+1}$ as the output.

This method is not really an actual algorithm. It can be considered as a template for an actual algorithm. Several aspects of the method need to be carefully chosen to come up with a viable algorithm.

1. How to select the initial point ${\mathbf{x}}_0$?

2. How to choose the descent direction?

3. How to select the step size?

4. How to decide when to stop the iterations (stopping criterion)?

The key result that we establish here is to show that if the step size $t_k$ is sufficient small in the descent direction ${\mathbf{d}}_k$, then there is sufficient decrease in the value of $f$ going from ${\mathbf{x}}_k$ to ${\mathbf{x}}_{k+1}$.

Theorem 9.52 (Sufficient decrease condition for descent direction method)

Let $f$ be a continuously differentiable function over ${\mathbb{R}}^n$. Let $\mathbf{x}\in {\mathbb{R}}^n$. Assume that a nonzero $\mathbf{d}$ is a descent direction for $f$ at $\mathbf{x}$. Let $\alpha \in (0,1)$. Then, there exists $ϵ>0$ such that the inequality

$$f(\mathbf{x})-f(\mathbf{x}+t\mathbf{d})\ge -\alpha t⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩$$

holds for every $t\in [0,ϵ]$.

Proof. We proceed as follows.

1. Since $f$ is continuously differentiable, hence due to Theorem 5.1,

   $$f(\mathbf{x}+t\mathbf{d})=f(\mathbf{x})+t\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}+o(t\Vert \mathbf{d}\Vert ).$$

2. Rearranging the terms and introducing an $\alpha \in (0,1)$, we obtain

   $$f(\mathbf{x})-f(\mathbf{x}+t\mathbf{d})=-\alpha t\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}-(1-\alpha )\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}-o(t\Vert \mathbf{d}\Vert ).$$

3. Since $\mathbf{d}$ is a descent direction of $f$, hence $f(\mathbf{x};\mathbf{d})=\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}<0$.

4. Thus,

   $$\underset{t\to 0^{+}}{lim}\frac{(1-\alpha )\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}+o(t\Vert \mathbf{d}\Vert )}{t}=(1-\alpha )\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}<0.$$

5. Hence, there exists $ϵ>0$ such that for every $t\in [0,ϵ]$,

   $$(1-\alpha )\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}+o(t\Vert \mathbf{d}\Vert <0.$$

6. Thus, from the previous equation:

   $$f(\mathbf{x})-f(\mathbf{x}+t\mathbf{d})\ge -\alpha t\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}$$

   for every $t\in [0,ϵ]$.

9.5.3.2. Step Size Selection

Following are common methods for step size selection. Each method has has advantages as well as drawbacks.

1. Constant step size

2. Exact line search

3. Backtracking

Constant step size uses $t_k=\overline{t}$ for every iteration.

• A large step size might cause algorithm to take non-decreasing steps.

• The algorithm may never converge with a large step size.

• A small constant step size may lead to very slow convergence.

Exact line search solves the minimization problem

$$\text{ minimize }f\text{ along the ray }{\mathbf{x}}_k+t{\mathbf{d}}_k.$$

The optimization variable is the step size parameter $t\in {\mathbb{R}}_{+}$. The solution is the value $t_k\ge 0$.

• Minimizing $f$ along the ray may not be straight-forward.

• Any closed form or algorithmic solution for the exact line search may not be available.

Backtracking is a compromise between these two approaches.

1. Input parameters $s>0$, $\alpha \in (0,1)$, $\beta \in (0,1)$.

2. Initialize $t_k=s$.

3. While

   $$f({\mathbf{x}}_k)-f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)<-\alpha t_k\mathrm{\nabla }f({\mathbf{x}}_k{)}^T\mathbf{d}$$

   1. Set $t_k\leftarrow \beta t_k$.

   2. Continue.

4. Return step size $t_k$.

Essentially, we are reducing the step size by a factor $\beta$ iteratively till $f$ shows sufficient decrease as stipulated by Theorem 9.52.

• There is no exact line search.

• Does find a good enough step size satisfying the sufficient decrease condition.

• Involves multiple evaluations of $f$.

• $s$ should be chosen carefully.

9.5.4. Gradient Method

The gradient method is a descent direction method in which the descent direction is always chosen to be the negative of the gradient at the current point (solution).

$${\mathbf{d}}_k=-\mathrm{\nabla }f({\mathbf{x}}_k).$$

Lemma 9.5 (Negative of gradient is a descent direction)

Let $f$ be a continuously differentiable function over an open set $S$. At any point $\mathbf{x}\in S$, the negative of the gradient $\mathbf{d}=-\mathrm{\nabla }f(\mathbf{x})$ is a descent direction whenever $\mathrm{\nabla }f(\mathbf{x})\ne \mathbf{0}$.

Proof. We just need to compute the directional derivative.

$$f^{\prime }(\mathbf{x};\mathbf{d})=⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩=⟨-\mathrm{\nabla }f(\mathbf{x}),\mathrm{\nabla }f(\mathbf{x})⟩=-\Vert \mathrm{\nabla }f(\mathbf{x}){\Vert }^2<0.$$

The last strict inequality is valid since $\mathrm{\nabla }f(\mathbf{x})\ne \mathbf{0}$.

9.5.5. Gradient Projection Method

In this subsection, we present a method to solve the optimization problem

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C\end{array}$$

where $C$ is a convex set and $f$ is differentiable over $C$.

Recall from Theorem 9.46, that $\mathbf{a}$ is a stationary point for the problem of minimizing $f$ over a convex set $C$ if and only if

$$\mathbf{a}=P_C(\mathbf{a}-s\mathrm{\nabla }f(\mathbf{a})).$$

This stationarity condition is the basis for the gradient projection method presented below.

Algorithm 9.2 (The gradient projection method)

Inputs

1. $ϵ>0$ - tolerance parameter

Initialization

1. Pick ${\mathbf{x}}_0\in C$ arbitrarily.

General iteration: for $k=0,1,2,\dots$, execute the following steps

1. Pick a step size $t_k$ by a line search procedure.

2. Update: ${\mathbf{x}}_{k+1}\leftarrow P_C({\mathbf{x}}_k-t_k\mathrm{\nabla }f({\mathbf{x}}_k))$.

3. Check for convergence: If $\Vert {\mathbf{x}}_{k+1}-{\mathbf{x}}_k\Vert \le ϵ$, then STOP.

Return ${\mathbf{x}}_{k+1}$ as the output.

In the case of unconstrained minimization:

1. $C={\mathbb{R}}^n$

2. $P_C({\mathbf{x}}_k-t_k\mathrm{\nabla }f({\mathbf{x}}_k))={\mathbf{x}}_k-t_k\mathrm{\nabla }f({\mathbf{x}}_k)$.

3. ${\mathbf{x}}_{k+1}={\mathbf{x}}_k-t_k\mathrm{\nabla }f({\mathbf{x}}_k)$.

4. We see that gradient projection reduces to gradient descent.

Another way to look at the algorithm is:

1. ${\mathbf{y}}_{k+1}={\mathbf{x}}_k-t_k\mathrm{\nabla }f({\mathbf{x}}_k)$ computes the next candidate solution assuming no constraints.

2. ${\mathbf{x}}_{k+1}=P_C({\mathbf{y}}_{k+1})$ step projects the next candidate solution back to the feasible set $C$.

3. Thus, we have a gradient step followed by a projection step.

9.5.5.1. Convergence

If we can establish conditions under which each iteration of the gradient projection algorithm leads to sufficient decrease in the value of the objective function, then we can guarantee that the algorithm will converge in a finite number of steps.

Lemma 9.6 (Sufficient decrease lemma for constrained problems)

Consider the optimization problem:

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C.\end{array}$$

Assume that $C$ is a nonempty closed convex set, $f$ is continuously differentiable over $C$, and $\mathrm{\nabla }f$ is Lipschitz continuous with a constant $L$ over $C$, Then, for any $\mathbf{x}\in C$, and $t\in (0,\frac{2}{L})$, the following inequality holds.

$$f(\mathbf{x})-f(\mathbf{y})\ge t(1-\frac{Lt}{2}){\Vert \frac{1}{t}(\mathbf{x}-\mathbf{y})\Vert }^2.$$

where $\mathbf{y}=P_C(\mathbf{x}-t\mathrm{\nabla }f(\mathbf{x}))$.

Proof.

previous

9.4. Basic Duality

next

9.6. Linear Constraints