# Convex Iteration

### From Wikimization

(→constraining cardinality of signed variable) |
|||

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} | + | <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} | + | <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} | + | \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} | + | \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} | + | <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} | + | <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 |

## Revision as of 13:23, 24 November 2011

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

Excert from Chapter 4 Semidefinite Programming:

Consider a feasibility problem equivalent to the classical problem from linear algebra
,
but with an upper bound on cardinality :
for vector

where means vector has at most nonzero entries;
such a vector is presumed existent in the feasible set.

Convex iteration works with a nonnegative variable; absolute value is therefore needed.

We propose that nonconvex problem (1) can be equivalently written
as a convex iteration:
for a relatively small positive constant,

is iterated with

to find *direction vector* .
The cardinality constraint has been moved to the objective as a linear regularization.

The term in (2) is necessary to determine absolute value
because vector can take zero values in its entries.

By initializing direction vector to ,
the first iteration of problem (2) is a 1-norm problem; *i.e.*,

Subsequent iterations of problem (2) engaging cardinality term
can be interpreted as corrections to this 1-norm problem leading to a -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 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

For a coded numerical example, see Candes.m