Moreau's decomposition theorem

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 1: Line 1:
-
= Projection on closed convex sets =
+
== Projection on closed convex sets ==
-
== Projection mapping ==
+
=== Projection mapping ===
Let <math>(\mathcal H,\langle\cdot,\cdot\rangle)</math> be a Hilbert space and <math>\mathcal C</math> a closed convex set in <math>\mathcal H</math>. The '''projection mapping''' <math>P_{\mathcal C}</math> onto <math>\mathcal C</math> is the mapping <math>P_{\mathcal C}:\mathcal H\to\mathcal H</math> defined by <math>P_{\mathcal C}(x)\in\mathcal C</math> and
Let <math>(\mathcal H,\langle\cdot,\cdot\rangle)</math> be a Hilbert space and <math>\mathcal C</math> a closed convex set in <math>\mathcal H</math>. The '''projection mapping''' <math>P_{\mathcal C}</math> onto <math>\mathcal C</math> is the mapping <math>P_{\mathcal C}:\mathcal H\to\mathcal H</math> defined by <math>P_{\mathcal C}(x)\in\mathcal C</math> and
Line 9: Line 9:
</center>
</center>
-
== Characterization of the projection ==
+
=== Characterization of the projection ===
Line 15: Line 15:
Let <math>(\mathcal H,\langle\cdot,\cdot\rangle)</math> be a Hilbert space, <math>\mathcal C</math> a closed convex set in <math>\mathcal H,\,u\in\mathcal H</math> and <math>v\in\mathcal C</math>. Then, <math>v=P_{\mathcal C}(u)</math> if and only if <math>\langle u-v,w-v\rangle\leq0</math> for all <math>w\in\mathcal C</math>.
Let <math>(\mathcal H,\langle\cdot,\cdot\rangle)</math> be a Hilbert space, <math>\mathcal C</math> a closed convex set in <math>\mathcal H,\,u\in\mathcal H</math> and <math>v\in\mathcal C</math>. Then, <math>v=P_{\mathcal C}(u)</math> if and only if <math>\langle u-v,w-v\rangle\leq0</math> for all <math>w\in\mathcal C</math>.
-
== Proof ==
+
=== Proof ===
Suppose that <math>v=P_{\mathcal C}u</math> and let <math>w\in\mathcal C</math> be arbitrary. By using the convexity of <math>\mathcal C</math>, it follows that <math>(1-t)v+tw\in\mathcal C</math>, for all <math>t\in (0,1)</math>. Then, by using the definition of the projection, we have
Suppose that <math>v=P_{\mathcal C}u</math> and let <math>w\in\mathcal C</math> be arbitrary. By using the convexity of <math>\mathcal C</math>, it follows that <math>(1-t)v+tw\in\mathcal C</math>, for all <math>t\in (0,1)</math>. Then, by using the definition of the projection, we have
Line 43: Line 43:
for all <math>w\in\mathcal C</math>. Hence, by using the definition of the projection, we get <math>v=P_{\mathcal C}u</math>.
for all <math>w\in\mathcal C</math>. Hence, by using the definition of the projection, we get <math>v=P_{\mathcal C}u</math>.
-
= Moreau's theorem =
+
== 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
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
Line 56: Line 56:
</ol>
</ol>
-
== Proof of Moreau's theorem ==
+
=== Proof of Moreau's theorem ===
<ul>
<ul>
Line 93: Line 93:
</ul>
</ul>
-
== References ==
+
=== References ===
* J. J. Moreau, D&eacute;composition orthogonale d'un espace hilbertien selon deux cones mutuellement polaires, C. R. Acad. Sci., volume 255, pages 238–240, 1962.
* J. J. Moreau, D&eacute;composition orthogonale d'un espace hilbertien selon deux cones mutuellement polaires, C. R. Acad. Sci., volume 255, pages 238–240, 1962.

Revision as of 06:05, 11 July 2009

Contents

Projection on closed convex sets

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.
Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Moreau%27s_decomposition_theorem"
Personal tools