最优化理论期末复习笔记 Part 1

2024-01-03 18:38:54

数学基础
线性代数
函数的可微性与展开
凸优化问题
- 凸函数的判断
无约束问题的最优性条件
线搜索
- 精确线搜索
- 非精确线搜索
梯度法和牛顿法
共轭方向法和共轭梯度法
拟牛顿法
有约束的最优化问题
- 等式约束最优化问题的最优性条件
约束优化问题的可行方向法
- Zoutendijk 可行方向法
- 梯度投影法
  - 怎么把一个向量投影到边界上
罚函数
划重点

在一定的约束条件 $\in \Omega$ 下，调整一组可变参数 $x$ ，使设计目标 $f (x)$ 达到最优值（最大/最小）

机翼最优化设计

描述机翼的方法：

给定点插值
自由型面方法

肋板结构优化

最初的方法是，预先给定一些洞，然后调整这些洞的大小和边界

可以想到，这种方法对初始值敏感

一开始设置为实心的，然后调整每一个点的密度

某一点的密度远远小于其他地方的密度时，可以认为是挖空的

数学基础

线性代数/向量/矩阵理论

多元函数分析

凸优化问题（凸集与凸函数问题）

无约束问题的最优化条件

线性代数

从行的角度

N 维矩阵（方程组）的第 i 行表示一个 N-1 维的解空间，比如 2 维矩阵（方程组）的每一行表示一条直线

从列的角度

考：线性代数方程的解，存在性

矩阵的每一列视为一个列向量，矩阵 $A$ 与列向量 $x$ 的乘积，可以视为矩阵 $A$ 第 i 列与 $x$ 中第 i 个元素相乘，对 i 求和， $A x = b$

有解，就是说明矩阵 $A$ 的每个列向量展开的空间之中有 $b$

行列式的几何解释

线性变换的面积

向量范数和矩阵范数

向量范数

1-范数：

$\vert \vert x \vert \vert_1 = \sum_{i=1}^{n} \vert x_i \vert$

2-范数：

$\vert \vert x \vert \vert_2 = (\sum_{i=1}^{n} \vert x_i \vert^2)^{\frac{1}{2}}$

∞-范数：

$\vert \vert x \vert \vert_{\infty} = \max_{1 \leqslant i \leqslant n} \vert x_i \vert$

p-范数：

$\vert \vert x \vert \vert_p = (\sum_{i=1}^{n} \vert x_i \vert^p)^{\frac{1}{p}}$

矩阵范数的更强的性质的意义

为矩阵范数加上第四个性质 $\vert \vert AB \vert \vert \leq \vert \vert A \vert \vert \cdot \vert \vert B \vert \vert$

我们希望对一个矩阵不断做变换的时候，变换之后的结果的范数不断变小，然后如果我们能证明他有一个下限，如果这个下限还为 0，那么就相当于把变换之前的矩阵变换到了另一个目标矩阵

例如初等变换 $P_n \cdots P_2 P_1 A = A^{-1}$

为矩阵范数加上第五个性质 $\vert \vert Ax \vert \vert \leq \vert \vert A \vert \vert _{\mu} \cdot \vert \vert x \vert \vert$

则称矩阵范数 $\vert \vert \cdot \vert \vert _{\mu}$ 与向量范数 $\vert \vert x \vert \vert$ 是相容的

那么根据这个不等式可以得到 $\dfrac{\vert \vert Ax \vert \vert}{\vert \vert x \vert \vert} \leq \vert \vert A \vert \vert _{\mu}$

进一步，若存在 $\ne 0$ 使成立：

$\vert \vert A \vert \vert _{\mu} = \max_{x \ne 0} \dfrac{\vert \vert Ax \vert \vert}{\vert \vert x \vert \vert} = \max_{\vert \vert x \vert \vert = 1}\vert \vert Ax \vert \vert$

取 x 的各个分量最大值是可以作为标准的唯一值

这是跟向量 x 有关的，称为向量 x 的诱导范数

令 x = 1，那么就与 x 的大小无关，但是跟计算 x 范数的方式有关

因为令了 x = 1，所以这个诱导范数表示单位圆/球/超球面上的所有向量 x 经过线性变换后得到的所有向量 Ax 中最长的那个的范数

几种向量范数诱导的矩阵范数

1 范数诱导的矩阵范数

$\vert \vert A \vert \vert = \max_{1 \leq j \leq n}\sum_{i=1}^{m}\vert A_{ij} \vert$

为什么？

首先把 A 写成列向量的形式 $A = [A_1 A_2 A_3]$

所以 $Ax = A_1 * x_1 + A_2 * x_2 + A_3 * x_3$

两边求一范数，就是

$\begin{align} \notag \vert \vert Ax \vert \vert_1 &= \vert \vert \sum_{j=1}^{n} A_j x_j \vert \vert \\ \notag \leq \sum_{j=1}^{n}\\ \end{align}$

无穷范数诱导的矩阵范数

$\vert \vert A \vert \vert = \max_{1 \leq i \leq n}\sum_{j=1}^{m}\vert A_{ij} \vert$

为什么？

首先把 A 写成行向量的形式

$A = [(A_1^T)^T;(A_2^T)^T;(A_3^T)^T]$

$\vert \vert Ax \vert \vert_{\infty} = \max_{1 \leq i \leq n} \vert \vert A_i^Tx \vert \vert_{\infty} \leq \max_{1 \leq i \leq n} \vert \vert A_i^T[1,1, \cdots, 1]^T \vert \vert_{\infty} = \max_{1 \leq i \leq n} \sum_{j=1}^{m} \vert A_{ij} \vert$

2 范数诱导的矩阵范数

$\vert \vert A \vert \vert = \max\{\sqrt{\lambda} \vert \lambda \in \lambda(A^TA)\}$

为什么？

$\vert \vert Ax \vert \vert = \vert x^TA^TAx \vert ^{1/2}$

因为 $x^TA^TAx \vert \vert$ 中的 $A^TA$ 是一个矩阵的转置乘上这个矩阵本身，所以他是一个对称矩阵，对称矩阵一定可以相似对角化

有

$\vert x^TA^TAx \vert ^{1/2} = \vert x^TP^T \Lambda Px \vert ^{1/2} = \vert y^T \Lambda y \vert ^{1/2} = \vert \sum_{i=1}^{n} \lambda_i y_i^2 \vert ^{1/2} = \sqrt{\lambda_{\max}}\vert \sum_{i=1}^{n} \dfrac{\lambda_i}{\lambda_{\max}} y_i^2 \vert ^{1/2} \leq \sqrt{\lambda_{\max}}$

此时 $\dfrac{\lambda_i}{\lambda_{\max}} \leq 1$

y 取对应 $\lambda_i = \lambda_{\max}$ 时的 $y_i = 1$ ，其他的 $y_i = 0$ 时，不等式

P 是正交的，所以一定是满秩的，然后 x 是任意取的，所以 Px 不会掉维度，所以 Px 可以等于任意值，所以 y = Px 可以取到上面要求的值，所以不等式的等号可以被取到

各种范数之间的等价性

用无穷范数证出来的性质可以推广到 1 范数上

向量与矩阵序列的收敛性

某一个向量/矩阵序列的范数 = a， $\ne 0$ ，那么不能证明这个向量/矩阵序列收敛，因为范数不等于 0 的话，那么其实相当于这个向量/矩阵在某种意义上的长度不等于 0

比如一个向量的二范数收敛为 1，也就是这个向量的长度始终为 1，但是这个向量的方向可以任意，那么这个向量序列的向量的方向如果一直是任意的话，那么即使向量长度不变，也不是收敛的

所以说范数收敛不能保证向量/矩阵收敛，因为范数只是表征长度的量，而向量/矩阵是有方向的

函数的可微性与展开

一维优化问题

每一步迭代：用简单的近似函数 $f_0$ 去代替复杂函数 $f (x)$

怎么选择 $f_0$ ？一般是泰勒展开

泰勒展开需要知道 $f (x)$ 的导数

泰勒展开一般取多少项？一般取二次项就够了

为什么是二次？二次函数是有极值的，三次函数不一定有

$f_0$ 的极值是可以知道的，然后我们把 x 移动到 $f_0$ 的极值点的位置，然后在这个极值点的位置对原函数展开，求新的 $f_0$ ，继续移动。直到不再移动的时候就是收敛了。

当然这样不一定会收敛到极小值，也可能收敛到极大值，但是这是有方法解决的

如果不知道 $f (x)$ 的导数？其他方法？

插值

差分代替微分

$f(\bf x) \approx f_0(\bf x) = f(\bf x_0) + \nabla f \vert_{\bf x_0}(\bf x - \bf x_0) + \dfrac{1}{2}(\bf x - \bf x_0)^T \nabla^2 f \vert_{\bf x_0}(\bf x - \bf x_0)$

其中 $\bf x$ 是向量， $\nabla$ 表示梯度， $\nabla^2$ 表示 Hesse 矩阵

存在这些导数的条件是足够光滑

误差： $o((\bf x - \bf x_0)^2)$

如果是用一次函数来近似，那么

$f(\bf x) = f(\bf x_0) + \nabla f \vert_{\bf x_0}(\bf x - \bf x_0) + o(\vert\vert \bf x - \bf x_0 \vert\vert)$

如果是二次函数来近似，那么

$f(\bf x) \approx f_0(\bf x) = f(\bf x_0) + \nabla f \vert_{\bf x_0}(\bf x - \bf x_0) + \dfrac{1}{2}(\bf x - \bf x_0)^T \nabla^2 f \vert_{\bf x_0}(\bf x - \bf x_0) + o(\vert\vert \bf x - \bf x_0 \vert\vert^2)$

$\mathbb{J}=\left[\begin{array}{ccc} \dfrac{\partial \mathbf{f}(\mathbf{x})}{\partial x_{1}} & \cdots & \dfrac{\partial \mathbf{f}(\mathbf{x})}{\partial x_{n}} \end{array}\right]=\left[\begin{array}{c} \nabla^{T} f_{1}(\mathbf{x}) \\ \vdots \\ \nabla^{T} f_{m}(\mathbf{x}) \end{array}\right]=\left[\begin{array}{ccc} \dfrac{\partial f_{1}(\mathbf{x})}{\partial x_{1}} & \cdots & \dfrac{\partial f_{1}(\mathbf{x})}{\partial x_{n}} \\ \vdots & \ddots & \vdots \\ \dfrac{\partial f_{m}(\mathbf{x})}{\partial x_{1}} & \cdots & \dfrac{\partial f_{m}(\mathbf{x})}{\partial x_{n}} \end{array}\right]$

雅可比矩阵是向量值函数的导数

$\nabla f = \left[\begin{array}{ccc} \dfrac{\partial f(\mathbf{x})}{\partial x_{1}} \\ \cdots\\ \dfrac{\partial f(\mathbf{x})}{\partial x_{n}} \end{array}\right]$

$\nabla^2 f = \nabla \nabla f = \left[\begin{array}{ccc} \dfrac{\partial \nabla f(\mathbf{x})}{\partial x_{1}} \\ \cdots\\ \dfrac{\partial \nabla f(\mathbf{x})}{\partial x_{n}} \end{array}\right] \\ =\left[\begin{array}{ccc} \dfrac{\partial f(\mathbf{x})}{\partial x_{1}^2} & \dfrac{\partial f(\mathbf{x})}{\partial x_{1}\partial x_{2}} \cdots & \dfrac{\partial f(\mathbf{x})}{\partial x_{1}\partial x_{n}}\\ \cdots\\ \dfrac{\partial f(\mathbf{x})}{\partial x_{n}} & \dfrac{\partial f(\mathbf{x})}{\partial x_{n}\partial x_{2}} \cdots & \dfrac{\partial f(\mathbf{x})}{\partial x_{n}^2} \end{array}\right]$

牛顿莱布尼茨公式对多维的拓展

$\bf F(\bf x+\bf h) = \bf F(\bf x) + \int_0^1 \nabla \bf F(\bf x+\tau \bf h)^T \bf h d \tau$

$\bf F, \bf x, \bf h$ 是列向量

Lipschitz 连续

$\vert\vert F(x) - F(y) \vert\vert \leq L \vert\vert x - y\vert\vert$

自变量在变化的时候，函数值的变化始终是在一个线性范围内的

知道这个条件，我们可以估计 $F (x)$ 的大小

给定一个抽象的函数，可以替换成一个线性的函数

中值定理

收敛性分析中，可能用到向量值函数的中值定理

设向量值函数 F 连续可微：

(1): 对任意的 x,y

$\vert\vert F(x) - F(y) \vert\vert \leq \mathrm{sup}_{0 \leq t \leq 1} \vert\vert F'(y+t(x-y)) \vert\vert \vert\vert x-y \vert\vert$

其实就是向量值函数的值的范数/变量的范数 < 向量值函数的导数（雅可比矩阵）的值

一维情况：

$\vert \dfrac{f(x)-f(y)}{x-y} \vert \leq \mathrm{sup}_{0 \leq t \leq 1} \vert f'(y+t(x-y)) \vert$

sup 相当于一个范围内的最大值

(2): 对任意的 x,y,z

$\vert\vert F(y) - F(z) - F'(x)(y-z) \vert\vert \mathrm{sup}_{0 \leq t \leq 1} \vert\vert F'(z+t(y-z)) - F'(x)\vert\vert \cdot \vert\vert y-z \vert\vert$

书上写错了，最后面那个是 y-z

一维情况：

$\vert \dfrac {f(y) - f(z)}{y-z} - f'(x) \vert \leq \mathrm{sup}_{0 \leq t \leq 1} \vert f'(z+t(y-z)) - f'(x)\vert$

由上述定理的结论 (2) 可推得

$\vert\vert F'(u) - F'(v) \vert\vert \leq L \vert\vert u-v \vert\vert$

则对任意的 x,h

$\vert\vert F(x+h)-F(x)-F'(x)h \vert\vert \leq L \vert\vert h \vert\vert^2$

凸优化问题

考：什么是凸集，凸函数

凸集对于 $\in D$ , 有 $\lambda x + (1-\lambda)y \in D$

集合中任意两个端点，组成的线段上的任何点也属于这个集合

凸函数对于 $\in D$ , 有 $f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$

函数中任意两个端点上的函数值，组成的线段上的任何点的值都大于函数在该点的函数值

凸优化：可行集是凸集，目标函数都是凸函数

对于凸优化问题，目标函数的任意局部极小值点都是其全局极小值点

证明：

反证法：

设 $x^*$ 是一个局部极小值点

假设 $x^*$ 不是全局极小值点，那么在可行域内存在 $x^o$ ，满足 $f(x^o) < f(x^*)$

因为可行域是凸集，所以 $\alpha x^o + (1-\alpha)x^*$ 在可行域内

又因为目标函数是凸函数，所以

$f(\alpha x^o + (1-\alpha)x^*) \leq \alpha f(x^o) + (1-\alpha)f(x^*) \leq \alpha f(x^*) + (1-\alpha)f(x^*) = f(x^*)$

当 $\alpha$ 取充分小时， $f(\alpha x^o + (1-\alpha)x^*) = f(x^*)$

这与 $f(x^*)$ 是局部极小值矛盾

凸函数的判断

f 在 D 一阶可微

充要条件：

$\geq f(x^*)+ \nabla f(x^*)^T(x-x^*)$

对一个点一阶泰勒展开，也就是得到一个超平面，超平面上的值都小于函数值

严格凸的充要条件：

$f(x^*)+ \nabla f(x^*)^T(x-x^*)$

正定矩阵

考：Hessian 矩阵正定表示什么含义

对于一元函数，二阶导大于 0 意味着开口向上

$h^T \nabla^2 f(x) h \geq 0$ 半正定

$h^T \nabla^2 f(x) h > 0$ 正定

其中 h 类似 $\left[\begin{array}{ccc} x \\ y \end{array}\right]$

矩阵正定，代表一个开口向上的抛物面

那就说明每一步迭代都会稳定

f 在 D 二阶可微

进一步，如果 $h^T \nabla^2 f(x) h \geq c\vert \vert h \vert \vert^2$ 一致正定

其中 $c\vert \vert h \vert \vert^2$ 就是一个抛物面

f 在 D 上凸充要条件 $\nabla^2 f(x)$ 对 D 半正定

f 在 D 上严格凸 $\nabla^2 f(x)$ 对一切 D 正定

我感觉是，函数二阶可微的时候，也可以用一阶可微时的那个充要条件，只是说，当函数二阶可微的时候，我们还可以有另外一个充要条件，这两个充要条件对于二阶可微的函数来说是同时有效的

无约束问题的最优性条件

考：必要条件，充分条件

一阶必要条件

若 $x^*$ 是局部极小点，那么有 $g(x^*) = 0$

$g (x)$ 为一阶导数

二阶必要条件

若 $x^*$ 是局部极小点，那么有 $g(x^*) = 0$ , $G(x^*)$ 是半正定矩阵

$g (x)$ 为一阶导数， $G (x)$ 为二阶导数

半正定的性质： $d^TG(x^*)d$ 表示一个抛物面

二阶充分条件

若 $f$ 二阶连续可微， $g(x^*) = 0$ ， $G(x^*)$ 正定，那么 $x^*$ 是局部极小点

其中， $G(x^*)$ 正定， $f$ 二阶连续可微 -> 在 $x^*$ 的邻域里面， $G(x^*+\theta \alpha d)$ 正定

充要条件

考：二次函数什么时候有最小值

是凸函数，是一阶连续可微，那么 $g(x^*) = 0 \iff$ $x^*$ 是全局极小点

一般算法框架

考：线搜索的框架

给定初始化参数及初始迭代点 $x_0$ ，置 $k := 0$
若 $x_k$ 满足某种终止准则，停止迭代，以 $x_k$ 作为近似极小点
通过求解 $x_k$ 处的某个子问题确定下降方向 $x_k$
通过某种搜索方式确定步长因子 $\alpha_k$ ，使得 $f(x_k + \alpha_k d_k) < f(x_k)$
令 $x_{k+1} := x_k + \alpha_k d_k, k := k + 1$ ，转步 2

线搜索

这里讲的是一般算法框架中的第 4 步中的“某种搜索方式”

考：已知搜索方向，给出一维方向上的表达式

$x_{k+1} := x_k + \alpha_k d_k$

精确线搜索

单峰区间

考：单峰区间的原理和步骤

进退法找近似单峰区间的时候，实际上是找到了高低高三个点，你是不知道两个端点之间的函数值分布的情况的

黄金分割方法

考：黄金分割的原理，具体步骤

找完近似单峰区间之后，接下来要继续找细分后的近似单峰区间，那么其实一个区间里面要知道四个点

然后我希望下一次找单峰区间的时候，能够尽可能利用到上一步采样的点

因为每一次算点的函数值都会很费时

使得新的小区间与旧的大区间成比例，那么可以复用三个点

也就是每迭代一步，只需要增加三个点

无法执行黄金分割的情况

进退法只能找到高低高三个点

黄金分割的一开始是，取两侧的高点，然后在中间先按照黄金分割插入两个点，然后看左侧三个点满足高低高还是右侧满足，选择满足高低高的那一侧递归

但是假设一开始我插入了两个点之后，我发现这两个点都大于我两侧的高点，那么我现在找不到高低高了

那么这就意味着我无法执行黄金分割了

一种方法是我换一个分割方法，也就是换一个“插点-找高低高-插点-找高低高”的思路

另外一种方法就是直接放弃精确线搜索，直接把一开始进退法找到的近似单峰区间的高低高的低点，作为下一步的线搜索的起点

牛顿法

原理

函数 $f (x)$ 在 $x_k$ 处近似为二次泰勒展开

$\approx f_k(x) = f(x_k) + f'(x_k)(x-x_k) + \dfrac{1}{2}f''(x_k)(x-x_k)^2$

以近似函数导数为零的点来近似函数 $f (x)$ 的极小值点

$f'_k(x) = f'(x_k) + f''(x_k)(x-x_k) = 0$

-> $x_{k+1} = x_k - \dfrac{f'(x_k)}{f''(x_k)}$

算法

给出 $x_1 \in \mathcal{R}, k := 1$
计算 $f'(x_k), f''(x_k)$
如果 $f'(x_k) = 0$ ，则停。否则更新：

$x_{k+1} = x_k - \dfrac{f'(x_k)}{f''(x_k)}$

收敛速度

因为 $\vert x_{k+1} - x^* \vert / \vert x_k - x^* \vert \rightarrow 0$ ，所以是超线性收敛

算误差的时候

$x_{k+1} - x^*$ 算是 k+1 步的误差

将牛顿法的迭代公式代入

$x_{k+1} - x^* = x_k - \dfrac{f'(x_k)}{f''(x_k)} - x^* = x_k - x^* - \dfrac{f'(x_k)}{f''(x_k)}$

其中 $x_k - x^*$ 就是 k 步的误差

所以我们希望把后面的 $\dfrac{f'(x_k)}{f''(x_k)}$ 也写成某步的误差

用牛顿莱布尼茨公式： $\dfrac{f'(x_k)}{f''(x_k)} = \dfrac{f'(x^*) + \int_{x^*}^{x_k}f''(x)\mathrm{d}x}{f''(x_k)}$

因为 $f'(x^*) = 0$

所以 $\dfrac{f'(x_k)}{f''(x_k)} = \dfrac{\int_{x^*}^{x_k}f''(x)\mathrm{d}x}{f''(x_k)}$

所以 $x_k - x^* - \dfrac{f'(x_k)}{f''(x_k)} = \dfrac{f''(x_k)(x_k - x^*) -\int_{x^*}^{x_k}f''(x)\mathrm{d}x}{f''(x_k)} = \dfrac{\int_{x^*}^{x_k}f''(x_k) - f''(x)\mathrm{d}x}{f''(x_k)}$

因为 $f''(x^*) \ne 0$ 所以 $x_k$ 充分靠近 $x^*$ 时，由保号性，也有 $f''(x_k) \ne 0$

所以分母不为 0，就不管了

李普希兹连续时， $\vert f''(x_k) - f''(x)\vert \leqslant M \vert x_k - x^*\vert$

又因为 $\mathrm{d}x$ 也是与 $x_k - x^*$ 同阶，所以 $\int_{x^*}^{x_k}f''(x_k) - f''(x)\mathrm{d}x = o(\vert x_k - x^*\vert^2)$

割线法

牛顿法需要计算二阶导数。如果我们不知道二阶导数？

那么就用差商代替导数，即

$f''(x_k) \approx \dfrac{f'(x_k)-f'(x_{k-1})}{x_k - x_{k-1}}$

从牛顿法可以导出：

$x_{k+1} = x_k - f'(x_k)\dfrac{x_k - x_{k-1}}{f'(x_k)-f'(x_{k-1})}$

抛物线方法

原理

考：精确线搜索的抛物线方法

他是一个在 $x_k, x_{k-1}, x_{k-2}$ 三点的二次插值函数

$f(x) = f(x_k) + (x - x_k)f[x_k, x_{k-1}] + (x-x_k)(x-x_{k-1})f[x_k,x_{k-1}, x_{k-2}]$

其中 $f[x_k, x_{k-1}] = \dfrac{f(x_k)-f(x_{k-1})}{x_k - x_{k-1}}$

$f[x_k,x_{k-1}, x_{k-2}] = \dfrac{f[x_k, x_{k-1}] - f[x_{k-1}, x_{k-2}]}{x_k - x_{k-2}}$

是函数 $f (x)$ 的一阶和二阶差商

差商是一种描述这个插值函数的方法

也可以用拉格朗日插值多项式来描述

算法

给定三个点，构建插值函数

用一阶导等于 0 来找这个插值函数的极小点

在三个插值点和这个找到的极小点之间，找左侧三个点是高低高还是右侧三个点是高低高

类似黄金分割也是不断找新的三个点

得到新的三个插值点，循环

与黄金分割的对比

与其他方法对比，黄金分割，确定三个点之后，新的点总是在这三个点里面的，所以区间总是收缩的

如果按照书上的方法，抛物线方法的初始时刻三个点选择 $s_0, s_0 + h, s_0 + 2*h$ ，那么这三个点不一定是高低高的，所以构建出的抛物线的最低点不一定是在这三个点之间，所以你的搜索区间不一定是收缩的

所以更好的方法是，一开始进退法找到了高低高三个点，然后把这三个点用来作为抛物线方法的初始三个点

抛物线方法与黄金分割的不同就是，插点方法的不同：黄金分割根据黄金比例来决定插点的位置，抛物线方法是根据近似的抛物线的最低点的位置来决定插点的位置

之后，递归条件仍然是一样的，找左侧三个点是高低高还是右侧三个点是高低高

判断插点位置的注意事项

要注意的是，判断插点的位置是用近似的抛物线，但是判断左侧三个点和右侧三个点的时候，点的取值是要代入原函数取值的

因为这里很容易写错，插点的函数值取值容易写错成，从抛物线最低点取到 x 的位置，然后把 x 代入抛物线取值

实际上正确的是，从抛物线最低点取到 x 的位置，然后把 x 代入原函数取值

非精确线搜索

一开始距离极小值点比较远的时候，使用精确线搜索也没有什么意义，反而迭代更多

准则：这一步的函数值比上一步的函数值小多少

Armijo-Goldstein 准则

要求这一步的函数值小于上一步的函数值

进一步，要求这一步的函数值相比于上一步的函数值有一定的下降量

每一步选择下降最快的方向，整体可能并不是下降最快的

$\mathbf{g}_k^T \mathbf{d}_k < 0$ 保证这是一个下降的方向

所以要求 $f(x_k) + \rho \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 有一个下降量，它相当于一个斜线

自然，我们知道这个斜线的斜率是不确定的，那么斜率就可能是一个问题，比如，如果斜率选择不当，可能导致击中的原函数的点的值与处发现很接近，也就是每一步下降的幅度可能会小

所以我们要想办法把 $\alpha = 0$ 附近的区域刨去

所以再要求 $f(x_k) + (1-\rho) \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 也有一个下降量

又因为我们希望 $f(x_k) + (1-\rho) \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 击中的点是 $\alpha = b$ ， $f(x_k) + \rho \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 击中的点是 $\alpha = c$

又希望可行区间是 $(b, c)$ 那么就是希望 $b < c$ ，那么就是希望 $f(x_k) + (1-\rho) \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 的斜率的绝对值比 $f(x_k) + \rho \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 更大

所以要求 $\rho < 1/2$

Wolfe-Powell 准则

之前的 Armijo-Goldstein 准则衡量“一定的下降量”是使用函数值来衡量的

现在这个 Wolfe-Powell 准则衡量“一定的下降量”是使用斜率 $\mathbf{g}_k^T \mathbf{d}_k$ 来衡量的

也就是，假设了 $f(x_k) + \rho \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 击中的点是 $\alpha = c$

然后希望有一定的斜率，那么设可接受斜率是初始斜率的 $\sigma$ 倍

那么我个人觉得有两种方法

一种是假设 $f(x_k) + \sigma \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 击中的点是 $\alpha = e$

还有一种是他设的，取原曲线上斜率为 $\sigma \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 的位置是 $\alpha = e$

可行区间为 $(e, c)$

他这种设法还可以使得精确解的最小值包含在 $(e, c)$ 中

为了保证 $e < c$ 需要 $\rho < \sigma$

$\sigma < 1$ 是为了使得 $\sigma \alpha_k \mathbf{g}_k^T \mathbf{d}_k$ 代表的斜率的线更靠近水平一点，这样就可以避开 $x_k$ 点，也就是避开 $\alpha = 0$ 的附近

Armijo 准则的实现

考：Armijo 准则知道怎么算

$\beta^m$ 随着步数 $m$ 从 0 开始增加

给定 $\beta \in (0,1), \sigma \in (0,0.5)$ ，令 $m := 0$
若不等式

$f(x_k +\beta^m d_k) \leqslant f(x_k) + \sigma \beta^m g_k^T d_k$

成立，置 $m_k := m, x_{k+1} = x_k + \beta^{m_k} d_k$ ，停算，否则，转步 3
令 $m := m + 1$ ，转步 2

线搜索方法框架

搜索方向与负梯度方向的夹角小于 90 度

线搜索方法的收敛性

$f(x_k)$ 单调下降且有界

$f(x_k)-f(x_{k+1}) \rightarrow 0$

意味着

$x_{k+1} = x_{k} + o(d_k)$

$\vert \vert a \cdot b \vert \vert \leqslant \vert \vert a \vert \vert \cdot \vert \vert b \vert \vert$

$d_k / \vert \vert d_k \vert \vert$ 是单位向量

所以 $[g(\varepsilon)-g_k]^T d_k / \vert \vert d_k \vert \vert \leqslant \vert \vert g(\varepsilon)-g_k \vert \vert$

之后的 $\vert \vert g(\varepsilon)-g_k \vert \vert \leqslant 1/2 * \epsilon_0$ 其中 $\epsilon_0$ 是人为取的

$\lim_{k \rightarrow \infty}\nabla f(x_{k+1})^T s_k/g_k^T s_k = 1$

这就是表示，这一步的斜率和下一步的斜率一样

但是 Armijo 准则要求 $\rho < \sigma < 1$ 于是矛盾

书上的一个问题，想要证明小于号变成大于号，但是万一一开始就满足大于号的话，就没有这个转变的过程了

梯度法和牛顿法

这里讲的是一般搜索框架中的“确定下降方向”

最速下降法（梯度法）

最速下降法（梯度法）取负梯度方向作为

牛顿法

牛顿法取 $G_k d_k = -g_k$ 的解 $d_k$ 作为下降方向

阻尼牛顿法

阻尼牛顿法引入线搜索方程保证收敛性，也就是，用牛顿法确定下降方向（搜索方向），有了搜索方向之后再沿这个搜索方向做 Armijo 搜索

修正牛顿法

基本/阻尼牛顿法中要每一步的 Hesse 矩阵正定，才能保证牛顿方向为下降方向

每一步怎么判断 Hesse 矩阵是否正定？直接算 dTGd? 不用，因为你是用 $G_k d_k = -g_k$ 算出来的解 $d_k$ ，所以你只要用 $g_k^T d_k$ 验证就好了，如果 $g_k^T d_k < 0$ ，表示求出来的搜索方向 $d_k$ 确实与负梯度成锐角，那么就说明 Hesse 矩阵正定，否则不是正定

那么 Hesse 矩阵不正定时，不能保证牛顿方向为下降方向，该怎么办？

牛顿/梯度混合法在 Hesse 矩阵不正定时用梯度下降法，也就是求出的 $d_k$ 不对时，直接令 $d_k$ 为负梯度

修正牛顿法在 Hesse 矩阵对角线上加一个正数保障正定性

也就是之前的算法都是用 $G_k d_k = -g_k$ 算出来的搜索方向 $d_k$

现在修正牛顿法用 $(G_k + \mu_k I) d_k = -g_k$ 算出来搜索方向 $d_k$

共轭方向法和共轭梯度法

首先，共轭方向法不等于共轭梯度法

考虑有极小值的函数

一次函数没有，所以考虑二次函数

多元函数 $f(x) = 1/2 x^TGx + b^Tx + c$

它的一阶导 $\nabla f = Gx + b$

求极小值就是求 $G x + b = 0$

求极小值就是等价于求这个线性代数方程组的解

有直接求解的方法或者迭代求解的方法

找一个解就是找这个 n 维空间的一个点

因为这个点在 n 维空间内，所以这个点可以表达成这个 n 维空间的 n 个线性独立的基向量的线性组合

直接的方法的话，就是直接确定这个线性组合的系数

迭代求解的，比如之前讲到的最速下降法和基本牛顿法

最速下降法的问题是他是一阶收敛速度，收敛速度太慢

基本牛顿法用 $G_k d_k = -g_k$ 算出来搜索方向 $d_k$

其中要算一个二阶导 Hesse 矩阵，对于工程问题计算量太大

现在我们希望有一个方法，把这个确定 n 个系数的过程分为 n 步，每一步确定一个系数

要求我们第 i 步求解不会影响我们之前求解出来的系数

那么就是要求我们的线性组合的 n 个线性独立的基向量，他不单单是线性独立的，还需要是正交的

每一步找距离精确点最近

在第 i 步上，沿着第 i 个基向量走，走到误差最小的点，所以这个时候，迭代向量在第 i 个基向量的方向上的投影，已经等于距离精确点在第 i 个方向上的投影

为了求第 i 步的长度，利用 $e_i$ 与 $d_i$ 垂直 $e_i \cdot d_i = 0$ 来计算，其中 $e_i = x_i - x^*$

但是 $x^*$ 不知道，所以我们新增一个要求 $e_i^TGd_i = 0$ ，其中的 $x^*$ 项会变成 $Gx^* = b$ ，这样就可以求了

那么其实我们现在不用 $e_i \cdot d_i = 0$ 来求 $e_i$ 了

我们直接用 $e_i^TGd_i = 0$ 来求 $e_i$

这就相当于我们新定义了一个内积的形式 $a,b> = a^TGb = 0$

那么要求 n 个基向量互相正交，也就是 $<d_i, d_j> = d_i^TGd_j = \delta_{ij}$

要求第 i 步的基向量 $d_i$ 与梯度方向 g 内积 < 0

也是用二次函数拟合，所以误差也是二次

收敛速度的证明

定理 21 第 i 步找的极小值点是函数曲面的等值线与第 i 步的基向量与之前的基向量张成的线性流形相切的点

比如第一步，极小值是 $d_1$ 这个线与函数曲面的等值线相切的点

第二步，极小值是 $d_1,d_2$ 张成的平面与函数曲面的切点

第三步，…

现在我们的要求改为了 n 个基向量是 G 共轭的

n 个基向量是 G 共轭可以推出这 n 个基向量是线性无关的，反证法

定理 21 的作用是，极小值意味着梯度 = 0

我们在共轭方向法中，下降方向虽然不是第 i 个点的梯度，但是我们需要知道第 i 个点的梯度来判断我们第 i 个点的下降方向是否是合理的，是否是使得函数下降的

那么我们要求第 i+1 点的梯度时，这个第 i+1 点的梯度是垂直于前 i 个基向量张成的流形

因此我们要证明第 i+1 点的梯度垂直于前 i 个基向量张成的流形

证明过程…两部分

解释第一部分：第 i 步的搜索搜索到的第 i + 1 步的点，它和第 i + 1 点处梯度相互垂直

计算过程中需要用到 G，也就是海森矩阵，怎么避免计算？

构造 d

公式略

系数为 0 的时候就是每一步为负梯度方向，就是最速下降

所以公式是负梯度减去负梯度在旧基向量方向上的投影，才能得到新的 d 与旧的 d 相互 G 共轭

这些系数就用新的 d 与旧的 d 相互 G 共轭来求

求的过程中，公式推导用到了

$G x = g$

还用到了 $g_k * g_{k-1} = 0$

因为根据公式 $g_{k-1}$ 就是 $d_0$ 到 $d_{k-1}$ 的线性组合

而 $g_k$ 已经证了和 $d_0$ 到 $d_{k-1}$ 张成的流形垂直，所以就是与 $d_0$ 到 $d_{k-1}$ 都垂直

另一种讲法

把精确解 $x^*$ 拆成 $d$ 的线性组合

如果 $d_i$ 之间是正交的，那么用 $a_id_i = xd_i$ 可以求出 $a_i$

但是现在精确解是未知的

$(\sum{a_i d_i} - x^*)^TGd_j=0$

未知 $x^*$ 的时候，如果用 d 这个线性组合把 $x^*$ 分解得很精确，那么 $\sum{a_i d_i} - x^* = 0$ 上式就成立

拆开：

$(\sum{a_i d_i})^TGd_j - (x^*)^TGd_j=0$

这个精确解 $x^*$ 还是未知，还是要处理

$x^*)^TGd_j$ 是一个标量，所以 $x^*)^TGd_j = ((x^*)^TGd_j)^T$

$x^*)^TGd_j = ((x^*)^TGd_j)^T = d_j^T G^T x^* = d_j^T G x^* = d_j^T b$

$x^*$ 就没了

怎么求第 k 步的搜索方向

共轭方向法只是确定了每一个搜索方向之间都要满足 G 共轭，在 k-1 步沿着 $d_{k-1}$ 搜索了之后，还要确定 $d_k$

如果仅仅是使用 G 共轭这个条件的话，可以求，但是要求 G

为了避免计算这个 G

我们把第 k 步搜索方向取为前 k?1 步搜索方向与第 k 步负梯度的线性组合

这个方法就叫做共轭梯度法

这就是共轭方向法和共轭梯度法的区别

$d_k = -g_k + \beta_{k-1}d_{k-1} + \sum_{i=0}^{k-2}\beta_{k}^i d_i$

根据 $d_k$ 与 $d_i, i = 0, ..., k-1$ G 共轭来确定线性组合中的系数

$d^T_{k-1}Gd_k = -d^T_{k-1}Gg_k + \beta_{k-1}d^T_{k-1}Gd_{k-1}+ \sum_{i=0}^{k-2}\beta_{k}^i d^T_{k-1}Gd_i$

为什么这里要把 0 到 k-2 和 k-1 分开写？

经过 k-1 步之后 0 到 k-2 的搜索方向和 k-1 步的搜索方向 G 共轭，所以

$d^T_{k-1}Gd_i = 0$

所以上式最后一项消去

现在变成

$-d^T_{k-1}Gg_k + \beta_{k-1}d^T_{k-1}Gd_{k-1}$

-> $\beta_{k-1} = \dfrac{g^T_{k}Gd_{k-1}}{d^T_{k-1}Gd_{k-1}}$

因为 G 是二阶导，所以乘以一个方向之后就是一阶导

或者这么想 $\nabla f(x) = Gx + b, G(x) = \nabla^2 f(x) = G$

所以 $g_1 - g_0 = G(x_1 - x_0) = \alpha_0 G d_0$

所以 $Gd_{k-1} = 1/\alpha_0 * g_k -g_{k-1}$

上式化为

$\beta_{k-1} = \dfrac{g^{T}_{k}Gd_{k-1}}{d^T_{k-1}Gd_{k-1}} = \dfrac{g^{T}_{k}(g_k -g_{k-1})}{d^T_{k-1}(g_k -g_{k-1})}$

其中用到了转置。因为最后计算结果是标量，所以可以随意转置

因为每一步确定搜索方向之后，沿着这个方向，不管是精确线搜索还是非精确线搜索，都是确定到了极小值点才停止，所以每一步走完之后的负梯度方向之间应该是互相垂直的

即 $g^T_k g_{k-1} = 0$

又因为我们前面证明过了第 i 步找的极小值点是函数曲面的等值线与第 i 步的基向量与之前的基向量张成的线性流形相切的点

也就是 $g^T_k d_i = 0, i = 0, ..., k-1$

那么上式化为

$KaTeX parse error: Unexpected end of input in a macro argument, expected '}' at end of input: …^T_{k-1}g_{k-1}$

这样就求出了 $\beta_{k-1}$

那么接下来求其他系数。根据 $d_k$ 与 $d_j, j = 0, ..., k-2$ G 共轭：

$d^T_j G d_k = -d^T_{j}Gg_k + \beta_{k-1}d^T_{j}Gd_{k-1}+ \sum_{i=0}^{k-2}\beta_{k}^i d^T_{j}Gd_i, j = 0, ..., k-2$

其中，因为各个搜索方向 G 共轭，所以 $d^T_{j}Gd_{k-1} = 0$ 中间那项消掉

对于第三项同理，因为 G 共轭，所以消到只剩下 dj 乘 dj 的那项

上式化简为

$-d^T_j G g_k + \beta_k^j d_j^T G d_j, j = 0, ..., k-2$

-> $\beta_k^j = \dfrac{G g_k^T d^Td^T}{d_j^T G d_j}$

其中用到了转置。因为最后计算结果是标量，所以可以随意转置

与之前一样，根据 $Gd_{k-1} = 1/\alpha_0 * g_k -g_{k-1}$

上式化为 $\beta_k^j = \dfrac{G g_k^T d^Td^T}{d_j^T G d_j} = \dfrac{1}{\alpha_k}\dfrac{g_k^T(g_{j+1}-g_{j})}{d_j^T G d_j}$

又因为每一步走完之后的负梯度方向之间应该是互相垂直的

所以 $g_k^T g_{j+1} = 0, g_k^T g_{j} = 0$

所以 $\beta_k^j = \dfrac{G g_k^T d^Td^T}{d_j^T G d_j} = \dfrac{1}{\alpha_k}\dfrac{g_k^T(g_{j+1}-g_{j})}{d_j^T G d_j} = 0$

也就是 0 到 k-2 前的系数为 0

对于非线性问题

对于线性问题，有连等式成立

$\beta_{k-1} = \dfrac{g^{T}_{k}Gd_{k-1}}{d^T_{k-1}Gd_{k-1}} = \dfrac{g^{T}_{k}(g_k -g_{k-1})}{d^T_{k-1}(g_k -g_{k-1})} = \dfrac{g^{T}_{k}g_k}{d^T_{k-1}g_{k-1}}$

但是对于非线性问题，其中任意一个确定 $\beta_{k-1}$ 的等式都不等价

用不同的等式确定 $\beta_{k-1}$ ，就可以是一种不同的算法

这里说的线性问题说的是，共轭方向法等价于解 $\nabla f(x) = Gx + b = 0$

二次终止性

当使用精确线搜索方法时，对于正定二次目标函数极小值问题，共轭方向法至多在n步内即可求得其唯一极小点，这称为二次终止性。

共轭梯度法也有这个性质

对于非二次目标函数（即更一般的非线性目标函数）极小值问题，共轭梯度法不具有二次终止性。但是收敛很快。为什么？

因为靠近精确解的时候，误差也比较小，所以也能得到好的结果

这说了个寂寞

从内积角度看傅里叶变换

函数展开，先确定基函数，再确定基函数的系数

对于泰勒展开，基函数是 (x-x0)^n 基函数的系数是通过要求函数与展开式在某点的各阶导数相等来确定的

$f(x_0) = F(x_0)$

$f'(x_0) = F'(x_0)$

$f''(x_0) = F''(x_0)$

但是这就要求原函数有 n 阶导数

一种更有效的展开方法：要求函数与展开式与 x^n 乘积的积分相等

不要求原函数是光滑的

可积的要求比可微的要求低

$\int f(x)\mathrm{d}x = \int F(x)\mathrm{d}x$

$\int f(x)x\mathrm{d}x = \int F(x)x\mathrm{d}x$

$\int f(x)x^2\mathrm{d}x = \int F(x)x^2\mathrm{d}x$

提出 a 交换求和和积分号，得到线性代数方程组

(…)

这做了个什么事呢？这相当于对两个函数定义了一个内积

$\cdot g(x) = \int f(x) g(x) \mathrm{d}x$

$\inf F x = \int f x$

$\cdot x^i$ 相当于 F 与 f 之间的误差垂直于 $x^i$

求到的是距离 f 误差最小的一个函数

取 n 个基函数的时候，和取 n + 1 个基函数的时候，得到的线性代数方程组是不一样的

得到的 a1 a2 a3 是可能会变的

所以每次加一个基函数的时候，都要重新求解一次

我们希望的是每增加一次基函数，之前求解出来的 a1 a2 a3 都不会变

这就需要每一次增加的基函数和之前的基函数都是正交的

傅里叶积分选取的基函数之间都是正交的，就满足这个条件

线性方程组的求解分为两大类

直接法和迭代法

直接法，比如高斯消元和 LU 分解

迭代法，例如雅可比迭代

回到我们的共轭方向法，假设我们已经知道了所有的 d1 d2 d3，那么共轭方向法就是一个直接法

但是我们换一个角度想，假设我们一开始什么基向量都不知道，我们是一步步构造 d1 d2 d3 的

构造 d1，解一次，得到 a1，然后再构造 d2，再解，得到 a2

所以也可以视为迭代法

在取每一步方向 d 的时候要用到 G 共轭，为了避免计算 G，把 d 写成一个形式

文章来源:https://blog.csdn.net/hijackedbycsdn/article/details/135357102
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！