优化模型与算法总结 第1篇

梯度类算法，其本质是仅仅使用函数的一阶导数信息选取下降方向。最基本的算法是梯度下降法，即直接选择负梯度作为下降方向。梯度下降法的方向选取非常直观，实际应用范围非常广，因此它在优化算法中的地位可相当于高斯消元法在线性方程组算法中的地位。

将辅助函数式(3)，泰勒展开为 \phi(\alpha) = f(x^k)+\alpha \triangledown f(x^k)^Td^k+\mathcal{O}(\alpha ^2||d^k||^2)\tag{12} 根据柯西不等式，当步长足够小时，下降方向选择负梯度方向函数下降最快，得到梯度下降方法的迭代方程如下： x^{k+1}=x^k-\alpha_k \triangledown f(x^k)\tag{13} 步长的选取依赖于线性搜索方法算法，也可以直接固定步长。

为了直观地理解梯度法的迭代过程，以二次函数为例来展示该过程，其迭代示意图如下图所示。

当问题的条件数很大，也即问题病态时，梯度下降法的收敛性质会受到很大影响。Barzilai-Borwein (BB) 方法是一种特殊的梯度法，经常比一般的梯度法有着更好的效果。其下降方向仍为负梯度方向，但步长不是有线性搜索算法给出的，其迭代格式为 x^{k+1}=x^k -\alpha_{BB}^k \triangledown f(x^k)\tag{14} 其中步长可以用下式中的一个来计算： \alpha_{BB1}^k \overset{\mathrm{def}}{=} \frac{(x^k-x^{k-1})^T(\triangledown f(x^k)-\triangledown f(x^{k-1}))}{(\triangledown f(x^k)-\triangledown f(x^{k-1}))^T(\triangledown f(x^k)-\triangledown f(x^{k-1}))}\tag{15}

\alpha_{BB2}^k \overset{\mathrm{def}}{=} \frac{(x^k-x^{k-1})^T(x^k-x^{k-1})}{(x^k-x^{k-1})^T(\triangledown f(x^k)-\triangledown f(x^{k-1}))}\tag{16}

计算两种BB 步长的任何一种仅仅需要函数相邻两步的梯度信息和迭代点信息，不需要任何线搜索算法即可选取算法步长。因为这个特点，BB 方法的使用范围特别广泛。实际用式(15)或(16)计算出的步长可能过大或过小，因此可以对步长做如下上下界约束： \alpha_m \leq \alpha_k \leq \alpha_M, 0 <\alpha_m < \alpha_M \tag{17} BB 方法是非单调方法，有时也配合非单调收敛准则使用以获得更好的实际效果，BB方法的计算流程如下所示。

对二次函数使用BB法和梯度下降法的对比如下图所示。

LASSO (least absolute shrinkage and selection operator)问题的原始形式为： \min \ f(x)=\frac{1}{2}||Ax-b||^2 + \mu ||x||_1 \tag{18} 上述目标函数在某些点无法计算梯度。因此不能利用梯度法对其进行求解。考虑到目标函数的不光滑项为绝对值函数，它实际上是 各个分量绝对值的和，如果能找到一个光滑函数来近似绝对值函数，那么梯度法就可以被用在上述问题的求解。实际考虑如下光滑函数： l_{\delta}(x) = \begin{cases} \frac{1}{2\delta}x^2,|x|<\delta \\ |x|-\frac{\delta}{2}, others \end{cases} \tag{19} 上式为实际上是Huber 损失函数的一种变形，当参数\delta \rightarrow0时,光滑函数和绝对值函数越来越接近，如下图所示。

因此构造光滑LASSO问题如下： \min \ f(x)=\frac{1}{2}||Ax-b||^2 + \mu \sum\limits_{i=1}^{n} l_{\delta}(x_i) \tag{20} 由此计算目标函数梯度，可以进行梯度法求解。不同正则化因子，对应的求解迭代过程，如下图所示。

光滑化梯度法在400 步左右收敛到LASSO 问题的解，收敛解与精确解的对比如下图所示。

优化模型与算法总结 第2篇

很多无约束优化问题的算法思想可以推广到其他优化问题上，因此掌握如何求解无约束优化问题 的方法是设计其他优化算法的基础。无约束优化考虑如下问题： \mathop{\min}\limits_{x \in \mathbb{R}^n} f(x), f(x): \mathbb{R}^n \rightarrow\mathbb{R}\tag{1}

无约束优化问题是无需可虑可行域，对于光滑函数，利用梯度和海森矩阵设计算法；对于非光滑函数，利用次梯度来构造迭代方程。

优化模型与算法总结 第3篇

信赖域算法(Trust-region methods)和线搜索算法都是借助泰勒展开来对目标函数进行局部近似，但它们看待近似函数的方式不同。在线搜索算法中，先利用近似模型求出下降方向，然后给定步长;而在信赖域类算法中，直接在一个有界区域内求解这个近似模型，而后迭代到下一个点。因此信赖域 算法实际上是同时选择了方向和步长。

根据带拉格朗日余项的泰勒展开， f(x^k+d)=f(x^k)+\triangledown f(x^k)^Td +\frac{1}{2}d^T\triangledown^2f(x^k+td)d, t \in (0,1)\tag{41} 类似牛顿法，二阶近似为 m_k(d)=f(x^k)+\triangledown f(x^k)d+\frac{1}{2}d^TB^kd \tag{42} 对上式可行域增加约束, 即信赖域： \Omega_k = \{ x^k +d|||d|| \leq \Delta_k \},\Delta_k > 0 \tag{43} 信赖域算法每一步都需要求解 如下子问题： \mathop{\min}_{d\in \mathbb{R}^n} \ m_k(d), \mathrm{.} \ ||d|| \leq. \Delta_k \tag{44} 下图显示了上式的求解过程，图中实线表示目标函数的等高线，虚线代表 m_k(d)的等高线，d_N^k 表示求解无约束问 题得到的下降方向，d_{TR}^k示求解信赖域上式得到的下降方向。信赖域算法正是限制了d 的大小，使得迭代更加保守，因此可以在牛顿方向很差时发挥作用 。

其计算流程如下：

Steihaug 在 1983 年对共轭梯度法进行了改造，使其成为能求解问题信赖子问题的算法。此算法能够应用在大规 模问题中，是一种非常有效的信赖域子问题的求解方法， 其计算流程如下所示。

考虑逻辑回归问题： \mathop{\min}_x \ \mathcal{l}(x) = \frac{1}{m}\sum\limits_{i=1}^{m}\ln(1+\exp(-b_ia_i^Tx))+\lambda||x||_2^2\tag{45} 在不同数据集上应用信頼域求解收敛过程如下图所示。从图中可以看到，在精确解附近梯度范数具有Q-超线性收敛性质。