该博客围绕最优化与凸优化展开，先介绍线性代数、函数可微性等数学基础，包括向量与矩阵范数、泰勒展开等。接着阐述凸优化问题，如凸函数判断。还讲解无约束和有约束最优化问题的最优性条件及多种算法，如线搜索、梯度法、共轭方向法等。
- 数学基础
- 线性代数
- 函数的可微性与展开
- 凸优化问题
- 无约束问题的最优性条件
- 线搜索
- 梯度法和牛顿法
- 共轭方向法和共轭梯度法
- 拟牛顿法
- 有约束的最优化问题
- 约束最优化问题的最优性条件
- 约束优化问题的可行方向法
- 罚函数
- 划重点
在一定的约束条件 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 Ax=b
有解，就是说明矩阵 A A A 的每个列向量展开的空间之中有 b b b
行列式的几何解释
线性变换的面积
向量范数和矩阵范数
向量范数
1-范数：
∣ ∣ x ∣ ∣ 1 = ∑ i = 1 n ∣ x i ∣ \vert \vert x \vert \vert_1 = \sum_{i=1}^{n} \vert x_i \vert ∣∣x∣∣1=∑i=1n∣xi∣
2-范数：
∣ ∣ x ∣ ∣ 2 = ( ∑ i = 1 n ∣ x i ∣ 2 ) 1 2 \vert \vert x \vert \vert_2 = (\sum_{i=1}^{n} \vert x_i \vert^2)^{\frac{1}{2}} ∣∣x∣∣2=(∑i=1n∣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_{i=1}^{n} \vert x_i \vert^p)^{\frac{1}{p}} ∣∣x∣∣p=(∑i=1n∣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⋯P2P1A=A−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 x=0 使成立：
∣ ∣ 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∣∣μ=maxx=0∣∣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_{i=1}^{m}\vert A_{ij} \vert ∣∣A∣∣=1≤j≤nmaxi=1∑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 Ax=A1∗x1+A2∗x2+A3∗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_{j=1}^{n} A_j x_j \vert \vert \\ \notag \leq \sum_{j=1}^{n}\\ \end{align} ∣∣Ax∣∣1≤j=1∑n=∣∣j=1∑nAjxj∣∣
无穷范数诱导的矩阵范数
∣ ∣ A ∣ ∣ = max 1 ≤ i ≤ n ∑ j = 1 m ∣ A i j ∣ \vert \vert A \vert \vert = \max_{1 \leq i \leq n}\sum_{j=1}^{m}\vert A_{ij} \vert ∣∣A∣∣=1≤i≤nmaxj=1∑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_{j=1}^{m} \vert A_{ij} \vert ∣∣Ax∣∣∞=max1≤i≤n∣∣AiTx∣∣∞≤max1≤i≤n∣∣AiT[1,1,⋯,1]T∣∣∞=max1≤i≤n∑j=1m∣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_{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}} ∣xTATAx∣1/2=∣xTPTΛPx∣1/2=∣yTΛy∣1/2=∣∑i=1nλiyi2∣1/2=λmax∣∑i=1nλ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 yi=1，其他的 y i = 0 y_i = 0 yi=0 时，不等式
P 是正交的，所以一定是满秩的，然后 x 是任意取的，所以 Px 不会掉维度，所以 Px 可以等于任意值，所以 y = Px 可以取到上面要求的值，所以不等式的等号可以被取到
各种范数之间的等价性
用无穷范数证出来的性质可以推广到 1 范数上
向量与矩阵序列的收敛性
某一个向量/矩阵序列的范数 = a， a ≠ 0 a \ne 0 a=0，那么不能证明这个向量/矩阵序列收敛，因为范数不等于 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)⋯⋱
最低0.47元/天 解锁文章
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
