Variations and Extensions of the Convex-Concave Procedure

T. Lipp and S. Boyd

Optimization and Engineering, 17(2):263-287, June 2016.

We investigate the convex-concave procedure (CCP), a local heuristic that utilizes the tools of convex optimization to find local optima of difference of convex (DC) programming problems. The class of DC problems is very general, and includes difficult problems such as the traveling salesman problem. We extend the standard procedure in two major ways and describe several variations. First, we describe a method that allows the algorithm to be initialized without a feasible point. Second, we generalize the algorithm to include vector inequalities. We then present several examples to demonstrate these algorithms.