第四章：Numerical Computation

Posted on Edited on In

4. Numerical Computation

数值优化（Numerical Computation）：通常指代那些在解决数学问题时，不使用从符号表达式中直接推导出解析解，而是使用迭代更新的方式获取答案的算法。

上溢和下溢（overflow/underflow）：数据太小或者太大，在计算机内存中无法表示。

优化问题（optimization problem）：优化目标：最小化函数：损失函数（loss function）/ 错误函数（error function）通常上标*表示最优解。$x^*=argmin f(x)$

临界点（critical point）：$f’(x)=0$的点称为临界点，一般临界点取得极大值或者极小值，否则为鞍点（saddle point）。

梯度下降（gradient descent）：$x’ = x-ε\triangledown _xf(x)$，其中，ε是学习率。

Jacobian 矩阵（Jacobian matrix）：

  • 如果我们有一个函数f:$\mathbb{R}^m \rightarrow \mathbb{R}^n$
  • 那么Jacobian矩阵即为：$J_{i,j} = \frac {\partial}{\partial x_j}f(x)_i$。

Hessian 矩阵（Hessian matrix）：

  • $H(f)(x)_{i,j} = \frac {\partial ^2}{\partial x_i \partial x_j}f(x)$。
  • 可以知道，Hessian矩阵是对称阵。

牛顿法（Newton’s method）：

  • 将函数用二阶的泰勒公式近似：$f(x)≈f(x^{(0)})+(x-x^{(0)})^T\triangledown_xf(x^{(0)})+\frac{1}{2}(x-x^{(0)})^TH(f)(x^{(0)})(x-x^{(0)})$，求解临界点$x^*
    = x^{(0)}-H(f)(x^{(0)})^{-1}\triangledown_xf(x^{(0)})$。
  • 梯度下降称为“一阶优化算法”；牛顿法称为“二阶优化算法”。

拉格朗日对偶性

原始问题：

$f(x),c_i(x),h_j(x)$是定义在$R^n$上的连续可微函数，考虑约束最优化问题：

$\underset{x\in R^n}{min}f(x) s.t. c_i(x)\leq 0 i=1,…,k h_j(x)=0 j=1,…,l$

即有$k$个不等式约束：$c_i(x)$和$l$个等式约束：$h_j(x)$。

拉格朗日函数：

  • $L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_i c_i(x)+\sum_{j=1}^l\beta_jh_j(x)$
  • $\alpha_i$和$\beta_j$，称为拉格朗日乘子，$\alpha_i\geq 0$。

拉格朗日函数的极大极小问题：

  • 令$\theta_P(x) = \underset{\alpha,\beta}{max};L(x,\alpha,\beta)$
  • 如果存在$x$违反了原始问题的约束条件，则$\theta_P(x)=\infty$，当$x$不违反原始问题的约束条件，则$\theta_P(x)=f(x)$
  • 因此：$\underset{x}{min}\theta_P(x)=\underset{x}{min}\underset{\alpha,\beta}{max}L(x,\alpha,\beta)$等价于原问题。

对偶问题：

  • $\underset{\alpha,\beta}{max}\underset{x}{min};L(x,\alpha,\beta)$
  • 定理：如果函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，则$x^*,\alpha^*,\beta^*$是同时是原始问题和对偶问题的解的必要条件是满足KKT条件。

KKT条件：

1.拉格朗日函数对$x$，$λ$，$α$求偏导都为0：

$$\triangledown_xL(x^*,\alpha^*,\beta^*)=0$$

$$\triangledown_{\alpha}L(x^*,\alpha^*,\beta^*)=0$$

$$\triangledown_{\beta}L(x^*,\alpha^*,\beta^*)=0$$

2.对于不等式约束，$\alpha_i^*c_i(x^*)=0 i=1,…,k$（对偶互补条件）。