wordpress投票插件wp-polls,seo技术是什么意思,创意设计app,模仿别人网站数学基础线性代数 从行的角度从列的角度行列式的几何解释向量范数和矩阵范数 向量范数矩阵范数的更强的性质的意义 几种向量范数诱导的矩阵范数 1 范数诱导的矩阵范数无穷范数诱导的矩阵范数2 范数诱导的矩阵范数 各种范数之间的等价性向量与矩阵序列的收敛性 函数的可微性与展…数学基础线性代数 从行的角度从列的角度行列式的几何解释向量范数和矩阵范数 向量范数矩阵范数的更强的性质的意义 几种向量范数诱导的矩阵范数 1 范数诱导的矩阵范数无穷范数诱导的矩阵范数2 范数诱导的矩阵范数 各种范数之间的等价性向量与矩阵序列的收敛性 函数的可微性与展开 一维优化问题牛顿莱布尼茨公式对多维的拓展Lipschitz 连续中值定理 凸优化问题 凸函数的判断 f 在 D 一阶可微正定矩阵f 在 D 二阶可微 无约束问题的最优性条件 一阶必要条件二阶必要条件二阶充分条件充要条件一般算法框架 线搜索 精确线搜索 单峰区间黄金分割方法 无法执行黄金分割的情况 牛顿法 原理算法收敛速度 割线法抛物线方法 原理算法与黄金分割的对比判断插点位置的注意事项 非精确线搜索 Armijo-Goldstein 准则Wolfe-Powell 准则Armijo 准则的实现线搜索方法框架线搜索方法的收敛性 梯度法和牛顿法 最速下降法梯度法牛顿法阻尼牛顿法修正牛顿法 共轭方向法和共轭梯度法 收敛速度的证明另一种讲法怎么求第 k 步的搜索方向对于非线性问题二次终止性从内积角度看傅里叶变换 拟牛顿法 对称秩一校正对称秩二DFP, BFGS对称正定 拟牛顿法的收敛性 有约束的最优化问题约束最优化问题的最优性条件 等式约束的最优性条件 拉格朗日乘子法证明一阶必要条件二阶充分条件 不等式约束问题的最优性条件 无效约束和有效约束Farkas 引理Gordan 引理不等式约束问题的几何最优性条件不等式约束问题的 KT 条件 一般约束问题的最优性条件 不等式约束和等式约束统一为等式约束一阶必要条件二阶充分条件 约束优化问题的可行方向法 Zoutendijk 可行方向法 可行方向非线性约束下的非线性优化问题转化迭代时满足约束下降可行方向的条件线性约束的可行方向法非线性约束的可行方向法 梯度投影法 怎么把一个向量投影到边界上 投影到 a 向量投影到 A 矩阵投影矩阵的性质投影到 Mx 0 表示的空间投影到 Mx b 表示的空间A (A1, A2) 算法流程 罚函数 外罚函数 证明收敛聚点算法框架优缺点 内点法 算法框架证明收敛优缺点 乘子法PH 算法 PH 算法流程 划重点 绪论无约束问题的最优性条件什么是凸集凸函数多元函数线搜索的框架常用方法的收敛速度判断迭代是否终止的判据线搜索梯度法共轭方向法 二次终止性 拟牛顿法有约束的优化问题约束问题的可行方向法约束问题的罚函数方法 在一定的约束条件 x ∈ Ω x \in \Omega x∈Ω 下调整一组可变参数 x x x使设计目标 f ( x ) f(x) f(x) 达到最优值最大/最小
机翼最优化设计
描述机翼的方法 给定点插值 自由型面方法
肋板结构优化
最初的方法是预先给定一些洞然后调整这些洞的大小和边界
可以想到这种方法对初始值敏感
一开始设置为实心的然后调整每一个点的密度
某一点的密度远远小于其他地方的密度时可以认为是挖空的
数学基础
线性代数/向量/矩阵理论
多元函数分析
凸优化问题凸集与凸函数问题
无约束问题的最优化条件
线性代数
从行的角度
N 维矩阵方程组的第 i 行表示一个 N-1 维的解空间比如 2 维矩阵方程组的每一行表示一条直线
从列的角度 考线性代数方程的解存在性 矩阵的每一列视为一个列向量矩阵 A A A 与列向量 x x x 的乘积可以视为矩阵 A A A 第 i 列与 x x x 中第 i 个元素相乘对 i 求和 A x b Ax b Axb
有解就是说明矩阵 A A A 的每个列向量展开的空间之中有 b b b
行列式的几何解释
线性变换的面积
向量范数和矩阵范数
向量范数
1-范数 ∣ ∣ x ∣ ∣ 1 ∑ i 1 n ∣ x i ∣ \vert \vert x \vert \vert_1 \sum_{i1}^{n} \vert x_i \vert ∣∣x∣∣1∑i1n∣xi∣
2-范数 ∣ ∣ x ∣ ∣ 2 ( ∑ i 1 n ∣ x i ∣ 2 ) 1 2 \vert \vert x \vert \vert_2 (\sum_{i1}^{n} \vert x_i \vert^2)^{\frac{1}{2}} ∣∣x∣∣2(∑i1n∣xi∣2)21
∞-范数 ∣ ∣ x ∣ ∣ ∞ max 1 ⩽ i ⩽ n ∣ x i ∣ \vert \vert x \vert \vert_{\infty} \max_{1 \leqslant i \leqslant n} \vert x_i \vert ∣∣x∣∣∞max1⩽i⩽n∣xi∣
p-范数 ∣ ∣ x ∣ ∣ p ( ∑ i 1 n ∣ x i ∣ p ) 1 p \vert \vert x \vert \vert_p (\sum_{i1}^{n} \vert x_i \vert^p)^{\frac{1}{p}} ∣∣x∣∣p(∑i1n∣xi∣p)p1
矩阵范数的更强的性质的意义
为矩阵范数加上第四个性质 ∣ ∣ A B ∣ ∣ ≤ ∣ ∣ A ∣ ∣ ⋅ ∣ ∣ B ∣ ∣ \vert \vert AB \vert \vert \leq \vert \vert A \vert \vert \cdot \vert \vert B \vert \vert ∣∣AB∣∣≤∣∣A∣∣⋅∣∣B∣∣
我们希望对一个矩阵不断做变换的时候变换之后的结果的范数不断变小然后如果我们能证明他有一个下限如果这个下限还为 0那么就相当于把变换之前的矩阵变换到了另一个目标矩阵
例如初等变换 P n ⋯ P 2 P 1 A A − 1 P_n \cdots P_2 P_1 A A^{-1} Pn⋯P2P1AA−1
为矩阵范数加上第五个性质 ∣ ∣ A x ∣ ∣ ≤ ∣ ∣ A ∣ ∣ μ ⋅ ∣ ∣ x ∣ ∣ \vert \vert Ax \vert \vert \leq \vert \vert A \vert \vert _{\mu} \cdot \vert \vert x \vert \vert ∣∣Ax∣∣≤∣∣A∣∣μ⋅∣∣x∣∣
则称矩阵范数 ∣ ∣ ⋅ ∣ ∣ μ \vert \vert \cdot \vert \vert _{\mu} ∣∣⋅∣∣μ 与向量范数 ∣ ∣ x ∣ ∣ \vert \vert x \vert \vert ∣∣x∣∣ 是相容的
那么根据这个不等式可以得到 ∣ ∣ A x ∣ ∣ ∣ ∣ x ∣ ∣ ≤ ∣ ∣ A ∣ ∣ μ \dfrac{\vert \vert Ax \vert \vert}{\vert \vert x \vert \vert} \leq \vert \vert A \vert \vert _{\mu} ∣∣x∣∣∣∣Ax∣∣≤∣∣A∣∣μ
进一步若存在 x ≠ 0 x \ne 0 x0 使成立 ∣ ∣ A ∣ ∣ μ max x ≠ 0 ∣ ∣ A x ∣ ∣ ∣ ∣ x ∣ ∣ max ∣ ∣ x ∣ ∣ 1 ∣ ∣ A x ∣ ∣ \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 ∣∣A∣∣μmaxx0∣∣x∣∣∣∣Ax∣∣max∣∣x∣∣1∣∣Ax∣∣
取 x 的各个分量 最大值是可以作为标准的唯一值
这是跟向量 x 有关的称为向量 x 的诱导范数
令 x 1那么就与 x 的大小无关但是跟计算 x 范数的方式有关
因为令了 x 1所以这个诱导范数表示单位圆/球/超球面上的所有向量 x 经过线性变换后得到的所有向量 Ax 中最长的那个的范数
几种向量范数诱导的矩阵范数
1 范数诱导的矩阵范数 ∣ ∣ A ∣ ∣ max 1 ≤ j ≤ n ∑ i 1 m ∣ A i j ∣ \vert \vert A \vert \vert \max_{1 \leq j \leq n}\sum_{i1}^{m}\vert A_{ij} \vert ∣∣A∣∣1≤j≤nmaxi1∑m∣Aij∣
为什么
首先把 A 写成列向量的形式 A [ A 1 A 2 A 3 ] A [A_1 A_2 A_3] A[A1A2A3]
所以 A x A 1 ∗ x 1 A 2 ∗ x 2 A 3 ∗ x 3 Ax A_1 * x_1 A_2 * x_2 A_3 * x_3 AxA1∗x1A2∗x2A3∗x3
两边求一范数就是 ∣ ∣ A x ∣ ∣ 1 ∣ ∣ ∑ j 1 n A j x j ∣ ∣ ≤ ∑ j 1 n \begin{align} \notag \vert \vert Ax \vert \vert_1 \vert \vert \sum_{j1}^{n} A_j x_j \vert \vert \\ \notag \leq \sum_{j1}^{n}\\ \end{align} ∣∣Ax∣∣1≤j1∑n∣∣j1∑nAjxj∣∣
无穷范数诱导的矩阵范数 ∣ ∣ A ∣ ∣ max 1 ≤ i ≤ n ∑ j 1 m ∣ A i j ∣ \vert \vert A \vert \vert \max_{1 \leq i \leq n}\sum_{j1}^{m}\vert A_{ij} \vert ∣∣A∣∣1≤i≤nmaxj1∑m∣Aij∣
为什么
首先把 A 写成行向量的形式 A [ ( A 1 T ) T ; ( A 2 T ) T ; ( A 3 T ) T ] A [(A_1^T)^T;(A_2^T)^T;(A_3^T)^T] A[(A1T)T;(A2T)T;(A3T)T] ∣ ∣ A x ∣ ∣ ∞ max 1 ≤ i ≤ n ∣ ∣ A i T x ∣ ∣ ∞ ≤ max 1 ≤ i ≤ n ∣ ∣ A i T [ 1 , 1 , ⋯ , 1 ] T ∣ ∣ ∞ max 1 ≤ i ≤ n ∑ j 1 m ∣ A i j ∣ \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_{j1}^{m} \vert A_{ij} \vert ∣∣Ax∣∣∞max1≤i≤n∣∣AiTx∣∣∞≤max1≤i≤n∣∣AiT[1,1,⋯,1]T∣∣∞max1≤i≤n∑j1m∣Aij∣
2 范数诱导的矩阵范数 ∣ ∣ A ∣ ∣ max { λ ∣ λ ∈ λ ( A T A ) } \vert \vert A \vert \vert \max\{\sqrt{\lambda} \vert \lambda \in \lambda(A^TA)\} ∣∣A∣∣max{λ ∣λ∈λ(ATA)}
为什么 ∣ ∣ A x ∣ ∣ ∣ x T A T A x ∣ 1 / 2 \vert \vert Ax \vert \vert \vert x^TA^TAx \vert ^{1/2} ∣∣Ax∣∣∣xTATAx∣1/2
因为 ∣ ∣ x T A T A x ∣ ∣ \vert \vert x^TA^TAx \vert \vert ∣∣xTATAx∣∣ 中的 A T A A^TA ATA 是一个矩阵的转置乘上这个矩阵本身所以他是一个对称矩阵对称矩阵一定可以相似对角化
有 ∣ x T A T A x ∣ 1 / 2 ∣ x T P T Λ P x ∣ 1 / 2 ∣ y T Λ y ∣ 1 / 2 ∣ ∑ i 1 n λ i y i 2 ∣ 1 / 2 λ max ∣ ∑ i 1 n λ i λ max y i 2 ∣ 1 / 2 ≤ λ max \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_{i1}^{n} \lambda_i y_i^2 \vert ^{1/2} \sqrt{\lambda_{\max}}\vert \sum_{i1}^{n} \dfrac{\lambda_i}{\lambda_{\max}} y_i^2 \vert ^{1/2} \leq \sqrt{\lambda_{\max}} ∣xTATAx∣1/2∣xTPTΛPx∣1/2∣yTΛy∣1/2∣∑i1nλiyi2∣1/2λmax ∣∑i1nλmaxλiyi2∣1/2≤λmax
此时 λ i λ max ≤ 1 \dfrac{\lambda_i}{\lambda_{\max}} \leq 1 λmaxλi≤1
y 取对应 λ i λ max \lambda_i \lambda_{\max} λiλmax 时的 y i 1 y_i 1 yi1其他的 y i 0 y_i 0 yi0 时不等式
P 是正交的所以一定是满秩的然后 x 是任意取的所以 Px 不会掉维度所以 Px 可以等于任意值所以 y Px 可以取到上面要求的值所以不等式的等号可以被取到
各种范数之间的等价性
用无穷范数证出来的性质可以推广到 1 范数上
向量与矩阵序列的收敛性
某一个向量/矩阵序列的范数 a a ≠ 0 a \ne 0 a0那么不能证明这个向量/矩阵序列收敛因为范数不等于 0 的话那么其实相当于这个向量/矩阵在某种意义上的长度不等于 0
比如一个向量的二范数收敛为 1也就是这个向量的长度始终为 1但是这个向量的方向可以任意那么这个向量序列的向量的方向如果一直是任意的话那么即使向量长度不变也不是收敛的
所以说范数收敛不能保证向量/矩阵收敛因为范数只是表征长度的量而向量/矩阵是有方向的
函数的可微性与展开
一维优化问题
每一步迭代用简单的近似函数 f 0 f_0 f0 去代替复杂函数 f ( x ) f(x) f(x)
怎么选择 f 0 f_0 f0一般是泰勒展开
泰勒展开需要知道 f ( x ) f(x) f(x) 的导数
泰勒展开一般取多少项一般取二次项就够了
为什么是二次二次函数是有极值的三次函数不一定有 f 0 f_0 f0 的极值是可以知道的然后我们把 x 移动到 f 0 f_0 f0 的极值点的位置然后在这个极值点的位置对原函数展开求新的 f 0 f_0 f0继续移动。直到不再移动的时候就是收敛了。
当然这样不一定会收敛到极小值也可能收敛到极大值但是这是有方法解决的
如果不知道 f ( x ) f(x) f(x) 的导数其他方法
插值
差分代替微分 f ( x ) ≈ f 0 ( x ) f ( x 0 ) ∇ f ∣ x 0 ( x − x 0 ) 1 2 ( x − x 0 ) T ∇ 2 f ∣ x 0 ( x − x 0 ) 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) f(x)≈f0(x)f(x0)∇f∣x0(x−x0)21(x−x0)T∇2f∣x0(x−x0)
其中 x \bf x x 是向量 ∇ \nabla ∇ 表示梯度 ∇ 2 \nabla^2 ∇2 表示 Hesse 矩阵
存在这些导数的条件是足够光滑
误差 o ( ( x − x 0 ) 2 ) o((\bf x - \bf x_0)^2) o((x−x0)2)
如果是用一次函数来近似那么 f ( x ) f ( x 0 ) ∇ f ∣ x 0 ( x − x 0 ) o ( ∣ ∣ x − x 0 ∣ ∣ ) 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(x)f(x0)∇f∣x0(x−x0)o(∣∣x−x0∣∣)
如果是二次函数来近似那么 f ( x ) ≈ f 0 ( x ) f ( x 0 ) ∇ f ∣ x 0 ( x − x 0 ) 1 2 ( x − x 0 ) T ∇ 2 f ∣ x 0 ( x − x 0 ) o ( ∣ ∣ x − x 0 ∣ ∣ 2 ) 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) f(x)≈f0(x)f(x0)∇f∣x0(x−x0)21(x−x0)T∇2f∣x0(x−x0)o(∣∣x−x0∣∣2) J [ ∂ f ( x ) ∂ x 1 ⋯ ∂ f ( x ) ∂ x n ] [ ∇ T f 1 ( x ) ⋮ ∇ T f m ( x ) ] [ ∂ f 1 ( x ) ∂ x 1 ⋯ ∂ f 1 ( x ) ∂ x n ⋮ ⋱ ⋮ ∂ f m ( x ) ∂ x 1 ⋯ ∂ f m ( x ) ∂ x n ] \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] J[∂x1∂f(x)⋯∂xn∂f(x)] ∇Tf1(x)⋮∇Tfm(x) ∂x1∂f1(x)⋮∂x1∂fm(x)⋯⋱⋯∂xn∂f1(x)⋮∂xn∂fm(x)
雅可比矩阵是向量值函数的导数 ∇ f [ ∂ f ( x ) ∂ x 1 ⋯ ∂ f ( x ) ∂ x n ] \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] ∇f ∂x1∂f(x)⋯∂xn∂f(x) ∇ 2 f ∇ ∇ f [ ∂ ∇ f ( x ) ∂ x 1 ⋯ ∂ ∇ f ( x ) ∂ x n ] [ ∂ f ( x ) ∂ x 1 2 ∂ f ( x ) ∂ x 1 ∂ x 2 ⋯ ∂ f ( x ) ∂ x 1 ∂ x n ⋯ ∂ f ( x ) ∂ x n ∂ f ( x ) ∂ x n ∂ x 2 ⋯ ∂ f ( x ) ∂ x n 2 ] \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] ∇2f∇∇f ∂x1∂∇f(x)⋯∂xn∂∇f(x) ∂x12∂f(x)⋯∂xn∂f(x)∂x1∂x2∂f(x)⋯∂xn∂x2∂f(x)⋯∂x1∂xn∂f(x)∂xn2∂f(x)
牛顿莱布尼茨公式对多维的拓展 F ( x h ) F ( x ) ∫ 0 1 ∇ F ( x τ h ) T h d τ \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 F(xh)F(x)∫01∇F(xτh)Thdτ F , x , h \bf F, \bf x, \bf h F,x,h 是列向量
Lipschitz 连续 ∣ ∣ F ( x ) − F ( y ) ∣ ∣ ≤ L ∣ ∣ x − y ∣ ∣ \vert\vert F(x) - F(y) \vert\vert \leq L \vert\vert x - y\vert\vert ∣∣F(x)−F(y)∣∣≤L∣∣x−y∣∣
自变量在变化的时候函数值的变化始终是在一个线性范围内的
知道这个条件我们可以估计 F ( x ) F(x) F(x) 的大小
给定一个抽象的函数可以替换成一个线性的函数
中值定理
收敛性分析中可能用到向量值函数的中值定理
设向量值函数 F 连续可微
(1): 对任意的 x,y ∣ ∣ F ( x ) − F ( y ) ∣ ∣ ≤ s u p 0 ≤ t ≤ 1 ∣ ∣ F ′ ( y t ( x − y ) ) ∣ ∣ ∣ ∣ x − y ∣ ∣ \vert\vert F(x) - F(y) \vert\vert \leq \mathrm{sup}_{0 \leq t \leq 1} \vert\vert F(yt(x-y)) \vert\vert \vert\vert x-y \vert\vert ∣∣F(x)−F(y)∣∣≤sup0≤t≤1∣∣F′(yt(x−y))∣∣∣∣x−y∣∣
其实就是向量值函数的值的范数/变量的范数 向量值函数的导数雅可比矩阵的值
一维情况 ∣ f ( x ) − f ( y ) x − y ∣ ≤ s u p 0 ≤ t ≤ 1 ∣ f ′ ( y t ( x − y ) ) ∣ \vert \dfrac{f(x)-f(y)}{x-y} \vert \leq \mathrm{sup}_{0 \leq t \leq 1} \vert f(yt(x-y)) \vert ∣x−yf(x)−f(y)∣≤sup0≤t≤1∣f′(yt(x−y))∣
sup 相当于一个范围内的最大值
(2): 对任意的 x,y,z ∣ ∣ F ( y ) − F ( z ) − F ′ ( x ) ( y − z ) ∣ ∣ s u p 0 ≤ t ≤ 1 ∣ ∣ F ′ ( z t ( y − z ) ) − F ′ ( 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(zt(y-z)) - F(x)\vert\vert \cdot \vert\vert y-z \vert\vert ∣∣F(y)−F(z)−F′(x)(y−z)∣∣sup0≤t≤1∣∣F′(zt(y−z))−F′(x)∣∣⋅∣∣y−z∣∣
书上写错了最后面那个是 y-z
一维情况 ∣ f ( y ) − f ( z ) y − z − f ′ ( x ) ∣ ≤ s u p 0 ≤ t ≤ 1 ∣ f ′ ( z t ( y − z ) ) − f ′ ( x ) ∣ \vert \dfrac {f(y) - f(z)}{y-z} - f(x) \vert \leq \mathrm{sup}_{0 \leq t \leq 1} \vert f(zt(y-z)) - f(x)\vert ∣y−zf(y)−f(z)−f′(x)∣≤sup0≤t≤1∣f′(zt(y−z))−f′(x)∣
由上述定理的结论 (2) 可推得 ∣ ∣ F ′ ( u ) − F ′ ( v ) ∣ ∣ ≤ L ∣ ∣ u − v ∣ ∣ \vert\vert F(u) - F(v) \vert\vert \leq L \vert\vert u-v \vert\vert ∣∣F′(u)−F′(v)∣∣≤L∣∣u−v∣∣
则对任意的 x,h ∣ ∣ F ( x h ) − F ( x ) − F ′ ( x ) h ∣ ∣ ≤ L ∣ ∣ h ∣ ∣ 2 \vert\vert F(xh)-F(x)-F(x)h \vert\vert \leq L \vert\vert h \vert\vert^2 ∣∣F(xh)−F(x)−F′(x)h∣∣≤L∣∣h∣∣2
凸优化问题 考什么是凸集凸函数 凸集 对于 x , y ∈ D x,y \in D x,y∈D, 有 λ x ( 1 − λ ) y ∈ D \lambda x (1-\lambda)y \in D λx(1−λ)y∈D
集合中任意两个端点组成的线段上的任何点也属于这个集合
凸函数 对于 x , y ∈ D x,y \in D x,y∈D, 有 f ( λ x ( 1 − λ ) y ) ≤ λ f ( x ) ( 1 − λ ) f ( y ) f(\lambda x (1-\lambda)y) \leq \lambda f(x) (1-\lambda)f(y) f(λx(1−λ)y)≤λf(x)(1−λ)f(y)
函数中任意两个端点上的函数值组成的线段上的任何点的值都大于函数在该点的函数值
凸优化可行集是凸集目标函数都是凸函数
对于凸优化问题目标函数的任意局部极小值点都是其全局极小值点
证明
反证法
设 x ∗ x^* x∗ 是一个局部极小值点
假设 x ∗ x^* x∗ 不是全局极小值点那么在可行域内存在 x o x^o xo满足 f ( x o ) f ( x ∗ ) f(x^o) f(x^*) f(xo)f(x∗)
因为可行域是凸集所以 α x o ( 1 − α ) x ∗ \alpha x^o (1-\alpha)x^* αxo(1−α)x∗ 在可行域内
又因为目标函数是凸函数所以 f ( α x o ( 1 − α ) x ∗ ) ≤ α f ( x o ) ( 1 − α ) f ( x ∗ ) ≤ α f ( x ∗ ) ( 1 − α ) f ( x ∗ ) f ( 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^*) f(αxo(1−α)x∗)≤αf(xo)(1−α)f(x∗)≤αf(x∗)(1−α)f(x∗)f(x∗)
当 α \alpha α 取充分小时 f ( α x o ( 1 − α ) x ∗ ) f ( x ∗ ) f(\alpha x^o (1-\alpha)x^*) f(x^*) f(αxo(1−α)x∗)f(x∗)
这与 f ( x ∗ ) f(x^*) f(x∗) 是局部极小值矛盾
凸函数的判断
f 在 D 一阶可微
充要条件 f ( x ) ≥ f ( x ∗ ) ∇ f ( x ∗ ) T ( x − x ∗ ) f(x) \geq f(x^*) \nabla f(x^*)^T(x-x^*) f(x)≥f(x∗)∇f(x∗)T(x−x∗)
对一个点一阶泰勒展开也就是得到一个超平面超平面上的值都小于函数值
严格凸的充要条件 f ( x ) f ( x ∗ ) ∇ f ( x ∗ ) T ( x − x ∗ ) f(x) f(x^*) \nabla f(x^*)^T(x-x^*) f(x)f(x∗)∇f(x∗)T(x−x∗)
正定矩阵 考Hessian 矩阵正定表示什么含义 对于一元函数二阶导大于 0 意味着开口向上 h T ∇ 2 f ( x ) h ≥ 0 h^T \nabla^2 f(x) h \geq 0 hT∇2f(x)h≥0 半正定 h T ∇ 2 f ( x ) h 0 h^T \nabla^2 f(x) h 0 hT∇2f(x)h0 正定
其中 h 类似 h [ x y ] h \left[\begin{array}{ccc} x \\ y \end{array}\right] h[xy]
矩阵正定代表一个开口向上的抛物面
那就说明每一步迭代都会稳定
f 在 D 二阶可微
进一步如果 h T ∇ 2 f ( x ) h ≥ c ∣ ∣ h ∣ ∣ 2 h^T \nabla^2 f(x) h \geq c\vert \vert h \vert \vert^2 hT∇2f(x)h≥c∣∣h∣∣2 一致正定
其中 c ∣ ∣ h ∣ ∣ 2 c\vert \vert h \vert \vert^2 c∣∣h∣∣2 就是一个抛物面
f 在 D 上凸 充要条件 ∇ 2 f ( x ) \nabla^2 f(x) ∇2f(x) 对 D 半正定
f 在 D 上严格凸 ∇ 2 f ( x ) \nabla^2 f(x) ∇2f(x) 对一切 D 正定
我感觉是函数二阶可微的时候也可以用一阶可微时的那个充要条件只是说当函数二阶可微的时候我们还可以有另外一个充要条件这两个充要条件对于二阶可微的函数来说是同时有效的
无约束问题的最优性条件 考必要条件充分条件 一阶必要条件
若 x ∗ x^* x∗ 是局部极小点那么有 g ( x ∗ ) 0 g(x^*) 0 g(x∗)0 g ( x ) g(x) g(x) 为一阶导数
二阶必要条件
若 x ∗ x^* x∗ 是局部极小点那么有 g ( x ∗ ) 0 g(x^*) 0 g(x∗)0, G ( x ∗ ) G(x^*) G(x∗) 是半正定矩阵 g ( x ) g(x) g(x) 为一阶导数 G ( x ) G(x) G(x) 为二阶导数
半正定的性质 d T G ( x ∗ ) d d^TG(x^*)d dTG(x∗)d 表示一个抛物面
二阶充分条件
若 f f f 二阶连续可微 g ( x ∗ ) 0 g(x^*) 0 g(x∗)0 G ( x ∗ ) G(x^*) G(x∗) 正定那么 x ∗ x^* x∗ 是局部极小点
其中 G ( x ∗ ) G(x^*) G(x∗) 正定 f f f 二阶连续可微 - 在 x ∗ x^* x∗ 的邻域里面 G ( x ∗ θ α d ) G(x^*\theta \alpha d) G(x∗θαd) 正定
充要条件 考二次函数什么时候有最小值 是凸函数是一阶连续可微那么 g ( x ∗ ) 0 ⟺ g(x^*) 0 \iff g(x∗)0⟺ x ∗ x^* x∗ 是全局极小点
一般算法框架 考线搜索的框架 给定初始化参数及初始迭代点 x 0 x_0 x0置 k : 0 k : 0 k:0 若 x k x_k xk 满足某种终止准则停止迭代以 x k x_k xk 作为近似极小点 通过求解 x k x_k xk 处的某个子问题确定下降方向 x k x_k xk 通过某种搜索方式确定步长因子 α k \alpha_k αk使得 f ( x k α k d k ) f ( x k ) f(x_k \alpha_k d_k) f(x_k) f(xkαkdk)f(xk) 令 x k 1 : x k α k d k , k : k 1 x_{k1} : x_k \alpha_k d_k, k : k 1 xk1:xkαkdk,k:k1转步 2
线搜索
这里讲的是一般算法框架中的第 4 步中的“某种搜索方式” 考已知搜索方向给出一维方向上的表达式 x k 1 : x k α k d k x_{k1} : x_k \alpha_k d_k xk1:xkαkdk
精确线搜索
单峰区间 考单峰区间的原理和步骤 进退法找近似单峰区间的时候实际上是找到了高低高三个点你是不知道两个端点之间的函数值分布的情况的
黄金分割方法 考黄金分割的原理具体步骤 找完近似单峰区间之后接下来要继续找细分后的近似单峰区间那么其实一个区间里面要知道四个点
然后我希望下一次找单峰区间的时候能够尽可能利用到上一步采样的点
因为每一次算点的函数值都会很费时
使得新的小区间与旧的大区间成比例那么可以复用三个点
也就是每迭代一步只需要增加三个点
已知两个点怎么算中间两个点
设已知 a, b, l (b-a), 第一个点 a 0.382 l, 第二个点 a 0.618 l
已知四个点怎么知道取左侧三个点还是取右侧三个点
比较中间两个点之间的大小如果左 右说明是 低-高那么就和左边端点组成 高-低-高所以我们取左侧三个点右侧同理
无法执行黄金分割的情况
进退法只能找到高低高三个点
黄金分割的一开始是取两侧的高点然后在中间先按照黄金分割插入两个点然后看左侧三个点满足高低高还是右侧满足选择满足高低高的那一侧递归
但是假设一开始我插入了两个点之后我发现这两个点都大于我两侧的高点那么我现在找不到高低高了
那么这就意味着我无法执行黄金分割了
一种方法是我换一个分割方法也就是换一个“插点-找高低高-插点-找高低高”的思路
另外一种方法就是直接放弃精确线搜索直接把一开始进退法找到的近似单峰区间的高低高的低点作为下一步的线搜索的起点
牛顿法
原理
函数 f ( x ) f(x) f(x) 在 x k x_k xk 处近似为二次泰勒展开 f ( x ) ≈ f k ( x ) f ( x k ) f ′ ( x k ) ( x − x k ) 1 2 f ′ ′ ( x k ) ( x − x k ) 2 f(x) \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)≈fk(x)f(xk)f′(xk)(x−xk)21f′′(xk)(x−xk)2
以近似函数导数为零的点来近似函数 f ( x ) f(x) f(x) 的极小值点 f k ′ ( x ) f ′ ( x k ) f ′ ′ ( x k ) ( x − x k ) 0 f_k(x) f(x_k) f(x_k)(x-x_k) 0 fk′(x)f′(xk)f′′(xk)(x−xk)0
- x k 1 x k − f ′ ( x k ) f ′ ′ ( x k ) x_{k1} x_k - \dfrac{f(x_k)}{f(x_k)} xk1xk−f′′(xk)f′(xk)
算法 给出 x 1 ∈ R , k : 1 x_1 \in \mathcal{R}, k : 1 x1∈R,k:1 计算 f ′ ( x k ) , f ′ ′ ( x k ) f(x_k), f(x_k) f′(xk),f′′(xk) 如果 f ′ ( x k ) 0 f(x_k) 0 f′(xk)0则停。否则更新 x k 1 x k − f ′ ( x k ) f ′ ′ ( x k ) x_{k1} x_k - \dfrac{f(x_k)}{f(x_k)} xk1xk−f′′(xk)f′(xk)
收敛速度
因为 ∣ x k 1 − x ∗ ∣ / ∣ x k − x ∗ ∣ → 0 \vert x_{k1} - x^* \vert / \vert x_k - x^* \vert \rightarrow 0 ∣xk1−x∗∣/∣xk−x∗∣→0所以是超线性收敛
算误差的时候 x k 1 − x ∗ x_{k1} - x^* xk1−x∗ 算是 k1 步的误差
将牛顿法的迭代公式代入 x k 1 − x ∗ x k − f ′ ( x k ) f ′ ′ ( x k ) − x ∗ x k − x ∗ − f ′ ( x k ) f ′ ′ ( x k ) x_{k1} - x^* x_k - \dfrac{f(x_k)}{f(x_k)} - x^* x_k - x^* - \dfrac{f(x_k)}{f(x_k)} xk1−x∗xk−f′′(xk)f′(xk)−x∗xk−x∗−f′′(xk)f′(xk)
其中 x k − x ∗ x_k - x^* xk−x∗ 就是 k 步的误差
所以我们希望把后面的 f ′ ( x k ) f ′ ′ ( x k ) \dfrac{f(x_k)}{f(x_k)} f′′(xk)f′(xk) 也写成某步的误差
用牛顿莱布尼茨公式 f ′ ( x k ) f ′ ′ ( x k ) f ′ ( x ∗ ) ∫ x ∗ x k f ′ ′ ( x ) d x 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′′(xk)f′(xk)f′′(xk)f′(x∗)∫x∗xkf′′(x)dx
因为 f ′ ( x ∗ ) 0 f(x^*) 0 f′(x∗)0
所以 f ′ ( x k ) f ′ ′ ( x k ) ∫ x ∗ x k f ′ ′ ( x ) d x f ′ ′ ( x k ) \dfrac{f(x_k)}{f(x_k)} \dfrac{\int_{x^*}^{x_k}f(x)\mathrm{d}x}{f(x_k)} f′′(xk)f′(xk)f′′(xk)∫x∗xkf′′(x)dx
所以 x k − x ∗ − f ′ ( x k ) f ′ ′ ( x k ) f ′ ′ ( x k ) ( x k − x ∗ ) − ∫ x ∗ x k f ′ ′ ( x ) d x f ′ ′ ( x k ) ∫ x ∗ x k f ′ ′ ( x k ) − f ′ ′ ( x ) 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)} xk−x∗−f′′(xk)f′(xk)f′′(xk)f′′(xk)(xk−x∗)−∫x∗xkf′′(x)dxf′′(xk)∫x∗xkf′′(xk)−f′′(x)dx
因为 f ′ ′ ( x ∗ ) ≠ 0 f(x^*) \ne 0 f′′(x∗)0 所以 x k x_k xk 充分靠近 x ∗ x^* x∗ 时由保号性也有 f ′ ′ ( x k ) ≠ 0 f(x_k) \ne 0 f′′(xk)0
所以分母不为 0就不管了
李普希兹连续时 ∣ f ′ ′ ( x k ) − f ′ ′ ( x ) ∣ ⩽ M ∣ x k − x ∗ ∣ \vert f(x_k) - f(x)\vert \leqslant M \vert x_k - x^*\vert ∣f′′(xk)−f′′(x)∣⩽M∣xk−x∗∣
又因为 d x \mathrm{d}x dx 也是与 x k − x ∗ x_k - x^* xk−x∗ 同阶所以 ∫ x ∗ x k f ′ ′ ( x k ) − f ′ ′ ( x ) d x o ( ∣ x k − x ∗ ∣ 2 ) \int_{x^*}^{x_k}f(x_k) - f(x)\mathrm{d}x o(\vert x_k - x^*\vert^2) ∫x∗xkf′′(xk)−f′′(x)dxo(∣xk−x∗∣2)
割线法
牛顿法需要计算二阶导数。如果我们不知道二阶导数
那么就用差商代替导数即 f ′ ′ ( x k ) ≈ f ′ ( x k ) − f ′ ( x k − 1 ) x k − x k − 1 f(x_k) \approx \dfrac{f(x_k)-f(x_{k-1})}{x_k - x_{k-1}} f′′(xk)≈xk−xk−1f′(xk)−f′(xk−1)
从牛顿法可以导出 x k 1 x k − f ′ ( x k ) x k − x k − 1 f ′ ( x k ) − f ′ ( x k − 1 ) x_{k1} x_k - f(x_k)\dfrac{x_k - x_{k-1}}{f(x_k)-f(x_{k-1})} xk1xk−f′(xk)f′(xk)−f′(xk−1)xk−xk−1
抛物线方法
原理 考精确线搜索的抛物线方法 他是一个在 x k , x k − 1 , x k − 2 x_k, x_{k-1}, x_{k-2} xk,xk−1,xk−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) 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)f(xk)(x−xk)f[xk,xk−1](x−xk)(x−xk−1)f[xk,xk−1,xk−2]
其中 f [ x k , x k − 1 ] f ( x k ) − f ( x k − 1 ) x k − x k − 1 f[x_k, x_{k-1}] \dfrac{f(x_k)-f(x_{k-1})}{x_k - x_{k-1}} f[xk,xk−1]xk−xk−1f(xk)−f(xk−1) f [ x k , x k − 1 , x k − 2 ] f [ x k , x k − 1 ] − f [ x k − 1 , x k − 2 ] x k − x k − 2 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[xk,xk−1,xk−2]xk−xk−2f[xk,xk−1]−f[xk−1,xk−2]
是函数 f ( x ) f(x) f(x) 的一阶和二阶差商
差商是一种描述这个插值函数的方法
也可以用拉格朗日插值多项式来描述
算法
给定三个点构建插值函数
用一阶导等于 0 来找这个插值函数的极小点
在三个插值点和这个找到的极小点之间找左侧三个点是高低高还是右侧三个点是高低高
类似黄金分割也是不断找新的三个点
得到新的三个插值点循环
与黄金分割的对比
与其他方法对比黄金分割确定三个点之后新的点总是在这三个点里面的所以区间总是收缩的
如果按照书上的方法抛物线方法的初始时刻三个点选择 s 0 , s 0 h , s 0 2 ∗ h s_0, s_0 h, s_0 2*h s0,s0h,s02∗h那么这三个点不一定是高低高的所以构建出的抛物线的最低点不一定是在这三个点之间所以你的搜索区间不一定是收缩的
所以更好的方法是一开始进退法找到了高低高三个点然后把这三个点用来作为抛物线方法的初始三个点
抛物线方法与黄金分割的不同就是插点方法的不同黄金分割根据黄金比例来决定插点的位置抛物线方法是根据近似的抛物线的最低点的位置来决定插点的位置
之后递归条件仍然是一样的找左侧三个点是高低高还是右侧三个点是高低高
判断插点位置的注意事项
要注意的是判断插点的位置是用近似的抛物线但是判断左侧三个点和右侧三个点的时候点的取值是要代入原函数取值的
因为这里很容易写错插点的函数值取值容易写错成从抛物线最低点取到 x 的位置然后把 x 代入抛物线取值
实际上正确的是从抛物线最低点取到 x 的位置然后把 x 代入原函数取值
非精确线搜索
一开始距离极小值点比较远的时候使用精确线搜索也没有什么意义反而迭代更多
准则这一步的函数值比上一步的函数值小多少
Armijo-Goldstein 准则
要求这一步的函数值小于上一步的函数值
进一步要求这一步的函数值相比于上一步的函数值有一定的下降量
每一步选择下降最快的方向整体可能并不是下降最快的 g k T d k 0 \mathbf{g}_k^T \mathbf{d}_k 0 gkTdk0 保证这是一个下降的方向
所以要求 f ( x k ) ρ α k g k T d k f(x_k) \rho \alpha_k \mathbf{g}_k^T \mathbf{d}_k f(xk)ραkgkTdk 有一个下降量它相当于一个斜线
自然我们知道这个斜线的斜率是不确定的那么斜率就可能是一个问题比如如果斜率选择不当可能导致击中的原函数的点的值与处发现很接近也就是每一步下降的幅度可能会小
所以我们要想办法把 α 0 \alpha 0 α0 附近的区域刨去
所以再要求 f ( x k ) ( 1 − ρ ) α k g k T d k f(x_k) (1-\rho) \alpha_k \mathbf{g}_k^T \mathbf{d}_k f(xk)(1−ρ)αkgkTdk 也有一个下降量
又因为我们希望 f ( x k ) ( 1 − ρ ) α k g k T d k f(x_k) (1-\rho) \alpha_k \mathbf{g}_k^T \mathbf{d}_k f(xk)(1−ρ)αkgkTdk 击中的点是 α b \alpha b αb f ( x k ) ρ α k g k T d k f(x_k) \rho \alpha_k \mathbf{g}_k^T \mathbf{d}_k f(xk)ραkgkTdk 击中的点是 α c \alpha c αc
又希望可行区间是 ( b , c ) (b,c) (b,c) 那么就是希望 b c bc bc那么就是希望 f ( x k ) ( 1 − ρ ) α k g k T d k f(x_k) (1-\rho) \alpha_k \mathbf{g}_k^T \mathbf{d}_k f(xk)(1−ρ)αkgkTdk 的斜率的绝对值比 f ( x k ) ρ α k g k T d k f(x_k) \rho \alpha_k \mathbf{g}_k^T \mathbf{d}_k f(xk)ραkgkTdk 更大
所以要求 0 ρ 1 / 2 0 \rho 1/2 0ρ1/2
Wolfe-Powell 准则
之前的 Armijo-Goldstein 准则衡量“一定的下降量”是使用函数值来衡量的
现在这个 Wolfe-Powell 准则衡量“一定的下降量”是使用斜率 g k T d k \mathbf{g}_k^T \mathbf{d}_k gkTdk 来衡量的
也就是假设了 f ( x k ) ρ α k g k T d k f(x_k) \rho \alpha_k \mathbf{g}_k^T \mathbf{d}_k f(xk)ραkgkTdk 击中的点是 α c \alpha c αc
然后希望有一定的斜率那么设可接受斜率是初始斜率的 σ \sigma σ 倍
那么我个人觉得有两种方法
一种是假设 f ( x k ) σ α k g k T d k f(x_k) \sigma \alpha_k \mathbf{g}_k^T \mathbf{d}_k f(xk)σαkgkTdk 击中的点是 α e \alpha e αe
还有一种是他设的取原曲线上斜率为 σ α k g k T d k \sigma \alpha_k \mathbf{g}_k^T \mathbf{d}_k σαkgkTdk 的位置是 α e \alpha e αe
可行区间为 ( e , c ) (e,c) (e,c)
他这种设法还可以使得精确解的最小值包含在 ( e , c ) (e,c) (e,c) 中
为了保证 e c ec ec 需要 ρ σ \rho \sigma ρσ σ 1 \sigma 1 σ1 是为了使得 σ α k g k T d k \sigma \alpha_k \mathbf{g}_k^T \mathbf{d}_k σαkgkTdk 代表的斜率的线更靠近水平一点这样就可以避开 x k x_k xk 点也就是避开 α 0 \alpha 0 α0 的附近
Armijo 准则的实现 考Armijo 准则知道怎么算 β m \beta^m βm 随着步数 m m m 从 0 开始增加 给定 β ∈ ( 0 , 1 ) , σ ∈ ( 0 , 0.5 ) \beta \in (0,1), \sigma \in (0,0.5) β∈(0,1),σ∈(0,0.5)令 m : 0 m : 0 m:0 若不等式 f ( x k β m d k ) ⩽ f ( x k ) σ β m g k T d k f(x_k \beta^m d_k) \leqslant f(x_k) \sigma \beta^m g_k^T d_k f(xkβmdk)⩽f(xk)σβmgkTdk 成立置 m k : m , x k 1 x k β m k d k m_k : m, x_{k1} x_k \beta^{m_k} d_k mk:m,xk1xkβmkdk停算否则转步 3 令 m : m 1 m : m 1 m:m1转步 2
线搜索方法框架
搜索方向与负梯度方向的夹角小于 90 度
线搜索方法的收敛性 f ( x k ) f(x_k) f(xk) 单调下降且有界 f ( x k ) − f ( x k 1 ) → 0 f(x_k)-f(x_{k1}) \rightarrow 0 f(xk)−f(xk1)→0
意味着 x k 1 x k o ( d k ) x_{k1} x_{k} o(d_k) xk1xko(dk) ∣ ∣ a ⋅ b ∣ ∣ ⩽ ∣ ∣ a ∣ ∣ ⋅ ∣ ∣ b ∣ ∣ \vert \vert a \cdot b \vert \vert \leqslant \vert \vert a \vert \vert \cdot \vert \vert b \vert \vert ∣∣a⋅b∣∣⩽∣∣a∣∣⋅∣∣b∣∣ d k / ∣ ∣ d k ∣ ∣ d_k / \vert \vert d_k \vert \vert dk/∣∣dk∣∣ 是单位向量
所以 [ g ( ε ) − g k ] T d k / ∣ ∣ d k ∣ ∣ ⩽ ∣ ∣ g ( ε ) − g k ∣ ∣ [g(\varepsilon)-g_k]^T d_k / \vert \vert d_k \vert \vert \leqslant \vert \vert g(\varepsilon)-g_k \vert \vert [g(ε)−gk]Tdk/∣∣dk∣∣⩽∣∣g(ε)−gk∣∣
之后的 ∣ ∣ g ( ε ) − g k ∣ ∣ ⩽ 1 / 2 ∗ ϵ 0 \vert \vert g(\varepsilon)-g_k \vert \vert \leqslant 1/2 * \epsilon_0 ∣∣g(ε)−gk∣∣⩽1/2∗ϵ0 其中 1 / 2 ∗ ϵ 0 1/2 * \epsilon_0 1/2∗ϵ0 是人为取的 lim k → ∞ ∇ f ( x k 1 ) T s k / g k T s k 1 \lim_{k \rightarrow \infty}\nabla f(x_{k1})^T s_k/g_k^T s_k 1 limk→∞∇f(xk1)Tsk/gkTsk1
这就是表示这一步的斜率和下一步的斜率一样
但是 Armijo 准则要求 ρ σ 1 \rho \sigma 1 ρσ1 于是矛盾
书上的一个问题想要证明小于号变成大于号但是万一一开始就满足大于号的话就没有这个转变的过程了
梯度法和牛顿法
这里讲的是一般搜索框架中的“确定下降方向”
最速下降法梯度法
最速下降法梯度法取负梯度方向作为
牛顿法
牛顿法取 G k d k − g k G_k d_k -g_k Gkdk−gk 的解 d k d_k dk 作为下降方向
阻尼牛顿法
阻尼牛顿法引入线搜索方程保证收敛性也就是用牛顿法确定下降方向搜索方向有了搜索方向之后再沿这个搜索方向做 Armijo 搜索
修正牛顿法
基本/阻尼牛顿法中要每一步的 Hesse 矩阵正定才能保证牛顿方向为下降方向
每一步怎么判断 Hesse 矩阵是否正定直接算 dTGd? 不用因为你是用 G k d k − g k G_k d_k -g_k Gkdk−gk 算出来的解 d k d_k dk所以你只要用 g k T d k g_k^T d_k gkTdk 验证就好了如果 g k T d k 0 g_k^T d_k 0 gkTdk0表示求出来的搜索方向 d k d_k dk 确实与负梯度成锐角那么就说明 Hesse 矩阵正定否则不是正定
那么 Hesse 矩阵不正定时不能保证牛顿方向为下降方向该怎么办
牛顿/梯度混合法在 Hesse 矩阵不正定时用梯度下降法也就是求出的 d k d_k dk 不对时直接令 d k d_k dk 为负梯度
修正牛顿法在 Hesse 矩阵对角线上加一个正数保障正定性
也就是之前的算法都是用 G k d k − g k G_k d_k -g_k Gkdk−gk 算出来的搜索方向 d k d_k dk
现在修正牛顿法用 ( G k μ k I ) d k − g k (G_k \mu_k I) d_k -g_k (GkμkI)dk−gk 算出来搜索方向 d k d_k dk
共轭方向法和共轭梯度法
首先共轭方向法不等于共轭梯度法
考虑有极小值的函数
一次函数没有所以考虑二次函数
多元函数 f ( x ) 1 / 2 x T G x b T x c f(x) 1/2 x^TGx b^Tx c f(x)1/2xTGxbTxc
它的一阶导 ∇ f G x b \nabla f Gx b ∇fGxb
求极小值就是求 G x b 0 Gx b 0 Gxb0
求极小值就是等价于求这个线性代数方程组的解
有直接求解的方法或者迭代求解的方法
找一个解就是找这个 n 维空间的一个点
因为这个点在 n 维空间内所以这个点可以表达成这个 n 维空间的 n 个线性独立的基向量的线性组合
直接的方法的话就是直接确定这个线性组合的系数
迭代求解的比如之前讲到的最速下降法和基本牛顿法
最速下降法的问题是他是一阶收敛速度收敛速度太慢
基本牛顿法用 G k d k − g k G_k d_k -g_k Gkdk−gk 算出来搜索方向 d k d_k dk
其中要算一个二阶导 Hesse 矩阵对于工程问题计算量太大
现在我们希望有一个方法把这个确定 n 个系数的过程分为 n 步每一步确定一个系数
要求我们第 i 步求解不会影响我们之前求解出来的系数
那么就是要求我们的线性组合的 n 个线性独立的基向量他不单单是线性独立的还需要是正交的
每一步找距离精确点最近
在第 i 步上沿着第 i 个基向量走走到误差最小的点所以这个时候迭代向量在第 i 个基向量的方向上的投影已经等于距离精确点在第 i 个方向上的投影
为了求第 i 步的长度利用 e i e_i ei 与 d i d_i di 垂直 e i ⋅ d i 0 e_i \cdot d_i 0 ei⋅di0 来计算其中 e i x i − x ∗ e_i x_i - x^* eixi−x∗
但是 x ∗ x^* x∗ 不知道所以我们新增一个要求 e i T G d i 0 e_i^TGd_i 0 eiTGdi0其中的 x ∗ x^* x∗ 项会变成 G x ∗ b Gx^* b Gx∗b这样就可以求了
那么其实我们现在不用 e i ⋅ d i 0 e_i \cdot d_i 0 ei⋅di0 来求 e i e_i ei 了
我们直接用 e i T G d i 0 e_i^TGd_i 0 eiTGdi0 来求 e i e_i ei
这就相当于我们新定义了一个内积的形式 a , b a T G b 0 a,b a^TGb 0 a,baTGb0
那么要求 n 个基向量互相正交也就是 d i , d j d i T G d j δ i j d_i, d_j d_i^TGd_j \delta_{ij} di,djdiTGdjδij
要求第 i 步的基向量 d i d_i di 与梯度方向 g 内积 0
也是用二次函数拟合所以误差也是二次
收敛速度的证明
定理 21 第 i 步找的极小值点是函数曲面的等值线与第 i 步的基向量与之前的基向量张成的线性流形相切的点
比如第一步极小值是 d 1 d_1 d1 这个线与函数曲面的等值线相切的点
第二步极小值是 d 1 , d 2 d_1,d_2 d1,d2 张成的平面与函数曲面的切点
第三步…
现在我们的要求改为了 n 个基向量是 G 共轭的
n 个基向量是 G 共轭可以推出这 n 个基向量是线性无关的反证法
定理 21 的作用是极小值意味着梯度 0
我们在共轭方向法中下降方向虽然不是第 i 个点的梯度但是我们需要知道第 i 个点的梯度来判断我们第 i 个点的下降方向是否是合理的是否是使得函数下降的
那么我们要求第 i1 点的梯度时这个第 i1 点的梯度是垂直于前 i 个基向量张成的流形
因此我们要证明第 i1 点的梯度垂直于前 i 个基向量张成的流形
证明过程…两部分
解释第一部分第 i 步的搜索搜索到的第 i 1 步的点它和第 i 1 点处梯度相互垂直
计算过程中需要用到 G也就是海森矩阵怎么避免计算
构造 d
公式略
系数为 0 的时候就是每一步为负梯度方向就是最速下降
所以公式是负梯度减去负梯度在旧基向量方向上的投影才能得到新的 d 与旧的 d 相互 G 共轭
这些系数就用新的 d 与旧的 d 相互 G 共轭来求
求的过程中公式推导用到了 G x g Gx g Gxg
还用到了 g k ∗ g k − 1 0 g_k * g_{k-1} 0 gk∗gk−10
因为根据公式 g k − 1 g_{k-1} gk−1 就是 d 0 d_0 d0 到 d k − 1 d_{k-1} dk−1 的线性组合
而 g k g_k gk 已经证了和 d 0 d_0 d0 到 d k − 1 d_{k-1} dk−1 张成的流形垂直所以就是与 d 0 d_0 d0 到 d k − 1 d_{k-1} dk−1 都垂直
另一种讲法
把精确解 x ∗ x^* x∗ 拆成 d d d 的线性组合
如果 d i d_i di 之间是正交的那么用 a i d i x d i a_id_i xd_i aidixdi 可以求出 a i a_i ai
但是现在精确解是未知的 ( ∑ a i d i − x ∗ ) T G d j 0 (\sum{a_i d_i} - x^*)^TGd_j0 (∑aidi−x∗)TGdj0
未知 x ∗ x^* x∗ 的时候如果用 d 这个线性组合把 x ∗ x^* x∗ 分解得很精确那么 ∑ a i d i − x ∗ 0 \sum{a_i d_i} - x^* 0 ∑aidi−x∗0 上式就成立
拆开 ( ∑ a i d i ) T G d j − ( x ∗ ) T G d j 0 (\sum{a_i d_i})^TGd_j - (x^*)^TGd_j0 (∑aidi)TGdj−(x∗)TGdj0
这个精确解 x ∗ x^* x∗ 还是未知还是要处理 ( x ∗ ) T G d j (x^*)^TGd_j (x∗)TGdj 是一个标量所以 ( x ∗ ) T G d j ( ( x ∗ ) T G d j ) T (x^*)^TGd_j ((x^*)^TGd_j)^T (x∗)TGdj((x∗)TGdj)T ( x ∗ ) T G d j ( ( x ∗ ) T G d j ) T d j T G T x ∗ d j T G x ∗ d j T b (x^*)^TGd_j ((x^*)^TGd_j)^T d_j^T G^T x^* d_j^T G x^* d_j^T b (x∗)TGdj((x∗)TGdj)TdjTGTx∗djTGx∗djTb x ∗ x^* x∗ 就没了
怎么求第 k 步的搜索方向
共轭方向法只是确定了每一个搜索方向之间都要满足 G 共轭在 k-1 步沿着 d k − 1 d_{k-1} dk−1 搜索了之后还要确定 d k d_k dk
如果仅仅是使用 G 共轭这个条件的话可以求但是要求 G
为了避免计算这个 G
我们把第 k 步搜索方向取为前 k−1 步搜索方向与第 k 步负梯度的线性组合
这个方法就叫做共轭梯度法
这就是共轭方向法和共轭梯度法的区别 d k − g k β k − 1 d k − 1 ∑ i 0 k − 2 β k i d i d_k -g_k \beta_{k-1}d_{k-1} \sum_{i0}^{k-2}\beta_{k}^i d_i dk−gkβk−1dk−1∑i0k−2βkidi
根据 d k d_k dk 与 d i , i 0 , . . . , k − 1 d_i, i 0, ..., k-1 di,i0,...,k−1 G 共轭来确定线性组合中的系数 0 d k − 1 T G d k − d k − 1 T G g k β k − 1 d k − 1 T G d k − 1 ∑ i 0 k − 2 β k i d k − 1 T G d i 0 d^T_{k-1}Gd_k -d^T_{k-1}Gg_k \beta_{k-1}d^T_{k-1}Gd_{k-1} \sum_{i0}^{k-2}\beta_{k}^i d^T_{k-1}Gd_i 0dk−1TGdk−dk−1TGgkβk−1dk−1TGdk−1∑i0k−2βkidk−1TGdi
为什么这里要把 0 到 k-2 和 k-1 分开写
经过 k-1 步之后 0 到 k-2 的搜索方向和 k-1 步的搜索方向 G 共轭所以 d k − 1 T G d i 0 d^T_{k-1}Gd_i 0 dk−1TGdi0
所以上式最后一项消去
现在变成 0 − d k − 1 T G g k β k − 1 d k − 1 T G d k − 1 0 -d^T_{k-1}Gg_k \beta_{k-1}d^T_{k-1}Gd_{k-1} 0−dk−1TGgkβk−1dk−1TGdk−1
- β k − 1 g k T G d k − 1 d k − 1 T G d k − 1 \beta_{k-1} \dfrac{g^T_{k}Gd_{k-1}}{d^T_{k-1}Gd_{k-1}} βk−1dk−1TGdk−1gkTGdk−1
因为 G 是二阶导所以乘以一个方向之后就是一阶导
或者这么想 g ( x ) ∇ f ( x ) G x b , G ( x ) ∇ 2 f ( x ) G g(x) \nabla f(x) Gx b, G(x) \nabla^2 f(x) G g(x)∇f(x)Gxb,G(x)∇2f(x)G
所以 g 1 − g 0 G ( x 1 − x 0 ) α 0 G d 0 g_1 - g_0 G(x_1 - x_0) \alpha_0 G d_0 g1−g0G(x1−x0)α0Gd0
所以 G d k − 1 1 / α 0 ∗ ( g k − g k − 1 ) Gd_{k-1} 1/\alpha_0 * (g_k -g_{k-1}) Gdk−11/α0∗(gk−gk−1)
上式化为 β k − 1 g k T G d k − 1 d k − 1 T G d k − 1 g k T ( g k − g k − 1 ) d k − 1 T ( 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})} βk−1dk−1TGdk−1gkTGdk−1dk−1T(gk−gk−1)gkT(gk−gk−1)
其中用到了转置。因为最后计算结果是标量所以可以随意转置
因为每一步确定搜索方向之后沿着这个方向不管是精确线搜索还是非精确线搜索都是确定到了极小值点才停止所以每一步走完之后的负梯度方向之间应该是互相垂直的
即 g k T g k − 1 0 g^T_k g_{k-1} 0 gkTgk−10
又因为我们前面证明过了第 i 步找的极小值点是函数曲面的等值线与第 i 步的基向量与之前的基向量张成的线性流形相切的点
也就是 g k T d i 0 , i 0 , . . . , k − 1 g^T_k d_i 0, i 0, ..., k-1 gkTdi0,i0,...,k−1
那么上式化为 β k − 1 g k T G d k − 1 d k − 1 T G d k − 1 g k T ( g k − g k − 1 ) d k − 1 T ( g k − g k − 1 ) g k T g k d k − 1 T 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})} \dfrac{g^{T}_{k}g_k}{d^{T}_{k-1}g_{k-1}} βk−1dk−1TGdk−1gkTGdk−1dk−1T(gk−gk−1)gkT(gk−gk−1)dk−1Tgk−1gkTgk
再次使用我们对 d 的假设 d k − g k β k − 1 d k − 1 ∑ i 0 k − 2 β k i d i d_k -g_k \beta_{k-1}d_{k-1} \sum_{i0}^{k-2}\beta_{k}^i d_i dk−gkβk−1dk−1∑i0k−2βkidi 代入到分母的那个 d k − 1 d_{k-1} dk−1 中和 g k − 1 g_{k-1} gk−1 一乘0 到 k-2 的 d 和 k-1 的 g 相乘是 0所以消到只剩下 k-1 的 g 乘 k-1 的 g β k − 1 g k T G d k − 1 d k − 1 T G d k − 1 g k T ( g k − g k − 1 ) d k − 1 T ( g k − g k − 1 ) g k T g k d k − 1 T g k − 1 g k T g k g k − 1 T 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})} \dfrac{g^{T}_{k}g_k}{d^{T}_{k-1}g_{k-1}} \dfrac{g^{T}_{k}g_k}{g^{T}_{k-1}g_{k-1}} βk−1dk−1TGdk−1gkTGdk−1dk−1T(gk−gk−1)gkT(gk−gk−1)dk−1Tgk−1gkTgkgk−1Tgk−1gkTgk
这样就求出了 β k − 1 \beta_{k-1} βk−1
那么接下来求其他系数。根据 d k d_k dk 与 d j , j 0 , . . . , k − 2 d_j, j 0, ..., k-2 dj,j0,...,k−2 G 共轭 0 d j T G d k − d j T G g k β k − 1 d j T G d k − 1 ∑ i 0 k − 2 β k i d j T G d i , j 0 , . . . , k − 2 0 d^T_j G d_k -d^T_{j}Gg_k \beta_{k-1}d^T_{j}Gd_{k-1} \sum_{i0}^{k-2}\beta_{k}^i d^T_{j}Gd_i, j 0, ..., k-2 0djTGdk−djTGgkβk−1djTGdk−1∑i0k−2βkidjTGdi,j0,...,k−2
其中因为各个搜索方向 G 共轭所以 d j T G d k − 1 0 d^T_{j}Gd_{k-1} 0 djTGdk−10 中间那项消掉
对于第三项同理因为 G 共轭所以消到只剩下 dj 乘 dj 的那项
上式化简为 0 − d j T G g k β k j d j T G d j , j 0 , . . . , k − 2 0 -d^T_j G g_k \beta_k^j d_j^T G d_j, j 0, ..., k-2 0−djTGgkβkjdjTGdj,j0,...,k−2
- β k j G g k T d T d T d j T G d j \beta_k^j \dfrac{G g_k^T d^Td^T}{d_j^T G d_j} βkjdjTGdjGgkTdTdT
其中用到了转置。因为最后计算结果是标量所以可以随意转置
与之前一样根据 G d k − 1 1 / α 0 ∗ g k − g k − 1 Gd_{k-1} 1/\alpha_0 * g_k -g_{k-1} Gdk−11/α0∗gk−gk−1
上式化为 β k j G g k T d T d T d j T G d j 1 α k g k T ( g j 1 − g j ) d j T G d j \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_{j1}-g_{j})}{d_j^T G d_j} βkjdjTGdjGgkTdTdTαk1djTGdjgkT(gj1−gj)
又因为每一步走完之后的负梯度方向之间应该是互相垂直的
所以 g k T g j 1 0 , g k T g j 0 g_k^T g_{j1} 0, g_k^T g_{j} 0 gkTgj10,gkTgj0
所以 β k j G g k T d T d T d j T G d j 1 α k g k T ( g j 1 − g j ) d j T G d 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_{j1}-g_{j})}{d_j^T G d_j} 0 βkjdjTGdjGgkTdTdTαk1djTGdjgkT(gj1−gj)0
也就是 0 到 k-2 前的系数为 0
对于非线性问题
对于线性问题有连等式成立 β k − 1 g k T G d k − 1 d k − 1 T G d k − 1 g k T ( g k − g k − 1 ) d k − 1 T ( g k − g k − 1 ) g k T g k d k − 1 T g k − 1 g k T g k g k − 1 T 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})} \dfrac{g^{T}_{k}g_k}{d^{T}_{k-1}g_{k-1}} \dfrac{g^{T}_{k}g_k}{g^{T}_{k-1}g_{k-1}} βk−1dk−1TGdk−1gkTGdk−1dk−1T(gk−gk−1)gkT(gk−gk−1)dk−1Tgk−1gkTgkgk−1Tgk−1gkTgk
但是对于非线性问题其中任意一个确定 β k − 1 \beta_{k-1} βk−1 的等式都不等价
用不同的等式确定 β k − 1 \beta_{k-1} βk−1就可以是一种不同的算法
这里说的线性问题说的是共轭方向法等价于解 ∇ f ( x ) G x b 0 \nabla f(x) Gx b 0 ∇f(x)Gxb0
二次终止性
当使用精确线搜索方法时对于正定二次目标函数极小值问题共轭方向法至多在n步内即可求得其唯一极小点这称为二次终止性。
共轭梯度法也有这个性质
对于非二次目标函数即更一般的非线性目标函数极小值问题共轭梯度法不具有二次终止性。但是收敛很快。为什么
因为靠近精确解的时候误差也比较小所以也能得到好的结果
这说了个寂寞
从内积角度看傅里叶变换
函数展开先确定基函数再确定基函数的系数
对于泰勒展开基函数是 (x-x0)^n 基函数的系数是通过要求函数与展开式在某点的各阶导数相等来确定的 f ( x 0 ) F ( x 0 ) f(x_0) F(x_0) f(x0)F(x0) f ′ ( x 0 ) F ′ ( x 0 ) f(x_0) F(x_0) f′(x0)F′(x0) f ′ ′ ( x 0 ) F ′ ′ ( x 0 ) f(x_0) F(x_0) f′′(x0)F′′(x0)
但是这就要求原函数有 n 阶导数
一种更有效的展开方法要求函数与展开式与 x^n 乘积的积分相等
不要求原函数是光滑的
可积的要求比可微的要求低 ∫ f ( x ) d x ∫ F ( x ) d x \int f(x)\mathrm{d}x \int F(x)\mathrm{d}x ∫f(x)dx∫F(x)dx ∫ f ( x ) x d x ∫ F ( x ) x d x \int f(x)x\mathrm{d}x \int F(x)x\mathrm{d}x ∫f(x)xdx∫F(x)xdx ∫ f ( x ) x 2 d x ∫ F ( x ) x 2 d x \int f(x)x^2\mathrm{d}x \int F(x)x^2\mathrm{d}x ∫f(x)x2dx∫F(x)x2dx
提出 a 交换求和和积分号得到线性代数方程组
(…)
这做了个什么事呢这相当于对两个函数定义了一个内积 f ( x ) ⋅ g ( x ) ∫ f ( x ) g ( x ) d x f(x) \cdot g(x) \int f(x) g(x) \mathrm{d}x f(x)⋅g(x)∫f(x)g(x)dx inf F x ∫ f x \inf F x \int f x infFx∫fx ( F − f ) ⋅ x i (F-f) \cdot x^i (F−f)⋅xi 相当于 F 与 f 之间的误差垂直于 x i x^i xi
求到的是距离 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 写成一个形式
