10.2. Projection on Convex Sets

We will assume $\mathbb{V}$ to be real $n$-dimensional vector space space with an inner product $⟨\cdot ,\cdot ⟩$ , the induced norm $\Vert \cdot \Vert$ and corresponding dual norm $\Vert \cdot {\Vert }_{\ast }$ for the dual space ${\mathbb{V}}^{\ast }$.

We are interested in mapping a point $\mathbf{x}$ to the nearest point in a set $C$. In general, this problem may have zero, one or multiple solutions. However, in the special case where $C$ is a nonempty, closed and convex set, then there is exactly one such point in $C$ which is nearest to a given point $\mathbf{x}$. This nearest point is called the projection of $\mathbf{x}$ on to $C$.

Main references for this section are [6, 9].

10.2.1. Projection Theorem

Theorem 10.6 (Projection theorem)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. For every $\mathbf{x}\in \mathbb{V}$, there exists a unique vector that minimizes $\Vert \mathbf{z}-\mathbf{x}\Vert$ over all $\mathbf{z}\in C$. This vector is called the projection of $\mathbf{x}$ on $C$.

Proof. We fix some $\mathbf{x}\in \mathbb{V}$ and choose an element $\mathbf{w}\in C$.

1. Consider the function

   $$g(\mathbf{z})=\frac{1}{2}\Vert \mathbf{z}-\mathbf{x}{\Vert }^2.$$

2. Minimizing $\Vert \mathbf{z}-\mathbf{x}\Vert$ over all $C$ is equivalent to minimizing $g(\mathbf{z})$ over the set

   $$D=\{\mathbf{z}\in C|\Vert \mathbf{z}-\mathbf{x}\Vert \le \Vert \mathbf{w}-\mathbf{x}\Vert \}.$$

3. We note that $D$ is a compact set and $g$ is a l.s.c., closed and coercive function.

4. By Weierstrass’ theorem Corollary 8.2, the set of minimizers for $g$ is nonempty and compact.

We now show that the minimizer is unique.

1. $g$ is a strictly convex function because its Hessian matrix is identity matrix which is positive definite.

2. Hence, the minimizer is unique due to Theorem 10.2.

10.2.2. Orthogonal Projection

Definition 10.6 (Orthogonal Projection Mapping)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. The orthogonal projection mapping $P_C:\mathbb{V}\to \mathbb{V}$ is defined by:

$$P_C(\mathbf{x})\triangleq \underset{\mathbf{y}\in C}{\arg \min }\Vert \mathbf{y}-\mathbf{x}\Vert \mathrm{\forall }\mathbf{x}\in \mathbb{V}.$$

This mapping is well defined since the projection is unique for a nonempty, closed and convex set $C$ due to Theorem 10.6.

The vector $P_C(\mathbf{x})$ is called the projection of $\mathbf{x}$ on the set $C$.

10.2.3. Characterization

Theorem 10.7 (Orthogonal projection characterization)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. For every vector $\mathbf{x}\in \mathbb{V}$, a vector $\mathbf{z}\in C$ is its projection if and only if

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

This result is also known as the second projection theorem [6].

Proof. Assume that for some $\mathbf{z}\in C$, $⟨\mathbf{y}-\mathbf{z},\mathbf{x}-\mathbf{z}⟩\le 0\mathrm{\forall }\mathbf{y}\in C$ holds true.

1. For any $\mathbf{y}\in C$

   $$\begin{array}{rl}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2& =\Vert (\mathbf{y}-\mathbf{z})-(\mathbf{x}-\mathbf{z}){\Vert }^2\\ & =\Vert \mathbf{y}-\mathbf{z}{\Vert }^2+\Vert \mathbf{z}-\mathbf{x}{\Vert }^2-2⟨\mathbf{y}-\mathbf{z},\mathbf{x}-\mathbf{z}⟩\\ & \ge \Vert \mathbf{z}-\mathbf{x}{\Vert }^2-2⟨\mathbf{y}-\mathbf{z},\mathbf{x}-\mathbf{z}⟩.\end{array}$$

2. Thus,

   $$\Vert \mathbf{y}-\mathbf{x}{\Vert }^2\ge \Vert \mathbf{z}-\mathbf{x}{\Vert }^2\mathrm{\forall }\mathbf{y}\in C.$$

3. Thus, $\mathbf{z}$ is indeed the projection of $\mathbf{x}$ on $C$.

Conversely, assume that $\mathbf{z}$ is the projection of $\mathbf{x}$ on $C$.

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

2. For any $t\ge 0$, define ${\mathbf{y}}_t=t\mathbf{y}+(1-t)\mathbf{z}$.

3. Then, we have

   $$\begin{array}{rl}\Vert \mathbf{x}-{\mathbf{y}}_t{\Vert }^2& =\Vert t\mathbf{x}+(1-t)\mathbf{x}+-t\mathbf{y}-(1-t)\mathbf{z}{\Vert }^2\\ & =\Vert t(\mathbf{x}-\mathbf{y})+(1-t)(\mathbf{x}-\mathbf{z}){\Vert }^2\\ & =t^2\Vert \mathbf{x}-\mathbf{y}{\Vert }^2+(1-t{)}^2\Vert \mathbf{x}-\mathbf{z}{\Vert }^2+2t(1-t)⟨\mathbf{x}-\mathbf{y},\mathbf{x}-\mathbf{z}⟩.\end{array}$$

4. Viewing $\Vert \mathbf{x}-{\mathbf{y}}_t{\Vert }^2$ as a function of $t$ and differentiating w.r.t. $t$, we have

   $$\begin{array}{rl}{\frac{d}{dt}\Vert \mathbf{x}-{\mathbf{y}}_t{\Vert }^2|}_{t=0}& =-2\Vert \mathbf{x}-\mathbf{z}{\Vert }^2+2⟨\mathbf{x}-\mathbf{y},\mathbf{x}-\mathbf{z}⟩\\ & =-2⟨\mathbf{x}-\mathbf{z},\mathbf{x}-\mathbf{z}⟩+2⟨\mathbf{x}-\mathbf{y},\mathbf{x}-\mathbf{z}⟩\\ & =-2⟨\mathbf{y}-\mathbf{z},\mathbf{x}-\mathbf{z}⟩.\end{array}$$

5. Since $t=0$ minimizes $\Vert \mathbf{x}-{\mathbf{y}}_t{\Vert }^2$ over $t\in [0,1]$, we must have

   $${\frac{d}{dt}\Vert \mathbf{x}-{\mathbf{y}}_t{\Vert }^2|}_{t=0}\ge 0.$$

6. Thus, we require that

   $$⟨\mathbf{y}-\mathbf{z},\mathbf{x}-\mathbf{z}⟩\le 0$$

   must hold true for every $\mathbf{y}\in C$.

Following is an alternative proof based on results from Constrained Optimization I. This proof is specific to the case where $\mathbb{V}={\mathbb{R}}^n$.

Proof. Define a function $f:{\mathbb{R}}^n\to \mathbb{R}$ as

$$f(\mathbf{y})=\Vert \mathbf{y}-\mathbf{x}{\Vert }^2.$$

Then, the projection problem can be cast as an optimization problem

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

Note that the gradient of $f$ is given by

$$\mathrm{\nabla }f(\mathbf{y})=\mathrm{\nabla }⟨\mathbf{y}-\mathbf{x},\mathbf{y}-\mathbf{x}⟩=\mathrm{\nabla }(⟨\mathbf{y},\mathbf{y}⟩-2⟨\mathbf{y},\mathbf{x}⟩+⟨\mathbf{x},\mathbf{x}⟩)=2(\mathbf{y}-\mathbf{x}).$$

By Theorem 10.47, $\mathbf{z}$ is an optimal solution if and only if

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

In other words

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

We can simplify this as

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

Theorem 10.8 (Orthogonal projection on an affine subspace)

Let $C$ be an affine subspace of $\mathbb{V}$. Let $S$ be the linear subspace parallel to $C$. For every vector $\mathbf{x}\in \mathbb{V}$, a vector $\mathbf{z}\in C$ is its projection if and only if

$$\mathbf{x}-\mathbf{z}\in S^{\perp }.$$

Proof. Since $C$ is an affine subspace of $\mathbb{V}$, hence $C$ is nonempty, convex and closed (as $\mathbb{V}$ is finite dimensional).

1. By Theorem 10.7, $\mathbf{z}$ is the projection of $\mathbf{x}$ on $C$ if and only if for every $\mathbf{y}\in C$, we have

   $$⟨\mathbf{y}-\mathbf{z},\mathbf{x}-\mathbf{z}⟩\le 0.$$

2. But $\mathbf{y}\in C$ if and only if $\mathbf{y}-\mathbf{z}\in S$.

3. Hence the condition is equivalent to

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

4. But then, it must be an equality since $\mathbf{w}$ and $-\mathbf{w}$ both belong to $S$. Thus, we have

   $$⟨\mathbf{w},\mathbf{x}-\mathbf{z}⟩=0\mathrm{\forall }\mathbf{w}\in S.$$

5. In other words, $\mathbf{x}-\mathbf{z}\in S^{\perp }$.

10.2.4. Distance Function

Recall that the distance of a point $\mathbf{x}\in \mathbb{V}$ from a set $C$ is defined as

$$d_C(\mathbf{x})\triangleq \underset{\mathbf{y}\in C}{inf}\Vert \mathbf{x}-\mathbf{y}\Vert .$$

Theorem 10.9 (Distance function for nonempty, closed and convex set)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. Then the function $d_C:\mathbb{V}\to \mathbb{R}$ defining the distance of a point $\mathbf{x}\in \mathbb{V}$ from the set $C$ satisfies

$$d_C(\mathbf{x})=\Vert \mathbf{x}-P_C(\mathbf{x})\Vert .$$

Proof. By Theorem 10.6, there exists a unique point $P_C(\mathbf{x})$ which minimizes the distance between $\mathbf{x}$ and $C$. Hence

$$d_C(\mathbf{x})=\Vert \mathbf{x}-P_C(\mathbf{x})\Vert$$

must hold true.

Theorem 10.10 (Distance function for nonempty, closed and convex set is convex)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. Let $d_C:\mathbb{V}\to \mathbb{R}$ be the distance to the set $C$ function as defined in Theorem 10.9. Then, $d_C$ is convex.

Proof. Assume, for contradiction, that $d_C$ is not convex.

1. Then, there exist $\mathbf{x},\mathbf{y}\in \mathbb{V}$ and $t\in (0,1)$ such that

   $$d_C(t\mathbf{x}+(1-t)\mathbf{y})>t{d}_C(\mathbf{x})+(1-t)d_C(\mathbf{y}).$$

2. Let $\mathbf{u}=P_C(\mathbf{x})$ and $\mathbf{v}=P_C(\mathbf{y})$. By definition, $\mathbf{u},\mathbf{v}\in C$.

3. Then,

   $$t{d}_C(\mathbf{x})+(1-t)d_C(\mathbf{y})=t\Vert \mathbf{u}-\mathbf{x}\Vert +(1-t)\Vert \mathbf{v}-\mathbf{y}\Vert .$$

4. Since $C$ is convex, hence, $t\mathbf{u}+(1-t)\mathbf{v}\in C$.

5. Since, $d_C(t\mathbf{x}+(1-t)\mathbf{y})$ minimizes the distance of $C$ from the point $t\mathbf{x}+(1-t)\mathbf{y}$, hence

   $$\Vert t\mathbf{u}+(1-t)\mathbf{v}-t\mathbf{x}-(1-t)\mathbf{y}\Vert \ge d_C(t\mathbf{x}+(1-t)\mathbf{y}).$$

6. Rewriting,

   $$d_C(t\mathbf{x}+(1-t)\mathbf{y})\le \Vert t(\mathbf{u}-\mathbf{x})+(1-t)(\mathbf{v}-\mathbf{y})\Vert \le t\Vert \mathbf{u}-\mathbf{x}\Vert +(1-t)\Vert \mathbf{v}-\mathbf{y}\Vert$$

   due to triangle inequality.

7. But, this leads to the contradiction

   $$t\Vert \mathbf{u}-\mathbf{x}\Vert +(1-t)\Vert \mathbf{v}-\mathbf{y}\Vert <d_C(t\mathbf{x}+(1-t)\mathbf{y})\le t\Vert \mathbf{u}-\mathbf{x}\Vert +(1-t)\Vert \mathbf{v}-\mathbf{y}\Vert .$$

8. Hence, $d_C$ must be convex.

10.2.5. Nonexpansiveness

Definition 10.7 (Nonexpansiveness property)

Let $\mathbb{V}$ be a normed linear space. An operator $T:\mathbb{V}\to \mathbb{V}$ is called nonexpansive if

$$\Vert T(\mathbf{x})-T(\mathbf{y})\Vert \le \Vert \mathbf{y}-\mathbf{x}\Vert \mathrm{\forall }\mathbf{x},\mathbf{y}\in \mathbb{V}.$$

In other words, the distance between mapped points in $\mathbb{V}$ is always less than or equal to the distance between original points in $\mathbb{V}$.

Theorem 10.11 (Nonexpansive operators are Lipschitz continuous)

Let $\mathbb{V}$ a be normed linear space. A nonexpansive operator $T:\mathbb{V}\to \mathbb{V}$ is Lipschitz continuous. Hence, it is uniformly continuous.

Proof. Recall from Definition 3.45 that if $T$ is a Lipschitz map, then there exists $L>0$ such that

$$\Vert T(\mathbf{x})-T(\mathbf{y})\Vert \le L\Vert \mathbf{x}-\mathbf{y}\Vert$$

for every $\mathbf{x},\mathbf{y}\in \mathbb{V}$.

For a nonexpansive operator, such $L=1$. This $T$ is indeed Lipschitz continuous. By Theorem 3.57, every Lipschitz continuous function is uniformly continuous.

Definition 10.8 (Firm nonexpansiveness property)

Let $\mathbb{V}$ be a real inner product space. An operator $T:\mathbb{V}\to \mathbb{V}$ is called firmly nonexpansive if

$$⟨T(\mathbf{x})-T(\mathbf{y}),\mathbf{x}-\mathbf{y}⟩\ge \Vert T(\mathbf{x})-T(\mathbf{y}){\Vert }^2$$

holds true for every $\mathbf{x},\mathbf{y}\in \mathbb{V}$.

Theorem 10.12 (A firmly nonexpansive operator is nonexpansive)

Let $\mathbb{V}$ be a real inner product space. Let $T:\mathbb{V}\to \mathbb{V}$ be a firmly nonexpansive operator. Then, $T$ is nonexpansive.

Proof. For every $\mathbf{x},\mathbf{y}\in \mathbb{V}$, we have

$$\Vert T(\mathbf{x})-T(\mathbf{y}){\Vert }^2\le ⟨T(\mathbf{x})-T(\mathbf{y}),\mathbf{x}-\mathbf{y}⟩.$$

Applying Cauchy Schwartz inequality on R.H.S., we get

$$\Vert T(\mathbf{x})-T(\mathbf{y}){\Vert }^2\le \Vert T(\mathbf{x})-T(\mathbf{y})\Vert \Vert \mathbf{x}-\mathbf{y}\Vert .$$

Canceling terms, we get:

$$\Vert T(\mathbf{x})-T(\mathbf{y})\Vert \le \Vert \mathbf{x}-\mathbf{y}\Vert$$

which is the nonexpansive property.

Theorem 10.13 (Orthogonal projection is nonexpansive)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. Let $P_C:\mathbb{V}\to \mathbb{V}$ be the orthogonal projection operator as defined in Definition 10.6 is nonexpansive (and therefore continuous).

In other words,

$$\Vert P_C(\mathbf{x})-P_C(\mathbf{y})\Vert \le \Vert \mathbf{x}-\mathbf{y}\Vert \mathrm{\forall }\mathbf{x},\mathbf{y}\in \mathbb{V}.$$

Proof. Let $\mathbf{x},\mathbf{y}\in \mathbb{V}$.

1. By Theorem 10.7,

   $$⟨\mathbf{w}-P_C(\mathbf{x}),\mathbf{x}-P_C(\mathbf{x})⟩\le 0\mathrm{\forall }\mathbf{w}\in C.$$

2. In particular $P_C(\mathbf{y})\in C$. Hence,

   $$⟨P_C(\mathbf{y})-P_C(\mathbf{x}),\mathbf{x}-P_C(\mathbf{x})⟩\le 0.$$

3. Similarly, starting with $P_C(\mathbf{x})$, we obtain

   $$⟨P_C(\mathbf{x})-P_C(\mathbf{y}),\mathbf{y}-P_C(\mathbf{y})⟩\le 0.$$

4. Adding these two inequalities, we obtain

   $$⟨P_C(\mathbf{y})-P_C(\mathbf{x}),\mathbf{x}-P_C(\mathbf{x})-\mathbf{y}+P_C(\mathbf{y})⟩\le 0.$$

5. By rearranging the terms, we get

$$⟨P_C(\mathbf{y})-P_C(\mathbf{x}),P_C(\mathbf{y})-P_C(\mathbf{x})⟩\le ⟨P_C(\mathbf{y})-P_C(\mathbf{x}),\mathbf{y}-\mathbf{x}⟩.$$

1. Applying the Cauchy Schwartz inequality on the R.H.S., we obtain

$$\Vert P_C(\mathbf{y})-P_C(\mathbf{x}){\Vert }^2\le \Vert P_C(\mathbf{y})-P_C(\mathbf{x})\Vert \Vert \mathbf{y}-\mathbf{x}\Vert .$$

1. Thus, $P_C$ is nonexpansive.

2. Since $P_C$ is nonexpansive, hence $P_C$ is continuous also.

Theorem 10.14 (Orthogonal projection is firmly nonexpansive)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. Let $P_C:\mathbb{V}\to \mathbb{V}$ be the orthogonal projection operator as defined in Definition 10.6. Then $P_C$ is a firmly nonexpansive operator.

In other words,

$$⟨P_C(\mathbf{x})-P_C(\mathbf{y}),\mathbf{x}-\mathbf{y}⟩\ge \Vert P_C(\mathbf{x})-P_C(\mathbf{y}){\Vert }^2$$

holds true for every $\mathbf{x},\mathbf{y}\in \mathbb{V}$.

Proof. Recall from Theorem 10.7 that for any $\mathbf{u}\in \mathbb{V}$ and $\mathbf{v}\in C$

$$⟨\mathbf{v}-P_C(\mathbf{u}),\mathbf{u}-P_C(\mathbf{u})⟩\le 0.$$

1. Substituting $\mathbf{u}=\mathbf{x}$ and $\mathbf{v}=P_C(\mathbf{y})$, we obtain

   $$⟨P_C(\mathbf{y})-P_C(\mathbf{x}),\mathbf{x}-P_C(\mathbf{x})⟩\le 0.$$

2. Substituting $\mathbf{u}=\mathbf{y}$ and $\mathbf{v}=P_C(\mathbf{x})$, we obtain

   $$⟨P_C(\mathbf{x})-P_C(\mathbf{y}),\mathbf{y}-P_C(\mathbf{y})⟩\le 0.$$

3. Adding the two inequalities gives us

   $$\begin{array}{rl}& ⟨P_C(\mathbf{x})-P_C(\mathbf{y}),\mathbf{y}-P_C(\mathbf{y})-\mathbf{x}+P_C(\mathbf{x})⟩\le 0\\ & ⟺⟨P_C(\mathbf{x})-P_C(\mathbf{y}),(\mathbf{y}-\mathbf{x})+(P_C(\mathbf{x})-P_C(\mathbf{y}))⟩\le 0\\ & ⟺\Vert P_C(\mathbf{x})-P_C(\mathbf{y}){\Vert }^2\le ⟨P_C(\mathbf{x})-P_C(\mathbf{y}),\mathbf{x}-\mathbf{y}⟩\end{array}$$

   as desired.

10.2.6. Squared Distance Function

Definition 10.9 (Squared distance function to a nonempty set)

Let $C$ be a nonempty subset of $\mathbb{V}$. The squared distance to set $C$ function denoted as ${\phi }_C:\mathbb{V}\to \mathbb{R}$ is defined as:

$${\phi }_C(\mathbf{x})\triangleq \frac{1}{2}{d}_C^2(\mathbf{x}).$$

We also define ${\psi }_C:\mathbb{V}\to \mathbb{R}$ as:

$${\psi }_C(\mathbf{x})\triangleq \frac{1}{2}(\Vert \mathbf{x}{\Vert }^2-d_C^2(\mathbf{x})).$$

Theorem 10.15 (Expression for ${\psi }_C$)

Let $C$ be a nonempty subset of $\mathbb{V}$. Then, the function ${\psi }_C$ as defined in Definition 10.9 is given by

$${\psi }_C(\mathbf{x})=\underset{\mathbf{y}\in C}{sup}[⟨\mathbf{y},\mathbf{x}⟩-\frac{1}{2}\Vert \mathbf{y}{\Vert }^2].$$

Proof. We proceed as follows.

1. Expanding on the definition of $d_C^2$

   $$\begin{array}{rl}{d}_C^2(\mathbf{x})& =\underset{\mathbf{y}\in C}{inf}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2\\ & =\underset{\mathbf{y}\in C}{inf}⟨\mathbf{x}-\mathbf{y},\mathbf{x}-\mathbf{y}⟩\\ & =\underset{\mathbf{y}\in C}{inf}(\Vert \mathbf{x}{\Vert }^2-2⟨\mathbf{x},\mathbf{y}⟩+\Vert \mathbf{y}{\Vert }^2)\\ & =\underset{\mathbf{y}\in C}{inf}(\Vert \mathbf{x}{\Vert }^2-(2⟨\mathbf{x},\mathbf{y}⟩-\Vert \mathbf{y}{\Vert }^2))\\ & =\Vert \mathbf{x}{\Vert }^2-\underset{\mathbf{y}\in C}{sup}(2⟨\mathbf{x},\mathbf{y}⟩-\Vert \mathbf{y}{\Vert }^2).\end{array}$$

2. Thus,

   $$\Vert \mathbf{x}{\Vert }^2-d_C^2(\mathbf{x})=\underset{\mathbf{y}\in C}{sup}(2⟨\mathbf{x},\mathbf{y}⟩-\Vert \mathbf{y}{\Vert }^2).$$

3. Thus,

   $${\psi }_C(\mathbf{x})=\frac{1}{2}(\Vert \mathbf{x}{\Vert }^2-d_C^2(\mathbf{x}))=\underset{\mathbf{y}\in C}{sup}[⟨\mathbf{x},\mathbf{y}⟩-\frac{1}{2}\Vert \mathbf{y}{\Vert }^2].$$

Theorem 10.16 (${\psi }_C$ is convex)

Let $C$ be a nonempty subset of $\mathbb{V}$. Then, the function ${\psi }_C$ as defined in Definition 10.9 is convex.

Beauty of this result is the fact that ${\psi }_C$ is convex irrespective of whether $C$ is convex or not.

Proof. We proceed as follows.

1. For every $\mathbf{y}\in C$, the function $g_y:\mathbb{V}\to \mathbb{R}$, given by

   $$g_y(\mathbf{x})=⟨\mathbf{y},\mathbf{x}⟩-\frac{1}{2}\Vert \mathbf{y}{\Vert }^2$$

   is an affine function.

2. $g_y$ is convex for every $\mathbf{y}\in C$ due to Theorem 9.68.

3. Now,

   $${\psi }_C(\mathbf{y})=sup\mathbf{y}\in C{g}_y.$$

4. Thus, ${\psi }_C$ is a pointwise supremum of convex functions.

5. Thus, by Theorem 9.114, ${\psi }_C$ is convex.

Theorem 10.17 (Squared distance function for nonempty, closed and convex sets)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. Then, the squared distance function ${\phi }_C$ is given by

$${\phi }_C(\mathbf{x})=\frac{1}{2}\Vert \mathbf{x}-P_C(\mathbf{x}){\Vert }^2.$$

This follows directly from Theorem 10.10.

10.2.7. Gradients and Subgradients

Theorem 10.18 (Gradient of the squared distance function)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. The gradient of the squared distance function ${\phi }_C$ as defined in Definition 10.9 at $\mathbf{x}\in \mathbb{V}$ is given by:

$$\mathrm{\nabla }{\phi }_C(\mathbf{x})=\mathbf{x}-P_C(\mathbf{x})\mathrm{\forall }\mathbf{x}\in \mathbb{V}.$$

Proof. We proceed as follows.

1. Let $\mathbf{x}\in \mathbb{V}$.

2. Let ${\mathbf{z}}_x=\mathbf{x}-P_C(\mathbf{x})$.

3. Consider the function

   $$g_x(\mathbf{d})={\phi }_C(\mathbf{x}+\mathbf{d})-{\phi }_C(\mathbf{x})-⟨\mathbf{d},{\mathbf{z}}_x⟩.$$

4. If

   $$\underset{\mathbf{d}\to \mathbf{0}}{lim}\frac{g_x(\mathbf{d})}{\Vert \mathbf{d}\Vert }=0$$

   then ${\mathbf{z}}_x$ is indeed the gradient of ${\phi }_C$ at $\mathbf{x}$.

5. By definition of orthogonal projection, for any $\mathbf{d}\in \mathbb{V}$,

   $$\Vert \mathbf{x}+\mathbf{d}-P_C(\mathbf{x}+\mathbf{d}){\Vert }^2\le \Vert \mathbf{x}+\mathbf{d}-P_C(\mathbf{x}){\Vert }^2$$

   as $P_C(\mathbf{x}+\mathbf{d})$ is the nearest point to $\mathbf{x}+\mathbf{d}$ in $C$. $P_C(\mathbf{x})$ is just another point in $C$.

6. Thus, for any $\mathbf{d}\in \mathbb{V}$

   $$\begin{array}{rl}{g}_x(\mathbf{d})& ={\phi }_C(\mathbf{x}+\mathbf{d})-{\phi }_C(\mathbf{x})-⟨\mathbf{d},{\mathbf{z}}_x⟩\\ & =\frac{1}{2}\Vert \mathbf{x}+\mathbf{d}-P_C(\mathbf{x}+\mathbf{d}){\Vert }^2-\frac{1}{2}\Vert \mathbf{x}-P_C(\mathbf{x}){\Vert }^2-⟨\mathbf{d},{\mathbf{z}}_x⟩\\ & \le \frac{1}{2}\Vert \mathbf{x}+\mathbf{d}-P_C(\mathbf{x}){\Vert }^2-\frac{1}{2}\Vert \mathbf{x}-P_C(\mathbf{x}){\Vert }^2-⟨\mathbf{d},{\mathbf{z}}_x⟩.\end{array}$$

7. Recall that for a norm induced by the inner product

   $$\Vert \mathbf{a}+\mathbf{b}{\Vert }^2=⟨\mathbf{a}+\mathbf{b},\mathbf{a}+\mathbf{b}⟩=\Vert \mathbf{a}{\Vert }^2+2⟨\mathbf{a},\mathbf{b}⟩+\Vert \mathbf{b}{\Vert }^2.$$

8. Thus,

   $$\begin{array}{rl}\Vert \mathbf{x}+\mathbf{d}-P_C(\mathbf{x}){\Vert }^2& =\Vert \mathbf{d}+(\mathbf{x}-P_C(\mathbf{x})){\Vert }^2\\ & =\Vert \mathbf{d}{\Vert }^2+\Vert \mathbf{x}-P_C(\mathbf{x}){\Vert }^2+2⟨\mathbf{d},\mathbf{x}-P_C(\mathbf{x})⟩.\end{array}$$

9. Putting it back and simplifying, we obtain

   $$g_x(\mathbf{d})\le \frac{1}{2}\Vert \mathbf{d}{\Vert }^2+⟨\mathbf{d},\mathbf{x}-P_C(\mathbf{x})⟩-⟨\mathbf{d},{\mathbf{z}}_x⟩=\frac{1}{2}\Vert \mathbf{d}{\Vert }^2.$$

10. Proceeding similarly, we also have

    $$g_x(-\mathbf{d})\le \frac{1}{2}\Vert \mathbf{d}{\Vert }^2.$$

11. Since ${\phi }_C$ is convex, hence $g_x$ is also convex.

12. Thus,

    $$0=g_x(\mathbf{0})=g_x(\frac{1}{2}\mathbf{d}+\frac{1}{2}(-\mathbf{d}))\le \frac{1}{2}{g}_x(\mathbf{d})+\frac{1}{2}{g}_x(-\mathbf{d}).$$

13. Thus,

    $$g_x(\mathbf{d})\ge -g_x(-\mathbf{d})\ge -\frac{1}{2}\Vert \mathbf{d}{\Vert }^2.$$

14. Combining, we have

    $$-\frac{1}{2}\Vert \mathbf{d}{\Vert }^2\le g_x(\mathbf{d})\le \frac{1}{2}\Vert \mathbf{d}{\Vert }^2.$$

15. Or, in terms of absolute values.

    $$|g_x(\mathbf{d})|\le \frac{1}{2}\Vert \mathbf{d}{\Vert }^2.$$

16. Then,

    $$\frac{|g_x(\mathbf{d})|}{\Vert \mathbf{d}\Vert }\le \frac{1}{2}\Vert \mathbf{d}\Vert .$$

17. Thus,

    $$\underset{\mathbf{d}\to \mathbf{0}}{lim}\frac{g_x(\mathbf{d})}{\Vert \mathbf{d}\Vert }=0$$

18. Thus, ${\mathbf{z}}_x=\mathbf{x}-P_C(\mathbf{x})$ is indeed the gradient of ${\phi }_C$ at $\mathbf{x}$.

Theorem 10.19 (Gradient of ${\psi }_C$.)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. The gradient of the function ${\psi }_C$ as defined in Definition 10.9 at $\mathbf{x}\in \mathbb{V}$ is given by:

$$\mathrm{\nabla }{\psi }_C(\mathbf{x})=P_C(\mathbf{x})\mathrm{\forall }\mathbf{x}\in \mathbb{V}.$$

Proof. We have

$${\psi }_C(\mathbf{x})=\frac{1}{2}(\Vert \mathbf{x}{\Vert }^2-d_C^2(\mathbf{x}))=\frac{1}{2}(\Vert \mathbf{x}{\Vert }^2-{\phi }_C(\mathbf{x}).$$

Hence,

$$\mathrm{\nabla }{\psi }_C(\mathbf{x})=\mathbf{x}-\mathrm{\nabla }{\phi }_C(\mathbf{x})=\mathbf{x}-(\mathbf{x}-P_C(\mathbf{x}))=P_C(\mathbf{x}).$$

Remark 10.5 (Distance function and square distance function relation)

We note that ${\phi }_C=g\circ d_C$ where $g(t)=\frac{1}{2}[t{]}_{+}^2$.

$g$ is a nonincreasing real-valued convex differentiable function. We also note that

$$g^{\prime }(t)=2[t{]}_{+}.$$

Theorem 10.20 (Subdifferential of the distance function)

Let $C$ be a nonempty, closed and convex subset of $\mathbb{V}$. The subdifferential of the distance function $d_C$ is given by

$$\begin{array}{r}\partial d_C(\mathbf{x})=\{\begin{array}{ll}\left\{\frac{\mathbf{x}-P_C(\mathbf{x})}{d_C(\mathbf{x})}\right\},& \mathbf{x}\notin C\\ N_C(\mathbf{x})\cap B[\mathbf{0},1],& \mathbf{x}\in C\end{array}.\end{array}$$

$N_C(\mathbf{x})$ denotes the normal cone of all vectors normal to the set $C$ at a point $\mathbf{x}\in C$.

Since $\partial d_C$ is a singleton for $\mathbf{x}\notin C$, hence $d_C$ is differentiable at $\mathbf{x}\notin C$.

Proof. We can get the subdifferentials for $d_C$ by applying the chain rule.

1. Recall that ${\phi }_C=g\circ d_C$ where $g(t)=\frac{1}{2}[t{]}_{+}^2$.

2. Thus, by subdifferential chain rule (Theorem 9.229):

   $$\partial {\phi }_C(\mathbf{x})=g^{\prime }(d_C(\mathbf{x}))\partial d_C(\mathbf{x})=[d_C(\mathbf{x}){]}_{+}\partial d_C(\mathbf{x})=d_C(\mathbf{x})\partial d_C(\mathbf{x}).$$

   We used the fact that $d_C$ is nonnegative.

3. Since ${\phi }_C$ is differentiable, hence $\partial {\phi }_C(\mathbf{x})=\{\mathbf{x}-P_C(\mathbf{x})\}$.

4. If $\mathbf{x}\notin C$, then, $d_C(\mathbf{x})>0$.

5. Thus, for $\mathbf{x}\notin C$

   $$\partial d_C(\mathbf{x})=\left\{\frac{\mathbf{x}-P_C(\mathbf{x})}{d_C(\mathbf{x})}\right\}.$$

6. For $\mathbf{x}\in C$, $d_C(\mathbf{x})=0$.

7. We need to show that $\partial d_C(\mathbf{x})=N_C(\mathbf{x})\cap B[\mathbf{0},1]$ in this case.

8. Consider any $\mathbf{d}\in \partial d_C(\mathbf{x})$.

9. Then, by subgradient inequality

   $$d_C(\mathbf{y})\ge d_C(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathbf{d}⟩=⟨\mathbf{y}-\mathbf{x},\mathbf{d}⟩\mathrm{\forall }\mathbf{y}\in \mathbb{V}$$

   since $d_C(\mathbf{x})=0$.

10. Then, in particular, for any $\mathbf{y}\in C$

    $$d_C(\mathbf{y})=0\ge ⟨\mathbf{y}-\mathbf{x},\mathbf{d}⟩.$$

11. Thus, $\mathbf{d}\in N_C(\mathbf{x})$.

10.2.8. Conjugates

Theorem 10.21 (Conjugate of norm squared plus indicator)

Let $C$ be a nonempty subset of $\mathbb{V}$. Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be given by:

$$f(\mathbf{x})=\frac{1}{2}\Vert \mathbf{x}{\Vert }^2+{\delta }_C(\mathbf{x}).$$

Then, its conjugate is given by:

$$f^{\ast }(\mathbf{y})=\frac{1}{2}\Vert \mathbf{y}{\Vert }^2-\frac{1}{2}{d}_C^2(\mathbf{y})={\psi }_C(\mathbf{y}).$$

Further, if $C$ is nonempty, closed and convex, then $f^{\ast \ast }=f$. In other words, ${\psi }_C^{\ast }=f$.

Proof. Recall from Definition 9.78 that

$$f^{\ast }(\mathbf{y})=\underset{\mathbf{x}\in \mathbb{V}}{sup}\{⟨\mathbf{x},\mathbf{y}⟩-f(\mathbf{x})\}\mathrm{\forall }\mathbf{y}\in {\mathbb{V}}^{\ast }.$$

Expanding, we obtain

$$\begin{array}{rl}\underset{\mathbf{x}\in \mathbb{V}}{sup}\{⟨\mathbf{x},\mathbf{y}⟩-f(\mathbf{x})\}& =\underset{\mathbf{x}\in \mathbb{V}}{sup}\{⟨\mathbf{x},\mathbf{y}⟩-\frac{1}{2}\Vert \mathbf{x}{\Vert }^2-{\delta }_C(\mathbf{x})\}\\ & =\underset{\mathbf{x}\in C}{sup}\{⟨\mathbf{x},\mathbf{y}⟩-\frac{1}{2}\Vert \mathbf{x}{\Vert }^2\}\\ & ={\psi }_C(\mathbf{y}).\end{array}$$

The last result is due to Theorem 10.15.

If $C$ is nonempty, closed and convex, then, $f$ is proper closed and convex. Then, due to Theorem 9.242, the biconjugate of $f$ is $f$ itself.

10.2.9. Smoothness

Recall from Definition 9.80 that a function $f:\mathbb{V}\to \mathbb{R}$ is $L$-smooth if

$$\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }\le L\Vert \mathbf{x}-\mathbf{y}\Vert \mathrm{\forall }\mathbf{x},\mathbf{y}\in \mathbb{V}.$$

Since the norm in this section is induced by the inner product, hence it is self dual.

Thus, the smoothness criteria becomes:

$$\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}){\Vert }_{\ast }\le L\Vert \mathbf{x}-\mathbf{y}\Vert \mathrm{\forall }\mathbf{x},\mathbf{y}\in \mathbb{V}.$$

Theorem 10.22 (Smoothness of the squared distance function)

The squared distance function ${\phi }_C$ is 1-smooth.

Proof. Recall the definition of ${\phi }_C$ from Definition 10.9.

1. By Theorem 10.18,

   $$\mathrm{\nabla }{\phi }_C(\mathbf{x})=\mathbf{x}-P_C(\mathbf{x}).$$

2. Hence,

   $$\begin{array}{rl}& \Vert \mathrm{\nabla }{\phi }_C(\mathbf{x})-\mathrm{\nabla }{\phi }_C(\mathbf{y}){\Vert }^2\\ & =\Vert \mathbf{x}-P_C(\mathbf{x})-\mathbf{y}+P_C(\mathbf{y}){\Vert }^2\\ & =\Vert (\mathbf{x}-\mathbf{y})-(P_C(\mathbf{x})-P_C(\mathbf{y})){\Vert }^2\\ & =\Vert \mathbf{x}-\mathbf{y}{\Vert }^2-2⟨P_C(\mathbf{x})-P_C(\mathbf{y}),\mathbf{x}-\mathbf{y}⟩+\Vert P_C(\mathbf{x})-P_C(\mathbf{y}){\Vert }^2\\ & \le \Vert \mathbf{x}-\mathbf{y}{\Vert }^2-2\Vert P_C(\mathbf{x})-P_C(\mathbf{y}){\Vert }^2+\Vert P_C(\mathbf{x})-P_C(\mathbf{y}){\Vert }^2& \text{ firm nonexpansiveness }\\ & =\Vert \mathbf{x}-\mathbf{y}{\Vert }^2-\Vert P_C(\mathbf{x})-P_C(\mathbf{y}){\Vert }^2\\ & \le \Vert \mathbf{x}-\mathbf{y}{\Vert }^2.\end{array}$$

3. Thus,

   $$\Vert \mathrm{\nabla }{\phi }_C(\mathbf{x})-\mathrm{\nabla }{\phi }_C(\mathbf{y})\Vert \le \Vert \mathbf{x}-\mathbf{y}\Vert .$$

4. Thus, ${\phi }_C$ is 1-smooth.

Theorem 10.23 (Smoothness of the ${\psi }_C$ function)

The function ${\psi }_C$ is 1-smooth.

Proof. We recall from Theorem 10.19 that $\mathrm{\nabla }{\psi }_C(\mathbf{x})=P_C(\mathbf{x})$.

Hence,

$$\Vert \mathrm{\nabla }{\psi }_C(\mathbf{x})-\mathrm{\nabla }{\psi }_C(\mathbf{y})\Vert =\Vert P_C(\mathbf{x})-P_C(\mathbf{y})\Vert \le \Vert \mathbf{x}-\mathbf{y}\Vert$$

due to the nonexpansiveness property (Theorem 10.13).

10.2.10. POCS Problems

In this section, we present some example optimization problems which can be converted into an equivalent projection on a convex set problem.

10.2.10.1. Equality Constrained Quadratic Programming

Quadratic programming problems are discussed extensively in Quadratic Programming. Here we discuss a specific form of minimizing a quadratic function subject to linear equality constraints.

Example 10.1 (Equality constrained quadratic programming)

We consider the quadratic programming problem

$$\begin{array}{rlrl}& \text{minimize }& & \frac{1}{2}\Vert \mathbf{x}{\Vert }^2+{\mathbf{c}}^T\mathbf{x}\\ & \text{subject to }& & \mathbf{A}\mathbf{x}=\mathbf{0}.\end{array}$$

where

1. $\mathbf{x}\in {\mathbb{R}}^n$ is the optimization variable.

2. $\mathbf{c}\in {\mathbb{R}}^n$ is a given vector.

3. $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ is an $m\times n$ matrix of rank $m$. Assume that $m<n$.

We proceed towards converting this problem into a projection on a convex set problem as follows.

1. By adding a constant term $\frac{1}{2}\Vert \mathbf{c}{\Vert }^2$ to the objective function, we obtain an equivalent problem.

   $$\begin{array}{rlrl}& \text{minimize }& & \frac{1}{2}\Vert \mathbf{c}+\mathbf{x}{\Vert }^2\\ & \text{subject to }& & \mathbf{A}\mathbf{x}=\mathbf{0}.\end{array}$$

2. The set $C=\{\mathbf{x}|\mathbf{A}\mathbf{x}=\mathbf{0}\}$ is the null space of the matrix $\mathbf{A}$ which is linear subspace, hence a nonempty, closed and convex set.

3. Minimizing $\frac{1}{2}\Vert \mathbf{c}+\mathbf{x}{\Vert }^2$ is equivalent to minimizing $\Vert (-\mathbf{c})-\mathbf{x}\Vert$ subject to $\mathbf{x}\in C$.

4. $\Vert (-\mathbf{c})-\mathbf{x}\Vert$ is $d(-\mathbf{c},\mathbf{x})$, the distance between $-\mathbf{c}$ and a point $\mathbf{x}$.

5. Thus, we are minimizing the distance of the point $-\mathbf{c}$ among $\mathbf{x}\in C$.

6. This is nothing but the distance of $-\mathbf{c}$ from the set $C$.

7. Since, $C$ is nonempty, close and convex, hence, there is a unique ${\mathbf{x}}^{\ast }$ which minimizes the distance due to the projection theorem.

8. Thus, the solution is the projection of the vector $-\mathbf{c}$ on the subspace $C$.

9. By Theorem 10.8, ${\mathbf{x}}^{\ast }$ is the unique projection of $-\mathbf{c}$ on $C$ if and only if $-\mathbf{c}-{\mathbf{x}}^{\ast }\in C^{\perp }$.

10. In other words, $$⟨\mathbf{c}+{\mathbf{x}}^{\ast },\mathbf{x}⟩=0\mathrm{\forall }\mathbf{x}\in C.$$

11. A closed form solution to this problem does exist given by

    $${\mathbf{x}}^{\ast }=-(\mathbf{I}-{\mathbf{A}}^T(\mathbf{A}{\mathbf{A}}^T{)}^{-1}bA)\mathbf{c}.$$

12. It is indeed the unique solution to this quadratic programming problem.