| |
Abstract:
We introduce the Concave-Convex procedure (CCCP) which
constructs discrete time iterative dynamical systems which are
guaranteed to monotonically decrease global optimization/energy
functions. It can be applied to (almost) any optimization problem
and many existing algorithms can be interpreted in terms of CCCP.
In particular, we prove relationships to some applications of
Legendre transform techniques. We then illustrate CCCP by
applications to Potts models, linear assignment, EM algorithms,
and Generalized Iterative Scaling (GIS). CCCP can be used both as
a new way to understand existing optimization algorithms and as a
procedure for generating new algorithms.
|
