交替极小化算法(Alternating Minimization, AM算法)

AM算法：给定一个初值，交替的固定一个变量，优化其他的，主要求解无约束优化．
对于二元函数，AM算法在双稳定点（bistable　point）停止，但有两个问题需要考虑的
１）收敛到双稳定点的速度，即算法收敛阶
２）收敛到的双稳定点是否是全局最小点
AM算法迭代没有参数，不必花时间调整参数，但也意味着用户对算法进程控制更少．AM算法的收敛性完全依赖优化问题的结构性质．
有界目标函数有多个双稳态点，AM最终收敛的稳定点取决于初始点的位置．
当AM算法求解学习隐变量模型，矩阵填充（子问题是边缘凸），相位恢复问题时，特别注意初始值接近最优点．而对于鲁棒回归（robust　regression），　只有一个稳定点，所以对初值没有太多要求．
AM对于凸问题：
（１）凸可微函数，所有双稳定点都是全局最小点．这与求解大规模凸优化问题的坐标极小化算法很类似（coordinate　minimization）但是AM可以求解不可微的目标函数．（CM其实也可以，不过需要目标函数满足其他的性质, P. Tseng 2001, Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization）(非凸非光滑)
（２）凸，连续可微，边缘强光滑（二次函数做上界），初值＝（０，０），可证明 $\mathcal{O}(\frac{1}{\epsilon })$ 次迭代可达到误差 $\epsilon$. 具体定理描述见Prateek Jain, Purushottam Kar《Non-convex Optimization for Machine Learning》的总结整理(2)的定理4.1.

AM对于非凸问题：
（１）对于边缘凸函数，双稳态点等价于稳定点
（２）鲁棒双稳态性（robust bistability property）

右边：通过边缘优化，目标函数局部降低，性质表明，如果目标函数局部不怎么下降了，则接近最优值了．定义有个推论：满足鲁棒双稳态性质的函数，所有的双稳态点都能达到最优函数值．这个推理可由定义４.&#x