#最优化计算方法
本文记录了博主在学习《最优化计算方法》时的总结，主要侧重于与深度学习相关的内容，更新于2018.09.17。
书目信息：《最优化计算方法》，黄正海等著，出版时间2015.02，科学出版社。
更多内容，欢迎加入星球讨论。
文章目录
##第1章 引论
###最优化问题概述
最优化要解决的问题：在一定限制条件下使得所关心的指标达到最优。
最优化问题的基本数学模型：
KaTeX parse error: No such environment: split at position 8: \begin{̲s̲p̲l̲i̲t̲}̲ &\min \quad &f…
其中x ∈ R n x\in \mathbb R^nx∈Rn称为决策向量，函数f : R n → R f:\mathbb R^n \to \mathbb Rf:Rn→R称为目标函数，函数c i ( ⋅ ) ( i ∈ I ) c_i(\cdot)(i \in I)ci(⋅)(i∈I)称为不等式约束函数，函数c i ( ⋅ ) ( i ∈ E ) c_i(\cdot)(i\in E)ci(⋅)(i∈E)称为等式约束函数，不等式c i ( x ) ≥ 0 ( i ∈ I ) c_i(x)\geq0(i\in I)ci(x)≥0(i∈I)称为不等式约束，方程c i ( x ) = 0 ( i ∈ E ) c_i(x)=0(i\in E)ci(x)=0(i∈E)称为等式约束，I II称为不等式约束的指标集，E EE称为等式约束的指标集。记：
\begin{split}
\mathscr F:=\left{ x\in \mathbb R^n \left\vert
\begin{aligned}
& c_i(x)\geq 0,\quad \forall i\in I={1,2,\cdot\cdot\cdot,p};\
& c_i(x)=0,\quad \forall i\in E={p+1,p+2,\cdot\cdot\cdot,m}
\end{aligned}
\right. \right}
\end{split}
称F \mathscr FF为上述最优化问题的可行域，F \mathscr FF中的每个点x xx称为上述最优化问题的一个可行点。若F = ∅ \mathscr F=\varnothingF=∅，则称上述最优化问题不可行；否则，称问题是可行的。
因此，上述最优化问题就是在可行域F \mathscr FF中找到一个点x xx，使其对应的f ( x ) f(x)f(x)的值不大于任何其他F \mathscr FF中的点对应的目标函数值。
**定义：**假设可行域F \mathscr FF由上式给出：
（i）若x ∗ ∈ F x^*\in \mathscr Fx∗∈F，且对所有的x ∈ F x\in \mathscr Fx∈F恒有f ( x ∗ ) ≤ f ( x ) f(x^*)\leq f(x)f(x∗)≤f(x)，则称x ∗ x^*x∗为上述最优化问题的一个全局解；
（ii）若x ∗ ∈ F x^*\in \mathscr Fx∗∈F，且对所有的x ∈ F / x ∗ x\in \mathscr F/\ {x^*}x∈F/ x∗恒有f ( x ∗ ) < f ( x ) f(x^*)\lt f(x)f(x∗)<f(x)，则称x ∗ x^*x∗为上述最优化问题的严格全局最优解；
（iii）若x ∗ ∈ F x^*\in \mathscr Fx∗∈F，且存在x ∗ x^*x∗的某个邻域
N ε ( x ∗ ) " = { x ∈ R n ∣ ∥ x − x ∗ ∥ < ε } ， ε 为 正 实 数 且 ∥ ⋅ ∥ 表 示 某 种 范 数 \mathscr N_\varepsilon (x^*)"=\left\{x\in \mathbb R^n \left\vert \Vert x-x^*\Vert \lt \varepsilon \right. \right\}，\varepsilon 为正实数且\Vert\cdot\Vert表示某种范数Nε(x∗)"={x∈Rn∣∥x−x∗∥<ε}，ε为正实数且∥⋅∥表示某种范数
使得对所有的x ∈ F ∩ N ε ( x ∗ ) x\in \mathscr F \cap\mathscr N_\varepsilon(x^*)x∈F∩Nε(x∗)恒有f ( x ∗ ) ≤ f ( x ) f(x^*)\leq f(x)f(x∗)≤f(x)，那么称x ∗ x^*x∗为上述最优化问题的一个局部最优解。
（iv）若x ∗ ∈ F x^*\in \mathscr Fx∗∈F，且存在x ∗ x^*x∗的某个邻域N ε ( x ∗ ) \mathscr N_\varepsilon(x^*)Nε(x∗)，使得对所有的x ∈ F ∩ N ε ( x ∗ ) / x ∗ x\in\mathscr F \cap \mathscr N_\varepsilon(x^*)/\ {x^*}x∈F∩Nε(x∗)/ x∗恒有f ( x ∗ ) < f ( x ) f(x^*)\lt f(x)f(x∗)<f(x)，那么称x ∗ x^*x∗为为上述最优化问题的一个严格局部最优解。
**定义：**对于上述最优化问题，称其最优解x ∗ x^*x∗对应的目标函数值f ( x ∗ ) f(x^*)f(x∗)为此优化问题的最优值。
最优解不一定存在，存在也不一定唯一，但如果存在最优解，那么最优值一定唯一。最优化问题也常被写成：
\begin{split}
\min\left{f(x) \left\vert
\begin{aligned}
& c_i(x)\geq 0,\quad \forall i\in I={1,2,\cdot\cdot\cdot,p};\
& c_i(x)=0,\quad \forall i\in E={p+1,p+2,\cdot\cdot\cdot,m}
\end{aligned}
\right. \right}
\end{split}
###预备知识
约定向量取列向量形式，即x ∈ R n x\in \mathbb R^nx∈Rn是指x xx具有如下形式：
\begin{split}
x:=(x_1,x_2,\cdot\cdot\cdot)^T=
\left(
\begin{aligned}
&x1\
&x2\
&\cdot\
&\cdot\
&\cdot\
&x_n
\end{aligned}
\right)
\end{split}
对任意的x , y ∈ R n x,y\in \mathbb R^nx,y∈Rn，常用的内积⟨ x , y ⟩ \langle x,y\rangle⟨x,y⟩定义为：
⟨ x , y ⟩ : = ∑ i = 1 n x i y i = x T y \langle x,y\rangle:=\sum_{i=1}^nx_iy_i=x^Ty⟨x,y⟩:=i=1∑nxiyi=xTy
常用的向量范数：
l 1 − 范 数 l_1-范数l1−范数：∥ x ∥ 1 = ∑ i = 1 n ∣ x i ∣ \Vert x\Vert_1=\sum_{i=1}^n\vert x_i\vert∥x∥1=∑i=1n∣xi∣
l 2 − 范 数 l_2-范数l2−范数：∥ x ∥ 2 = x T x = ∑ i = 1 n x i 2 \Vert x\Vert_2=\sqrt{x^Tx}=\sqrt{\sum_{i=1}^nx_i^2}∥x∥2=xTx=∑i=1nxi2
l ∞ − 范 数 l_\infty-范数l∞−范数：∥ x ∥ ∞ = max { ∣ x i ∣ ∣ i ∈ { 1 , 2 , ⋅ ⋅ ⋅ , n } } \Vert x\Vert_\infty=\max \{\vert x_i\vert \vert i\in \{1,2,\cdot\cdot\cdot,n\}\}∥x∥∞=max{∣xi∣∣i∈{1,2,⋅⋅⋅,n}}
一般地，对于p ∈ [ 1 , ∞ ) p\in \left[1,\infty\right)p∈[1,∞)，l p − 范 数 l_p-范数lp−范数定义为：
∥ x p ∥ = ( ∑ i = 1 n ∣ x i ∣ p ) 1 / p \Vert x_p \Vert=\left( \sum_{i=1}^n\vert x_i\vert^p\right)^{1/p}∥xp∥=(∑i=1n∣xi∣p)1/p
各范数之间的关系有：
∥ x ∥ ∞ ≤ ∥ x ∥ 2 ≤ ∥ x ∥ 1 ≤ n ∥ x ∥ ∞ \Vert x \Vert _\infty \leq \Vert x\Vert _2 \leq \Vert x \Vert _1 \leq n\Vert x\Vert _\infty∥x∥∞≤∥x∥2≤∥x∥1≤n∥x∥∞
常用的矩阵范数
假设A ∈ R n × n A\in \mathbb R^{n\times n}A∈Rn×n是对称正定矩阵，那么向量的椭球范数∥ ⋅ ∥ A \Vert\cdot\Vert_A∥⋅∥A定义如下：
∥ x ∥ A : = x T A x , ∀ x ∈ R n \Vert x \Vert _A:=\sqrt{x^TAx},\quad\forall x \in \mathbb R^n∥x∥A:=xTAx,∀x∈Rn
对于任意的A = ( a i j ) n × n ∈ R n × n A=(a_{ij})_{n\times n}\in \mathbb R^{n\times n}A=(aij)n×n∈Rn×n，常用的矩阵范数是Frobenius范数，定义为：
∥ A ∥ F : = ∑ i = 1 n ∑ j = 1 n a i j 2 = T r ( A T A ) \Vert A\Vert _F:=\sqrt{\sum_{i=1}^n\sum_{j=1}^na_{ij}^2}=\sqrt{Tr(A^TA)}∥A∥F:=i=1∑nj=1∑naij2=Tr(ATA)
其中，T r ( A T A ) Tr(A^TA)Tr(ATA)表示矩阵A T A A^TAATA的迹，即A T A A^TAATA的所有主对角线元素之和，也等于A T A A^TAATA的所有特征值之和。
另一个常用的矩阵范数是由向量所诱导的矩阵范数，也称算子范数，定义为：
∥ A ∥ : = max x ∈ R n / { 0 } ∥ A x ∥ ∥ x ∥ , ∀ A ∈ R n × n \Vert A \Vert:=\max_{x\in \mathbb R^n/\ \{0\}}\frac{\Vert Ax\Vert}{\Vert x\Vert},\quad \forall A\in \mathbb R^{n\times n}∥A∥:=x∈Rn/ {0}max∥x∥∥Ax∥,∀A∈Rn×n
其中，∥ ⋅ ∥ \Vert \cdot\Vert∥⋅∥是某种向量范数。
特别地，对于任意的A ∈ R n × n A\in \mathbb R ^{n\times n}A∈Rn×n，有：
- 由向量l 1 − 范 数 l_1-范数l1−范数诱导的矩阵范数（列范数）为∥ A ∥ 1 = max { ∑ i = 1 n ∣ a i j ∣ ∣ j ∈ { 1 , 2 , ⋅ ⋅ ⋅ , n } } \Vert A \Vert _1 = \max \left\{ \sum_{i=1}^n\vert a_{ij}\vert \left\vert j\in \{1,2,\cdot\cdot\cdot,n\}\right. \right\}∥A∥1=max{∑i=1n∣aij∣∣j∈{1,2,⋅⋅⋅,n}}
- 由向量l ∞ − 范 数 l_\infty-范数l∞−范数诱导的矩阵范数（行范数）为∥ A ∥ ∞ = max { ∑ j = 1 n ∣ a i j ∣ ∣ i ∈ { 1 , 2 , ⋅ ⋅ ⋅ , n } } \Vert A \Vert _\infty = \max \left\{ \sum_{j=1}^n\vert a_{ij}\vert \left\vert i\in \{1,2,\cdot\cdot\cdot,n\}\right. \right\}∥A∥∞=max{∑j=1n∣aij∣∣i∈{1,2,⋅⋅⋅,n}}
- 由向量l 2 − 范 数 l_2-范数l2−范数诱导的矩阵范数（谱范数）为KaTeX parse error: Got function '\max' with no arguments as subscript at position 33: …= \sqrt{\lambda_̲\max(A^TA)}，其中KaTeX parse error: Got function '\max' with no arguments as subscript at position 8: \lambda_̲\max(A^TA)表示矩阵A T A A^TAATA的最大特征值。
矩阵范数满足相容性条件，常用的不等式有Cauchy-Schwarz不等式，广义Cauchy-Schwarz不等式，Young不等式，Holder不等式，Minkowski不等式。
函数的可微性
如果函数f ff是二阶连续可微，那么函数f ff在点x xx处的二阶导数组成的矩阵称为Hesse阵。
给定多变量向量值函数F FF，如果其在x xx处连续可微，那么函数F FF在点x xx处的一阶导数矩阵称为Jacobi矩阵。
###凸集、凸函数、凸规划
凸集
给定非空集合F ⊆ R n \mathscr F \subseteq \mathbb R^nF⊆Rn。如果对任意的x , y ∈ F x,y\in \mathscr Fx,y∈F以及任意的实数α ∈ [ 0 , 1 ] \alpha \in [0,1]α∈[0,1]都有
α x + ( 1 + α ) y ∈ F \alpha x+(1+\alpha)y\in \mathscr Fαx+(1+α)y∈F
那么，称F \mathscr FF为R n \mathbb R^nRn中的一个凸集。若凸集F \mathscr FF为开集，则称为开凸集；若凸集F \mathscr FF为闭集，则称为闭凸集。
空集∅ \varnothing∅通常被规定为凸集。
凸集分离定理
假设F 1 , F 2 ⊆ R n \mathscr F_1, \mathscr F_2 \subseteq \mathbb R^nF1,F2⊆Rn为两个非空凸集。如果存在非零向量w ∈ R n w\in\mathbb R^nw∈Rn和实数t tt，使得
（i）对任意的x ∈ F 1 x\in\mathscr F_1x∈F1和y ∈ F 2 y\in \mathscr F_2y∈F2，都有w T x ≥ t w^Tx\geq twTx≥t且w T y ≤ t w^Ty\leq twTy≤t，则称超平面π : = { x ∈ R n ∣ w T x = t } \pi := \{x\in \mathbb R^n \vert w^Tx=t\}π:={x∈Rn∣wTx=t}分离集合F 1 \mathscr F_1F1和F 2 \mathscr F_2F2；
（ii）对任意的x ∈ F 1 x\in\mathscr F_1x∈F1和y ∈ F 2 y\in \mathscr F_2y∈F2，都有w T x > t w^Tx\gt twTx>t且w T y < t w^Ty\lt twTy<t，则称超平面π : = { x ∈ R n ∣ w T x = t } \pi := \{x\in \mathbb R^n \vert w^Tx=t\}π:={x∈Rn∣wTx=t}严格分离集合F 1 \mathscr F_1F1和F 2 \mathscr F_2F2。
Farkas引理
设A ∈ R m × n A\in \mathbb R^{m\times n}A∈Rm×n且b ∈ R n b\in \mathbb R^nb∈Rn，考虑不等式组
A x ≤ 0 , b T x > 0 Ax\leq0,\quad b^Tx\gt 0Ax≤0,bTx>0
和等式不等式组
A T y = b , y ≥ 0 A^Ty=b,\quad y\geq0ATy=b,y≥0
那么，上述两式有且仅一组有解。