目录
1. 高等数学(梯度与牛顿法)
1.1 梯度
1.2 雅各比矩阵(Jacobian矩阵)
1.3?海森矩阵(Hessian矩阵)
1.4?基于梯度的优化方法——牛顿法
2. 线性代数(范数)
2.1?向量范数
2.2?矩阵范数
3. 概率论(全概公式和逆概公式)
3.1?全概公式
3.2?逆概公式
4.?作业
4.1?问题1
1. 高等数学(梯度与牛顿法)
1.1 梯度
? ? ? ? 梯度是一个“向量”而非标量。因此梯度具有两个属性:方向和长度(模)。
? ? ? ? 梯度与方向导数具有很密切的联系。函数在某点的梯度,其方向意味着函数在该点的所有方向导数中沿着该方向可以取得最大值,而这个最大方向导数的值就是梯度的模。
? ? ? ? 更通俗些来讲,从函数变化的角度来看,函数在某点的梯度,其意味着函数在该点沿着此方向增长速度会最快,这个增长的变化率就是梯度的模。
1.2 雅各比矩阵(Jacobian矩阵)
? ? ? ? 假设有一个函数 ,该函数是一个从n维空间映射到m维空间的函数。也就是说,这个函数由m个实函数 组成,每个实函数都具有n个参数 。如果将这些函数对这些参数的一阶偏导数罗列在一起(假设它们都是存在的),就可以组成一个m*n的矩阵。这个矩阵就是雅各比矩阵。
![\LARGE J(F)=\begin{aligned}\left[\begin{array}{ccc} \frac{\partial y_{1}}{\partial x_{1}} & \cdots & \frac{\partial y_{1}}{\partial x_{n}} \\ \vdots & \ddots & \vdots \\ \frac{\partial y_{m}}{\partial x_{1}} & \cdots & \frac{\partial y_{m}}{\partial x_{n}} \end{array}\right]\end{aligned}](https://latex.codecogs.com/gif.latex?%5CLARGE%20J%28F%29%3D%5Cbegin%7Baligned%7D%5Cleft%5B%5Cbegin%7Barray%7D%7Bccc%7D%20%5Cfrac%7B%5Cpartial%20y_%7B1%7D%7D%7B%5Cpartial%20x_%7B1%7D%7D%20%26%20%5Ccdots%20%26%20%5Cfrac%7B%5Cpartial%20y_%7B1%7D%7D%7B%5Cpartial%20x_%7Bn%7D%7D%20%5C%5C%20%5Cvdots%20%26%20%5Cddots%20%26%20%5Cvdots%20%5C%5C%20%5Cfrac%7B%5Cpartial%20y_%7Bm%7D%7D%7B%5Cpartial%20x_%7B1%7D%7D%20%26%20%5Ccdots%20%26%20%5Cfrac%7B%5Cpartial%20y_%7Bm%7D%7D%7B%5Cpartial%20x_%7Bn%7D%7D%20%5Cend%7Barray%7D%5Cright%5D%5Cend%7Baligned%7D)
? ? ? ? ?因此,梯度属于雅各比矩阵的一种简单情况
1.3?海森矩阵(Hessian矩阵)
? ? ? ? 假设有一个实函数 ,其如果将该函数对所有参数的二阶偏导数都罗列在一起(假设它们都是存在的),就可以组成一个n*n的矩阵。这个矩阵就是海森矩阵。
![\LARGE H(f)=\left[\begin{array}{cccc} \frac{\partial^{2} f}{\partial x_{1}^{2}} & \frac{\partial^{2} f}{\partial x_{1} \partial x_{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{1} \partial x_{n}} \\ \frac{\partial^{2} f}{\partial x_{2} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{2}^{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{2} \partial x_{n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^{2} f}{\partial x_{n} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{n} \partial x_{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{n}^{2}} \end{array}\right]](https://latex.codecogs.com/gif.latex?%5CLARGE%20H%28f%29%3D%5Cleft%5B%5Cbegin%7Barray%7D%7Bcccc%7D%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7B1%7D%5E%7B2%7D%7D%20%26%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7B1%7D%20%5Cpartial%20x_%7B2%7D%7D%20%26%20%5Ccdots%20%26%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7B1%7D%20%5Cpartial%20x_%7Bn%7D%7D%20%5C%5C%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7B2%7D%20%5Cpartial%20x_%7B1%7D%7D%20%26%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7B2%7D%5E%7B2%7D%7D%20%26%20%5Ccdots%20%26%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7B2%7D%20%5Cpartial%20x_%7Bn%7D%7D%20%5C%5C%20%5Cvdots%20%26%20%5Cvdots%20%26%20%5Cddots%20%26%20%5Cvdots%20%5C%5C%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7Bn%7D%20%5Cpartial%20x_%7B1%7D%7D%20%26%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7Bn%7D%20%5Cpartial%20x_%7B2%7D%7D%20%26%20%5Ccdots%20%26%20%5Cfrac%7B%5Cpartial%5E%7B2%7D%20f%7D%7B%5Cpartial%20x_%7Bn%7D%5E%7B2%7D%7D%20%5Cend%7Barray%7D%5Cright%5D)
? ? ? ? 海森矩阵可以用来描述函数的局部曲率。
1.4?基于梯度的优化方法——牛顿法
? ? ? ? 牛顿法是求解函数零点的方法。利用牛顿法求解目标函数的最小值实际上指的是利用牛顿法求解目标函数一阶导数的零点。因为函数极值点处一阶导数为0。
? ? ? ? 牛顿法是一个以随即位置开始,不断迭代得到新位置,直到新位置与零点位置重合时停止的方法。更具体来说,假设目标函数的导数是一个一元函数 ,我们先在横坐标上随机选取一个位置 ,计算 处切线与x轴的交点的横坐标 。然后以 为新位置重复该过程,直到切点与零点重合为止。
![](https://img-blog.csdnimg.cn/20210817135143717.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1plZV9DaGFv,size_16,color_FFFFFF,t_70)
? ? ? ? ?假设目标函数为 ,则牛顿法的迭代公式如下:
![\theta:=\theta- \frac{L^{\prime}(\theta)}{L^{\prime\prime}(\theta)}](https://latex.codecogs.com/gif.latex?%5Ctheta%3A%3D%5Ctheta-%20%5Cfrac%7BL%5E%7B%5Cprime%7D%28%5Ctheta%29%7D%7BL%5E%7B%5Cprime%5Cprime%7D%28%5Ctheta%29%7D)
? ? ? ? 如果 是一个向量,则牛顿法的迭代公式还可以表示为:
![\theta:=\theta- H^{-1}J^{T}](https://latex.codecogs.com/gif.latex?%5Ctheta%3A%3D%5Ctheta-%20H%5E%7B-1%7DJ%5E%7BT%7D)
? ? ? ? 其中 和 就是 对应的海森矩阵和雅各比矩阵。
? ? ? ? 牛顿法在优化目标函数时具有以下优势:
? ? ? ? 1.?收敛速度快,比梯度下降要快很多;
? ? ? ? 2.?海森矩阵的逆在迭代工程中会不断变小,可以起到逐步减小步长的效果;
? ? ? ? 牛顿法的缺点如下:
? ? ? ? 1.?目标函数必须二阶可导;
? ? ? ? 2.?初始点需要足够“靠近”极小点,否则,有可能导致算法不收敛。因为牛顿法是不能控制方向的,有可能会向错误的方向优化。因此有了阻尼牛顿法,简单来说就是引入的一个阻尼系数以控制步长,即
![\theta:=\theta-\lambda H^{-1}J^{T}](https://latex.codecogs.com/gif.latex?%5Ctheta%3A%3D%5Ctheta-%5Clambda%20H%5E%7B-1%7DJ%5E%7BT%7D)
? ? ? ?不过这个阻尼系数不一定是固定的,也需要计算。这里不做介绍。
????????3.?海森矩阵的逆求解复杂。因此有了拟牛顿法。
2. 线性代数(范数)
2.1?向量范数
? ? ? ? 假设向量 ,则:
? ? ? ? 1-范数
![\|\vec{x}\|_{1}=\sum_{i=1}^{m}\left|x_{i}\right|](https://latex.codecogs.com/gif.latex?%5C%7C%5Cvec%7Bx%7D%5C%7C_%7B1%7D%3D%5Csum_%7Bi%3D1%7D%5E%7Bm%7D%5Cleft%7Cx_%7Bi%7D%5Cright%7C)
? ? ? ? n-范数(n>1)
![\|\vec{x}\|_{n}=\sqrt[n]{\sum_{i=1}^{m}x_{i}^{n}}](https://latex.codecogs.com/gif.latex?%5C%7C%5Cvec%7Bx%7D%5C%7C_%7Bn%7D%3D%5Csqrt%5Bn%5D%7B%5Csum_%7Bi%3D1%7D%5E%7Bm%7Dx_%7Bi%7D%5E%7Bn%7D%7D)
? ? ? ? -范数
![\|\vec{x}\|_{\infty}=\max _{1 \leq i \leq n}\left|x_{i}\right|](https://latex.codecogs.com/gif.latex?%5C%7C%5Cvec%7Bx%7D%5C%7C_%7B%5Cinfty%7D%3D%5Cmax%20_%7B1%20%5Cleq%20i%20%5Cleq%20n%7D%5Cleft%7Cx_%7Bi%7D%5Cright%7C)
2.2?矩阵范数
? ? ? ? 1-范数(列范数,实际是每个列绝对值最大的元素的和)
![\|A\|_{1}=\max _{1 \leq j \leq n} \sum_{i=1}^{n}\left|a_{i, j}\right|](https://latex.codecogs.com/gif.latex?%5C%7CA%5C%7C_%7B1%7D%3D%5Cmax%20_%7B1%20%5Cleq%20j%20%5Cleq%20n%7D%20%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%5Cleft%7Ca_%7Bi%2C%20j%7D%5Cright%7C)
? ? ? ? 2-范数(谱范数,实际是矩阵 的最大特征值)
![\|A\|_{2}=\sqrt{\lambda_{1}}](https://latex.codecogs.com/gif.latex?%5C%7CA%5C%7C_%7B2%7D%3D%5Csqrt%7B%5Clambda_%7B1%7D%7D)
???????? -范数(行范数,实际是每个行绝对值最大的元素的和)
![\|A\|_{\infty}=\max _{1 \leq i \leq n} \sum_{j=1}^{n}\left|a_{i, j}\right|](https://latex.codecogs.com/gif.latex?%5C%7CA%5C%7C_%7B%5Cinfty%7D%3D%5Cmax%20_%7B1%20%5Cleq%20i%20%5Cleq%20n%7D%20%5Csum_%7Bj%3D1%7D%5E%7Bn%7D%5Cleft%7Ca_%7Bi%2C%20j%7D%5Cright%7C)
3. 概率论(全概公式和逆概公式)
3.1?全概公式
? ? ? ? 如果事件 是一个完备事件组,则:
![\begin{gathered} P(B)=P\left(A_{1}\right) P\left(B \mid A_{1}\right)+P\left(A_{2}\right) P\left(B \mid A_{2}\right)+\cdots+P\left(A_{n}\right) P\left(B \mid A_{n}\right) \\ =\sum_{i=1}^{n} P\left(A_{i}\right) P\left(B \mid A_{i}\right) \end{gathered}](https://latex.codecogs.com/gif.latex?%5Cbegin%7Bgathered%7D%20P%28B%29%3DP%5Cleft%28A_%7B1%7D%5Cright%29%20P%5Cleft%28B%20%5Cmid%20A_%7B1%7D%5Cright%29+P%5Cleft%28A_%7B2%7D%5Cright%29%20P%5Cleft%28B%20%5Cmid%20A_%7B2%7D%5Cright%29+%5Ccdots+P%5Cleft%28A_%7Bn%7D%5Cright%29%20P%5Cleft%28B%20%5Cmid%20A_%7Bn%7D%5Cright%29%20%5C%5C%20%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20P%5Cleft%28A_%7Bi%7D%5Cright%29%20P%5Cleft%28B%20%5Cmid%20A_%7Bi%7D%5Cright%29%20%5Cend%7Bgathered%7D)
3.2?逆概公式
????????如果事件 是一个完备事件组,则对任意事件 ,有:
![P\left(A_{i} \mid B\right)=\frac{P\left(A_{i} B\right)}{P(B)}=\frac{P\left(A_{i}\right) P\left(B \mid A_{i}\right)}{\sum_{i=1}^{n} P\left(A_{i}\right) P\left(B \mid A_{i}\right)}](https://latex.codecogs.com/gif.latex?P%5Cleft%28A_%7Bi%7D%20%5Cmid%20B%5Cright%29%3D%5Cfrac%7BP%5Cleft%28A_%7Bi%7D%20B%5Cright%29%7D%7BP%28B%29%7D%3D%5Cfrac%7BP%5Cleft%28A_%7Bi%7D%5Cright%29%20P%5Cleft%28B%20%5Cmid%20A_%7Bi%7D%5Cright%29%7D%7B%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20P%5Cleft%28A_%7Bi%7D%5Cright%29%20P%5Cleft%28B%20%5Cmid%20A_%7Bi%7D%5Cright%29%7D)
4.?作业
4.1?问题1
? ? ? ? 在数学最优化中,Rosenbrock函数是一个用来测试最优化算法性能的非凸函数,由Howard Harry Rosenbrock在1960年提出 。也称为Rosenbrock山谷或Rosenbrock香蕉函数。已知Rosenbrock函数的表达式为
![f(x)=(a-x_{1})^{2}+b(x_{2}-x_{1})^{2}](https://latex.codecogs.com/gif.latex?f%28x%29%3D%28a-x_%7B1%7D%29%5E%7B2%7D+b%28x_%7B2%7D-x_%7B1%7D%29%5E%7B2%7D)
请编程完成以下工作:
(1)为a和b取不同的值,绘制3D表面。观察a和b的不同取值对曲面形状的影响
(2)编写算法找到全局最小值以及相应的最小解,并在3D图像中标出。分析算法的时空效率,给出运行时间
全局最小值(x, y, z)和运行时间
| ![b=-100](https://latex.codecogs.com/gif.latex?b%3D-100) | ![b=0](https://latex.codecogs.com/gif.latex?b%3D0) | ![b=100](https://latex.codecogs.com/gif.latex?b%3D100) | ![a=-1](https://latex.codecogs.com/gif.latex?a%3D-1) | (1, 1, 0) 2.41s | (1, 1, 0) 2.56s | (1, 1, 0) 2.54s | ![a=0](https://latex.codecogs.com/gif.latex?a%3D0) | (1, 1, 0) 2.63s | (1, 1, 0) 3.15s | (1, 1, 0) 2.40s | ![a=1](https://latex.codecogs.com/gif.latex?a%3D1) | (1, 1, 0) 2.49s | (1, 1, 0) 2.47s | (1, 1, 0) 2.46s |
? ? ? ? 对教案中的代码做了一些修改,自动生成所有不同取值的图像和结果
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import time
%matplotlib inline
from mpl_toolkits.mplot3d import Axes3D
import itertools
class Rosenbrock():
def __init__(self, a, b):
self.x1 = np.arange(-100, 100, 0.0001)
self.x2 = np.arange(-100, 100, 0.0001)
#self.x1, self.x2 = np.meshgrid(self.x1, self.x2)
self.a = a
self.b = b
self.newton_times = 1000
self.answers = []
self.min_answer_z = []
# 准备数据
def data(self):
z = np.square(self.a - self.x1) + self.b * np.square(self.x2 - np.square(self.x1))
#print(z.shape)
return z
# 随机牛顿
def snt(self,x1,x2,z,alpha):
rand_init = np.random.randint(0,z.shape[0])
x1_init,x2_init,z_init = x1[rand_init],x2[rand_init],z[rand_init]
x_0 =np.array([x1_init,x2_init]).reshape((-1,1))
#print(x_0)
for i in range(self.newton_times):
x_i = x_0 - np.matmul(np.linalg.inv(np.array([[12*x2_init**2-4*x2_init+2,-4*x1_init],[-4*x1_init,2]])),np.array([4*x1_init**3-4*x1_init*x2_init+2*x1_init-2,-2*x1_init**2+2*x2_init]).reshape((-1,1)))
x_0 = x_i
x1_init = x_0[0,0]
x2_init = x_0[1,0]
answer = x_0
return answer
# 绘图
def plot_data(self,min_x1,min_x2,min_z):
x1 = np.arange(-100, 100, 0.1)
x2 = np.arange(-100, 100, 0.1)
x1, x2 = np.meshgrid(x1, x2)
a = self.a
b = self.b
z = np.square(a - x1) + b * np.square(x2 - np.square(x1))
fig4 = plt.figure()
ax4 = plt.axes(projection='3d')
ax4.plot_surface(x1, x2, z, alpha=0.3, cmap='winter') # 生成表面, alpha 用于控制透明度
ax4.contour(x1, x2, z, zdir='z', offset=-3, cmap="rainbow") # 生成z方向投影,投到x-y平面
ax4.contour(x1, x2, z, zdir='x', offset=-6, cmap="rainbow") # 生成x方向投影,投到y-z平面
ax4.contour(x1, x2, z, zdir='y', offset=6, cmap="rainbow") # 生成y方向投影,投到x-z平面
ax4.contourf(x1, x2, z, zdir='y', offset=6, cmap="rainbow") # 生成y方向投影填充,投到x-z平面,contourf()函数
ax4.scatter(min_x1,min_x2,min_z,c='r')
# 设定显示范围
ax4.set_xlabel('X')
ax4.set_ylabel('Y')
ax4.set_zlabel('Z')
plt.title('a = %d, b = %d' % (self.a, self.b))
plt.show()
plt.close()
# 开始
def start(self):
# times = int(input("请输入需要随机优化的次数:"))
# alpha = float(input("请输入随机优化的步长"))
times = 100
alpha = 0.02
z = self.data()
start_time = time.time()
for i in range(times):
answer = self.snt(self.x1,self.x2,z,alpha)
self.answers.append(answer)
min_answer = np.array(self.answers)
# print(min_answer)
for i in range(times):
self.min_answer_z.append((1-min_answer[i,0,0])**2+(min_answer[i,1,0]-min_answer[i,0,0]**2)**2)
optimal_z = np.min(np.array(self.min_answer_z))
optimal_z_index = np.argmin(np.array(self.min_answer_z))
optimal_x1,optimal_x2 = min_answer[optimal_z_index,0,0],min_answer[optimal_z_index,1,0]
print(optimal_x1, optimal_x2, optimal_z)
end_time = time.time()
running_time = end_time-start_time
print("优化的时间:%.2f秒!" % running_time)
self.plot_data(optimal_x1,optimal_x2,optimal_z)
if __name__ == '__main__':
parameter_a = [-1, 0, 1];
parameter_b = [-100, 0, 100];
for a, b in itertools.product(parameter_a, parameter_b):
print(a, b)
snt = Rosenbrock(a, b)
snt.start()
|