0 简介
Majorization-Minimization 算法在实际工程问题中是一类非常有效的算法，Majorization-Minimization 算法实际上并不是一个具体的算法，而是提供了一个算法的框架。在实际应用的过程中，需要根据自身问题的情况来确定算法框架中的各个元素。本文只是对 Majorization-Minimization 算法进行一个介绍，只给出算法的收敛性的结论，不会聚焦于证明的部分。实际上 Majorization-Minimization 算法在一些条件下是可以保证收敛性的。对理论部分感兴趣的同学可以查阅参考文献。在公众号后台回复关键词“MM”即可获得 MM 算法的详细资料。
1 Majorization-Minimization (MM) 算法基本原理
MM主要的思想呢就是我想要优化一个函数， 但是问题是直接优化这个 太难了，例如说 这个函数是个非凸的函数，我们直接求 极小化是很困难的事情。这个时候我们就想到一个思路：我们可以找另外一个函数 ，这个 是对原来的目标函数 在点 处的一个近似，这个时候我们就转而去优化 来达到优化 的目的，当然了我们对这个函数 实际上有两个要求：
最好是可微分，凸的，因为这样的话就很容易对 来求优化 是对 的一个近似，显然如果 一点也不近似于 就无法达到通过优化 来近似优化 的目的。我们可以认为 就是 的一个替身，英文就是 surrogate function
那么下图就是 和 的示意图：
假设 在A点，我们构造一个在函数上面的函数 ，我们通过找到 的最小值B点，在下一步 移动到和B横坐标一样的 C点，用表达式写出就是：
其中 表示可行域， 表示迭代次数。
那么为什么要保证 在函数 上面呢？这就是我们所说的 是的一个替身，我们极小化 就是在极小化 的上界，就是间接的在极小化 。用表达式写出就是：
从图上看呢，就是C点比B点低比A点低。这么一来，目标函数的值就不会上升了，我们期望它能下降，原理就是这么简单。算法流程也很简单如下所示：
算法1：
2 一个具体的例子
我们考虑如下优化问题：
其中
因为目标函数 是一个非凸函数，直接求解是比较困难的事情。如前所述，我们先找到 函数的一个上界函数 。由于 是一个 cancave function，所以有如下一阶条件成立：
这个条件表示的含义是 concave function 在定义域内任意一点的泰勒展开的一阶近似 总会是该函数的上界。将上式用图像表示出来就是如下图所示：
那么我们自然而然就会想到采用上式中右端项来作为 ：
进一步带入具体的函数表达式可得：
需要注意的在上式中 是当前的迭代点 是一个常数，那么上面 是关于 的一个线性函数。那么我们在算法1中的 step 3 要做的就是：
如前所示这实际上是一个线性规划问题。算法1 本质上就是每次迭代求解一个线性规划问题来近似逼近原来的目标函数。
从上面的例子看出如果目标函数是一个 concave function 是很容易构造出 的。然而对于一般的问题而言 Majorization-Minimization 关键点就在于如何构造出 函数。
3 Majorization-Minimization 理论性保证
Majorization-Minimization 简单易行，当然大家也会问那么 Majorization-Minimization 算法是否可以保证收敛到全局最优呢？
答案是在选取合适的条件的 函数的情况下（具体什么条件我放到文末 A1-A4 供大家参考），Majorization-Minimization 算法可以保证收敛到 stationary point，也就是说 Majorization-Minimization 算法是无法保证一定能收敛到全局最优的，有可能收敛到局部最优 也有可能收敛到 saddle point
4 总结
在很多非凸问题上 Majorization-Minimization 算法收敛速度是非常快的，而且可以保证拿到一个数值上还不错的解，因此 Majorization-Minimization 是比较实用的一套求解非凸优化的套路。
关于 Majorization-Minimization 算法 详细深入的教程 可以在公众号后台回复“MM” 获取Majorization-Minimization 算法的详细资料。
参考文献：
【1】工程中的非凸优化利器：Majorization-Minimization：https://zhuanlan.zhihu.com/p/107204751
【2】 工程中的非凸优化利器：Successive Convex Approximation
【3】 Sun Y, Babu P, Palomar D P. Majorization-minimization algorithms in signal processing, communications, and machine learning[J]. IEEE Transactions on Signal Processing, 2016, 65(3): 794-816.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：王源
微信编辑：疑疑
文章转载自『科研式学习』公众号，原文链接：非凸优化问题的大杀器：Majorization-Minimization 算法
关注我们
FOLLOW US
