首页 > 代码库 > 无约束最优化约束

无约束最优化约束

无约束最优化概述

无约束最优化的基本问题是要解决如下的问题: $$ argmin_x \; f(x) $$ 在这里要求$ f(x) $是连续且可导的。

优化的基本策略

如果优化问题不能够直接求解,那么解决问题的方法只有通过不停的迭代。迭代的基本方式如下:

  1. 设置初始点 $ x_0 $,同时设置迭代计数器 $ i = 0 $ ;
  2. 根据当前点 $x_i$ 的$ Gradient,Hessian$ 或者是之前点的信息计算得优化方向$ d_i $
  3. 计算优化方向 $ di $ 对应的步长 $ \alphai $,然后获得下一个点 $ x{i+1} = xi + \alphai di $
  4. 计算当前点 $ x_{i+1} $ 是否收敛,如果收敛则获得答案,否则转回步骤2。

在这样的计算框架中,基本可以分解成三部分,第一是是产生优化方向,第二是计算步长,第三是检查整个过程是否收敛。一个完成的优化算法就是由这三个部分组成的。计算步长的过程基本可以独立于第一步,第三步和第一步是整个算法最密切相关的。

对一个算法的评估包括以下几个方面,首先是算法的收敛速度如何,然后是算法的计算复杂度是多少,最后会考虑算法的稳定性。稳定性的考虑是因为算法的解决依赖于数值计算方法,如果算法不稳定,那么会导致一个理论可行的算法不能给出最优解甚至不能解决问题。

$ Gradient Descent $

梯度下降法的推到特别简单,使用泰勒一阶展式即可: $$ f(xk + dk) = f(xk) + \nabla f(x) ^ T dk + o $$ 在这里 $ O $ 代表一个低阶项,先在足够近的情况下可以直接忽略。使用这样的近似,可以看出如果想要减小函数值,那么选择$ \; d_k \; $为 $ - \nabla f(x) $即可,当 $ \nabla f(x) $ 为0时,函数值无法再减小,因此可以使用 $ \nabla f(x) $ 作为终止条件。由于使用的是一阶展式,如果步长过大,那么这样的近似就可能是错误的。而且梯度下降法在问题的规模较大时需要花费很长的时间收敛,因此在现实中几乎不可用。

$ Newton Method $

牛顿法可以使用泰勒二阶展式推到: $$ f(xk + dk) = f(xk) + \nabla f(x) ^ T dk + 1/2 \cdotp dk ^ T Hk dk + o $$ 对这个二阶的问题优化,对右边的等式求导并令其倒数为0,可获得方向 $ dk = - Hk ^ {-1} \nabla f(x) $。迭代的停止条件可以选择是$ \nabla f(x) $或者是 $ \nabla f(x) ^ T Hk \nabla f(x) $,如果这两个数值小于一定的程度,那么可以考虑将算法收敛。牛顿法最大的问题就在于海森矩阵的计算,如果问题的规模较大,而且没有特殊的结构可以使用,牛顿法就是不可使用的。

$ Quasi-Newton Method $

牛顿法具有二次收敛速度,但是需要计算 $ Hk $,因此拟牛顿法的提出是为了解决这个问题。在拟牛顿法中不显示的计算海森矩阵,而且从每一步的迭代信息中构造海森矩阵的一个近似,替代真实的海森矩阵去计算优化方向。在牛顿法中迭代方向计算是 $ dk = - Hk ^ {-1} \nabla f(xk) $,现在计算方法如下 $ dk = - Bk \nabla f(xk) $。为了唯一的求得矩阵$ Bk $,我们必须施加一定的限制。假设当前点为$ xk $,迭代方向是$ \alphak dk $,下一个迭代点 $ x{k+1} = xk + \alphak dk $,在点 $ x{k+1} $ 上构造近似如下: $$ f(p) = f(x{k+1}) + \nabla f(x{k+1}) ^ T p + 1/2 p ^ T B{k+1} p $$ 对这个函数求导可得 $ \nabla f(p) = B{k+1} p \; +\; \nabla f(x{k+1}) $,如果将$ p = xk - x{k+1} $,那么近似函数的倒数应该等于函数$ f(x) $ 在 $ xk $ 处的导数$ \nabla f(xk) $: $$ \nabla f(xk) = B{k+1}p +\nabla f(x{k+1}) $$ 定义$ sk = x{k+1} - xk; yk = \nabla f(x{k+1}) - \nabla f(xk) $,那么上述公式可以写成如下形式: $$ B{k+1} sk = yk $$ 事实上如果要求 $ B{k+1} $ 是 $ Hk $ 的近似,那么应该满足如下的等式要求: $$ B{k+1} si = yi \quad (i =0, 1, ..., k) $$ 因此为了获得$ B{k+1} $,我们需要优化如下的问题: $$ argminB \left|| B - Bk \right|| $$ $$ s.t. B = B ^ T ; B sk = yk $$ 使用不同的范数,可以获得不同的由 $ Bk $ 产生 $ B_{k+1} $的方法。

$ SR1 \; Update $

全称是Symmetric Rank 1 updae, 具有如下形式的迭代: $$ B{k+1} = Bk + \alpha \beta \beta ^ T $$ 这里主要的问题就在于如何计算这个修正项。 (skip )

$ DFP & BFGS Update $

对应的是两个不同的更新规则,但是这里使用的是Rank 2更新。 Wikipedia

$ L-BFGS Update $

在BFGS更新的基础上,只保留最近几个迭代的信息用于计算海森矩阵的近似。可以适用于大规模的数据优化。在这个算法中不需要显示的构造矩阵 $ B_k $ 即可完成迭代方向的计算。

$ Conjugate \; Gradient $

共轭梯度法本来是为解方程 $Ax = b$ 提出的,但是最后发现也可以使用到一般的函数优化中。 共轭梯度法就是在一组相互共轭的方向上优化目标函数,知道目标函数达到最优点。 两个向量共轭定义如下: $$ v ^ T H \mu = 0 $$ 其中矩阵H是正定矩阵。如果一组向量共轭,那么意味着这组向量中任意两个向量都是共轭向量。可以证明对于二次函数 $ 1/2 x ^ T A x + b ^ T x $来说,沿着一组有n个向量的方向优化,那么最终可以到达最优点。对于共轭梯度来来说,产生新的迭代方向使用如下的公式: h $$ d{k+1} = - \nabla f(x{k+1}) + \beta dk $$,也就是实现当前点的梯度和之前的迭代方向来产生新的优化方向 $d{k+1}$。相比于其他的方法,共轭梯度法使用更少的内存,这是很大的优势。

评价

从数值优化的角度,梯度下降法几乎不可用,因此对于实际的问题可能需要很长的时间去迭代。但是对于机器学习来说,这却不是问题,因为机器学习方法并不对解的精度有要求,唯一的要求是泛化性能。牛顿法具有二阶收敛速度,但是由于需要使用很多的内存,因此在实际中很少使用。拟牛顿法和L-BFGS方法,由于需要的内存较少,而且可以实现超线性的收敛,在实践中被广泛使用,特别是L-BFGS。