Moreau's decomposition theorem - Revision history

Nemeth: /* Projection mapping */

Nemeth — Fri, 28 Jun 2019 12:07:29 GMT

Projection mapping

←Older revision		Revision as of 12:07, 28 June 2019
Line 9:		Line 9:

	<center>		<center>
-	<math>\parallel x-P_{\mathcal{C}}(x)\parallel=\min\{\parallel x-y\parallel\,:\,y\in\mathcal{C}\}.</math>	+	<math>\parallel x-P_{\mathcal{C}}(x)\parallel=\min\{\parallel x-y\parallel\,:y\in\mathcal{C}\}.</math>
	</center>		</center>

Ranjelin at 05:07, 5 December 2011

Ranjelin — Mon, 05 Dec 2011 05:07:31 GMT

←Older revision		Revision as of 05:07, 5 December 2011
Line 1:		Line 1:
	[http://web.mat.bham.ac.uk/S.Z.Nemeth/ <math>-</math> Sándor Zoltán Németh]		[http://web.mat.bham.ac.uk/S.Z.Nemeth/ <math>-</math> Sándor Zoltán Németh]

-	(In particular, we can have <math>\mathbb H=\mathbb R^n</math> everywhere in this page.)	+	(In particular, we can have <math>\mathbb{H}=\mathbb{R}^n</math> everywhere in this page.)

	== Projection on closed convex sets ==		== Projection on closed convex sets ==

Nemeth: /* notes */

Nemeth — Sat, 19 Nov 2011 08:59:59 GMT

notes

←Older revision		Revision as of 08:59, 19 November 2011
Line 98:		Line 98:
	For definition of ''polar cone'' in finite dimension, see [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry].		For definition of ''polar cone'' in finite dimension, see [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry].

-	<math>\mathcal K^{\circ\circ}=K</math> see [[Farkas%27_lemma#Extended_Farkas.27_lemma\|Extended Farkas' lemma]].	+	<math>\mathcal{K}^{\circ\circ}=\mathcal{K}</math> see [[Farkas%27_lemma#Extended_Farkas.27_lemma\|Extended Farkas' lemma]].

	== Applications ==		== Applications ==

Nemeth: /* Moreau's theorem */

Nemeth — Sat, 19 Nov 2011 08:59:10 GMT

Moreau's theorem

←Older revision		Revision as of 08:59, 19 November 2011
Line 48:		Line 48:
	under the addition of vectors and multiplication of vectors by positive scalars.		under the addition of vectors and multiplication of vectors by positive scalars.

-	'''Theorem (Moreau).''' Let <math>\mathcal K</math> be a closed convex cone in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> and <math>\mathcal K^\circ</math> its '''polar cone'''; that is, the closed convex cone defined by <math>\mathcal K^\circ=\{a\in\mathbb H\mid\langle a,b\rangle\leq0,\,\forall b\in\mathcal K\}.</math>	+	'''Theorem (Moreau).''' Let <math>\mathcal{K}</math> be a closed convex cone in the Hilbert space <math>(\mathbb{H},\langle\cdot,\cdot\rangle)</math> and <math>\mathcal{K}^\circ</math> its '''polar cone'''; that is, the closed convex cone defined by <math>\mathcal{K}^\circ=\{a\in\mathbb{H}\,\mid\,\langle a,b\rangle\leq0,\,\forall b\in\mathcal{K}\}.</math>

-	For <math>x,y,z\in\mathbb H</math> the following statements are equivalent:	+	For <math>x,y,z\in\mathbb{H}</math> the following statements are equivalent:

	<ol>		<ol>
-	<li><math>z=x+y,\,x\in\mathcal K,\,y\in\mathcal K^\circ</math> and <math>\langle x,y\rangle=0,</math></li>	+	<li><math>z=x+y,\,x\in\mathcal{K},\,y\in\mathcal{K}^\circ</math> and <math>\langle x,y\rangle=0,</math></li>
-	<li><math>x=P_{\mathcal K}z</math> and <math>y=P_{\mathcal K^\circ}z.</math>	+	<li><math>x=P_{\mathcal{K}}z</math> and <math>y=P_{\mathcal{K}^\circ}z.</math>
	</li>		</li>
	</ol>		</ol>
Line 60:		Line 60:
	=== Proof of Moreau's theorem ===		=== Proof of Moreau's theorem ===
	<ul>		<ul>
-	<li>1<math>\Rightarrow</math>2: For all <math>p\in K</math> we have	+	<li>1<math>\Rightarrow</math>2: For all <math>p\in\mathcal{K}</math> we have

	<center>		<center>
Line 66:		Line 66:
	</center>		</center>

-	Then, by the characterization of the projection, it follows that <math>x=P_{\mathcal K}z.</math> Similarly, for all <math>q\in K^\circ</math> we have	+	Then, by the characterization of the projection, it follows that <math>x=P_{\mathcal{K}}z.</math> Similarly, for all <math>q\in\mathcal{K}^\circ</math> we have

	<center>		<center>
Line 72:		Line 72:
	</center>		</center>

-	and thus <math>y=P_{\mathcal K^\circ}z.</math></li>	+	and thus <math>y=P_{\mathcal{K}^\circ}z.</math></li>
-	<li>2<math>\Rightarrow</math>1: By using the characterization of the projection, we have <math>\langle z-x,p-x\rangle\leq0,</math> for all <math>p\in\mathcal K.</math> In particular, if <math>p=0,\,</math> then <math>\langle z-x,x\rangle\geq0</math> and if <math>p=2x,\,</math> then <math>\langle z-x,x\rangle\leq0.</math> Thus, <math>\langle z-x,x\rangle=0.</math> Denote <math>u=z-x.\,</math> Then <math>\langle x,u\rangle=0.</math> It remains to show that <math>u=y.\,</math> First, we prove that <math>u\in\mathcal K^\circ.</math> For this we have to show that <math>\langle u,p\rangle\leq0,</math> for	+	<li>2<math>\Rightarrow</math>1: By using the characterization of the projection, we have <math>\langle z-x,p-x\rangle\leq0,</math> for all <math>p\in\mathcal K.</math> In particular, if <math>p=0,\,</math> then <math>\langle z-x,x\rangle\geq0</math> and if <math>p=2x,\,</math> then <math>\langle z-x,x\rangle\leq0.</math> Thus, <math>\langle z-x,x\rangle=0.</math> Denote <math>u=z-x.\,</math> Then <math>\langle x,u\rangle=0.</math> It remains to show that <math>u=y.\,</math> First, we prove that <math>u\in\mathcal{K}^\circ.</math> For this we have to show that <math>\langle u,p\rangle\leq0,</math> for
-	all <math>p\in\mathcal K.</math> By using the characterization of the projection, we have	+	all <math>p\in\mathcal{K}.</math> By using the characterization of the projection, we have

	<center>		<center>
Line 82:		Line 82:
	</center>		</center>

-	for all <math>p\in\mathcal K.</math> Thus, <math>u\in\mathcal K^\circ.</math> We also have	+	for all <math>p\in\mathcal{K}.</math> Thus, <math>u\in\mathcal{K}^\circ.</math> We also have

	<center>		<center>
Line 90:		Line 90:
	</center>		</center>

-	for all <math>q\in K^\circ,</math> because <math>x\in K.</math> By using again the characterization of the projection, it follows that <math>u=y.\,</math>	+	for all <math>q\in\mathcal{K}^\circ,</math> because <math>x\in\mathcal{K}.</math> By using again the characterization of the projection, it follows that <math>u=y.\,</math>
	</ul>		</ul>

Nemeth: /* Proof */

Nemeth — Sat, 19 Nov 2011 08:53:59 GMT

Proof

←Older revision		Revision as of 08:53, 19 November 2011
Line 20:		Line 20:
	<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,	+	\parallel u-v\parallel^2\leq\parallel u-((1-t)v+tw)\parallel^2=\parallel u-v-t(w-v)\parallel^2=\parallel u-v\parallel^2-2t\langle u-v,w-v\rangle+t^2\parallel w-v\parallel^2,
	</math>		</math>
	</center>		</center>
Line 27:		Line 27:

	<center>		<center>
-	<math>\langle u-v,w-v\rangle\leq\frac t2\\|w-v\\|^2.</math>	+	<math>\langle u-v,w-v\rangle\leq\frac t2\parallel w-v\parallel^2.</math>
	</center>		</center>

Line 37:		Line 37:

	<center>		<center>
-	<math>\\|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,</math>	+	<math>\parallel u-w\parallel^2=\parallel u-v-(w-v)\parallel^2=\parallel u-v\parallel^2-2\langle u-v,w-v\rangle+\parallel w-v\parallel^2\geq \parallel u-v\parallel^2,</math>
	</center>		</center>

Nemeth: /* Proof */

Nemeth — Sat, 19 Nov 2011 08:50:24 GMT

Proof

←Older revision		Revision as of 08:50, 19 November 2011
Line 16:		Line 16:

	=== 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>

Nemeth: /* Characterization of the projection */

Nemeth — Sat, 19 Nov 2011 08:48:25 GMT

Characterization of the projection

←Older revision		Revision as of 08:48, 19 November 2011
Line 13:		Line 13:

	=== Characterization of the projection ===		=== Characterization of the projection ===
-	Let <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> be a Hilbert space, <math>\mathcal C</math> a closed convex set in <math>\mathbb H,\,u\in\mathbb 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>(\mathbb{H},\langle\cdot,\cdot\rangle)</math> be a Hilbert space, <math>\mathcal{C}</math> a closed convex set in <math>\mathbb{H},\,u\in\mathbb{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 ===

Nemeth: /* Projection mapping */

Nemeth — Sat, 19 Nov 2011 08:46:39 GMT

Projection mapping

←Older revision		Revision as of 08:46, 19 November 2011
Line 6:		Line 6:

	=== Projection mapping ===		=== Projection mapping ===
-	Let <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> be a Hilbert space and <math>\mathcal C</math> a closed convex set in <math>\mathbb H.</math> The '''projection mapping''' <math>P_{\mathcal C}</math> onto <math>\mathcal C</math> is the mapping <math>P_{\mathcal C}:\mathbb H\to\mathbb H</math> defined by <math>P_{\mathcal C}(x)\in\mathcal C</math> and	+	Let <math>(\mathbb{H},\langle\cdot,\cdot\rangle)</math> be a Hilbert space and <math>\mathcal{C}</math> a closed convex set in <math>\mathbb{H}.</math> The '''projection mapping''' <math>P_{\mathcal{C}}</math> onto <math>\mathcal{C}</math> is the mapping <math>P_{\mathcal{C}}:\mathbb{H}\to\mathbb{H}</math> defined by <math>P_{\mathcal{C}}(x)\in\mathcal{C}</math> and

	<center>		<center>
-	<math>\\|x-P_{\mathcal C}(x)\\|=\min\{\\|x-y\\|\~~mid~~ y\in\mathcal C\}.</math>	+	<math>\parallel x-P_{\mathcal{C}}(x)\parallel=\min\{\parallel x-y\parallel\,:\,y\in\mathcal{C}\}.</math>
	</center>		</center>

Nemeth at 21:01, 5 January 2010

Nemeth — Tue, 05 Jan 2010 21:01:27 GMT

←Older revision		Revision as of 21:01, 5 January 2010
Line 1:		Line 1:
-	Sándor Zoltán Németh	+	[http://web.mat.bham.ac.uk/S.Z.Nemeth/ <math>-</math> Sándor Zoltán Németh]

	(In particular, we can have <math>\mathbb H=\mathbb R^n</math> everywhere in this page.)		(In particular, we can have <math>\mathbb H=\mathbb R^n</math> everywhere in this page.)

Nemeth at 20:52, 15 September 2009

Nemeth — Tue, 15 Sep 2009 20:52:23 GMT

←Older revision		Revision as of 20:52, 15 September 2009
Line 1:		Line 1:
	Sándor Zoltán Németh		Sándor Zoltán Németh

-	(In particular we can have <math>\mathbb H=\mathbb R^n</math> everywhere in this page.)	+	(In particular, we can have <math>\mathbb H=\mathbb R^n</math> everywhere in this page.)

	== Projection on closed convex sets ==		== Projection on closed convex sets ==