无约束优化迭代法
迭代法的基本结构(最小化 $f(x)$)
- 决定一个初始点，设置一个 convergence tolerance $\epsilon$, 计数 $k=0$
- 决定搜索方法 $d_k$, 使得函数下降. （算法的核心）
- 决定步长 $\a_k$, 使得 $f(\boldsymbol{x_k} + a_k \boldsymbol{d_k})$ 对于 $a_k \ge 0$ 最小化, 构建 $\boldsymbol{x_{k+1}} = \boldsymbol{x_k} + a_k \boldsymbol{d_k}$
-
如果 $ \boldsymbol{d_k} 2 \lt \epsilon$, 则停止输出解 $\boldsymbol{x{k+1}}$; 否则继续重复迭代
梯度下降法
- $\boldsymbol{d_k} = - g(\boldsymbol{x_k})$, 即取梯度的反方向, 思考为什么这么取?
为了让函数下降最快, 即 $f(\boldsymbol{x_k + d_k})$ 比 $f(\boldsymbol{x_k})$ 越小越好, 最 $g^T(\boldsymbol{x_k}) \boldsymbol{d_k}$ 为负数, 且绝对值越小越好. 从向量的角度来看, 意味着向量 $f(\boldsymbol{x_k + d_k})$ 和微量 $g^T(\boldsymbol{x_k}) \boldsymbol{d_k}$ 方向相反.
- 需要 $f(\boldsymbol{x_k + d_k}) \downarrow$, 则 $f(\boldsymbol{x_k})$ 加个负数
-
回忆两个向量的内积, $\boldsymbol{a \cdot b = a^T b = a \quad b } cos \theta$
牛顿法
- 方向选取 $\boldsymbol{d_k} = - \boldsymbol{H^{-1}(x_k) g(x_k)}$
- 方向选取依据:
- 函数 $f(\boldsymbol{x_k + d_k}) = f(\boldsymbol{x_k}) + \boldsymbol{g^T(x_k) d_k} + \frac{1}{2} \boldsymbol{d^T_k H(x_k) d_k}$ (考虑了二阶项)
- 令 $\frac{\partial f(\boldsymbol{x_k + d_k})}{\boldsymbol{d_k}} = 0 \Rightarrow \boldsymbol{g(x_k) + H(x_k) d_k = 0}$
- 若 Hessian 矩阵正定, 则有 $\boldsymbol{d_k = - H^{-1}(x_k) g(x_k)}$
- 强制要求 Hessian 矩阵正定
