Convex Iteration - Revision history

Ranjelin at 20:43, 31 May 2026

2026-05-31T20:43:16Z

←Older revision		Revision as of 20:43, 31 May 2026
Line 24:		Line 24:
	for <math>\varepsilon</math> a relatively small positive constant,		for <math>\varepsilon</math> a relatively small positive constant,

-	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,\;t_{}\in_{_{}}\mathbb{R}^n}&\langle t_{}\,,\,y+\varepsilon^{}\mathbf{1}\rangle\\	+	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,\,t_{}\in_{_{}}\mathbb{R}^n}&\langle t_{}\,,\,y+\varepsilon^{}\mathbf{1}\rangle\\
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t
Line 45:		Line 45:

	<math>\begin{array}{ccc}		<math>\begin{array}{ccc}
-	\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n,\;t\in\mathbb{R}^n}&\langle t\,,\,\mathbf{1}\rangle\\	+	\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n,\,t\in\mathbb{R}^n}&\langle t\,,\,\mathbf{1}\rangle\\
	\mbox{subject to}&Ax=b\\		\mbox{subject to}&Ax=b\\
	&-t\preceq x\preceq t		&-t\preceq x\preceq t
Line 69:		Line 69:
	but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow0^+\,</math>		but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow0^+\,</math>

-	<math>\begin{array}{cl}{\text minimize}_{x_{}\in_{_{}}\mathbb{R}^n,\;t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\	+	<math>\begin{array}{cl}{\text minimize}_{x_{}\in_{_{}}\mathbb{R}^n,\,t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\
	\text{subject to}&_{}A_{}x=b\\		\text{subject to}&_{}A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t

Ranjelin at 20:39, 31 May 2026

2026-05-31T20:39:32Z

←Older revision		Revision as of 20:39, 31 May 2026
Line 38:		Line 38:
	to find ''direction vector'' <math>y</math>.		to find ''direction vector'' <math>y</math>.
	The cardinality constraint has been moved to the objective as a linear regularization.		The cardinality constraint has been moved to the objective as a linear regularization.
-	<br>The term <math>\langle t\,,~~_{_{}}~~\varepsilon^{}\mathbf{1}\rangle</math> in (2) is necessary to determine absolute value	+	<br>The term <math>\langle t\,,\,\varepsilon^{}\mathbf{1}\rangle</math> in (2) is necessary to determine absolute value
	<math>\|x\|_{\!}=_{}t^{*_{}}</math> because vector <math>y</math> can take zero values in its entries.		<math>\|x\|_{\!}=_{}t^{*_{}}</math> because vector <math>y</math> can take zero values in its entries.

-	By initializing direction vector <math>y</math> to <math>(1\!-_{}\!\varepsilon)\mathbf{1}_{}</math>,	+	By initializing direction vector <math>y</math> to <math>(1-_{}\varepsilon)\mathbf{1}_{}</math>,
	the first iteration of problem (2) is a 1-norm problem; ''i.e.'',		the first iteration of problem (2) is a 1-norm problem; ''i.e.'',

	<math>\begin{array}{ccc}		<math>\begin{array}{ccc}
-	\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n,\;t\in\mathbb{R}^n}&\langle t,\mathbf{1}\rangle\\	+	\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n,\;t\in\mathbb{R}^n}&\langle t\,,\,\mathbf{1}\rangle\\
	\mbox{subject to}&Ax=b\\		\mbox{subject to}&Ax=b\\
	&-t\preceq x\preceq t		&-t\preceq x\preceq t

Ranjelin at 23:43, 6 May 2026

2026-05-06T23:43:08Z

←Older revision		Revision as of 23:43, 6 May 2026
Line 24:		Line 24:
	for <math>\varepsilon</math> a relatively small positive constant,		for <math>\varepsilon</math> a relatively small positive constant,

-	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t_{}\,,\,y+\varepsilon^{}\mathbf{1}\rangle\\	+	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,\;t_{}\in_{_{}}\mathbb{R}^n}&\langle t_{}\,,\,y+\varepsilon^{}\mathbf{1}\rangle\\
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t
Line 45:		Line 45:

	<math>\begin{array}{ccc}		<math>\begin{array}{ccc}
-	\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n,~t\in\mathbb{R}^n}&\langle t,\mathbf{1}\rangle\\	+	\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n,\;t\in\mathbb{R}^n}&\langle t,\mathbf{1}\rangle\\
	\mbox{subject to}&Ax=b\\		\mbox{subject to}&Ax=b\\
	&-t\preceq x\preceq t		&-t\preceq x\preceq t
Line 69:		Line 69:
	but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow0^+\,</math>		but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow0^+\,</math>

-	<math>\begin{array}{cl}{\text minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\	+	<math>\begin{array}{cl}{\text minimize}_{x_{}\in_{_{}}\mathbb{R}^n,\;t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\
	\text{subject to}&_{}A_{}x=b\\		\text{subject to}&_{}A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t

Ranjelin: /* constraining cardinality of signed variable */

2016-10-04T04:18:00Z

constraining cardinality of signed variable

Ranjelin: /* constraining cardinality of signed variable */

2016-10-04T04:12:51Z

constraining cardinality of signed variable

←Older revision		Revision as of 04:12, 4 October 2016
Line 12:		Line 12:
	for vector <math>b\!\in\mathcal{R}(A)</math>		for vector <math>b\!\in\mathcal{R}(A)</math>

-	<math>\begin{array}{rl}\text{find}&_{}x\in_{}\mathbb{R}^n\\	+	<math>\begin{array}{rl}{\text find}&_{}x\in_{}\mathbb{R}^n\\
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
	&\\|x\\|_0\leq_{}k		&\\|x\\|_0\leq_{}k
Line 45:		Line 45:

	<math>\begin{array}{ccc}		<math>\begin{array}{ccc}
-	\begin{array}{cl}\text{minimize}_{~~x_{}~~\~~in_{_{}}~~\mathbb{R}^n,~~~t_{}~~\~~in_{_{}}~~\mathbb{R}^n}&\langle t\,~~,_{}~~\mathbf{1}\rangle\\	+	\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n,~t\in\mathbb{R}^n}&\langle t,\mathbf{1}\rangle\\
-	\mbox{subject to}&~~A_{}x~~=b\\	+	\mbox{subject to}&Ax=b\\
-	&-t\preceq x\~~preceq_{_{}}~~t	+	&-t\preceq x\preceq t
	\end{array}		\end{array}
-	&\equiv&~	+	&\equiv&
-	\begin{array}{cl}\text{minimize}_{~~x_{}~~\~~in_{_{}}~~\mathbb{R}^n}&\\|x\\|_1\\	+	\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n}&\|\|x\|\|_1\\
-	\mbox{subject to}&~~A_{}x~~=b	+	\mbox{subject to}&Ax=b
	\end{array}		\end{array}
	\end{array}</math>          (4)		\end{array}</math>          (4)
Line 69:		Line 69:
	but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow0^+\,</math>		but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow0^+\,</math>

-	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\	+	<math>\begin{array}{cl}{\text minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\
	\text{subject to}&_{}A_{}x=b\\		\text{subject to}&_{}A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t
	\end{array}</math>		\end{array}</math>

-	<math>\begin{array}{cl}\text{minimize}_{y_{}\in_{_{}}\mathbb{R}^n}&\langle \|x^*\|\,,\,y\rangle\\	+	<math>\begin{array}{cl}{\text minimize}_{y_{}\in_{_{}}\mathbb{R}^n}&\langle \|x^*\|\,,\,y\rangle\\
	\text{subject to}&0\preceq y\preceq\mathbf{1}\\		\text{subject to}&0\preceq y\preceq\mathbf{1}\\
	&y^{\rm T}\mathbf{1}=n-_{}k		&y^{\rm T}\mathbf{1}=n-_{}k

Ranjelin: /* constraining cardinality of signed variable */

2011-12-05T06:08:28Z

constraining cardinality of signed variable

←Older revision		Revision as of 06:08, 5 December 2011
Line 15:		Line 15:
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
	&\\|x\\|_0\leq_{}k		&\\|x\\|_0\leq_{}k
-	\end{array}~~~~~~~~~~~~(1)~~</math>	+	\end{array}</math>           (1)

	where <math>\\|x\\|_{0\!}\leq_{_{}\!}k</math> means vector <math>x</math> has at most <math>k</math> nonzero entries;		where <math>\\|x\\|_{0\!}\leq_{_{}\!}k</math> means vector <math>x</math> has at most <math>k</math> nonzero entries;
Line 27:		Line 27:
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t
-	\end{array}~~~~~~~~~~~~~~~~(2)~~</math>	+	\end{array}</math>              (2)

	is iterated with		is iterated with
Line 34:		Line 34:
	\mbox{subject to}&0\preceq y\preceq\mathbf{1}\\		\mbox{subject to}&0\preceq y\preceq\mathbf{1}\\
	&y^T\mathbf{1}=n-_{}k		&y^T\mathbf{1}=n-_{}k
-	\end{array}~~~~~~~~~~~~~~~~~~~~~(3)~~</math>	+	\end{array}</math>                   (3)

	to find ''direction vector'' <math>y</math>.		to find ''direction vector'' <math>y</math>.
Line 53:		Line 53:
	\mbox{subject to}&A_{}x=b		\mbox{subject to}&A_{}x=b
	\end{array}		\end{array}
-	\end{array}~~~~~~~~~~~~(4)~~</math>	+	\end{array}</math>          (4)

	Subsequent iterations of problem (2) engaging cardinality term <math>\langle t_{}\,,\,y\rangle</math>		Subsequent iterations of problem (2) engaging cardinality term <math>\langle t_{}\,,\,y\rangle</math>
Line 67:		Line 67:
	===equivalent===		===equivalent===
	Several simple equivalents to linear programs (2) (3) are easily devised,		Several simple equivalents to linear programs (2) (3) are easily devised,
-	but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\~~rightarrow\!0~~^+\,</math>	+	but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow0^+\,</math>

	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\		<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\

Ranjelin: /* constraining cardinality of signed variable */

2011-12-05T06:04:29Z

constraining cardinality of signed variable

←Older revision		Revision as of 06:04, 5 December 2011
Line 10:		Line 10:
	<math>A_{}x_{\!}=_{\!}b</math> ,		<math>A_{}x_{\!}=_{\!}b</math> ,
	but with an upper bound <math>k</math> on cardinality <math>\\|x\\|_0</math> :		but with an upper bound <math>k</math> on cardinality <math>\\|x\\|_0</math> :
-	for vector <math>b\!\in\!\mathcal{R}(A)</math>	+	for vector <math>b\!\in\mathcal{R}(A)</math>

	<math>\begin{array}{rl}\text{find}&_{}x\in_{}\mathbb{R}^n\\		<math>\begin{array}{rl}\text{find}&_{}x\in_{}\mathbb{R}^n\\

Ranjelin: /* constraining cardinality of signed variable */

2011-11-24T20:23:27Z

constraining cardinality of signed variable

←Older revision		Revision as of 20:23, 24 November 2011
Line 24:		Line 24:
	for <math>\varepsilon</math> a relatively small positive constant,		for <math>\varepsilon</math> a relatively small positive constant,

-	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^{^n},~t_{}\in_{_{}}\mathbb{R}^{^n}}&\langle t_{}\,,\,y+\varepsilon^{}\mathbf{1}\rangle\\	+	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t_{}\,,\,y+\varepsilon^{}\mathbf{1}\rangle\\
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t
Line 31:		Line 31:
	is iterated with		is iterated with

-	<math>\begin{array}{cl}\text{minimize}_{y_{}\in_{_{}}\mathbb{R}^{^n}}&\langle t^*,\,y+\varepsilon^{}\mathbf{1}\rangle\\	+	<math>\begin{array}{cl}\text{minimize}_{y_{}\in_{_{}}\mathbb{R}^n}&\langle t^*,\,y+\varepsilon^{}\mathbf{1}\rangle\\
	\mbox{subject to}&0\preceq y\preceq\mathbf{1}\\		\mbox{subject to}&0\preceq y\preceq\mathbf{1}\\
	&y^T\mathbf{1}=n-_{}k		&y^T\mathbf{1}=n-_{}k
Line 45:		Line 45:

	<math>\begin{array}{ccc}		<math>\begin{array}{ccc}
-	\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^{^n},~t_{}\in_{_{}}\mathbb{R}^{^n}}&\langle t\,,_{}\mathbf{1}\rangle\\	+	\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,_{}\mathbf{1}\rangle\\
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t
	\end{array}		\end{array}
	&\equiv&~		&\equiv&~
-	\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^{^n}}&\\|x\\|_1\\	+	\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n}&\\|x\\|_1\\
	\mbox{subject to}&A_{}x=b		\mbox{subject to}&A_{}x=b
	\end{array}		\end{array}
Line 69:		Line 69:
	but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow\!0^+\,</math>		but their geometrical interpretation is not as apparent: ''e.g.'', equivalent in the limit <math>\,\varepsilon\!\rightarrow\!0^+\,</math>

-	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^{^n},~t_{}\in_{_{}}\mathbb{R}^{^n}}&\langle t\,,\,y\rangle\\	+	<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^n,~t_{}\in_{_{}}\mathbb{R}^n}&\langle t\,,\,y\rangle\\
	\text{subject to}&_{}A_{}x=b\\		\text{subject to}&_{}A_{}x=b\\
	&-t\preceq x\preceq_{_{}}t		&-t\preceq x\preceq_{_{}}t
	\end{array}</math>		\end{array}</math>

-	<math>\begin{array}{cl}\text{minimize}_{y_{}\in_{_{}}\mathbb{R}^{^n}}&\langle \|x^*\|\,,\,y\rangle\\	+	<math>\begin{array}{cl}\text{minimize}_{y_{}\in_{_{}}\mathbb{R}^n}&\langle \|x^*\|\,,\,y\rangle\\
	\text{subject to}&0\preceq y\preceq\mathbf{1}\\		\text{subject to}&0\preceq y\preceq\mathbf{1}\\
	&y^{\rm T}\mathbf{1}=n-_{}k		&y^{\rm T}\mathbf{1}=n-_{}k

Ranjelin at 20:21, 24 November 2011

2011-11-24T20:21:01Z

←Older revision		Revision as of 20:21, 24 November 2011
Line 56:		Line 56:

	Subsequent iterations of problem (2) engaging cardinality term <math>\langle t_{}\,,\,y\rangle</math>		Subsequent iterations of problem (2) engaging cardinality term <math>\langle t_{}\,,\,y\rangle</math>
-	can be interpreted as corrections to this 1-norm problem leading to a 0-norm solution.	+	can be interpreted as corrections to this 1-norm problem leading to a <math>0</math>-norm solution.
	<br>		<br>
	Iteration (2) (3) always converges to a locally optimal solution by virtue of		Iteration (2) (3) always converges to a locally optimal solution by virtue of

Ranjelin at 20:19, 24 November 2011

2011-11-24T20:19:48Z

←Older revision		Revision as of 20:19, 24 November 2011
Line 12:		Line 12:
	for vector <math>b\!\in\!\mathcal{R}(A)</math>		for vector <math>b\!\in\!\mathcal{R}(A)</math>

-	<math>\begin{array}{rl}\text{find}&_{}x\in_{}\~~reals~~^n\\	+	<math>\begin{array}{rl}\text{find}&_{}x\in_{}\mathbb{R}^n\\
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
	&\\|x\\|_0\leq_{}k		&\\|x\\|_0\leq_{}k

←Older revision		Revision as of 04:18, 4 October 2016
Line 6:		Line 6:

	==constraining cardinality of signed variable==		==constraining cardinality of signed variable==
-	~~Excert~~ from Chapter 4 [http://meboo.convexoptimization.com/Meboo.html Semidefinite Programming]:	+	Excerpt from Chapter 4 [http://meboo.convexoptimization.com/Meboo.html Semidefinite Programming]:
	<br>Consider a feasibility problem equivalent to the classical problem from linear algebra		<br>Consider a feasibility problem equivalent to the classical problem from linear algebra
	<math>A_{}x_{\!}=_{\!}b</math> ,		<math>A_{}x_{\!}=_{\!}b</math> ,
-	but with an upper bound <math>k</math> on cardinality <math>\\|x\\|_0</math> :	+	but with an upper bound <math>k</math> on cardinality <math>\|\|x\|\|_0</math> :
	for vector <math>b\!\in\mathcal{R}(A)</math>		for vector <math>b\!\in\mathcal{R}(A)</math>

	<math>\begin{array}{rl}{\text find}&_{}x\in_{}\mathbb{R}^n\\		<math>\begin{array}{rl}{\text find}&_{}x\in_{}\mathbb{R}^n\\
	\mbox{subject to}&A_{}x=b\\		\mbox{subject to}&A_{}x=b\\
-	&\\|x\\|_0\leq_{}k	+	&\|\|x\|\|_0\leq_{}k
	\end{array}</math>           (1)		\end{array}</math>           (1)

-	where <math>\\|x\\|~~_{0\!}\leq_{_{}~~\!}k</math> means vector <math>x</math> has at most <math>k</math> nonzero entries;	+	where <math>\|\|x\|\|_0\leq k</math> means vector <math>x</math> has at most <math>k</math> nonzero entries;
	such a vector is presumed existent in the feasible set.		such a vector is presumed existent in the feasible set.
	<br>Convex iteration works with a nonnegative variable; absolute value <math>\|x\|</math> is therefore needed.		<br>Convex iteration works with a nonnegative variable; absolute value <math>\|x\|</math> is therefore needed.