Hulu机器学习问题与解答系列

Happy New Year!

新年伊始，我们都会在祝福他人之余，为自己暗暗定下几个小目标。那就从现在开始努力吧，跑得更快一点，才会让时间显得慢一些~

今天的内容是

【经典优化算法】

场景描述

针对我们遇到的各类优化问题，研究者们提出了多种有各自适用场景的求解算法，并逐渐发展出了有严格理论支撑的研究领域——凸优化[1]。在这众多的算法中，有几种经典的优化算法是值得被牢记的，了解它们的适用场景有助于我们在面对新的优化问题时有求解思路。

问题描述

有一道无约束优化问题摆在你面前

其中目标函数L(·) 是光滑的。请问求解该问题的优化算法有哪些？它们的适用场景是什么？

先验知识：微积分、线性代数、凸优化基本概念

解答与分析

经典的优化算法可以分为两大类：直接法和迭代法。

直接法，顾名思义，就是能够直接给出优化问题最优解的方法。这个方法听起来非常厉害的样子，但它不是万能的。直接法要求目标函数满足两个条件。第一个条件是，L(·)是凸函数。什么是凸函数呢？它的严格定义可以参见文献[1]的第3章：对任意x和y，任意0≤λ≤1，都成立

一个直观的解释是，任取函数曲面上的两点连接成线段，该线段的任意一点都不会处于函数曲面的下方，示意图如下

任取函数曲面上的两点连接成线段，

该线段的任意一点都不会处于函数曲面的下方

若L(·) 是凸函数，则文献[1]第140页的一个结论是，θ*是优化问题最优解的充分必要条件是L(·) 在θ*处的梯度为0，即

因此，为了能够直接求解出θ*，第二个条件是，上式有闭式解。同时满足这两个条件的经典例子是岭回归（ridge regression），其中目标函数为

稍加推导就能得到最优解为（要试着自己推导哟）

直接法的这两个要求限制了它的广泛应用，因此在很多实际问题中，我们会采用迭代法。这类方法迭代地修正对最优解的估计，即假设当前的估计为θt，我们希望求解优化问题

从而得到更好的估计θt+1＝θt﹢δt。迭代法又可以分为两类，一阶法和二阶法。

一阶法对函数L(θt﹢δ) 做一阶泰勒展开，得到近似式

由于该近似式仅在δ较小时才比较准确，我们可以求解带l2正则的近似优化问题

因此一阶法的迭代更新公式是

一阶法也称为梯度下减法，梯度是目标函数的一阶信息。

二阶法对函数L(θt﹢δ)做二阶泰勒展开，得到近似式

其中

是函数L(·) 在θt处的Hessian矩阵。我们可以求解近似优化问题

从而得到二阶法的迭代更新公式

二阶法也称为牛顿法，Hessian矩阵是目标函数的二阶信息。二阶法的收敛速度一般要远快于一阶法，但是在高维情况下Hessian矩阵求逆的计算复杂度更大，而且当目标函数非凸时，二阶法有可能会收敛到鞍点（saddle point）。