最优化理论与算法第1章：引言

本文的内容主要来自陈宝林的《最优化理论与算法（第2版）》第1章《引言》。

学科简述

（略）

线性与非线性规划问题

目标函数和约束函数都是线性的，称为线性规划问题，若含有非线性函数，称为非线性规划问题。

满足约束条件的点称为可行点，全体可行点组成的集合称为可行集或可行域。如果可行域是整个空间称为无约束问题。

定义1.2.1 $f:\mathbb{R}^n\rightarrow\mathbb{R}$为目标函数，$S$为可行域，$\vec{x}’\in S$，若$\forall \vec{x}(\vec{x}\in S\rightarrow f(\vec{x})\geq f(\vec{x}’))$，则称$\vec{x}’$为$f$在$S$上的全局极小点。

定义1.2.2 $f:\mathbb{R}^n\rightarrow\mathbb{R}$为目标函数，$S$为可行域，$\vec{x}’\in S$，若$\exists\epsilon(\epsilon\in\mathbb{R}^+\land\forall \vec{x}(\vec{x}\in N(\vec{x}’,\epsilon)\rightarrow f(\vec{x})\geq f(\vec{x}’)))$，则称$\vec{x}’$为$f$在$S$上的局部极小点。其中$N(\vec{x}’,\epsilon)={\vec{x}\mid|\vec{x}-\vec{x}’|<\epsilon}$为邻域。

注：全局极小点不需要用到距离和范数，它和函数的最值定义几乎是一样的，只是定义域成了可行域。而局部极小点用到了邻域，需要距离也就是范数，它和函数的极小值定义也几乎是一样的。

几个数学概念

向量范数和矩阵范数

定义1.3.1 实值函数$|\cdot|:\mathbb{R}^n\rightarrow\mathbb{R}$称为向量范数，若满足$\forall\alpha,\vec{x},\vec{y}(\alpha\in\mathbf{R}\land \vec{x},\vec{y}\in\mathbf{R}^n)$：

1. 严格正定性：$|\vec{x}|\geq 0\land(|\vec{x}|=0\leftrightarrow\vec{x}=\vec{0})$；
2. 齐次性（线性形）：$|\alpha\vec{x}|=|\alpha|\cdot|\vec{x}|$
3. 三角不等式：$|\vec{x}+\vec{y}|\leq|\vec{x}|+|\vec{y}|$

常见的向量范数有：

1. $L_1$范数：$|\vec{x}|_1=\sum\limits_{j=1}^n |x_j|$
2. $L_2$范数：$|\vec{x}|_2=(\sum\limits_{j=1}^n x_j^2)^\frac{1}{2}$
3. $L_\infty$范数：$|\vec{x}|_\infty=\max\limits_j |x_j|$

注：这里的范数都称为$L_p$-范数，来源于$|\vec{x}|_p=(\sum\limits_{j=1}^n |x_j|^p)^\frac{1}{p}$。其中$|\vec{x}|_\infty=\lim\limits_{p\rightarrow+\infty}(\sum\limits_{j=1}^n |x_j|^p)^\frac{1}{p}$。

定义1.3.2 $|\cdot|_\alpha,|\cdot|_\beta$为$\mathbb{R}^n$上的范数，若$\exists c_1, c_2(c_1, c_2\in\mathbb{R}^+\land\forall\vec{x}(\vec{x}\in\mathbb{R}^n\rightarrow c_1|\vec{x}|_\alpha\leq |\vec{x}|_\beta\leq c_2|\vec{x}|_\alpha))$，则称这两个范数等价。

$\mathbb{R}^n$中任何两个范数等价（这里必须是有限维，这个定理的证明我尚不能掌握，需要参考泛函分析）。

定义1.3.3 $\mathbf{A}\in\mathbb{R}^{m\times n}$为矩阵，$|\cdot|_\alpha$为$\mathbb{R}^m$上的向量范数，$|\cdot|_\beta$为$\mathbb{R}^n$上的向量范数，定义矩阵范数$|\mathbf{A}|=\max\limits_{|\vec{x}|_\beta=1}|\mathbf{A}\vec{x}|_\alpha$。

注：这里可以想像成矩阵的范数，是其对应的线性映射，能够将一个向量拉长的最大倍数。

定理1.3.1 矩阵范数的性质：

1. $|\mathbf{A}\vec{x}|_\alpha\leq|\mathbf{A}|\cdot|\vec{x}|_\beta$；
2. $|\lambda\mathbf{A}|=|\lambda|\cdot|\mathbf{A}|$；
3. $|\mathbf{A}+\mathbf{B}|\leq|\mathbf{A}|+|\mathbf{B}|$；
4. $|\mathbf{A}\mathbf{D}|\leq|\mathbf{A}|\cdot|\mathbf{D}|$。

定理1.3.1 (1) 证：

$$ \begin{aligned} &|\mathbf{A}|=\max\limits_{|\vec{x}|_\beta=1}|\mathbf{A}\vec{x}|_\alpha \\ \Rightarrow &|\mathbf{A}|=\max\limits_{|\frac{\vec{x}}{|\vec{x}|}_\beta|_\beta=1}|\mathbf{A}\frac{\vec{x}}{|\vec{x}|}_\beta|_\alpha;(\text{变量代换}) \\ \Rightarrow &|\mathbf{A}|=\max\frac{|\mathbf{A}\vec{x}|_\alpha}{|\vec{x}|_\beta};(\text{利用齐次性，并去掉了恒成立的max条}) \\ \Rightarrow &|\mathbf{A}|\geq\frac{|\mathbf{A}\vec{x}|_\alpha}{|\vec{x}|_\beta} \end{aligned} $$

定理1.3.1 (3) 证：

$$ \begin{aligned} |\mathbf{A}+\mathbf{B}|&=\max\limits_{|\vec{x}|_\beta=1}|(\mathbf{A}+\mathbf{B})\vec{x}|_\alpha \\ &\leq\max\limits_{|\vec{x}|_\beta=1}|\mathbf{A}\vec{x}|_\alpha + |\mathbf{B}\vec{x}|_\alpha;(\text{三角不等式}) \\ &=|\mathbf{A}|+|\mathbf{B}| \end{aligned} $$

定理1.3.1 (4) 证：

$$ \begin{aligned} |\mathbf{A}\mathbf{D}|&=\max\limits_{|\vec{x}|_\beta=1}|\mathbf{A}\mathbf{D}\vec{x}|_\alpha \\ &\leq\max\limits_{|\vec{x}|_\beta=1}|\mathbf{A}|\cdot|\mathbf{D}\vec{x}|_\gamma;(\text{性质1}) \\ &=|\mathbf{A}|\cdot|\mathbf{D}| \end{aligned} $$

常见的矩阵范数有：

1. $|\mathbf{A}|_1=\max_j\sum\limits_{i=1}^m |a_{ij}|$；
2. $|\mathbf{A}|_2=\sqrt[]{\lambda_{\mathbf{A}^T\mathbf{A}}}$，（$\lambda$是最大特征值，这被称为谱范数）；
3. $|\mathbf{A}|_\infty=\max_i\sum\limits_{j=1}^n |a_{ij}|$。

注：这里$p$矩阵范数就是$L_p$向量范数的组合，我采用形象化的方式来解释这3种范数。先考虑第2个范数，它将球拉伸成椭球，长径拉伸最大值也就是其最大的奇异值；再考虑第1个范数，它将一个立方体拉伸成长方体，其中立方体的顶点是$[0,\dots,0,1,0,\dots,0]^T$，映射完后，相当于挨个取出列向量，求他们的$L_1$范数（求和），再取出最大的；最后考虑第3个范数，它同样将一个立方体拉伸成长方体，其中立方体的顶点是$[1,\dots,1]^T$，映射完后，相当于将行向量求和，最后取出最大的。

序列的极限

定义1.3.4 ${\vec{x}^{(k)}}$是$\mathbb{R}^n$中的向量序列，$\vec{x}’\in\mathbb{R}^n$，若：

$$\forall\epsilon(\epsilon\in\mathbb{R}^+\rightarrow\exists N(N\in\mathbb{N}^+\land\forall n(n\in\mathbb{N}^+\land n>N\rightarrow |\vec{x}^{(n)}-\vec{x}’|<\epsilon))$$

则称序列收敛到$\vec{x}’$，或序列以$\vec{x}’$为极限，记作$\lim\limits_{k\to\infty}\vec{x}^{(k)}=\vec{x}’$。

序列若存在极限，则任何子序列有相同的极限（选取适当的$N$即可证明），序列的极限是唯一的。

序列的极限是唯一的 证：

反证法，若存在两极限，则$\lim\limits_{k\to\infty}\vec{x}^{(k)}=\vec{a}$同时$\lim\limits_{k\to\infty}\vec{x}^{(k)}=\vec{b}$，且$\vec{a}\neq\vec{b}$。取$\epsilon_0=\frac{|\vec{b}-\vec{a}|}{2}$，由假设知道：

$$ \begin{aligned} &\begin{aligned} &\exists N_1(N_1\in\mathbf{N}^+\land\forall n(n\in\mathbb{N}^+\land n>N_1\rightarrow |\vec{x}^{(n)}-\vec{a}|<\epsilon_0))) \\ \land &\exists N_2(N_2\in\mathbf{N}^+\land\forall n(n\in\mathbb{N}^+\land n>N_2\rightarrow |\vec{x}^{(n)}-\vec{b}|<\epsilon_0))) \end{aligned} \\ \Rightarrow & \exists N_1,N_2(N_1,N_2\in\mathbf{N}^+\land \forall n (n\in\mathbb{N}^+\land n>N_1\land n>N_2\rightarrow |\vec{x}^{(n)}-\vec{a}|<\epsilon_0 \land |\vec{x}^{(n)}-\vec{b}|<\epsilon_0)) \\ \Rightarrow & \exists N_1,N_2(N_1,N_2\in\mathbf{N}^+\land \forall n (n\in\mathbb{N}^+\land n>\max(N_1,N_2)\rightarrow |\vec{x}^{(n)}-\vec{a}| + |\vec{x}^{(n)}-\vec{b}|<|\vec{b}-\vec{a}|)) \\ \Rightarrow & \bot ;(\text{违反三角不等式}) \end{aligned} $$

定义1.3.5 ${\vec{x}^{(k)}}$是$\mathbb{R}^n$中的向量序列，若存在子序列${\vec{x}^{(k_j)}}$，$\lim\limits_{k_j\to\infty}\vec{x}^{(k_j)}=\hat{\vec{x}}$，则称$\hat{\vec{x}}$是${\vec{x}^{(k)}}$的一个聚点。

Bolzano–Weierstrass定理：$\mathbb{R}^n$中有界序列必有聚点，即有界序列必有收敛子列，证明详见波尔查诺-魏尔斯特拉斯定理 - 维基百科，自由的百科全书。这只在有限维实向量赋范空间成立。

定义1.3.6 ${\vec{x}^{(k)}}$是$\mathbb{R}^n$中的向量序列，若：

$$\forall\epsilon(\epsilon\in\mathbb{R}^+\rightarrow\exists N(N\in\mathbb{N}^+\land\forall n_1,n_2(n_1,n_2\in\mathbb{N}^+\land n_1,n_2>N\rightarrow|\vec{x}^{n_1}-\vec{x}^{n_2}|<\epsilon)))$$

则称${\vec{x}^{(k)}}$为柯西序列。$\mathbb{R}^n$中，柯西序列和收敛数学互为充要条件。

注：柯西序列的定义没有涉及到极限值，这便于完成一些对收敛性的证明。那些所有柯西序列收敛到空间中某点的空间，称为完备空间，比如实数是完备的，有理数是不完备的。完备空间中，柯西序列和收敛序列互为充要条件。不完备空间中，柯西序列是收敛序列的必要条件。

定理1.3.2 ${\vec{x}^{(k)}}$是$\mathbb{R}^n$中的柯西序列，则其聚点为极限点。

注：$\mathbb{R}^n$中，收敛序列（即柯西序列）必有唯一聚点，且该聚点为极限点。一个序列可能有多个聚点。

设$S\subseteq\mathbb{R}^n$：

1. 若$S$中每个收敛序列的极限均在$S$，则称$S$为闭集；
2. 若$\forall\hat{\vec{x}}(\hat{\vec{x}}\in S\rightarrow\exists\epsilon(\epsilon\in\mathbb{R}^+\land N(\hat{\vec{x}},\epsilon)\subseteq S))$，则称$S$为开集，这样的$\hat{\vec{x}}$称为内点；
3. 若$S$是有界闭集，则称$S$为紧集。

闭集的另一个定义是：一个补集是开集的集合称为闭集。这里集合$S$的补集定义为$S^C={x\mid x\notin S,x\in\mathbb{N}}$。

紧集的一个等价定义是：集合中的序列都有收敛子序列。由Bolzano–Weierstrass定理可证$S\subseteq\mathbb{R}^n$紧致，当且仅当，$S$为有界闭集。

梯度、海森矩阵、泰勒展开式

设$f:S\to\mathbb{R}$，其中$S\subseteq\mathbb{R}^n$。如果$f$在$S$中的每一点连续，则称$f$在$S$上连续，记作$f\in C(S)$。若$f$在每一点$\vec{x}\in S$，一阶导数$\frac{\partial f(\vec{x})}{\partial x_i}$存在且连续，则称$f$在$S$上连续可微，记作$f\in C^1(S)$。若$f$在每一点$\vec{x}\in S$，二阶导数$\frac{\partial^2 f(\vec{x})}{\partial x_i\partial x_j}$存在且连续，则称$f$在$S$上二次连续可微，记作$f\in C^2(S)$。

函数$f\in C^1(S)$在$\vec{x}$的梯度为：

$$\nabla f(\vec{x})=\begin{bmatrix} \frac{\partial f(\vec{x})}{\partial x_1},\frac{\partial f(\vec{x})}{\partial x_2},\cdots,\frac{\partial f(\vec{x})}{\partial x_n} \end{bmatrix}^T$$

函数$f\in C^2(S)$在$\vec{x}$的海森矩阵为对称矩阵，如下：

$$[\nabla^2 f(\vec{x})]_{ij}=\frac{\partial^2 f(\vec{x})}{\partial x_i\partial x_j}$$

对于二次函数$f(\vec{x})=\frac{1}{2}\vec{x}^T\mathbf{A}\vec{x}+\vec{b}^T\vec{x}+c$：

1. 其梯度：$\nabla f(\vec{x})=\mathbf{A}\vec{x} + \vec{b}$；
2. 其海森矩阵：$\nabla^2 f(\vec{x})=\mathbf{A}$。

对$S\in\mathbb{R}^n$上的函数$f:S\to\mathbb{R}$：

1. 若$f\in C^1(S)$，则对任意$\vec{x}_0\in\mathbb{R}^n$，有一阶泰勒展式： $$f(\vec{x})=f(\vec{x_0})+\nabla f(\vec{x}_0)^T(\vec{x}-\vec{x}_0)+o(|\vec{x}-\vec{x}_0|)$$
2. 若$f\in C^2(S)$，则对任意$\vec{x}_0\in\mathbb{R}^n$，有二阶泰勒展式： $$f(\vec{x})=f(\vec{x_0})+\nabla f(\vec{x}_0)^T(\vec{x}-\vec{x}_0)+\frac{1}{2}(\vec{x}-\vec{x}_0)^T\nabla^2 f(\vec{x}_0)(\vec{x}-\vec{x}_0)+o(|\vec{x}-\vec{x}_0|^2)$$

雅可比矩阵、链式法则和隐函数存在定理

雅可比矩阵

考虑向量值函数$\vec{h}:\mathbb{R}^n\to\mathbb{R}^m$：

$$\vec{h}(\vec{x})=(h_1(\vec{x}),h_2(\vec{x}),\cdots,h_m(\vec{x}))^T$$

若对任意$i,j$，$\frac{\partial h_i(\vec{x})}{\partial x_j}$存在，则其雅可比矩阵为：

$$[\vec{h}’(\vec{x})]_{ij}=\frac{\partial h_i(\vec{x})}{\partial x_j}$$

也可记作$\nabla\vec{h}(\vec{x})^T$。

链式法则

对于实数空间上的复合向量值函数$\vec{h}(\vec{x})=\vec{f}(\vec{g}(\vec{x}))$，若$f,g$均可微，则有：

$$\vec{h}’(\vec{x})=\vec{h}’(\vec{g}(\vec{x}))\vec{g}’(\vec{x})$$

隐函数定理

定理 1.3.3 对于$\vec{h}:\mathbb{R}^m\times\mathbb{R}^n\to\mathbb{R}^m$，定点向量$\vec{a}^{(0)}\in\mathbb{R}^m,\vec{b}^{(0)}\in\mathbb{R}^n$，令$\vec{x}^{(0)}=[\vec{a}^{(0)},|,\vec{b}^{(0)}]$，满足：

1. $\vec{h}(\vec{x}^{(0)})=\vec{0}$；
2. 在$\vec{x}^{(0)}$的某一个邻域中，$h_i\in C^1 (i=1,\cdots,m)$；
3. $\begin{vmatrix}\begin{bmatrix}\frac{\partial h_i}{\partial a_j}(\vec{x})\end{bmatrix}_{m\times m}\end{vmatrix}\neq 0$

则存在$\vec{b}^{(0)}\in\mathbb{R}^n$的一个邻域，使得对于邻域中的点$\vec{b}\in\mathbb{R}^n$，唯一存在函数$\vec{\phi}:\mathbb{R}^n\to\mathbb{R}^m$，满足：

1. $\phi_i\in C^1;(i=1,\cdots,m)$；
2. $\vec{a}^{(0)}=\phi(\vec{b}^{(0)})$；
3. $\vec{h}([\vec{\phi}(\vec{b}^{(0)}),|,\vec{b}^{(0)}])=\vec{0}$。

二次型的正定性与半正定性

正定二次型的定义 对实二次型$f(\vec{x})=\vec{x}^T\mathbf{A}\vec{x}$，若：

$$\forall\vec{x}(\vec{x}\in\mathbb{R}^n\land\vec{x}\neq\vec{0}\rightarrow f(\vec{x})\geq 0)$$

则称$f(x)$为正定二次型，$\mathbf{A}$为正定矩阵。

正定二次型的判断 对于$\mathbf{A}\in\mathbb{R}^{n\times n}$，下列命题等价：

1. $\vec{x}^T\mathbf{A}\vec{x}$是正定二次型；
2. $\mathbf{A}$是正定矩阵；
3. $\mathbf{A}$的$n$个顺序主子式都大于零；
4. $\mathbf{A}$的$n$个特征值都大于零；
5. 存在可逆矩阵$\mathbf{P}$，使得$A=P^TP$。

半正定二次型的定义 对实二次型$f(\vec{x})=\vec{x}^T\mathbf{A}\vec{x}$，若：

$$\forall\vec{x}(\vec{x}\in\mathbb{R}^n\land\vec{x}\neq\vec{0}\rightarrow f(\vec{x})\geq 0)\land\exists\vec{x}(\vec{x}\in\mathbb{R}^n\land\vec{x}\neq\vec{0}\land f(\vec{x})=0)$$

则称$f(x)$为半正定二次型，$\mathbf{A}$为半正定矩阵。

半正定二次型的判断 对于$\mathbf{A}\in\mathbb{R}^{n\times n}$，下列命题等价：

1. $\vec{x}^T\mathbf{A}\vec{x}$是半正定二次型；
2. $\mathbf{A}$是半正定矩阵；
3. $\mathbf{A}$的所有主子式都大于等于零，且至少有一个等于零；
4. $\mathbf{A}$的$n$个特征值都大于等于零，且至少有一个等于零。

凸集和凸函数

凸集

定义1.4.1 设$S\subseteq\mathbb{R}^n$，若$\forall\vec{x}_1,\vec{x}_2,\lambda(x_1,x_2\in S\land\lambda\in[0,1]\rightarrow\lambda\vec{x}_1+(1-\lambda)\vec{x}_2\in S)$，则称$S$为凸集。其中$\lambda\vec{x}_1+(1-\lambda)\vec{x}_2$称为凸组合。

常见的凸集有超平面${\vec{x}\mid\vec{p}^T\vec{x}=\alpha}$、半空间${\vec{x}\mid\vec{p}^T\vec{x}\leq\alpha}$、射线${\vec{x}\mid\vec{x}_0+\lambda\vec{d},\lambda\geq 0}$（其中$\vec{x}_0$为顶点，$\vec{d}$为方向向量)。

设$S_1,S_2\subseteq\mathbb{R}^n$为凸集，$\beta\in\mathbb{R}$，则：

1. $\beta S_1={\beta\vec{x}\mid\vec{x}\in S_1}$为凸集；
2. $S_1\cap S_2$为凸集；
3. $S_1+S_2={\vec{x}_1+\vec{x}_2\mid\vec{x}_1\in S_1,\vec{x}_2\in S_2}$为凸集；
4. $S_1-S_2={\vec{x}_1-\vec{x}_2\mid\vec{x}_1\in S_1,\vec{x}_2\in S_2}$为凸集。

凸集的线性组合也是凸集，但凸集的并不是凸集。

定义1.4.2 设$C\subseteq\mathbb{R}^n$，若$\forall\vec{x},\lambda(\vec{x}\in C\land\lambda\in\mathbb{R}^*\rightarrow\lambda\vec{x}\in C)$，则称$C$为锥。若$C$又为凸集，则称$C$为凸锥。

向量集${\vec{x}_1,\vec{x}_2,\cdots,\vec{x}_n}$的非负线性组合${\sum\limits_{i=1}^n\lambda_i\vec{x}_i\mid\lambda_i\geq 0,i=1,\cdots,n}$。

定义1.4.3 有限个半空间的交${\vec{x}\mid\mathbf{A}\vec{x}\leq\vec{b}}$称为多面集，若$\vec{b}=\vec{0}$，则多面集成为凸锥。

定义1.4.4 设$S$为非空凸集，$\vec{x}\in S$，若$\forall\vec{x}_1,\vec{x}_2,\lambda(\vec{x}_1,\vec{x}_2\in S\land\lambda\in(0,1)\land\vec{x}=\lambda\vec{x}_1+(1-\lambda)\vec{x}_2\rightarrow\vec{x}=\vec{x}_1=\vec{x}_2)$，则称$\vec{x}$为凸集$S$的极点。

紧凸集中的点可以表示为极点的线性组合，但对无界集并不成立。

定义1.4.5 设$S\subseteq\mathbb{R}^n$为闭凸集，$\vec{d}\in\mathbb{R}^n$非零，若$\forall\vec{x}(\vec{x}\in S\rightarrow{\vec{x}+\lambda\vec{d}\mid\lambda\in\mathbb{R}^+}\subseteq S)$，则称$\vec{d}$为$S$的方向。又设$\vec{d}_1,\vec{d}_2$是$S$的两个方向，若$\forall\lambda(\lambda\in\mathbb{R}^+\rightarrow\vec{d}_1\neq\lambda\vec{d}_2)$，则称$\vec{d}_1,\vec{d}_2$是不同的方向。若$S$的方向$\vec{d}$不能表示成两个不同方向的正的线性组合，则称$\vec{d}$是$S$的极方向。

有界集不存在方向和极方向。

考虑平面直角坐标系中的半平面$x\geq \alpha$，可以发现有3个极方向，分别是$(0, \lambda_+)^T,(0, \lambda_-)^T,(\lambda_+, \lambda)^T$，且不存在极点。

特别地，对于$S={x\mid\mathbf{A}\vec{x}=\vec{b},\vec{x}\geq\vec{0}}$，$\vec{d}$为$S$的方向等价于$\vec{d}\geq\vec{0}\land\mathbf{A}\vec{d}=\vec{0}$。

定理1.4.1 表示定理：设$S={x\mid\mathbf{A}\vec{x}=\vec{b},\vec{x}\geq\vec{0}}$为非空多面集（它一定是多面集），则：

1. 极点集非空且为有限个$\vec{x}_1,\cdots,\vec{x}_k$；
2. 极方向为空当且仅当$S$有界，$S$无界，则有有限个极方向$\vec{d}_1,\cdots,\vec{d}_l$；
3. $\vec{x}\in S$当且仅当： $$\begin{aligned}&\vec{x}=\sum_{j=1}^k\lambda_j\vec{x}_{j}+\sum_{j=1}^l\mu_j\vec{d}_j,\\ &\sum_{j=1}^k\lambda_j=1,\\ &\lambda_j\geq 0, j=1,\cdots,k,\\ &\mu_j\geq 0, j=1,\cdots,l. \end{aligned}$$

凸集分离定理

（暂不收录）

凸函数

（暂不收录）

凸函数的判别

（暂不收录）

凸规划

（暂不收录）