1. 基于DC 分解：CCCP / DCA 到底是什么
这两个东西高度相关。
- DCA = Difference of Convex Algorithm
- CCCP = Convex-Concave Procedure
它们都建立在一个核心表示上：
把原目标函数写成
其中 都是 凸函数。
2. DCA 的基本迭代公式
如果
那么在第 步，先取
也就是 在 处的一个次梯度。
然后解下面这个问题：
注意这里发生了什么：
- 原来难的是
- 现在把 在 处线性化成
- 于是子问题变成
这仍然是 凸优化问题。
因为“凸函数 - 线性函数”还是凸的。
这就是 DCA 的本质。
3. CCCP 和 DCA 的关系
如果函数可微，而且你把问题写成
那么每一步对 concave part 做一阶线性化，这就是 CCCP。
所以你可以粗略理解为：
- DCA：更一般，允许非光滑，用 DC 语言表述
- CCCP：更常见于可微情形，用“凸-凹分解”表述
很多地方你甚至可以把它们看成同一家族。
4. 它能保证什么，不能保证什么
能保证的
通常可以保证：
- 目标值下降
- 迭代点收敛到某个驻点、临界点，或局部稳定点附近
- 每步子问题都是凸的，容易算
不能保证的
一般 不能保证全局最优。
因为原问题还是非凸的。
你只是把它拆成了一串凸子问题来做局部推进，而不是把整个非凸性消灭了。
所以 CCCP / DCA 的本质是：
把“难的非凸问题”转成“一连串好解的凸问题”，从而求得一个较好的局部解。
5. 一个简单例子
考虑
这个函数显然非凸。
我们把它写成 DC 形式：
设
则 都是凸函数，所以
是一个 DC 分解。
在当前点 处，
于是下一步解：
这已经是一个凸问题了，因为
对 是凸的。
所以原来的非凸优化，就变成了 不断求解凸子问题。