MM 优化框架

基本原理

Majorization-Minimization优化框架在各类算法中很常见。在目标函数$J(x)$难优化时，可以寻找一个容易优化的目标函数$G(x)$，当$G(x)$满足一定条件时，$G(x)$的最优解能无限逼近$J(x)$的最优解。

$G(x)$应该满足的条件

容易优化
$G_k(x)\ge J(x)$
$G_k(x_k)=J(x_k)$

优化过程

考虑一个优化问题，$\mathscr X$为闭凸集、$J(\mathbf x)$连续

$$ \min_\mathbf x J(\mathbf x)\quad \text{s.t.} \quad x \in \mathscr X. $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


\begin{algorithm}
\caption{Majorization Minimization}
\begin{algorithmic}
    \STATE 寻找一个可行点$x^0 \in \mathscr X，k \gets 0$
    \REPEAT
        \STATE $\mathbf x^{k+1}=\arg\min_{x\in \mathscr X} G_k(\mathbf{x})$
        \STATE $k\gets k+1$
    \UNTIL{满足一些条件}
\end{algorithmic}
\end{algorithm}