Moreau's decomposition theorem

From Wikimization

(Difference between revisions)
Jump to: navigation, search
m (→Proof of Moreau's theorem)
m (→Projection on closed convex sets)
Line 3: Line 3:
=== 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
<center>
<center>
Line 13: Line 13:
-
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>. Let <math>w\in\mathcal C</math> and <math>t\in (0,1)</math> be arbitrary. By using the convexity of <math>\mathcal C</math>, it follows that <math>(1-t)v+tw\in\mathcal C</math>. Then, by using the definition of the projection, we have
+
Suppose that <math>v=P_{\mathcal C}u.</math> Let <math>w\in\mathcal C</math> and <math>t\in (0,1)</math> be arbitrary. By using the convexity of <math>\mathcal C,</math> it follows that <math>(1-t)v+tw\in\mathcal C.</math> Then, by using the definition of the projection, we have
<center>
<center>
<math>
<math>
-
\|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
+
\|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,
-
</math>,
+
</math>
</center>
</center>
Line 31: Line 31:
</center>
</center>
-
By tending with <math>t</math> to <math>0</math>, we get <math>\langle u-v,w-v\rangle\leq0</math>.
+
By tending with <math>t\,</math> to <math>0,\,</math> we get <math>\langle u-v,w-v\rangle\leq0.</math>
<br>
<br>
<br>
<br>
-
Conversely, suppose that <math>\langle u-v,w-v\rangle\leq0,</math> for all <math>w\in\mathcal C</math>. Then,
+
Conversely, suppose that <math>\langle u-v,w-v\rangle\leq0,</math> for all <math>w\in\mathcal C.</math> Then,
<center>
<center>
Line 41: Line 41:
</center>
</center>
-
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 ==

Revision as of 05:02, 12 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. Let LaTeX: w\in\mathcal C and LaTeX: t\in (0,1) be arbitrary. By using the convexity of LaTeX: \mathcal C, it follows that LaTeX: (1-t)v+tw\in\mathcal C. 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 cones, 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 using 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