数值计算基础（上溢下溢、梯度优化、牛顿法、KKT方法）

目录

上溢和下溢

病态条件

基于梯度的优化方法

KKT 方法

如果这篇文章对你有一点小小的帮助，请给个关注喔~我会非常开心的~

上溢和下溢

上溢：当大量级的数字被近似为 $infty$ 时发生上溢，进一步计算会导致这些无限值变为非数字
下溢：当接近零的数字被四舍五入为零时发生下溢

病态条件

条件数，表示函数相对于输入的微小变化而变化的快慢程度。

如果条件数大，有可能造成输入的舍入误差造成输出巨大变化。

函数 $f(x)=A^{-1}x$ ，当 $A$ 为 $ntimes n$ 时具有特征值分解，条件数表示为：

$max_{i,j}left| frac{lambda_i}{lambda_j} right|$

基于梯度的优化方法

梯度是相对一个向量求导的导数， $f$ 的导数是包含所有偏导数的向量，记为 $nabla_xf(x)$ 。

方向导数是在某方向上的斜率。

梯度下降是将 $x$ 往导数的反方向移动一小步以降低损失函数。

当目标函数满足凸函数的时候，梯度下降收敛的值是全局最小值，但是在深度学习的背景下，即使找到的解不是真正最小的，但是只要它们对于损失函数显著低，就可以接受。

若有一函数 $f:mathbb{R}^mrightarrow mathbb{R}^n$ ，则 $f$ 的 Jacobian 矩阵定义为：

$J_{i,j}=frac{partial }{partial x_j}f(x)_i$

对函数求二阶导数时，若导数有很多，可将其合并成一个 Hessian 矩阵，等价于梯度的 Jacobian 矩阵：

$H(f)(x)_{i,j}=frac{partial^2 }{partial x_ix_j}f(x)$

牛顿法，基于一个二阶泰勒展开来近似 $x^{(0)}$ 附近的 $f(x)$ ：

$f(x)approx f(x^{(0)})+(x-x^{(0)})^T nabla_xf(x^{(0)})+frac{1}{2}(x-x^{(0)})^TH(f)(x^{(0)})(x-x^{(0)})$

$x^*=x^{(0)}-H(f)(x^{(0)})^{-1}nabla_xf(x^{(0)})$

仅使用梯度的优化算法被称为一阶优化算法。

使用 Hessian 矩阵的优化算法被称为二阶优化算法。

Lipschitz 连续，表示为：

$forall x,forall y, left|f(x)-f(y)right|leqslant mathfrak{L} left|x-yright|_2$

KKT 方法

拉格朗日乘子法只允许等式约束。

KKT 方法是拉格朗日乘子法的推广，存在等式和不等式约束。

Karush-Kuhn-Tucker（KKT）是一种优化在约束条件下求 $f(x)$ 的最大值或者最小值的方法。

$f(x)$ 为原优化函数， $g^{(i)}(x)=0$ 为等式约束， $h^{(j)}leqslant 0$ 为不等式约束，引入 KKT 乘子，广义拉格朗日函数定义为：

$L(x,lambda,alpha)=f(x)+sum_ilambda_ig^{(i)}(x)+sum_jalpha_jh^{(j)}(x)$

原问题转换为对偶问题， $min_{x in mathbb{S}}f(x)=max_lambda max_{alpha,alphageqslant 0}L(x,lambda,alpha)$ 。

最优点满足以下必要条件：

满足 $L(x,lambda,alpha)$ 的梯度为零
满足所有关于 $x$ 和 KKT 乘子的约束条件
满足 $sum_{j}alpha_jh^{(j)}(x)=0$

如果这篇文章对你有一点小小的帮助，请给个关注喔~我会非常开心的~

Published by

风君子

独自遨游何稽首揭天掀地慰生平 View all posts by 风君子