# Convex Iteration

(Difference between revisions)
 Revision as of 14:05, 4 September 2008 (edit)← Previous diff Revision as of 14:11, 4 September 2008 (edit) (undo)Next diff → Line 7: Line 7: ==constraining cardinality of signed variable== ==constraining cardinality of signed variable== Excert from [http://meboo.convexoptimization.com/BOOK/semidefiniteprogramming.pdf Semidefinite Programming]: Excert from [http://meboo.convexoptimization.com/BOOK/semidefiniteprogramming.pdf Semidefinite Programming]: - Consider a feasibility problem equivalent to the classical problem from linear algebra +
Consider a feasibility problem equivalent to the classical problem from linear algebra $A_{}x_{\!}=_{\!}b$ ,  $A_{}x_{\!}=_{\!}b$ ,  but with an upper bound $k$ on cardinality $\|x\|_0$ : but with an upper bound $k$ on cardinality $\|x\|_0$ : Line 18: Line 18: where $\|x\|_{0\!}\leq_{_{}\!}k$ means vector $x$ has at most $k$ nonzero entries; where $\|x\|_{0\!}\leq_{_{}\!}k$ means vector $x$ has at most $k$ nonzero entries; - such a vector is presumed existent in the feasible set.
Convex iteration works with a nonnegative variable; + such a vector is presumed existent in the feasible set. - absolute value $|x|$ is therefore needed. +
Convex iteration works with a nonnegative variable; absolute value $|x|$ is therefore needed. - We propose that nonconvex problem (1) can be equivalently written +
We propose that nonconvex problem (1) can be equivalently written as a convex iteration: as a convex iteration: for $\varepsilon$ a relatively small positive constant, for $\varepsilon$ a relatively small positive constant, - $\begin{array}{rl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^{^n},~t_{}\in_{_{}}\mathbb{R}^{^n}}&\langle t_{}\,,\,y+\varepsilon^{}\mathbf{1}\rangle\\ + [itex]\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 38: Line 38: to find ''direction vector'' [itex]y$. to find ''direction vector'' $y$. 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. - The term $\langle t\,,_{_{}}\varepsilon^{}\mathbf{1}\rangle$ in (2) is necessary to determine absolute value +
The term $\langle t\,,_{_{}}\varepsilon^{}\mathbf{1}\rangle$ in (2) is necessary to determine absolute value $|x|_{\!}=_{}t^{\star_{}}$ because vector $y$ can take zero values in its entries. $|x|_{\!}=_{}t^{\star_{}}$ because vector $y$ can take zero values in its entries. Line 62: Line 62:

There can be no proof of global optimality, defined by an optimal objective equal to 0. 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. +
Local solutions are therefore detected by nonzero optimal objective. -
+
Heuristics for reinitializing direction vector $y$ can lead to a globally optimal solution. - Heuristics for reinitializing direction vector $y$ can lead to a globally optimal solution. +

## Revision as of 14:11, 4 September 2008

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.
Then two convex problems are iterated until convergence where, ideally, solution to the original problem is found.

## constraining cardinality of signed variable

Excert from 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_{}\reals^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^\star,\,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^{\star_{}}$ 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}&A_{}x=b\\ &-t\preceq x\preceq_{_{}}t \end{array} &\equiv&~ \begin{array}{cl}\text{minimize}_{x_{}\in_{_{}}\mathbb{R}^{^n}}&\|x\|_1\\ \mbox{subject to}&A_{}x=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 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\!\rightarrow\!0^+\,$ $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^\star|\,,\,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