Month: April 2018

Convex-Concave Procedure

The section 1 of paper “Variations and extension of the convex–concave procedure” provides an overview of convex-concave problem . The convex-concave procedure (CCP) is a heuristic method used to find local optimum solutions to difference of covex (DC) programming problems.

Difference of convex programming

Consider DC programming problems as the form below

minimize { f }_{ 0 }(x)-{ g }_{ 0 }(x)

subject to { f }_{ 1 }(x)-{ g }_{ 1 }(x) \le  0,\quad i=1,...m, 

where x\in { R }^{ n } is the optimization variable and { f }_{ i }:{ R }^{ n }\rightarrow R and { g }_{ i }:{ R }^{ n }\rightarrow R for i=0,...,m are convex. Both fuction { f }_{ 0 }(x) and { g }_{ 0 }(x) should be affine to make sure DC program is convex.

What if the objective and contraint fuctions are not convex? For example, the Boolean LP probem proposed in this section and the traveling salesman probelm, no polynomial time algorithm is known and are hard to solve. So here convex-concave procedure (CCP) is presented for finding a local optimum to solve convex-optimization problems.

Assuming that all of the { f }_{ i } and { g }_{ i } are differentiable for the ease of notation. The basic CCP algorithm has the form of gradient desent algorithm with convexify. The procedure is choosing an initial feasible point  randomly or through a heuristic if one is known. Then iterates convexity until the stopping criterion is satisfied. in each iteration the { g }_{ i }   is replaced with its first-order Taylor approximation, which makes the final problem convex and effcient to solve.  The key procedure is convexification, which is shown below

  • Convexify: \hat { g } (x;{ x }_{ k })\equiv { g }_{ i }({ x }_{ k })+\triangledown { { g }_{ i }({ x }_{ k }) }^{ T }(x-{ x }_{ k })\quad for\quad i=0,...,m
  • Solve: Set { x }_{ k+1 } to the solution of the original problem
  • k=k+1

In the paper, one reasonal stopping criterion is proposed as { (f }_{ 0 }({ x }_{ k })-{ g }_{ 0 }({ x }_{ k }))-{ (f }_{ 0 }({ x }_{ k+1 })-{ g }_{ 0 }({ x }_{ k+1 }))\le \delta , where \delta is threshold. Here as we discussed in the class, the stop criterion can be further improved.

The paper proves that each iteration of the algorithm produces a feasible point. It also shows that the convex-concave procedure is indeed a descent algorithm. However, the proof of convergence is ambiguous as negative infinity does not exist. The section 1 provides us an idea to generally convert problem with non-convex contraints to one that can be solved using convex optimzation. The basic idea is to minimize a function, usually use linear approximations to the contraints.

Then the authors go on to show the advantages of CCP which are retaining more information in each of the iterates and are global wihout requiring trust regionswhich limit progress at an iteration to a region where the approximation is valid. The proof of this is shown

convexification at { x }_{ k } : replace f(x)-g(x) with

\hat { f } (x)\quad =\quad f(x)-g({ x }_{ k })-\triangledown { g({ x }_{ k }) }^{ T }(x-{ x }_{ k })

Since \hat { f } (x)\ge f(x) for all x, no trust region is needed.

  • true objective at \tilde { x } is better than convexified objective
  • true feasible set contains feasible set for convexified problem