Skip to main content

MM Algorithm

· 4 min read
PuQing
PuQing
AI, CVer, Pythoner, Half-stack Developer
info

The MM algorithm is an iterative optimization method which exploits the convexity of a function in order to find its maxima or minima. The MM stands for “Majorize-Minimization” or “Minorize-Maximization”, depending on whether the desired optimization is a minimization or a maximization. Despite the name, MM itself is not an algorithm, but a description of how to construct an optimization algorithm.

MM 算法原理​

MM 主要的思想是 非凸函数 太难优化了，我们就构造一个 “ 代理模型 ” ，通过迭代优化该函数达到优化的目的。

以最小化为例： Untitled.bmp

关于 Q(x,xk)Q(x,x_{k})

这样的写法可能会很奇怪，其中第一个 xx 是函数自变量，第二个 xkx_{k} 是指示第 kk 个代理函数，下面的写法可能会更清晰：

Q(x,xk):=Qxk(x)Q(x,x_{k}):= Q_{x_{k}}(x)

假设 x0x_{0} 在 AA 点，函数 ff 很难最小化，我们就构造一个在此时好优化并且在它上面的函数 QQ，我们找到 QQ 的最小值点 BB，然后下一步 x1x_{1} 移动到和 BB 横坐标一样的点 CC，用表达式表达为：

xk+1=arg⁡min⁡x∈DQ(x,xk)x_{k+1} = \arg \min_{x \in \mathcal{D}} Q(x,x_{k})
tip

而在上面更加形式化的表述为

Q(x,xk)≥f(x)for all xQ(xk,xk)=f(xk)\begin{aligned} &Q(x,x_{k}) \geq f(x)\quad \text{for all x} \\ &Q(x_{k},x_{k}) = f(x_{k}) \end{aligned}

这样，通过构造

f(xk+1)≤Q(xk+1,xk)≤Q(xk,xk)=f(xk)f(x_{k+1}) \leq Q(x_{k+1},x_{k})\leq Q(x_{k},x_{k}) = f(x_{k})

这样的过程将会保证 f(xk),x→∞f(x_{k}),x\to\infty 会收敛到局部最优或者鞍点

而 MM 算法的名字也很有意思

info

最大化：Minorize-Maximization\text{Minorize-Maximization}

最小化：Majorize-Minimization\text{Majorize-Minimization}

导出算法​

MM 原理很简单，但是如何构造 QQ 是一大问题，这里介绍两种构造 QQ 函数的方法——泰勒展开和凸不等式

泰勒展开法​

一阶展开​

info

对于一个 Minimization\text{Minimization} 问题

假设有函数 f:Rn→Rf:\mathbb{R}^n\to \mathbb{R}，n∈Nn\in \mathbb{N}，假设这个函数 f(x)=g(x)−h(x)f(\mathbf{x})=g(\mathbf{x})-h(\mathbf{x})，其中 g(x)g(\mathbf{x}) 和 h(x)h(\mathbf{x}) 都是凸函数，于是我们称这里的 f(x)f(x) 为 Difference of Convex Function\text{Difference of Convex Function}。很明显的是我们无法判定 f(x)f(\mathbf{x}) 的凸性。因为，g′′(x)≥0g''(\mathbf{x})\geq 0，h′′(x)≥0h''(\mathbf{x})\geq 0，所以 f′′(x)f''(\mathbf{x}) 的正负性是不知道的。

所以这是一个非凸优化

min⁡x∈Dg(x)⏟convex +−h(x)⏟concave \min _{x \in \mathcal{D}} \underbrace{g(x)}_{\text {convex }}+\underbrace{-h(x)}_{\text {concave }}

然后使用一阶展开将 h(x)h(\mathbf{x}) Minorize\text{Minorize}

xk+1=arg⁡min⁡x∈Dg(x)−[h(xk)+⟨∇h(xk),x−xk⟩]x_{k+1} = \arg \min_{x \in \mathcal{D}} g(x) - \left[ h(x_{k}) + \left \langle \nabla h(x_{k}),x-x_{k} \right \rangle \right]

这样每次迭代解一个凸问题就好

warning

值得注意的是，其实是利用的 Fenchel Conjugate Function

相关资料​