最优化算法：无约束优化

无约束优化

无约束优化：为定义在上的可微函数。
无约束优化要求求解

$\min_{x\in\mathbb{R}^n}f(x)$

线性回归

试图学得一个线性模型，通过因素、属性或者说特征的线性组合，来尽可能准确地预测实际输出值，即寻求线性函数

$f(\boldsymbol{x})=\boldsymbol{w}^T\boldsymbol{x}_i+b$

基于均方误差最小化来进行模型求解的方法也被称为“最小二乘法”(least square method)。

带正则项的线性回归

范数正则项：如果想要得到一个稀疏的解，就是解中非零分量的个数尽可能少，可借助或者范数。

$\min_{\widehat{\boldsymbol{w}}\in\mathbb{R}^{l+1}}\|X\widehat{\boldsymbol{w}}-\boldsymbol{b}\|_2^2+\mu\|\widehat{\boldsymbol{w}}\|_1^2$

其中被称为正则项，上述模型也被称为LASSO (Least Absolute Shrinkage and Selection Operator)

岭回归： 为了平衡模型的拟合性质和解的光滑性，还可以用正则项

$\min_{\widehat w\in\mathbb{R}^{l+1}}\|X\widehat{\boldsymbol{w}}-b\|_2^2+\mu\|\widehat{\boldsymbol{w}}\|_2^2$

通过设置合适的值，上述目标函数可以变成严格凸函数，使得解性质得到改善。

无约束优化最优性条件

一阶必要条件（FONC）

一阶必要条件：设一阶连续可微。如果是局部极小点，则

$\nabla f(\boldsymbol{x}^*)=0$

利用一阶泰勒展开式证明即可。

注意：

驻点（平稳点）是一阶导数为的点。
极大值、极小值、鞍点都可能是平稳点。

二阶必要条件（SONC）

二阶必要条件：设二阶连续可微。如果是局部极小点，则

$\nabla f(\boldsymbol{x}^*)=0\text{且}\nabla^2f(\boldsymbol{x}^*)\text{是半正定}$

证明：如果非半正定，则存在，使得，然后用二阶泰勒展开即可。

二阶充分条件（SOSC）

设二阶连续可微。如果点满足 $且$ 正定，则

$\boldsymbol{x}^* \text{是一个严格极小点}$

证明：根据泰勒级数，领域内任意一个值都要比它更大，即

$f(x^*+\alpha d^*)=f(x^*)+\frac12\alpha^2d^T\nabla^2f(x^*)d+o(\alpha^2)>f(x^*)$

注意：SOSC不是必要条件。

凸函数最优性条件

凸优化能保证驻点为局部极小点，也就是全局极小点。

无约束凸优化 : 设凸函数在上连续可微，则存在使得是全局最优解。

证明：

根据凸函数性质，对于任意点,有

$f(x)-f(x^*)\geq\nabla f(x^*)(x-x^*)=0$

因此。是全局最优解

是全局最优解，则必然也是局部最优解，由FONC可得。

下降法

难以求解获得平稳点时，采用更常见的无约束求解方法：下降算法

步骤：

首先确定目标函数的极小点的一个初始估计 : 。
然后按照一定规则产生一个下降方向。
再沿方向，求得下一个迭代点即在射线上确定一个新点：，使得，其中称为步长因子。
若满足停机条件则输出，否则，转到第二步

注意：机器学习中也常常被称为学习率。

下降方向

下降方向：设函数，点和某个向量，如果存在，使得，则为下降方向。由泰勒展开式，即存在使得

$f(x^{(k)}+\alpha d)=f(x^{(k)})+\alpha\nabla f\left(x^{(k)}\right)^Td<f(x^{(k)})$

因此 $\boldsymbol{d}$ 是 $f$ 在 $\boldsymbol{x}^{(k)}$ 的下降方向 $\rightarrow$ $\boldsymbol{d}$ 满足 $\nabla f(\boldsymbol{x}^{(k)})^T\boldsymbol{d}<0$ 。

负梯度 $-\nabla f(x^{(k)})$ 就是一个的下降方向。

确定步长因子

固定步长
衰减步长因子：$\alpha_k=\alpha_0\gamma^{k-1}$ ，其中 $\gamma\in(0, 1]$
精确/近似线搜索：$\phi_k(\alpha)=f(x^{(k)}+\alpha p^{(k)})$ ，则 $\alpha_k=arg\min_{\alpha\geq0}\phi_k(\alpha)$ 。

精确线搜索

性质：由于 $\alpha_k=arg\min_{\alpha\geq0}f(x^{(k)}+\alpha d^{(k)})$ ，对 $\alpha$ 求导得：

$\phi^\prime_k(\alpha)=\nabla f\left(\boldsymbol{x}^{(k+1)}\right)^T\boldsymbol{d}^{(k)}=0$

换句话说，在精确线搜索中，在处的梯度和方向正交。

近似线搜索

充分下降条件 (Amijo条件)

选择常数（通常），满足

$\phi_k(\alpha_k)\leq\phi_k(0)+\beta\alpha_k\phi^{\prime}_k(0)$

回溯线搜索

为了满足我们可以以大的步长开始，并且通过恒定的缩减因子将其减小至满足充分下降条件。因为该算法沿着下降方向回溯，所以被称为回溯线搜索。

曲率条件

Amijo条件不足以保证收敛到局部极小值。非常小的步长可以满足第一个条件，但可能致过早收敛。

曲率条件（第一WOLF条件）

$\phi'_k(\alpha)\ge \eta\phi'_k(0)$

其中控制下一个方向导数的深度。上述条件要求下一次迭代时的方向导数曲率更小。

强曲率条件（第二WOLF条件）

$|\phi'_k(\alpha)|\ge \eta|\phi'_k(0)|$

停机条件

限制迭代次数
$或$

一阶方法

共轭梯度法

共轭定义：设且, 对于方向，如果对于所有的都有，则称它们是关于共轭的。

二次型下的共轭方向法

针对，的闭式解：

令，则

$\phi^\prime(\alpha)=\nabla f\Big(\boldsymbol{x}^{(k)}+\alpha \boldsymbol{d}^{(k)}\Big)^T\boldsymbol{d}^{(k)}=\boldsymbol{d}^{(k)T}(Q\boldsymbol{x}^{(k)}+\alpha Q\boldsymbol{d}^{(k)}-\boldsymbol{b})$

再由 FONC 得

$\alpha_k = arg\min \phi(\alpha)=-\frac{\boldsymbol{d}^{(k)T}(Q\boldsymbol{x}^{(k)}-\boldsymbol{b})}{\boldsymbol{d}^{(k)T}Q\boldsymbol{d}^{(k)}}=-\frac{\boldsymbol{g}^{(k)T}\boldsymbol{d}^{(k)}}{\boldsymbol{d}^{(k)T}Q\boldsymbol{d}^{(k)}}$

证明：由于方向线性无关，存在满足：

$\boldsymbol{x}^* - \boldsymbol{x}^{(0)}=\beta_0\boldsymbol{d}^{(0)} + \dots + \beta_{n - 1}\boldsymbol{d}^{(n - 1)}$

……

找出一组共轭的向量

共轭梯度法：利用上一次搜索方向和目标函数在当前迭代点的梯度向量之间的线性组合构造一个新方向，即，使其与前面已经产生搜索方向组成共轭方向。

初始方向：

时：

$d^{(0)}=-\nabla f\left(x^{(0)}\right)=-g^{(0)}$

那么，其中

时 : 设第次的方向为 , 第次的梯度是，设

$d^{(k)}=-g^{(k)}+\beta_{k-1}d^{(k-1)}$

为了使和关于共轭 , 应有

$(d^{(k)})^TQd^{(k-1)}=-(g^{(k)})^TQd^{(k-1)}+\beta_{k-1}(d^{(k-1)})^TQd^{(k-1)}=0$

因此

$\beta_{k-1}=\frac{\left(g^{(k)}\right)^TQd^{(k-1)}}{\left(d^{(k-1)}\right)^TQd^{(k-1)}}$

对于，共轭梯度法的搜索方向是关于的共轭方向。

二阶方法

问题：假设二阶可微，要求找出的局部极小点：

$\min f(x)\\x\in\mathbb{R}^n$

牛顿法

算法流程：

选定初始点 $，$
通过计算。
确定下一个迭代点是否满足停机规则。

拟牛顿法

。

是对的近似矩阵，对称矩阵。

秩一修正法：构造

由于故名曰秩一修正法。

再根据拟牛顿条件，其中可推出下式。

$H_{k+1}=H_k+\frac{(\Delta x^{(k)}-H_k\Delta g^{(k)})(\Delta x^{(k)}-H_k\Delta g^{(k)})^T}{\Delta g^{(k)T}(\Delta x^{(k)}-H_k\Delta g^{(k)})}$