凸优化系列一:什么是最优化算法

1.优化问题的一般形式

最优化问题的一般数学形式为: m i n f ( x ) s . t . x ∈ X min f(x) \ s.t. quad x in X minf(x)s.t.x∈X 其中， x ∈ R n x in R^n x∈Rn为自变量， f ( x ) f(x) f(x)为目标函数， x ⊂ R n x subset R^n x⊂Rn为约束集或者说可行域。 如果上面的优化问题中， s . t . x ∈ X s.t. x in X s.t.x∈X这部分约束内容没有，这个优化问题就叫做无约束优化。如果有，那这个优化问题叫有约束优化。如果约束内容里面包含的全是等式，那就叫做等式约束。如果包含不等式，则叫做不等式约束。

2.最优化方法的定义

一般优化问题的解法就叫做最优化方法。 实际中的问题一般都比较复杂，不太可能有直接的解析解。所以通常的解法都是采用迭代的方式求它的最优解。基本的步骤是:给定一个初始点 x 0 ∈ R n x_0 in R^n x0∈Rn，按照某一个迭代规律产生一个点序列 x k x_k xk，使得当 x k x_k xk是有穷点序列时，最后的点就是最优化问题的最优解。而当 x k x_k xk是无穷序列点时，它有极限点，而且该极限点就是最优化问题的最优解。 好的算法应该具备的典型特征为：迭代 x k x_k xk能稳定地接近局部极小值点 x ∗ x_* x∗的邻域，然后迅速收敛于 x ∗ x_* x∗。当给定的某个收敛准则满足时，迭代终止。

如果用数学语言来描述，设 x k x_k xk为第k次迭代点， d k d_k dk为第k次的搜索方向， α k alpha_k αk为第k次步长因子，那么第k次迭代的表达式为: x k + 1 = x k + α k d k x_{k + 1} = x_k + alpha_kd_k xk+1=xk+αkdk

接下来的工作就是调整 α k d k alpha_kd_k αkdk这一项，不同的步长 α k alpha_k αk与不同的搜索方向 d k d_k dk就分别构成了不同的最优化方法。

当然 α k alpha_k αk与搜索方向 d k d_k dk需要满足一些条件。毕竟是求极小值，不能越迭代越大。比如下面是一些条件 ∇ f ( x k ) T d k < 0 f ( x k + α k d k ) < f ( x k ) abla f(x_k) ^ T d_k < 0 \ f(x_k + alpha_kd_k) < f(x_k) ∇f(xk)Tdk<0f(xk+αkdk)<f(xk)

上面的式子说明搜索方向必须跟梯度方向的夹角大于90度。因为梯度的方向一般是使目标函数增大。如果不增大，说明目标函数已经到了极值。所以当搜索的方向与梯度方向大于90度的时候，就能保证是向目标函数值更小的方向搜索。 而下面那个式子的意义就很明确了，迭代的下一步的目标函数必须比上一步要小。

最后总结一下最优化方法的基本结构为: 先给点初始点 x 0 x_0 x0 1.按照一定规则，确实搜索方向 d k d_k dk，构造目标函数f在 x k x_k xk点处的下降方向为搜索方向。 2.确定步长因子 α k alpha_k αk，使目标函数值具有某种意义的下降。 3.令 x k + 1 = x k + α k d k x_{k + 1} = x_k + alpha_k d_k xk+1=xk+αkdk 若 x k + 1 x_k+1 xk+1满足某种终止条件，则停止迭代，得到近似最优解 x k + 1 x_{k + 1} xk+1。否则重复上述步骤。 而能不能收敛到最优解是衡量最优化算法的有效性的一个重要方面。

3.收敛速度

除了能不能收敛，收敛速度也是最优化方法有效性的一个重要因素。 设有相邻的两个迭代点分别为 x k x_k xk与 x k + 1 x_{k+1} xk+1，假设最优解为 x ∗ x^* x∗，弱存在实数q>0，且有: lim ⁡ k → ∞ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ = q limlimits_{k ightarrowinfty}frac{|x_{k+1}-x^{*}|}{|x_{k}-x^{*}|}=q k→∞lim∥xk−x∗∥∥xk+1−x∗∥=q

如果0<q<1，表示算法线性收敛。 如果q=0，表示算法超线性收敛。

举个例子，有如下数列： a 1 = 1 , a 2 = 1 2 , a 3 = 1 4 , ⋯   , a k = 1 2 k − 1 , ⋯   , a ∞ = 0 a_1 = 1, a_2 = frac{1}{2}, a_3 = frac{1}{4}, cdots, a_k = frac{1}{2 ^ {k-1}}, cdots, a_{infty} = 0 a1=1,a2=21,a3=41,⋯,ak=2k−11,⋯,a∞=0 根据上面的计算公式，易知 q = 1 2 q = frac{1}{2} q=21，因此该数列为线性收敛。

参考文献: 1.袁亚湘. 非线性优化计算方法