老师的讲课视频在 B 站BV1nB4y137j9。 主要分为数学基础、局部最优化问题求解和全局局部最优化问题，只讲了局部的部分。

  • 绪论
  • 单变量优化问题——线搜索
    • 黄金分割法
  • 多变量优化问题
    • 梯度法
    • 共轭梯度法
    • 牛顿法
    • 拟牛顿法
  • 约束优化问题
    • 约束问题的最优性条件
    • 可行方向法
    • 梯度投影法、简约梯度法
    • 罚函数法
    • 乘子法

绪论

优化问题的表述：在一定的约束下，调整一组可变参数 x，使设计目标 f(x)达到最小值（或最大值）。 数学表述可以表示为：

min f(x⃗) s.t. x⃗∈K min\ f(\vec{x})\ s.t.\ \vec{x} \in K
  • s.t. 是数学中 subject to (such that) 的缩写，表示受约束的意思
  • f(x⃗)f(\vec{x}) 是目标函数（实值函数）
  • x⃗\vec{x}为参数向量，KK为可行域，即参数能够许可的取值范围

进而可以将最优化问题细分为：

  • 线性规划和非线性规划问题：可行集是有限维向量空间的子集
  • 组合优化或网络规划：可行集中的元素是离散的
  • 动态规划：可行集是一个依赖时间的决策序列
  • 最优控制：可行集是无穷维空间中的一个连续子集

线性最优化问题（线性函数，线性约束）的情况，最有情况出现在端点。 课程考虑非线性规划/优化：

min f(x⃗) s.t. hi(x⃗)=0,i=1,…,l,gi(x⃗)<0,i=1,…m, \begin{align} & min\ f(\vec{x}) \\ \ s.t.\ & h_i(\vec{x})=0,i=1,\dots,l, \\ & g_i(\vec{x})<0,i=1,\dots m, \\ \end{align}

最优化问题求解的一般思路

无约束问题的一般算法框架：

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

最优化问题的数学基础

线性代数

线性代数的核心内容是 Ax=bAx=b 线性代数方程组解的存在性问题，以及如何求解他的问题， 以及这样的数学结构的问题。

  • 矩阵行的含义，A 的每一行是平面线的法向量（线的表达式系数，二维情况），n 个法向量互相不相关，那么方程有唯一解，相关则可能有无数解（共线）或没有解（平行）
  • 矩阵列的含义，相当于 x 是 A 的列向量的加权系数，加权组合结果为 b
  • 矩阵行列式：Ax=bAx=b， 向量 x 被 A 左乘后，变成了向量 b，称为线性变换，矩阵 A 的行列式的绝对值表示经过该矩阵变换前后图形的面积之比；符号表示该图形变换后法向是否翻转了
  • 矩阵的秩：将图形变化为线（秩为 1），面（秩为 2），体（秩为 3）
  • 矩阵的逆：一一映射才有逆，行列式为 0 时，矩阵没有逆

范数

迭代求解过程中，如何判断点序列是否收敛，需要通过度量来衡量， 通常用范数来定义这个度量：

“言为士则、行为世范”出自南朝宋刘义庆著《世说新语》开篇《德行第一》的第一则第一句， 意思是说言行足以为士人的法则、举世的示范。

向量的范数必须满足以下条件：

  • 非负性 ∥x∥≥0\Vert x\Vert \geq 0, ∥x∥=0,iffx=0\Vert x\Vert =0, iff x=0
  • 线性性 λ∥x∥=λ∥x∥\lambda \Vert x \Vert =\lambda \Vert x \Vert
  • 三角不等式（又叫广义加）∥x+y∥≤∥x∥+∥y∥\Vert x+y \Vert \leq \Vert x \Vert +\Vert y \Vert

常用向量的 p 范数，∥x∥p=(∑i=1n∣xi∣p)1p\Vert x \Vert_p=(\sum_{i=1}^{n} |x_i|^p)^\frac{1}{p}。

lim⁡p→∞∥x∥p=∥x∥maxlim⁡p→∞(∑i(∥x∥∥x∥max)p)1p\lim_{p\to\infty} \Vert x \Vert^p
=\Vert x\Vert _{max} \lim_{p\to\infty} \left(\sum_{i}(\frac{\Vert x \Vert}{\Vert x\Vert _{max}})^p\right)^\frac{1}{p}

由于1≤∑i(∥x∥∥x∥max)p≤n1 \leq\sum\limits_{i}(\frac{\Vert x \Vert}{\Vert x\Vert _{max}})^p\leq n，根据夹逼原理可以得到极限部分为 1，另一个思路是求和里面只有一个底数为 1，其他均小于 1，可以得到结果。

矩阵范数，也需要满足非负性，线性性以及三角不等式。为了体现向量的乘法，增加乘法性质。进一步要求相容性：

  • 乘法性质 ∥AB∥≤∥A∥∥B∥\Vert AB\Vert \leq \Vert A \Vert \Vert B \Vert
  • 相容性质 ∥Ax∥≤∥A∥∥x⃗∥\Vert Ax \Vert \leq \Vert A \Vert \Vert\vec{x}\Vert

矩阵范数∥⋅∥μ\Vert \cdot \Vert _{\mu}如果满足下列条件，则称为由向量范数的诱导范数（诱导算子）。

∥A∥μ=supx≠0∥Ax∥∥x∥=maxx=1∥Ax∥ \Vert A \Vert_\mu =sup_{x\neq0} \frac{\Vert Ax \Vert }{\Vert x \Vert}=max_{x=1}\Vert Ax \Vert

矩阵范数表示单位圆/球/超球面上的所有向量 x 经过线性变换后得到的所有向量 Ax 中最长的那个的范数， 或者说表示任向量经过矩阵 A 所代表的线性变换后得到的所有向量中最长的那个的范数与原向量 x 的范数的比值。

  • 矩阵范数是矩阵长度（大小）的度量
  • 可以用来判断矩阵是否相等，判断两个矩阵之间的距离
  • 矩阵范数可以表达经过变换之后向量范数大小的变化

各种范数之间具有等价性：

  1. 设∥⋅∥\Vert \cdot \Vert和∥⋅∥’\Vert \cdot \Vert’是定义在RnR^n上的两个向量范数，则存在两个正数c1,c2c_1,c_2，对所有x∈Rnx\in R^n 均成立：c1∥x∥≤∥x∥’≤c2∥x∥c_1 \Vert x\Vert\leq \Vert x \Vert’ \leq c_2\Vert x \Vert
  2. 设∥⋅∥\Vert \cdot \Vert和∥⋅∥’\Vert \cdot \Vert’是定义在Rn×nR^{n\times n}上的两个两个范数，则存在两个正数c1,c2c_1,c_2，对所有x∈Rnx\in R^n 均成立：c1∥A∥≤∥A∥’≤c2∥A∥c_1 \Vert A\Vert\leq \Vert A \Vert’ \leq c_2\Vert A \Vert

向量 1 范数推导矩阵列和范数

∥A∥1=max⁡x≠0∥Ax∥1∥x∥1∥Ax∥1=∑i=1n∣∑j=1naijxj∣≤∑i=1n∑j=1n∣aijxj∣≤∑i=1n∑j=1n∣aij∣∣xj∣≤max⁡1≤j≤n(∑i=1n∣aij∣)⋅∑j=1n∣xj∣\begin{align*}
\Vert A \Vert_1
&= \max_{x\neq 0} \frac{\Vert Ax \Vert_1}{\Vert x \Vert_1} \\
\Vert Ax\Vert_1
&=\sum_{i=1}^{n}\left|\sum_{j=1}^{n}a_{ij}{x_j}\right|
\leq \sum_{i=1}^{n}\sum_{j=1}^{n}|a_{ij}{x_j}|\\
&\leq \sum_{i=1}^{n}\sum_{j=1}^{n}|a_{ij}||{x_j}|
\leq \max_{1\leq j \leq n}(\sum_{i=1}^{n}|a_{ij}|)\cdot \sum_{j=1}^{n}|x_j|\\
\end{align*}

向量无穷范数推导矩阵行和范数

∥A∥1=max⁡x≠0∥Ax∥1∥x∥1∥Ax∥1=max⁡i=1,…,n∣∑j=1naijxj∣≤max⁡i=1,…,n∑j=1n∣aijxj∣≤max⁡i=1,…,n∑j=1n∣aij∣∣xj∣≤max⁡1≤i≤n(∑i=1n∣aij∣)⋅∑j=1n∣xj∣\begin{align*}
\Vert A \Vert_1
&= \max_{x\neq 0} \frac{\Vert Ax \Vert_1}{\Vert x \Vert_1} \\
\Vert Ax\Vert_1
&=\max_{i=1,\dots,n}\left|\sum_{j=1}^{n}a_{ij}{x_j}\right|
\leq\max_{i=1,\dots,n}\sum_{j=1}^{n}|a_{ij}{x_j}|\\
&\leq \max_{i=1,\dots,n}\sum_{j=1}^{n}|a_{ij}||{x_j}|
\leq \max_{1\leq i \leq n}(\sum_{i=1}^{n}|a_{ij}|)\cdot \sum_{j=1}^{n}|x_j|\\
\end{align*}

向量 2 范数推导矩阵谱范数

∥Ax∥22=xTATAx=(Hx)Tdiag⁡(λi)(Hx)=∑i=1nλiyi2≤(max⁡1≤i≤nλi)∥y∥22.\|A x\|_2^2=x^T A^T A x=(H x)^T \operatorname{diag}\left(\lambda_i\right)(H x)=\sum_{i=1}^n \lambda_i y_i^2 \leq\left(\max _{1 \leq i \leq n} \lambda_i\right)\|y\|_2^2 .

以上推导省略等于号情况，详细推导可以看模糊计算士

多元函数

一维泰勒展开

f(x)≈f0(x)=f(x0)+∂f∂x∣x=x0(x−x0)+12∂2f∂x2∣x=x0(x−x0)2f(x)\approx f_0(x)
=f(x_0)+
\textcolor{red}{\left.\frac{\partial f}{\partial x}\right|_{x=x_0}}(x-x_0)
+\frac{1}{2}\textcolor{red}{\left.\frac{\partial^2 f}{\partial x^2}\right|_{x=x_0}}(x-x_0)^2

二维展开

f(x⃗)≈f0(x⃗)=f(x⃗0)+∇f∣x⃗=x⃗0(x⃗−x⃗0)+12(x⃗−x⃗0)T∇2f∣x⃗=x⃗0(x⃗−x⃗0)f(\vec{x})\approx f_0(\vec{x})
=f(\vec{x}_0)+
\textcolor{red}{\left.\nabla f\right|_{\vec{x}=\vec{x}_0}}(\vec{x}-\vec{x}_0)
+\frac{1}{2}(\vec{x}-\vec{x}_0)^T\textcolor{red}{\left.\nabla^2 f\right|_{\vec{x}=\vec{x}_0}}(\vec{x}-\vec{x}_0)

若函数 f(x)连续可微，则

f(x⃗)≈f0(x⃗)=f(x⃗0)+∇f∣x⃗=x⃗0(x⃗−x⃗0)+o(∥x⃗−x⃗0∥)f(\vec{x})\approx f_0(\vec{x})
=f(\vec{x}_0)
+\textcolor{red}{\left.\nabla f\right|_{\vec{x}=\vec{x}_0}}(\vec{x}-\vec{x}_0)+\textcolor{green}{o(\Vert \vec{x}-\vec{x}_0\Vert)}

若函数 f(x)二次连续可微，则

f(x⃗)≈f0(x⃗)=f(x⃗0)+∇f∣x⃗=x⃗0(x⃗−x⃗0)+12(x⃗−x⃗0)T∇2f∣x⃗=x⃗0(x⃗−x⃗0)+o(∥x⃗−x⃗0∥2)\begin{align*}
f(\vec{x})\approx f_0(\vec{x})
&=f(\vec{x}_0)\\
&+\textcolor{red}{\left.\nabla f\right|_{\vec{x}=\vec{x}_0}}(\vec{x}-\vec{x}_0)\\
&+\frac{1}{2}(\vec{x}-\vec{x}_0)^T\textcolor{red}{\left.\nabla^2 f\right|_{\vec{x}=\vec{x}_0}}(\vec{x}-\vec{x}_0)\\
&+\textcolor{green}{o(\Vert \vec{x}-\vec{x}_0\Vert^2)}\\
\end{align*}

进一步可以推广到函数 F:Rn→RmF:R^n\to R^m 的情况，有时称 F 的 Jacobi 矩阵的转置称为 F 的转置。

凸集与凸函数