Moreau's decomposition theorem

From Wikimization

Revision as of 04:07, 11 July 2009 by Nemeth (Talk | contribs)
Jump to: navigation, search

Contents

Projection mapping

Let LaTeX: (\mathcal H,\langle\cdot,\cdot\rangle) be a Hilbert space and LaTeX: \mathcal C a closed convex set in LaTeX: \mathcal H. The projection mapping LaTeX: P_{\mathcal C} onto LaTeX: \mathcal C is the mapping LaTeX: P_{\mathcal C}:\mathcal H\to\mathcal H defined by LaTeX: P_{\mathcal C}(x)\in\mathcal C and

LaTeX: \|x-P_{\mathcal C}(x)\|=\min\{\|x-y\|\mid y\in\mathcal C\}.

Characterization of the projection

Let LaTeX: (\mathcal H,\langle\cdot,\cdot\rangle) be a Hilbert space, LaTeX: \mathcal C a closed convex set in LaTeX: \mathcal H,\,u\in\mathcal H and LaTeX: v\in\mathcal C. Then, LaTeX: v=P_{\mathcal C}(u) if and only if LaTeX: \langle u-v,w-v\rangle\leq0 for all LaTeX: w\in\mathcal C.

Proof

Suppose that LaTeX: v=P_{\mathcal C}u and let LaTeX: w\in\mathcal C be arbitrary. By using the convexity of LaTeX: \mathcal C, it follows that LaTeX: (1-t)v+tw\in\mathcal C, for all LaTeX: t\in (0,1). Then, by using the definition of the projection, we have

LaTeX: 
\|u-v\|^2\leq\|u-[(1-t)v+tw]\|^2=\|u-v-t(w-v)\|^2=\|u-v\|^2-2t\langle u-v,w-v\rangle+t^2\|w-v\|^2
.

Hence,

LaTeX: \langle u-v,w-v\rangle\leq\frac t2\|w-v\|^2.

By tending with LaTeX: t to LaTeX: 0, we get LaTeX: \langle u-v,w-v\rangle\leq0.

Conversely, suppose that LaTeX: \langle u-v,w-v\rangle\leq0, for all LaTeX: w\in\mathcal C. Then,

LaTeX: \|u-w\|^2=\|u-v-(w-v)\|^2=\|u-v\|^2-2\langle u-v,w-v\rangle+\|w-v\|^2\geq \|u-v\|^2,

for all LaTeX: w\in\mathcal C. Hence, by using the definition of the projection, we get LaTeX: v=P_{\mathcal C}u.

Moreau's theorem

Moreau's theorem is a fundamental result characterizing projections onto closed convex cones in Hilbert spaces. Recall that a convex cone in a vector space is a set which is invariant under the addition of vectors and multiplication of vectors by positive scalars (see more at Convex cone (Wikipedia) or for finite dimension at Convex cone (Wikimization)).

Theorem (Moreau) Let LaTeX: \mathcal K be a closed convex cone in the Hilbert space LaTeX: (\mathcal H,\langle\cdot,\cdot\rangle) and LaTeX: \mathcal K^\circ its polar cone; that is, the closed convex cone defined by LaTeX: K^\circ=\{a\in\mathcal H\mid\langle a,b\rangle\leq0,\,\forall b\in\mathcal K\} (for finite dimension see more at Dual cone and polar cone; see also Extended Farkas lemma). For LaTeX: x,y,z\in\mathcal H the following statements are equivalent:

  1. LaTeX: z=x+y,\,x\in\mathcal K,\,y\in\mathcal K^\circ and LaTeX: \langle x,y\rangle=0
  2. LaTeX: x=P_{\mathcal K}z and LaTeX: y=P_{\mathcal K^\circ}z

Proof of Moreau's theorem

  • 1LaTeX: \Rightarrow2: For all LaTeX: p\in K we have

    LaTeX: \langle z-x,p-x\rangle=\langle y,p-x\rangle=\langle y,p\rangle\leq0.

    Then, by the characterization of the projection, it follows that LaTeX: x=P_{\mathcal K}z. Similarly, for all LaTeX: q\in K^\circ we have

    LaTeX: \langle z-y,q-y\rangle=\langle x,q-y\rangle=\langle x,q\rangle\leq0

    and thus LaTeX: y=P_{\mathcal K^\circ}z.
  • 2LaTeX: \Rightarrow1: Let LaTeX: x=P_{\mathcal K}z. By the characterization of the projection we have LaTeX: \langle z-x,p-x\rangle\leq0, for all LaTeX: p\in\mathcal K. In particular, if LaTeX: p=0, then LaTeX: \langle z-x,x\rangle\geq0 and if LaTeX: p=2x, then LaTeX: \langle z-x,x\rangle\leq0. Thus, LaTeX: \langle z-x,x\rangle=0. Denote LaTeX: y=z-x. Then, LaTeX: \langle x,y\rangle=0. It remained to show that LaTeX: y=P_{\mathcal K^\circ}z. First, we prove that LaTeX: y\in\mathcal K^\circ. For this we have to show that LaTeX: \langle y,p\rangle\leq0, for all LaTeX: p\in\mathcal K. By using the characterization of the projection, we have

    LaTeX: 
\langle y,p\rangle=\langle y,p-x\rangle=\langle z-x,p-x\rangle\leq0,

    for all LaTeX: p\in\mathcal K. Thus, LaTeX: y\in\mathcal K^\circ. We also have

    LaTeX: 
\langle z-y,q-y\rangle=\langle x,q-y\rangle=\langle x,q\rangle\leq0,

    for all LaTeX: q\in K^\circ, because LaTeX: x\in K. By using again the characterization of the projection, it follows that LaTeX: y=P_{\mathcal K^\circ}z.

References

  • J. J. Moreau, Décomposition orthogonale d'un espace hilbertien selon deux cones mutuellement polaires, C. R. Acad. Sci., volume 255, pages 238–240, 1962.
Personal tools