组合优化与凸优化

基础知识：向量求导

在优化方法、机器学习领域，向量求导非常常见。作为凸优化的前导知识，我们在这一节重点记录一些常用的向量求导公式。注意，这里仅记录标量函数$f:\mathbb{R}^n\to\mathbb{R}$对向量的导数（梯度）。在下面的公式中，$\boldsymbol{x}, \boldsymbol{b}, \boldsymbol{c}\in\mathbb{R}^n, A\in\mathbb{R}^{n\times n}$.

1. 多元线性函数求导。

   $$\frac{d\boldsymbol{c}^T\boldsymbol{x}}{d\boldsymbol{x}} = \boldsymbol{c}$$

2. 仿射函数求导。

   $$\frac{dA\boldsymbol{x}}{d\boldsymbol{x}} = \frac{d\boldsymbol{x}A}{d\boldsymbol{x}} = A^T,A\in\mathbb{R}^{n\times n}$$

3. 二次型求导。

   $$\frac{d\boldsymbol{x}^TA\boldsymbol{x}}{d\boldsymbol{x}} = (A+A^T)\boldsymbol{x}$$

4. 特别地，上式中，如果$A$为对称矩阵，则有

   $$\frac{d\boldsymbol{x}^TA\boldsymbol{x}}{d\boldsymbol{x}} = 2A\boldsymbol{x}$$

   用标准二次型写法，等价地有

   $$\frac{d}{d\boldsymbol{x}}\left( \frac{1}{2}\boldsymbol{x}^TA\boldsymbol{x} \right) = A\boldsymbol{x}$$

5. 向量二范数求导。

   $$\frac{d\parallel A\boldsymbol{x}+\boldsymbol{b} \parallel_2^2}{d\boldsymbol{x}} = \frac{d(A\boldsymbol{x}+\boldsymbol{b})^T(A\boldsymbol{x}+\boldsymbol{b})}{d\boldsymbol{x}} = 2A^T(A\boldsymbol{x}+\boldsymbol{b}) \\ \frac{d\parallel \boldsymbol{x}A+\boldsymbol{b} \parallel_2^2}{d\boldsymbol{x}} = \frac{d(\boldsymbol{x}A+\boldsymbol{b})^T(\boldsymbol{x}A+\boldsymbol{b})}{d\boldsymbol{x}} = 2(A\boldsymbol{x}+\boldsymbol{b})A^T$$
6. $$\frac{d\boldsymbol{b}^T\boldsymbol{x}\boldsymbol{x}^T\boldsymbol{c}}{d\boldsymbol{x}} = (\boldsymbol{b}\boldsymbol{c}^T+\boldsymbol{c}\boldsymbol{b}^T)\boldsymbol{x}$$

基本概念

仿射组合与仿射集

• 定义一

  对于集合$\mathcal{C}$，若$\forall \boldsymbol{x}_1,\boldsymbol{x}_2 \in \mathcal{C}$，$\theta \in \mathbb{R}$，$s.t. \theta \boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2\in \mathcal{C}$，则称$\mathcal{C}$为仿射集。

• 定义二

  对于集合$\mathcal{C}$，若$\forall \boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_k \in \mathcal{C}$，$\theta_1,\theta_2,\dots,\theta_k \in \mathbb{R}$且$\displaystyle \sum_{i=1}^k\theta_i=1$，若仿射组合$\displaystyle\boldsymbol{x}=\sum_{i=1}^k\theta_i\boldsymbol{x}_i\in \mathbb{R}$，则称$\mathcal{C}$为仿射集。

上面均为仿射集的定义。我们接下来尝试证明两个定义的等价性。

一方面，由定义二推导定义一非常容易，因为定义二本身就比定义一更强。

另一方面，由定义一推导定义二，我们这里仅给出推导三个元素的情况。即证明：

$$\forall \boldsymbol{x}_1,\boldsymbol{x}_2,\boldsymbol{x}_3\in \mathcal{C}, \theta_1,\theta_2,\theta_3\in\mathbb{R},\sum_{i=1}^3\theta_i=1,\sum_{i=1}^3\theta_i\boldsymbol{x}_i\in \mathcal{C}$$

根据定义一，有$\alpha \boldsymbol{x}_1+(1-\alpha)\boldsymbol{x}_2 \in \mathcal{C}$，进而有

$$\beta[\alpha \boldsymbol{x}_1+(1-\alpha)\boldsymbol{x}_2] + (1-\beta)\boldsymbol{x}_3 \in \mathcal{C}$$

我们对上式进行整理，得

$$\alpha\beta\boldsymbol{x}_1 + (1-\alpha)\beta\boldsymbol{x}_2 + (1-\beta)\boldsymbol{x}_3 \in \mathcal{C}$$

令

$$\begin{cases} \alpha\beta &= \theta_1 \\ (1-\alpha)\beta &= \theta_2 \\ 1-\beta &= \theta_3 \end{cases}$$

得

$$\begin{cases} \displaystyle\alpha = \frac{\theta_1}{\theta_1+\theta_2} \\ \beta = \theta_1 + \theta_2 \end{cases}$$

故我们最终构造的证明过程如下：

$$\forall \boldsymbol{x}_1,\boldsymbol{x}_2 \in \mathcal{C}, \frac{\theta_1}{\theta_1+\theta_2}\boldsymbol{x}_1 + \frac{\theta_2}{\theta_1+\theta_2}\boldsymbol{x}_2 \in \mathcal{C}$$

又$\theta_1+\theta_2+\theta_3=1$，故有

$$\forall \boldsymbol{x}_3\in \mathcal{C},(\theta_1+\theta_2)\left( \frac{\theta_1}{\theta_1+\theta_2}\boldsymbol{x}_1 + \frac{\theta_2}{\theta_1+\theta_2}\boldsymbol{x}_2 \right) + \theta_3 \boldsymbol{x}_3 \in \mathcal{C}$$

即

$$\forall \boldsymbol{x}_1,\boldsymbol{x}_2,\boldsymbol{x}_3\in \mathcal{C}, \theta_1,\theta_2,\theta_3\in\mathbb{R},\sum_{i=1}^3\theta_i=1,\sum_{i=1}^3\theta_i\boldsymbol{x}_i\in \mathcal{C}$$

相关子空间

对于仿射集$\mathcal{C}$，定义与$\mathcal{C}$相关的子空间$\mathcal{V}$，

$$\mathcal{V}=\{ \boldsymbol{x}-\boldsymbol{x}_0 | \boldsymbol{x}_0\in\mathcal{C},\forall \boldsymbol{x}\in \mathcal{C} \}$$

性质

$\forall \boldsymbol{x}_1,\boldsymbol{x}_2\in\mathcal{V},\alpha,\beta\in\mathbb{R},\alpha\boldsymbol{x}_1+\beta\boldsymbol{x}_2\in \mathcal{V}.$

与之前的仿射组合中参数之和为1的限制不同，此处的参数取值无限制。下面给出证明。

$$\forall \alpha,\beta\in\mathbb{R},\boldsymbol{x}_1,\boldsymbol{x}_2\in\mathcal{C},\boldsymbol{x}_1-\boldsymbol{x}_0,\boldsymbol{x}_2-\boldsymbol{x}_0\in\mathcal{V}$$

故

$$\alpha(\boldsymbol{x}_1-\boldsymbol{x}_0) + \beta(\boldsymbol{x}_2-\boldsymbol{x}_0) = \alpha\boldsymbol{x}_1+\beta\boldsymbol{x}_2-(\alpha+\beta)\boldsymbol{x}_0$$

而

$$\alpha\boldsymbol{x}_1+\beta\boldsymbol{x}_2-(\alpha+\beta)\boldsymbol{x}_0 + \boldsymbol{x}_0 = \alpha\boldsymbol{x}_1+\beta\boldsymbol{x}_2+(1-\alpha-\beta)\boldsymbol{x}_0 \in \mathcal{C}$$

因此得到

$$\alpha(\boldsymbol{x}_1-\boldsymbol{x}_0) + \beta(\boldsymbol{x}_2-\boldsymbol{x}_0) = \alpha\boldsymbol{x}_1+\beta\boldsymbol{x}_2-(\alpha+\beta)\boldsymbol{x}_0 \in \mathcal{V}$$

证毕。

例 线性方程组的解集$\mathcal{C} = \{ \boldsymbol{x}\in\mathbb{R}^n|A\boldsymbol{x}=\boldsymbol{b} \}$是仿射集，其中$A\in\mathbb{R}^{m\times n},\boldsymbol{b}\in\mathbb{R}^m$。

证明：

$$\forall \boldsymbol{x}_1,\boldsymbol{x}_2\in\mathcal{C},A\boldsymbol{x}_1=\boldsymbol{b},A\boldsymbol{x}_2=\boldsymbol{b}.$$

故有

$$\forall \theta\in\mathbb{R}^n,A(\theta\boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2)=\theta A\boldsymbol{x}_1+(1-\theta)A\boldsymbol{x}_2=\boldsymbol{b}$$

因此得到$\theta\boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2 \in \mathcal{C}$，证毕。

如果一个集合并不是仿射集，那么如何将其中添加元素，得到一个仿射集呢？于是我们引入如下概念：

仿射包 对于集合$\mathcal{C}$，其仿射包为$\displaystyle aff(\mathcal{C})=\left\{ \sum_{i=1}^k\theta_i\boldsymbol{x}_i | \forall \boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_k\in \mathcal{C},\sum_{i=1}^k \theta_i=1 \right\}$.

显然，仿射集的仿射包就是他本身。

凸组合，凸集与凸包

和仿射集类似地，凸集有如下定义：

凸集 集合$\mathcal{C}$为凸集，当且仅当$\forall \boldsymbol{x}_1,\boldsymbol{x}_2 \in \mathcal{C}, \theta\in [0,1], \theta\boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2 \in \mathcal{C}$.

凸组合 设$\displaystyle\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_k\in\mathcal{C},\theta_1,\theta_2,\dots,\theta_k\in[0,1],\sum_{i=1}^k\theta_i=1$，则$\displaystyle\boldsymbol{x}=\sum_{i=1}^k\theta_i\boldsymbol{x}_i$为$\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_k$的凸组合.

凸包 集合$\mathcal{C}$的凸包可以表示为$\displaystyle conv(\mathcal{C})=\left\{ \sum_{i=1}^k\theta_i\boldsymbol{x}_i | \forall \boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_k \in \mathcal{C},\theta_1,\theta_2,\dots,\theta_k\in [0,1], \sum_{i=1}^k\theta_i=1 \right\}$.

在二维平面中，任何凸多边形都是凸集；特别地，单个点组成的集合也是凸集。

锥，凸锥，凸锥组合与凸锥包

类似地，我们给出如下定义：

锥 集合$\mathcal{C}$为锥，当且仅当$\forall \boldsymbol{x}\in\mathcal{C},\theta\geqslant 0, \theta \boldsymbol{x} \in \mathcal{C}$.

凸锥 集合$\mathcal{C}$为凸锥，当且仅当$\forall \boldsymbol{x}_1,\boldsymbol{x}_2\in\mathcal{C},\theta_1,\theta_2\geqslant 0, \theta_1\boldsymbol{x}_1+\theta_2\boldsymbol{x}_2\in\mathcal{C}$.

凸锥组合 设$\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_k\in\mathcal{C},\theta_1,\theta_2,\dots,\theta_k\geqslant 0$，点$\displaystyle \boldsymbol{x}=\sum_{i=1}^k\theta_i\boldsymbol{x}_i$为$\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_k$的凸锥组合.

凸锥包 集合$\mathcal{C}$的凸锥包可以表示为$\displaystyle \left\{ \sum_{i=1}^k\theta_i\boldsymbol{x}_i|\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_k\in\mathcal{C},\theta_1,\theta_2,\dots,\theta_k\geqslant 0 \right\}$.

在二维平面中，一条以原点为源点的射线，即为凸锥；特别地，仅含原点的单点集合也是一个凸锥。

超平面和半空间

超平面 集合$\mathcal{A} = \{ \boldsymbol{x}\in\mathbb{R}^n|\boldsymbol{a}^T\boldsymbol{x}=b \}$为超平面，其中$b\in\mathbb{R},\boldsymbol{a}\ne\boldsymbol{0}$.

半空间 超平面$\mathcal{A}$将$\mathbb{R}^n$划分为两个半空间

$$\mathcal{H}^+ = \{ \boldsymbol{x}|\boldsymbol{a}^T\boldsymbol{x}\geqslant b \}\\ \mathcal{H}^- = \{ \boldsymbol{x}| \boldsymbol{a}^T\boldsymbol{x}\leqslant b \}$$

球和椭球

球 $\mathcal{B}(\boldsymbol{x}_c,r)=\{ \boldsymbol{x}| \parallel\boldsymbol{x}-\boldsymbol{x}_c\parallel_2\leqslant r \}$.

椭球 $\varepsilon(\boldsymbol{x}_c,P) = \{ \boldsymbol{x}|\sqrt{(\boldsymbol{x}-\boldsymbol{x}_c)^TP^{-1}(\boldsymbol{x}-\boldsymbol{x}_c)}\leqslant 1 \}$，其中$\boldsymbol{x}\in\mathbb{R}^n,P\in S_{++}^n$（$S_{++}^n\in\mathbb{R}^{n\times n}$为对称正定矩阵）.

根据之前的定义，球有如下性质：

• 一定是凸集；
• 一般来说不是仿射集，当$r=0$时，$\mathcal{B}$为仿射集；
• 一般来说不是凸锥，但当$r=0$且$\boldsymbol{x}_c=0$时，$\mathcal{B}$为凸锥。

我们给出球是凸集的证明：

由球的定义可得

$$\forall \boldsymbol{x}_1,\boldsymbol{x}_2\in\mathcal{B},\parallel \boldsymbol{x}_1-\boldsymbol{x}_c \parallel_2\leqslant r, \parallel \boldsymbol{x}_2-\boldsymbol{x}_c \parallel_2\leqslant r$$

故

$$\begin{aligned} \forall \theta\in[0,1],&\parallel \theta\boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2-\boldsymbol{x}_c \parallel_2 \\ &=\parallel \theta\boldsymbol{x}_1-\theta\boldsymbol{x}_c+(1-\theta)\boldsymbol{x}_2-(1-\theta)\boldsymbol{x}_c \parallel_2 \\ &= \parallel \theta(\boldsymbol{x}_1-\boldsymbol{x}_c) + (1-\theta)(\boldsymbol{x}_2-\boldsymbol{x}_c) \parallel_2 \\ &\leqslant \theta\parallel \boldsymbol{x}_1-\boldsymbol{x}_c \parallel_2 + (1-\theta)\parallel \boldsymbol{x}_2-\boldsymbol{x}_c \parallel_2 \\ &\leqslant \theta r+(1-\theta)r \\ &= r \end{aligned}$$

因此，$\theta \boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2\in\mathcal{B}$，$\mathcal{B}$为凸集。

凸函数

这里给出凸函数的4个常用定义。

凸函数定义一 定义在凸集$\mathcal{C}$上的函数$f$是凸的，倘若$\forall 0<\lambda<1$，均有$f(\lambda \boldsymbol{x}+(1-\lambda)\boldsymbol{y})\leqslant \lambda f(\boldsymbol{x})+(1-\lambda)f(\boldsymbol{y})$成立。当不等式严格成立时，称$f$为严格凸函数。相反地，若$-f$为凸函数，则$f$为凸集$\mathcal{C}$上的凹函数，不等式严格成立时，称$f$为严格凹函数。

凸函数定义二 定义在凸集$\mathcal{C}$上的函数$f$是凸的，倘若$\forall \boldsymbol{x} \in \mathrm{dom}(f), \forall \boldsymbol{v}$，函数$g(t) = f(\boldsymbol{x} + t\boldsymbol{v})$是凸函数，其中$t\in \{ t|\boldsymbol{x}+t\boldsymbol{v}\in\mathrm{dom}(f) \}$.

凸函数定义三 定义在凸集$\mathcal{C}$上的可微函数$f$是凸的，倘若$\forall \boldsymbol{x},\boldsymbol{y}\in\mathrm{dom}(f)$，均有$f(\boldsymbol{y})\geqslant f(\boldsymbol{x})+\nabla^Tf(\boldsymbol{x})(\boldsymbol{y}-\boldsymbol{x})$成立；当不等式严格成立时，称$f$为严格凸函数.

凸函数定义四 定义在凸集$\mathcal{C}$上的二阶可微函数$f$是凸的，倘若其Hessian矩阵$\displaystyle H=\left( \frac{\partial^2f}{\partial \boldsymbol{x}_i \partial \boldsymbol{x}_j} \right)$半正定，也即$\forall \boldsymbol{x}\in\mathrm{dom}(f),\nabla^2f(\boldsymbol{x})\succeq 0$；此处注意，若$H$为正定的，$f$不一定严格凸.

保凸运算

非负加权和 $f_1,f_2,\dots,f_m$为凸函数，则对于$w_i\geqslant 0,i=1,2,\dots,n$，函数$\displaystyle f=\sum_{i=1}^mw_if_i$仍为凸函数。

非负加权和扩展到无穷形式的积分 若$f(x,y)$对于任意$y\in \mathcal{A}$，$f(x,y)$均为凸函数，当$w(y)\geqslant 0$，$\displaystyle\forall y\in\mathcal{A},g(x)=\int_{y\in\mathcal{A}}w(y)f(x,y)dy$为凸函数。

仿射映射 映射$f:\mathbb{R}^n\to \mathbb{R},A\in\mathbb{R}^{n\times m},\boldsymbol{b}\in\mathbb{R}^m$，定义映射$g:\mathbb{R}^m\to\mathbb{R},g(x)=f(Ax+\boldsymbol{b})$，其中$\mathrm{dom}(g)=\{ \boldsymbol{x}|A\boldsymbol{x}+\boldsymbol{b}\in \mathrm{dom}(f) \}$，若$f$为凸函数，则$g$也为凸函数。

注 仿射映射，可以看作“先仿射（仿射不改变凸性）后映射”，因此仿射映射不改变原映射的凸性。但是对于凸函数的仿射结果不一定仍为凸函数，例如

若函数$f_i:\mathbb{R}^n\to\mathbb{R}$为凸函数，函数$g:\mathbb{R}^n\to\mathbb{R},g(x)=A^T[f_1(x),f_2(x),\dots,f_m(x)]^T+b,A\in\mathbb{R}^m,b\in\mathbb{R}$不一定为凸函数，因为凸函数的“非负加权和”才仍为凸函数。

逐点最大函数 函数$f(x)=\max\{f_1(x),f_2(x)\}$，$\mathrm{dom}(f)=\mathrm{dom}(f_1)\cap \mathrm{dom}(f_2)$，当$f_1,f_2$为凸函数时，$f$也为凸函数。

这里给出简单的证明。在此之前给出一个引理

设$a,b,c,d\in\mathbb{R}$，如下不等式成立

$$\max\{ a+b,c+d \} \leqslant \max\{ a,c \} + \max\{ b,d \}$$

【证明上述逐点最大函数为凸函数】

由于函数$f_1,f_2$为凸函数，则$\forall x,y\in\mathrm{dom}(f),\theta \in [0,1]$，有

$$\begin{aligned} f(\theta x+(1-\theta)y) &= \max\{ f_1(\theta x+(1-\theta)y),f_2(\theta x+(1-\theta)y) \} \\ &\leqslant \max\{ \theta f_1(x)+(1-\theta)f_1(y), \theta f_2(x)+(1-\theta)f_2(y) \} \\ &\leqslant \max\{ \theta f_1(x),\theta f_2(x) \} + \max\{ (1-\theta)f_1(y),(1-\theta)f_2(y) \} \\ &=\theta \max\{ f_1(x),f_2(x) \} + (1-\theta)\max\{ f_1(y),f_2(y) \} \\ &=\theta f(x) + (1-\theta)f(y) \end{aligned}$$

因此$f$为凸函数。

_例 实对称矩阵的最大特征值_

函数$f(X)=\lambda_{max}(X),\ \mathrm{dom}(f)=S^n$，根据特征值的定义，得$\exist \boldsymbol{y}\in\mathbb{R}^n,X\boldsymbol{y}=\lambda \boldsymbol{y}$，进而

$$\begin{aligned} \boldsymbol{y}^TX\boldsymbol{y} &= \boldsymbol{y}^T\lambda\boldsymbol{y} \\ \Leftrightarrow \boldsymbol{y}^TX\boldsymbol{y}&=\lambda \parallel \boldsymbol{y} \parallel_2^2 \\ \Leftrightarrow \lambda &= \frac{\boldsymbol{y}^TX\boldsymbol{y}}{\parallel \boldsymbol{y} \parallel_2^2} \end{aligned}$$

不妨有$\parallel \boldsymbol{y} \parallel_2^2=1$，则$\lambda = \boldsymbol{y}^TX\boldsymbol{y}$，于是

$\displaystyle f(X) = \sup\{ \boldsymbol{y}^TX\boldsymbol{y}|\boldsymbol{y}为X的特征向量且\parallel \boldsymbol{y} \parallel_2^2=1 \}$

几何平均 函数$\displaystyle f(\boldsymbol{x})=(x_1x_2\dots x_n)^{\frac{1}{n}},\boldsymbol{x}\in\mathbb{R}^n$在定义域$\mathbb{R}_{++}^n$上是凹函数。

【证明】

首先需要强调$\mathbb{R}_{++}^n$为凸集。由$f(\boldsymbol{x})$在$\mathbb{R}_{++}^n$上二阶可微，得

$$\nabla f(\boldsymbol{x}) = \frac{1}{n}\left( \prod_{k=1}^nx_k \right)^{\frac{1}{n}-1}\left[ \prod_{k\ne 1}x_k, \prod_{k\ne 2}x_k,\dots, \prod_{k\ne n}x_k \right]^T$$

当$i\ne j$时，

$$\begin{aligned} \frac{\partial^2f}{\partial x_i \partial x_j} &= \frac{\partial }{\partial x_j}\left[ \frac{1}{n}\left( \prod_{k=1}^nx_k \right)^{\frac{1}{n}-1} \prod_{k\ne i}x_k \right] \\ &= \frac{1}{n^2}\left( \prod_{k=1}^nx_k \right)^{\frac{1}{n}}\cdot \frac{1}{x_ix_j} \end{aligned}$$

当$i=j$时，

$$\frac{\partial^2f}{\partial x_i^2} = \frac{1-n}{n}\left( \prod_{k=1}^nx_k \right)^{\frac{1}{n}}\cdot \frac{1}{x_i^2}$$

故而二阶Hessian矩阵

$$\begin{aligned} H&=\nabla^2f(\boldsymbol{x}) = \frac{1}{n^2}\left( \prod_{k=1}^nx_k \right)^{\frac{1}{n}} \begin{bmatrix}\displaystyle (1-n)\frac{1}{x_1^2} & \displaystyle\frac{1}{x_1x_2} & \displaystyle\cdots & \displaystyle\frac{1}{x_1x_n} \\ \displaystyle\frac{1}{x_1x_2} & \displaystyle(1-n)\frac{1}{x_2^2} & \cdots & \displaystyle\frac{1}{x_2x_n} \\ \vdots & \vdots & \vdots & \vdots \\ \displaystyle\frac{1}{x_1x_n} & \displaystyle\frac{1}{x_2x_n} & \displaystyle\cdots & \displaystyle(1-n)\frac{1}{x_n^2} \end{bmatrix} \\ &= \frac{1}{n^2}\left( \prod_{k=1}^nx_k \right)^{\frac{1}{n}}\left[ \boldsymbol{p}\boldsymbol{p}^T - n\mathbf{diag}\left( \frac{1}{x_1^2},\frac{1}{x_2^2},\cdots,\frac{1}{x_n^2} \right) \right] \end{aligned}$$

其中，

$$\boldsymbol{p} = \left[\frac{1}{x_1},\frac{1}{x_2},\cdots,\frac{1}{x_n}\right]^T$$

故$\forall \boldsymbol{y}=[y_1,y_2,\cdots,y_n]^T\in\mathbb{R}^n$，

$$\begin{aligned} \boldsymbol{y}^TH\boldsymbol{y} &= \frac{1}{n^2}\left( \prod_{k=1}^nx_k \right)^{\frac{1}{n}}\left[ \boldsymbol{y}^T\boldsymbol{p}\boldsymbol{p}^T\boldsymbol{y} - n\boldsymbol{y}^T\mathbf{diag}\left( \frac{1}{x_1^2},\frac{1}{x_2^2},\cdots,\frac{1}{x_n^2} \right)\boldsymbol{y} \right] \\ &= \frac{1}{n^2}\left( \prod_{k=1}^nx_k \right)^{\frac{1}{n}} \left[ \left( \sum_{k=1}^n\frac{y_k}{x_k} \right)^2-n\left( \sum_{k=1}^n\frac{y_k^2}{x_k^2} \right) \right] \end{aligned}$$

由Cauchy-Schwartz不等式$(\boldsymbol{a}^T\boldsymbol{b})^2\leqslant (\boldsymbol{a}^T\boldsymbol{a})(\boldsymbol{b}^T\boldsymbol{b})$，令$\displaystyle \boldsymbol{a} = \left[ \frac{y_1}{x_1}, \frac{y_2}{x_2}, \cdots, \frac{y_n}{x_n} \right]^T$，$\boldsymbol{b}=\boldsymbol{1}$，得

$$\left( \sum_{k=1}^n\frac{y_k}{x_k} \right)^2 \leqslant n\left( \sum_{k=1}^n\frac{y_k^2}{x_k^2} \right)$$

故有$\forall \boldsymbol{y} \in \mathbb{R}^n$，$\boldsymbol{y}^TH\boldsymbol{y} \leqslant 0$，即$H\preceq 0$，因此$f(\boldsymbol{x})$在$\mathbb{R}_{++}^n$上为凹函数。

行列式的对数 函数$f:S_{++}^n\to \mathbb{R},f(X)=\log\det X,X\in\mathbb{R}^{n\times n}$是凸函数。

考虑

$$\begin{aligned} g(t) &= f(X+tV) \\ &= \log\det(X+tV) \\ &= \log\det\left(X^{\frac{1}{2}} (I+tX^{-\frac{1}{2}}VX^{-\frac{1}{2}})X^{\frac{1}{2}} \right) \\ &= \log\left( \det X^{\frac{1}{2}}\cdot \det X^{\frac{1}{2}} \cdot \det\left( I+tX^{-\frac{1}{2}}VX^{-\frac{1}{2}} \right) \right) \\ &= \log \det X + \sum_{i=1}^n\log(1+t\lambda_i) \end{aligned}$$

其中，$\lambda_1,\cdots,\lambda_n$为$I+tX^{-\frac{1}{2}}VX^{-\frac{1}{2}}$的$n$个特征值。故

$$g'(t)=\sum_{i=1}^n\frac{\lambda_i}{1+t\lambda_i}$$ $$g''(t) = -\sum_{i=1}^n\frac{\lambda_i^2}{(1+t\lambda_i)^2} \leqslant 0$$

因而$g(t)$是凹函数，$f(X)$也为凹函数。

复合函数的凸性

给定函数$h:\mathbb{R}^k\to\mathbb{R},g:\mathbb{R}^n\to\mathbb{R}^k$，定义复合函数$f=h\circ g:\mathbb{R}^n\to\mathbb{R},f(\boldsymbol{x})=h(g(\boldsymbol{x})),\mathrm{dom}(f)=\{ \boldsymbol{x}\in\mathrm{dom}(g)|g(\boldsymbol{x})\in \mathrm{dom}(h) \}$，接下来给出复合函数之间的凹凸性质。

我们从简单情况考虑，即一维情况$k=n=1$、$\mathrm{dom}(f)=\mathrm{dom}(h)=\mathrm{dom}(g)=\mathbb{R}$以及$h,g$均二阶可微，根据凸函数的定义4，对$f$求二阶导数，得

$$f''(x) = h''(g(x))[g'(x)]^2 + h'(g(x))g''(x)$$

因此我们有如下结论：

• 若$h$为凸函数且单调不减，$g$为凸函数，则$f$为凸函数；
• 若$h$为凸函数且单调不增，$g$为凹函数，则$f$为凸函数；
• 若$h$为凹函数且单调不减，$g$为凹函数，则$f$为凹函数；
• 若$h$为凹函数且单调不增，$g$为凸函数，则$f$为凹函数。

那么更复杂的情况，也即$k,n\geqslant 1$、$\mathrm{dom}(f),\mathrm{dom}(g),\mathrm{dom}(h)\ne \mathbb{R}^n,\mathbb{R}^n,\mathbb{R}^k$以及$h,g$均不二阶可微呢？这里我们引入一个新概念：$h$的扩展函数$\widetilde{h}$，和上述四条结论类似地，有

• 若$h$为凸函数且$\widetilde{h}$单调不减，$g$为凸函数，则$f$为凸函数；
• 若$h$为凸函数且$\widetilde{h}$单调不增，$g$为凹函数，则$f$为凸函数；
• 若$h$为凹函数且$\widetilde{h}$单调不减，$g$为凹函数，则$f$为凹函数；
• 若$h$为凹函数且$\widetilde{h}$单调不增，$g$为凸函数，则$f$为凹函数。

其中，若$h$为凸函数，则

$$\widetilde{h}(\boldsymbol{x}) = \begin{cases} h(\boldsymbol{x}),\ \boldsymbol{x}\in \mathrm{dom}(h) \\ +\infin, \boldsymbol{x} \notin \mathrm{dom}(h) \end{cases}$$

反之，若$h$为凹函数，只需将上述$\boldsymbol{x}\notin \mathrm{dom}(h)$时取值$+\infin$改为$-\infin$即可。

共轭函数

函数的共轭 函数$f:\mathbb{R}^n\to \mathbb{R}$，其共轭函数$f^*:\mathbb{R}^n\to\mathbb{R}$定义为

$$f^*(\boldsymbol{y}) = \sup_{\boldsymbol{x}\in\mathrm{dom}(f)}\{ \boldsymbol{y}^T\boldsymbol{x}-f(\boldsymbol{x}) \}$$

之所以提出函数共轭的概念，因为其有如下良好性质：

1. 若函数$f$可微，则$f^(\boldsymbol{y})$对应的$\displaystyle\boldsymbol{x}^=\arg\sup_{\boldsymbol{x}\in\mathrm{dom}(f)}\{ \boldsymbol{y}^T\boldsymbol{x}-f(\boldsymbol{x}) \}$必是使得$\nabla f(\boldsymbol{x})=y$的一点；

   此处令$\displaystyle \nabla_\boldsymbol{x}(\boldsymbol{y}^T\boldsymbol{x}-f(\boldsymbol{x}))=0$，也即$\boldsymbol{y}-\nabla f(\boldsymbol{x})=0$.

2. 函数的共轭一定是凸函数。

_例 二次型_ 求函数$\displaystyle f(\boldsymbol{x})=\frac{1}{2}\boldsymbol{x}^TQ\boldsymbol{x},Q\in S_{++}^n,\mathrm{dom}(f)=\mathbb{R}^n$的共轭。

令$\nabla f(\boldsymbol{x})=\boldsymbol{y}$，即$Q\boldsymbol{x}^=\boldsymbol{y}$，得$\boldsymbol{x}^=Q^{-1}\boldsymbol{y}$，注意到$Q\in S_{++}^n,Q^{-1}\in S_{++}^n$，故

$$\begin{aligned} f^*(\boldsymbol{y}) &= \boldsymbol{y}^TQ^{-1}\boldsymbol{y}-\frac{1}{2}\boldsymbol{y}^T(Q^{-1})^TQQ^{-1}\boldsymbol{y} \\ &= \frac{1}{2}\boldsymbol{y}^TQ^{-1}\boldsymbol{y} \end{aligned}$$

$\alpha$-下水平集

对于$f:\mathbb{R}^n\to \mathbb{R}$，其$\alpha$-下水平集为

$$\mathcal{C}_\alpha = \{\boldsymbol{x}\in\mathrm{dom}(f)|f(\boldsymbol{x})\leqslant \alpha\}$$

注意，凸函数的任意下水平集均为凸集；但是反之，若函数$f$的任意$\alpha$-下水平集均为凸集，则$f$不一定为凸函数。例如$f(x)=-e^x,x\in\mathbb{R}$为凹函数，但其$\alpha$-下水平集（$\alpha\in\mathbb{R}$）为凸集。

拟凸函数

虽然上面的性质“函数$f$的任意$\alpha$-下水平集均为凸集”并不一定能够推导出其一定为凸函数，但是该性质非常良好。因此，给出拟凸函数的定义：

拟凸函数 称函数$f:\mathbb{R}^n\to\mathbb{R}$为拟凸函数，倘若其定义域为凸集，且任意的$\alpha$-下水平集也为凸集。

拟凹函数 称函数$f:\mathbb{R}^n\to\mathbb{R}$为拟凹函数，倘若其定义域为凸集，且任意的$\alpha$-上水平集也为凸集。

拟线性函数 称函数$f:\mathbb{R}^n\to\mathbb{R}$为拟凸函数，倘若其定义域为凸集，且任意的$\alpha$-水平集也为凸集。

此外，我们给出另一个拟凸函数的定义。

拟凸函数（定义2） 函数$f$是拟凸函数，倘若$\mathrm{dom}(f)$为凸函数，且$\forall \boldsymbol{x},\boldsymbol{y}\in\mathrm{dom}(f),0\leqslant \lambda \leqslant 1$，均有

$$f(\lambda\boldsymbol{x}+(1-\lambda)\boldsymbol{y}) \leqslant \max\{ f(\boldsymbol{x}),f(\boldsymbol{y}) \}$$

凸优化问题

基本概念

一般优化问题 一个优化问题通常被形式地定义为

$$\begin{aligned} \min\ f_0(\boldsymbol{x})& \\ s.t.\ f_i(\boldsymbol{x})&\leqslant 0,i=1,2,\dots,m \\ h_j(\boldsymbol{x})&=0,j=1,2,\dots,p \end{aligned}$$

其中，前$m$个不等式称为不等式约束，后$p$个等式称为等式约束。

接下来借助上述定义说明几个概念。

优化变量 问题中的$\boldsymbol{x}\in\mathbb{R}^n$称为优化变量。

目标函数/损失函数 函数$f_0:\mathbb{R}^n\to\mathbb{R}$称为目标函数/损失函数。若为最大化问题，则称之为效用函数。

优化问题的域 称$D = \displaystyle \bigcap_{i=0}^m\mathrm{dom}(f_i)\cap \bigcap_{j=1}^p\mathrm{dom}(h_j)$为优化问题的域。

可行解 $\boldsymbol{x}\in D$为可行解，若$f_i(\boldsymbol{x})\leqslant 0,i=1,2,\dots,m;h_j(\boldsymbol{x})=0,j=1,2,\dots,p$.

可行解集 全部可行解组成的集合$X_f = \{ \boldsymbol{x}| f_i(\boldsymbol{x})\leqslant 0,i=1,2,\dots,m;h_j(\boldsymbol{x})=0,j=1,2,\dots,p \}$称为可行解集.

问题的最优值 问题的最优值为该最小化问题能取得的最小值$\displaystyle p^*=\inf_{\boldsymbol{x}\in X_f}\{f_0(\boldsymbol{x})\}$.

问题的最优解 问题的最优解为取得最优值时，所对应的优化变量的取值，即$\displaystyle\boldsymbol{x}^=\arg\min_{\boldsymbol{x}\in D} f_0(\boldsymbol{x}),f(\boldsymbol{x}^)=p^*$.

最优解集 称最优解构成的集合为最优解集$X_{opt}=\{ \boldsymbol{x}|\boldsymbol{x}\in X_f, f_0(\boldsymbol{x})=p^* \}$

$\varepsilon-$次优解集 称次优解集为$X_\varepsilon = \{ \boldsymbol{x}|\boldsymbol{x}\in X_f, f_0(\boldsymbol{x})\leqslant p^*+\varepsilon \}$

线性规划与单纯形法

这一部分，我们通过一个具体的实例，来展现单纯形法的执行步骤。

例如如下的标准型线性规划问题

$$\begin{aligned} \max\ 3x_1 + x_2 + 2x_3 & \\ s.t.\ x_1 + x_2 + 3x_3 &\leqslant 30 \\ 2x_1 + 2x_2 + 5x_3 &\leqslant 24 \\ 4x_1 + x_2 + 2x_3 &\leqslant 36 \\ x_1,x_2,x_3 &\geqslant 0 \end{aligned}$$

首先，为了方便后续单纯形法的执行，我们将标准型重写为松弛型，即引入新的变量$x_4,x_5,x_6\geqslant 0$，并忽略显而易见的单变量不等式约束$x_i\geqslant 0$，写为

$$\begin{aligned} Z &= 3x_1 + x_2 + 2x_3 \\ x_4 &= 30 - x_1 - x_2 - 3x_3 \\ x_5 &= 24 - 2x_1 - 2x_2 - 5x_3 \\ x_6 &= 36 - 4x_1 - x_2 - 2x_3 \end{aligned}$$

单纯形法开始执行。等式左侧的$x_4,x_5,x_6$被称为基变量，而右侧的$x_1,x_2,x_3$被称为非基变量。初始解为

$$(\bar{x}_1,\bar{x}_2,\bar{x}_3,\bar{x}_4,\bar{x}_5,\bar{x}_6) = (0,0,0,30,24,36);Z=0$$

这个初始解是符合条件（$\boldsymbol{x}\geqslant 0$）的，下面继续执行单纯形法，也即迭代地将基变量换出称为非基变量，而非基变量转为基变量，以提高$Z$。

第一次迭代：我们发现$Z=3x_1+x_2+2x_3$这个式子中，$x_1$的系数最大，因此将$x_1$换入基变量；而下面的三个等式约束中，$x_6=36-4x_1-x_2-2x_3\geqslant0$对$x_1$是最紧的，因此将$x_6$换出成为非基变量，即对第三个等式进行变形为左侧只有$x_1$：

$$x_1 = 9 - \frac{x_2}{4} - \frac{x_3}{2} - \frac{x_6}{4}$$

根据上式得到新的松弛型

$$\begin{aligned} Z &= 27 + \frac{x_2}{4} + \frac{x_3}{2} - \frac{3x_6}{4} \\ x_1 &= 9 - \frac{x_2}{4} - \frac{x_3}{2} - \frac{x_6}{4} \\ x_4 &= 21 - \frac{3x_2}{4} - \frac{5x_3}{2} + \frac{x_6}{4} \\ x_5 &= 6 - \frac{3x_2}{2} - 4x_3 + \frac{x_6}{2} \end{aligned}$$

得到新的解

$$(9,0,0,21,6,0);Z=27$$

第二次迭代：和第一次类似，注意$Z$的表达式中$x_6$的系数已经为负，因此不再考虑优化$x_6$，故而选择$x_3$，将其换入基变量，将$x_5$换出成为非基变量，因为其所在的等式对$x_3$的约束最紧：

$$\begin{aligned} Z &= \frac{111}{4} + \frac{x_2}{16} - \frac{x_5}{8} - \frac{11x_6}{16}\\ x_1 &= \frac{33}{4} - \frac{x_2}{16} + \frac{x_5}{8} - \frac{16x_6}{5} \\ x_3 &= \frac{3}{2} - \frac{3x_2}{8} - \frac{x_5}{4} + \frac{x_6}{8}\\ x_4 &= \frac{69}{4} + \frac{3x_2}{16} + \frac{5x_5}{8} - \frac{x_6}{16} \end{aligned}$$

得到新的解

$$\left(\frac{33}{4},0,\frac{3}{2},\frac{69}{4},0,0\right);Z=\frac{111}{4}$$

第三次迭代：只能选择$x_2$换入基变量，选择$x_3$换出成为非基变量。

$$\begin{aligned} Z &= 28 - \frac{x_3}{6} - \frac{x_5}{6} - \frac{2x_6}{3}\\ x_1 &= 8 + \frac{x_3}{6} + \frac{x_5}{6} - \frac{x_6}{3}\\ x_2 &= 4 - \frac{8x_3}{3} - \frac{2x_5}{3} + \frac{x_6}{3}\\ x_4 &= 18 - \frac{x_3}{2} + \frac{x_5}{2} \end{aligned}$$

此时，再无非基变量可以继续优化（换入非基变量），因此算法执行结束，得到最终解为

$$(\bar{x}_1,\bar{x}_2,\bar{x}_3,\bar{x}_4,\bar{x}_5,\bar{x}_6) = (8,4,0,18,0,0);Z=28$$

良好性质

局部最优也是全局最优

不妨设$f(z)$为$f(x)$的局部最优，即下式成立

$$\exist r>0, s.t. f(z) = \inf_{x}\{ f(x)|x,z可行,\parallel x-z \parallel_2\leqslant r \}$$

往证$f(z)$也为全局最优。不然，则存在$z’$使得$f(z’)<f(z)$，且$\parallel z’-z \parallel_2 > r$.

取$\displaystyle\tilde{z} = (1-\theta)z+\theta z’, \theta = \frac{r}{2\parallel x-z \parallel_2}$,

则$\displaystyle\parallel \tilde{z} - z \parallel_2 = \parallel \theta(z’-z) \parallel_2 = \theta\parallel z’-z\parallel_2 = \frac{r}{2} < r$,由$z$为局部最优点得$f(\tilde{z}) > f(z)$.

另一方面，由$f$凸性得$f(\tilde{z}) = f((1-\theta)z+\theta z’) \leqslant (1-\theta)f(z) + \theta f(z’) \leqslant (1-\theta)f(z) + \theta f(z) = f(z)$,

矛盾。故假设不成立，得到$z$就是全局最优点.

（可微）最优性条件

对于凸优化问题，则$\boldsymbol{x}^$为最优解，当且仅当$\forall \boldsymbol{y} \in X_f, \nabla f_0^T(\boldsymbol{x}^)(\boldsymbol{y}-\boldsymbol{x}^*)\geqslant 0$

拉格朗日对偶

对偶函数性质

• 对偶函数是凹函数
• $\forall \lambda\geqslant 0,v, g(\lambda, v) \leqslant p^*$

证明第二条。首先根据对偶函数定义，有

$$g(\lambda, v) = \inf_xL(x,\lambda,v)$$

而

$$\forall \lambda_i>0,\ \inf_xL(x,\lambda,v) \leqslant L(x^*,\lambda,v) = f_0(x^*)+\sum_{i=1}^n\lambda_if_i(x^*)+\sum_{i=1}^pv_ih_i(x^*) \leqslant f_0(x^*) = p^*$$

故得到$g(\lambda,v) \leqslant p^*$.

鞍点解释

考虑仅含有不等式约束的凸优化问题

$$\begin{aligned} \min &f_0(\boldsymbol{x}) \\ s.t. &f_i(\boldsymbol{x}) \leqslant 0, i=1,2,\cdots,n \end{aligned}$$

拉格朗日函数为

$$L(\boldsymbol{x}, \boldsymbol{\lambda})=f_0(\boldsymbol{x}) + \sum_{i=1}^n\lambda_if_i(\boldsymbol{x})$$

有如下鞍点定理：

$\boldsymbol{x}^,\boldsymbol{\lambda}^$为$L(\boldsymbol{x},\boldsymbol{\lambda})$的鞍点，当且仅当强对偶成立，且$\boldsymbol{x}^,\boldsymbol{\lambda}^$为原问题和对偶问题的最优解。

证明：先证明必要性。若$\boldsymbol{x}^,\boldsymbol{\lambda}^$为$L(\boldsymbol{x},\boldsymbol{\lambda})$的鞍点，根据鞍点定义，有

$$\sup_{\boldsymbol{\lambda}\geqslant0}\inf_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\lambda}) = \inf_{\boldsymbol{x}}\sup_{\boldsymbol{\lambda}\geqslant0}L(\boldsymbol{x},\boldsymbol{\lambda})$$

且

$$\begin{aligned} \boldsymbol{x}^* &= \arg\inf_{\boldsymbol{x}}\sup_{\boldsymbol{\lambda}\geqslant0}L(\boldsymbol{x},\boldsymbol{\lambda}) \\ \boldsymbol{\lambda}^* &= \arg\sup_{\boldsymbol{\lambda}\geqslant0}\inf_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\lambda}) \end{aligned}$$

即$p^=d^$.且$\boldsymbol{x}^,\boldsymbol{\lambda}^$为原问题和对偶问题的最优解.

再证明充分性。首先由$\boldsymbol{x}^,\boldsymbol{\lambda}^$为原问题和对偶问题的最优解，则其必然可行，即有

$$\begin{aligned} f_i(\boldsymbol{x}^*) \leqslant 0, i=1,2,\dots,n \\ \lambda_i^* \geqslant 0,i=1,2,\dots,n \end{aligned}$$

由强对偶成立，即

$$\begin{aligned} f_0(\boldsymbol{x^*}) = d^* = p^* &= \inf_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\lambda}^*) \\ &=\inf_{\boldsymbol{x}}\left(f_0(\boldsymbol{x})+\sum_{i=1}^n\lambda_i^*f_i(\boldsymbol{x})\right) \\ &\leqslant f_0(\boldsymbol{x^*}) + \sum_{i=1}^n\lambda_i^*f_i(\boldsymbol{x}^*) \\ &\leqslant f_0(\boldsymbol{x}^*) \end{aligned}$$

因此，上面不等关系全部为等式关系，其中有

$$f_0(\boldsymbol{x}^*) = \inf_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\lambda}^*) = L(\boldsymbol{x}^*,\boldsymbol{\lambda}^*)$$

故

$$L(\boldsymbol{x}^*,\boldsymbol{\lambda}^*) \leqslant L(\boldsymbol{x},\boldsymbol{\lambda}^*)$$

另一方面，由

$$\sup_{\boldsymbol{\lambda}\geqslant0}L(\boldsymbol{x}^*,\boldsymbol{\lambda}) = \sup_{\boldsymbol{\lambda}\geqslant}\left( f_0(\boldsymbol{x^*})+\sum_{i=1}^n\lambda_if_i(\boldsymbol{x}^*) \right) \leqslant f_0(\boldsymbol{x}^*) = L(\boldsymbol{x}^*,\boldsymbol{\lambda}^*)$$

综上有

$$L(\boldsymbol{x}^*,\boldsymbol{\lambda}) \leqslant L(\boldsymbol{x}^*,\boldsymbol{\lambda}^*) \leqslant L(\boldsymbol{x},\boldsymbol{\lambda}^*)$$

优化算法与收敛速率

函数的强凸性与海塞矩阵上界

强凸性 函数$f$是强凸的，倘若$\exist m>0,s.t.\forall \boldsymbol{x},\nabla^2f(\boldsymbol{x})-mI \succeq 0$。也可以等价地表述为$\displaystyle\forall \boldsymbol{x}, \boldsymbol{y}, f(\boldsymbol{y})\geqslant f(\boldsymbol{x})+\nabla^Tf(\boldsymbol{x})(\boldsymbol{y}-\boldsymbol{x})+\frac{m}{2}\parallel \boldsymbol{y}-\boldsymbol{x} \parallel_2^2$.

我们进一步分析上式。对右侧式子关于$\boldsymbol{y}$求导得$\displaystyle \nabla f(\boldsymbol{x})+m(\boldsymbol{y}-\boldsymbol{x})$，令其等于零，有

$$\boldsymbol{y}^* = \boldsymbol{x} - \frac{\nabla f(\boldsymbol{x})}{m}$$

代回，有

$$\forall \boldsymbol{y},f(\boldsymbol{y}) \geqslant f(\boldsymbol{x}) - \frac{1}{2m}\parallel \nabla f(\boldsymbol{x}) \parallel_2^2$$

记最优解为$\boldsymbol{x}^*$，得到

$$p^* = f(\boldsymbol{x}^*) \geqslant f(\boldsymbol{x}) - \frac{1}{2m}\parallel \nabla f(\boldsymbol{x}) \parallel_2^2$$

整理得到

$$f(\boldsymbol{x}) - f(\boldsymbol{x}^*) \leqslant \frac{1}{2m}\parallel \nabla f(\boldsymbol{x}) \parallel_2^2$$

Hessian矩阵上界 $\exist M>0,s.t.\forall \boldsymbol{x}\in \mathrm{dom}f,\nabla^2f(\boldsymbol{x})-MI \preceq 0$.等价地表述为$\displaystyle\forall \boldsymbol{x},\boldsymbol{y}\in \mathrm{dom}f, f(\boldsymbol{y})\leqslant f(\boldsymbol{x}) + \nabla^Tf(\boldsymbol{x})(\boldsymbol{y} - \boldsymbol{x}) + \frac{M}{2}\parallel \boldsymbol{y}-\boldsymbol{x} \parallel_2^2$.

梯度下降法的收敛速率

赏