Convex Iteration

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Current revision (20:18, 3 October 2016) (edit) (undo)
(constraining cardinality of signed variable)
 
(22 intermediate revisions not shown.)
Line 1: Line 1:
-
Convex iteration is method for constraining rank or cardinality in an otherwise convex optimization problem. A rank or cardinality constraint is replaced by a weighted linear regularization term added to the objective, and then two convex problems are iterated until convergence where, ideally, solution to the original problem is found.
+
Convex iteration is method for constraining rank or cardinality in an otherwise convex optimization problem.
 +
<br>
 +
A rank or cardinality constraint is replaced by a linear regularization term added to the objective.
 +
<br>
 +
Then two convex problems are iterated until convergence where, ideally, solution to the original problem is found.
==constraining cardinality of signed variable==
==constraining cardinality of signed variable==
-
Now consider a feasibility problem equivalent to the classical problem from linear algebra
+
Excerpt from Chapter 4 [http://meboo.convexoptimization.com/Meboo.html Semidefinite Programming]:
-
<math>A_{}x_{\!}=_{\!}b</math>,
+
<br>Consider a feasibility problem equivalent to the classical problem from linear algebra
-
but with an upper bound <math>k</math> on cardinality <math>\|x\|_0</math> :
+
<math>A_{}x_{\!}=_{\!}b</math> ,&nbsp;
-
&nbsp;for vector <math>b\!\in\!\mathcal{R}(A)</math>
+
but with an upper bound <math>k</math> on cardinality <math>||x||_0</math> :
 +
&nbsp;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
-
\end{array}~~~~~~~~~~(1)</math>
+
\end{array}</math> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(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. <br>Convex iteration works with a nonnegative variable;
+
such a vector is presumed existent in the feasible set.
-
absolute value <math>|x|</math> is therefore needed.
+
<br>Convex iteration works with a nonnegative variable; absolute value <math>|x|</math> is therefore needed.
-
We propose that problem (1) can be equivalently written
+
<br>We propose that nonconvex problem (1) can be equivalently written
-
 
+
as a convex iteration:
-
<math>\begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^{^n},~y_{}\in_{_{}}\mathbb{R}^{^n}}&\langle_{}|x|_{}\,,\,y^{}\rangle\\
+
-
\mbox{subject to}&A_{}x=b\\
+
-
&0\preceq y\preceq\mathbf{1}\\
+
-
&y^T\mathbf{1}=n-_{}k
+
-
\end{array}</math>
+
-
 
+
-
which moves the cardinality constraint to the objective.
+
-
To express this nonconvex problem as a convex iteration, we separate it into halves:
+
for <math>\varepsilon</math> a relatively small positive constant,
for <math>\varepsilon</math> a relatively small positive constant,
-
<math>\begin{array}{rl}\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
-
\end{array}~~~~~~~~~~~~~~(2)</math>
+
\end{array}</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(2)
-
by iterating with
+
is iterated with
-
<math>\begin{array}{cl}\text{minimize}_{y_{}\in_{_{}}\mathbb{R}^{^n}}&\langle t^\star,\,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
-
\end{array}~~~~~~~~~~~~~~~~~~~(3)</math>
+
\end{array}</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(3)
-
to find direction vector <math>y</math>.
+
to find ''direction vector'' <math>y</math>.
-
The term <math>\langle t\,,_{_{}}\varepsilon^{}\mathbf{1}\rangle</math> in (2) is necessary to determine absolute value
+
The cardinality constraint has been moved to the objective as a linear regularization.
-
<math>|x|_{\!}=_{}t^{\star_{}}</math> because vector <math>y</math> can take zero values in its entries;
+
<br>The term <math>\langle t\,,_{_{}}\varepsilon^{}\mathbf{1}\rangle</math> in (2) is necessary to determine absolute value
-
a good estimate of <math>|x|</math> is required for (3).
+
<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>,
Line 48: Line 45:
<math>\begin{array}{ccc}
<math>\begin{array}{ccc}
-
\begin{array}{rl}\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}~~~~~~~~~~(4)</math>
+
\end{array}</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(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>
-
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>
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
a monotonically nonincreasing objective sequence.
a monotonically nonincreasing objective sequence.
-
There can be no proof of global optimality.
+
<br>
 +
There can be no proof of global optimality, defined by an optimal objective equal to 0.
 +
<br>Local solutions are therefore detected by nonzero optimal objective.
 +
<br>Heuristics for reinitializing direction vector <math>y</math> can lead to a globally optimal solution.
 +
 
 +
===equivalent===
 +
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\!\rightarrow0^+\,</math>
 +
 
 +
<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\\
 +
&-t\preceq x\preceq_{_{}}t
 +
\end{array}</math>
 +
 
 +
<math>\begin{array}{cl}{\text minimize}_{y_{}\in_{_{}}\mathbb{R}^n}&\langle |x^*|\,,\,y\rangle\\
 +
\text{subject to}&0\preceq y\preceq\mathbf{1}\\
 +
&y^{\rm T}\mathbf{1}=n-_{}k
 +
\end{array}</math>
 +
 
 +
----
 +
For a coded numerical example, see [[Candes.m]]

Current revision

Convex iteration is method for constraining rank or cardinality in an otherwise convex optimization problem.
A rank or cardinality constraint is replaced by a linear regularization term added to the objective.
Then two convex problems are iterated until convergence where, ideally, solution to the original problem is found.

constraining cardinality of signed variable

Excerpt from Chapter 4 Semidefinite Programming:
Consider a feasibility problem equivalent to the classical problem from linear algebra LaTeX: A_{}x_{\!}=_{\!}b ,  but with an upper bound LaTeX: k on cardinality LaTeX: ||x||_0 :  for vector LaTeX: b\!\in\mathcal{R}(A)

LaTeX: \begin{array}{rl}{\text find}&_{}x\in_{}\mathbb{R}^n\\
\mbox{subject to}&A_{}x=b\\
&||x||_0\leq_{}k
\end{array}           (1)

where LaTeX: ||x||_0\leq k means vector LaTeX: x has at most LaTeX: k nonzero entries; such a vector is presumed existent in the feasible set.
Convex iteration works with a nonnegative variable; absolute value LaTeX: |x| is therefore needed.
We propose that nonconvex problem (1) can be equivalently written as a convex iteration: for LaTeX: \varepsilon a relatively small positive constant,

LaTeX: \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\\
&-t\preceq x\preceq_{_{}}t
\end{array}              (2)

is iterated with

LaTeX: \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}\\
&y^T\mathbf{1}=n-_{}k
\end{array}                   (3)

to find direction vector LaTeX: y. The cardinality constraint has been moved to the objective as a linear regularization.
The term LaTeX: \langle t\,,_{_{}}\varepsilon^{}\mathbf{1}\rangle in (2) is necessary to determine absolute value LaTeX: |x|_{\!}=_{}t^{*_{}} because vector LaTeX: y can take zero values in its entries.

By initializing direction vector LaTeX: y to LaTeX: (1\!-_{}\!\varepsilon)\mathbf{1}_{}, the first iteration of problem (2) is a 1-norm problem; i.e.,

LaTeX: \begin{array}{ccc}
\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\\
&-t\preceq x\preceq t
\end{array}
&\equiv&
\begin{array}{cl}{\text minimize}_{x\in\mathbb{R}^n}&||x||_1\\
\mbox{subject to}&Ax=b
\end{array}
\end{array}          (4)

Subsequent iterations of problem (2) engaging cardinality term LaTeX: \langle t_{}\,,\,y\rangle can be interpreted as corrections to this 1-norm problem leading to a LaTeX: 0-norm solution.
Iteration (2) (3) always converges to a locally optimal solution by virtue of a monotonically nonincreasing objective sequence.
There can be no proof of global optimality, defined by an optimal objective equal to 0.
Local solutions are therefore detected by nonzero optimal objective.
Heuristics for reinitializing direction vector LaTeX: y can lead to a globally optimal solution.

equivalent

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 LaTeX: \,\varepsilon\!\rightarrow0^+\,

LaTeX: \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\\
&-t\preceq x\preceq_{_{}}t
\end{array}

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


For a coded numerical example, see Candes.m

Personal tools