（最优化理论与方法）第二章最优化所需基础知识-第六节1：凸函数前置基础知识

一：梯度

梯度：给定函数$f:{\mathbb{R}}^n\to \mathbb{R}$，且$f$在点$x$的一个领域内有意义，若存在向量$g\in R^n$满足

$$\underset{p\to 0}{\lim }\frac{f(x+p)-f(x)-g^{T}p}{||p||}=0$$

• $||.||$是任意的向量范数

就称$f$在$x$处可微（Frechet可微）。此时$g$称为$f$在点$x$处的梯度，记作$\nabla f(x)$。如果对区域$D$上每一个点$x$都有$\nabla f(x)$存在，则称$f$在$D$上可微

若$f$在点$x$处的梯度存在，在定义式中令$p=\xi e_i$，$e_i$是第$i$个分量为1的单位向量，可知$\nabla f(x)$的第$i$个分量为$\frac{\partial f(x)}{\partial x_i}$，因此

$$\nabla f(x)=(\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},...,\frac{\partial f(x)}{\partial x_n}{)}^T$$

例如$f(x,y)=\frac{1}{x^2+y^2}$，则$\nabla \frac{1}{x^2+y^2}=-\frac{2x}{(x^2+y^2{)}^2}i-\frac{2y}{(x^2+y^2{)}^2}j$

二：海瑟矩阵

海瑟矩阵：如果函数$f(x):{\mathbb{R}}^n\to \mathbb{R}$在$x$处的二阶偏导数$\frac{{\partial }^{2}f(x)}{\partial x_i\partial x_j}(i,j=1,2,...,n)$都存在，则$f$在点$x$处的海瑟矩阵为

• 当${\nabla }^{2}f(x)$在区域$D$上的每个点$x$处都存在时，则称$f$在$D$上二阶可微
• 当${\nabla }^{2}f(x)$在区域$D$上还连续，则称$f$在$D$上二阶连续可微，可以证明此时海瑟矩阵为对称矩阵

补充：Python中计算梯度和海瑟矩阵计算

• 有关梯度、散度、旋度等计算可借助sympy库进行

import numpy as np
from sympy import *

# 导数的计算
x, f1 = symbols('x f1')  # 符号化
f1 = ln(x) + sin(1/x)
print('ln(x) + sin(1/x)的导数为：', f1.diff(x))
print("-"*30)

# 梯度的计算
x1, x2, x3, f2 = symbols('x1, x2, x3, f2')  # 符号化
f2 = 3*x1**2 + 2*x1*x2 + 2*x2*x3 + x3**2
list1 = []
list1.append(diff(f2, x1))
list1.append(diff(f2, x2))
list1.append(diff(f2, x3))
list1 = np.array(list1)
print('3*x1**2 + 2*x1*x2 + 2*x2*x3 + x3**2的梯度为：', list1)
print("-"*30)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

来一个复杂点的例子，计算$f(x)=ln(e^{x1}+e^{x2}+e^3)$的$\nabla f(x)$和${\nabla }^{2}f(x)$

# 梯度的计算
x1, x2, x3, f1 = symbols('x1, x2, x3, f1')  # 符号化
f1 = ln(exp(x1) + exp(x2) + exp(x3))
print(f1)
list1 = []
list1.append(diff(f1, x1))
list1.append(diff(f1, x2))
list1.append(diff(f1, x3))
list1 = np.array(list1)
print('ln(exp(x1) + exp(x2) + exp(x3))的梯度为：', list1)
print("-"*30)


# 海瑟矩阵的计算(利用定义计算)
vars = symbols('x1 x2, x3')
f2 = sympify(['ln(exp(x1) + exp(x2) + exp(x3))'])
H = zeros(len(vars), len(vars))
for i, fi in enumerate(f2):
    for j, r in enumerate(vars):
        for k, s in enumerate(vars):
            H[j, k] = diff(diff(fi, r), s)

H = np.array(H)
print('ln(exp(x1) + exp(x2) + exp(x3))的海瑟矩阵为：')


for i in range(3):
    for j in range(3):
        print(H[i][j])
    print()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

$\nabla f(x)=[\frac{e^{x1}}{e^{x1}+e^{x2}+e^{x3}},\frac{e^{x2}}{e^{x1}+e^{x2}+e^{x3}},\frac{e^{x3}}{e^{x1}+e^{x2}+e^{x3}}]$

${\nabla }^{2}f(x)=\left(\begin{array}{ccc}\frac{e^{x1}}{e^{x1}+e^{x2}+e^{x3}}-\frac{e^{2x1}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}& \frac{-e^{x1}\ast e^{x2}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}& \frac{-e^{x1}\ast e^{x3}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}\\ \frac{-e^{x1}\ast e^{x2}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}& \frac{e^{x2}}{e^{x1}+e^{x2}+e^{x3}}-\frac{e^{2x2}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}& \frac{-e^{x2}\ast e^{x3}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}\\ \frac{-e^{x1}\ast e^{x3}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}& \frac{-e^{x2}\ast e^{x3}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}& \frac{e^{x3}}{e^{x1}+e^{x2}+e^{x3}}-\frac{e^{2x3}}{(e^{x1}+e^{x2}+e^{x3}{)}^2}\end{array}\right)$

三：矩阵变量函数的导数

多元函数梯度的定义可以推广到变量是矩阵的情形。对于以$m\times n$矩阵$X$为自变量的函数$f(X)$，若存在矩阵$G\in {\mathbb{R}}^{m\times n}$满足

$$\underset{V\to 0}{\lim }\frac{f(X+V)-f(X)-<G,V>}{||V||}=0$$

• $||.||$是任意矩阵范数

就称矩阵变量函数$f$在$X$处Frechet可微，称$G$$f$在Frechet可微意义下的梯度，如果令$\frac{\partial f}{\partial x_{ij}}$表示$f$关于$x_{ij}$的偏导数，则矩阵变量函数$f(X)$的梯度为

（1）Gateaux可微

但是在实际应用中，矩阵rechet可微的定义和使用往往比较繁琐为此我们需要介绍另外一种定义——Gateaux可微

Gateaux可微：设$f(X)$为矩阵变量函数，如果对任意方向$V\in R^{m\times n}$，存在矩阵$G\in R^{m\times n}$满足

$$\underset{t\to 0}{\lim }\frac{f(X+tV)-f(X)-<G,V>}{||t||}=0$$

则称$f$关于$X$是Gateaux可微的，满足上式的$G$称为$f$在X处在Gateaxu可微意义下的梯度

• 可以证明，当$f$是Frechet可微函数时，$f$也是Gateaux可微的，且这两种意义下的梯度相等

（2）举例

线性函数：$f(X)=tr(A{X}^{T}B)$，其中$A\in {\mathbb{R}}^{p\times n}$，$B\in {\mathbb{R}}^{m\times p}$，$X\in {\mathbb{R}}^{m\times n}$。对任意方向$V\in R^{m\times n}$以及$t\in \mathbb{R}$，有

$$\underset{t\to 0}{\lim }\frac{f(X+tV)-f(X)}{t}=\underset{t\to 0}{\lim }\frac{tr(A(X+tV{)}^{T}B)-tr(A{X}^{T}B)}{t}=tr(A{V}^{T}B)=<BA,V>$$

因此，$\nabla f(X)=BA$

二次函数：$f(X,Y)=\frac{1}{2}||XY-A|{|}_F^2$，其中$(X,Y)\in {\mathbb{R}}^{m\times p}\times {\mathbb{R}}^{p\times n}$对变量$Y$，取任意方向$V$以及充分小的$t\in \mathbb{R}$，有

$$f(X,Y+tV)-f(X,Y)=t<V,X^T(XY-A)>+O(t^2)$$

由定义可知$\frac{\partial f}{\partial Y}=X^T(XY-A)$，对变量$X$，同理有$\frac{\partial f}{\partial X}=(XY-A)Y^T$

ln-det函数：$f(X)=ln(det(X))$,$X\in S_{++}^n$，给定$X⪰0$，对任意方向$V\in S^n$以及$t\in \mathbb{R}$。所以$\nabla f(X)=(X^{-1}{)}^T$

四：广义实值函数和适当函数

广义实值函数：令 R ˉ = R ∪ { ± ∞ } \bar{\R}=R\cup \{\pm \infty\} Rˉ=R∪{±∞}为广义实数空间，则映射$f：{\mathbb{R}}^n\to \bar{\mathbb{R}}$称为广义实值函数

适当函数：给定广义实值函数$f$和非空集合$\chi$。如果存在$x\in \chi$使得$f(x)<+\infty$，并且对任意的$x\in \chi$，都有$f(x)>-\infty$，那么称函数$f$关于集合$\chi$是适当的

• 适当函数$f$的特点是至少有一处取出不为正无穷和处处取值不为负无穷

五：下水平集、上方图和闭函数

下水平集：对于广义实值函数$f：{\mathbb{R}}^n\to \bar{\mathbb{R}}$，把

C α = { x ∣ f ( x ) ≤ α } C_{\alpha}=\{x|f(x)\leq \alpha\} Cα​={x∣f(x)≤α}

称为$f$的$\alpha$-下水平集

上方图：对于广义实值函数$f：{\mathbb{R}}^n\to \bar{\mathbb{R}}$，把

$$epif=\{(x,t)\in R^{n+1}|f(x)\le t\}$$

称为$f$的上方图

闭函数：对于广义实值函数$f：{\mathbb{R}}^n\to \bar{\mathbb{R}}$，若$epif$为闭集，则称$f$为闭函数

六：闭函数与下半连续函数

（1）下半连续函数

下半连续函数：设广义实值函数$f：{\mathbb{R}}^n\to \bar{\mathbb{R}}$，若对任意的$x\in R^n$，有

$$\underset{y\to x}{\mathrm{liminf}}f(y)\ge f(x)$$

则$f(x)$称为下半连续函数

（2）闭函数与下半连续函数

闭函数与下半连续函数：虽然表明上看这两种函数的定义方式截然不同，但闭函数与下半连续函数是等价的。设广义实值函数$f：{\mathbb{R}}^n\to \bar{\mathbb{R}}$，则以下命题等价

• $f(x)$的任意$\alpha$-下水平集都是闭集
• $f(x)$是下半连续的
• $f(x)$是闭函数

闭（下半连续）函数间的简单运算会保持原有性质

• 加法：若$f$与$g$均为适当的闭（下半连续）函数，并且dom $f\cap$ dom$g$ $\ne \varnothing$，则$f+g$也是闭（下半连续）函数。其中适当函数的条件是为了避免出现未定式$(-\infty )+(+\infty )$的情况
• 仿射映射的复合：若$f$为闭（下半连续）函数，则$f(Ax+b)$也为闭（下半连续）函数
• 取上确界：若每一个函数$f_{\alpha }$均为闭（下半连续）函数，则$su{p}_{\alpha }{f}_{\alpha }(x)$也为闭（下半连续）函数