非凸优化入门

广义上来讲，如果一个优化问题的目标函数是凸函数且可行域是凸集，那么它就是一个凸优化问题。反过来讲，如果不满足两个条件中任意的一个，即目标函数非凸或者可行域非凸，那么它就是一个非凸优化问题。

解：

• 局部极小点: ∇f(x)=0,∇2f(x)>0

• KKT点

• 一阶驻点(First-order stationary point, FOSP)，或者说关键点(Critical point)：∇f(x)=0。

• 二阶驻点(Second-order stationary point, SOSP)：∇f(x)=0,∇2f(x)≥0。二阶驻点一定是局部极小点，但比局部极小点更好一些。

  not just local minima; as good as global minima.

  对于部分优化问题而言，二阶驻点即为全局极小点，如矩阵分解问题。

算法：

• Perturbed push-sum algorithm
• Successive convex approximation

[1] Understanding Non-convex Optimization