大扯闲话之--优化算法Difference of Convex Algorithm （DCA）

发布时间：2024-04-22 14:25:49

非凸优化一直是最常见，最蛋疼的一个问题。

今天介绍的这种算法，Difference of Convex Algorithm，也就是DCA，以便咱们解决非凸优化问题。

但这种问题仅仅针对某些特定情况。

首先，咱们对这串英文进行解读，Difference理解为差，convex是凸，即凸函数，algorithm嘛，你们自己查词典，哈哈哈。所以呢，DCA就是两个凸函数的差的算法。

你们肯定懵逼了，啥凸函数的差？Emmm，

设有个函数为 $f: \\mathbb{R}^n\\rightarrow \\mathbb{R},\\quad n \\in \\mathbb{N}$ ，假设这个函数 $f(\\mathbf{x})=g(\\mathbf{x})-h(\\mathbf{x})$ ，其中 $g(\\mathbf{x})$ 和 $h(\\mathbf{x})$ 都是凸函数，那么就可以说 $f(x)$ 是个DC function。很明显，我们无法判定 $f(\\mathbf{x})$ 的凸性。因为， $g''(\\mathbf{x}) \\leq 0$ ， $h''(\\mathbf{x}) \\leq 0$ ，所以， $f''(\\mathbf{x})$ 的正负性咱不知道，所以，它是不是凸的呢？咱不知道。

这就诡异了，既然不知道它的凸性，求个鬼头啊？？？

没法了，只能派上大将DCA（不小心点题了）。

在了解DCA之前，先介绍个之后有用的东西。啥？Fenchel Conjugate Function，这又是啥？参见下式：

$f^{*}(\\mathbf{y})=\\arg \\min \\left( f(\\mathbf{x}) - \\left< \\mathbf{x}, \\mathbf{y}\\right> \\right)$ ,

其中， $<,>$ 这玩意儿代表的是内积，不知道内积是啥的，拖出去暴打半小时。

好啦，不好意思就等啦。下面说说DCA这个算法。假设有个函数 $f(\\mathbf{x})$ 是DC function，而咱们又要优化它，咋写呢？

$\\min \\quad f(\\mathbf{x})=g(\\mathbf{x}) - h(\\mathbf{x})$

其中 $g(\\mathbf{x})$ 和 $h(\\mathbf{x})$ 均为凸函数。那么DCA算法过程如下：

输入 $\\mathbf{x}_1 \\in D$ 位于定义域内， $N$ 为自然数，表示为迭代次数。
进行迭代，用“for k=1:N”，循环体内的内容为 $\\mathbf{y}_k \\in \\partial h(\\mathbf{x}_k)$ ， $\\mathbf{x}_{k+1}\\in \\partial g^*(\\mathbf{y}_k)$ 。注意的是N的值越大，收敛性越强。
输出 $\\mathbf{x}_{N+1}$ 。

举个栗子， $\\min \\quad f(x)=x^4 - 3x^2 -x$ ，令 $g(x)=x^4$ ， $h(x)=3x^2+x$ ，显然 $g(x)$ 和 $h(x)$ 均为凸函数。所以， $\\partial h(x)=6x+1$ ， $\\partial g^*(y)=\\arg \\min \\limits_y \\left( x^4-xy \\right)=\\sqrt[3]{\\frac{y}{4}}$ 。

所以 $x_{N+1}=\\sqrt[3]{\\frac{6x_N + 1}{4}}$ 。

Emmm，严肃的话题说完了，我其实扯了这些，就是直接说了DCA这个算法，至于细节与证明啥的，建议大家看看原文叭。

^[1]^[2]

上一篇：优化营商环境激发市场活力（坚定信心开局起步）
下一篇：MATLAB优化算法（第2版）返回列表

华体会动态

大扯闲话之--优化算法Difference of Convex Algorithm （DCA）