II.1.3.2: The Concave-Convex Procedure

The Concave-Convex Procedure (CCCP) was first proposed by Yuille and Rangarajan [2003] . Its global convergence was studied using the Zangwill theory by Sriperumbudur and Lanckriet [2012], and its rate of convergence using block relaxation theory by Yen et al [2012]. The CCCP was discussed in a wider optimization context by Lipp and Boyd [2014].

The starting point of Yuille and Rangarajan, in the context of energy functions for discrete dynamical systems, is the decomposition of a function $f$ with bounded Hessian into a sum of a convex and a concave function. As we shall show in section 9.2.1 on differences of convex functions any function on a compact set with continuous second derivatives can be decomposed in this way. If $f=u+v$ with $u$ convex and $v$ concave, then the CCCP is the algorithm $$\mathcal{D}u(x^{(k+1)})=-\mathcal{D}v(x^{(k)}).$$ Now, by tangential majorization, $f(x)\leq g(x,y)$ with $$g(x,y) = u(x)+v(y)+(x-y)'\mathcal{D}v(y).$$ The function $g$ is convex in $x$, and consequently the majorization algorithm in this case is exactly the CCCP.