# Convex Iteration

### From Wikimization

Line 2: | Line 2: | ||

==constraining cardinality of signed variable== | ==constraining cardinality of signed variable== | ||

- | + | (Excert from [http://meboo.convexoptimization.com/BOOK/semidefiniteprogramming.pdf Semidefinite Programming]). | |

- | <math>A_{}x_{\!}=_{\!}b</math>, | + | Consider a feasibility problem equivalent to the classical problem from linear algebra |

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

Line 32: | Line 33: | ||

\end{array}~~~~~~~~~~~~~~(2)</math> | \end{array}~~~~~~~~~~~~~~(2)</math> | ||

- | + | 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^\star,\,y+\varepsilon^{}\mathbf{1}\rangle\\ | ||

Line 63: | Line 64: | ||

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. | + | |

+ | There can be no proof of global optimality, defined by an optimal objective euqal to 0. | ||

+ | Local solutions are therefore detected by nonzero optimal objective. | ||

+ | |||

+ | Heuristics for reinitializing direction vector <math>y</math> can lead to a globally optimal solution. |

## Revision as of 20:21, 5 February 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, and 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 , 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 problem (1) can be equivalently written

which moves the cardinality constraint to the objective. To express this nonconvex problem as a convex iteration, we separate it into halves: for a relatively small positive constant,

is iterated with

to find direction vector . The term in (2) is necessary to determine absolute value because vector can take zero values in its entries; a good estimate of is required for (3).

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 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 euqal to 0. Local solutions are therefore detected by nonzero optimal objective.

Heuristics for reinitializing direction vector can lead to a globally optimal solution.