最優(yōu)化算法python實(shí)現(xiàn)篇（4）——無約束多維極值（梯度下降法）

• 摘要
• 算法簡介
• 注意事項
• 算法適用性
• python實(shí)現(xiàn)
• 實(shí)例運(yùn)行結(jié)果
• 算法過程可視化

摘要

本文介紹了多維無約束極值優(yōu)化算法中的梯度下降法，通過python進(jìn)行實(shí)現(xiàn)，并可視化展示了算法過程。

算法簡介

給定初始點(diǎn)，沿著負(fù)梯度方向（函數(shù)值下降最快的方向）按一定步長（機(jī)器學(xué)習(xí)中也叫學(xué)習(xí)率）進(jìn)行搜索，直到滿足算法終止條件，則停止搜索。

注意事項

學(xué)習(xí)率不能太小，也不能太大，可以多嘗試一些值。當(dāng)然每次沿著負(fù)梯度方向搜索時，總會存在一個步長使得該次搜索的函數(shù)值最低，也就是一個一維無約束極值問題，可調(diào)用黃金分割法的一維無約束優(yōu)化方法求取最佳步長（學(xué)習(xí)率）。

算法適用性

1、有可能會陷入局部小值。
2、適用于凸函數(shù)，由于線性回歸的損失函數(shù)（Loss Function）是凸函數(shù)，所以該算法的應(yīng)用之一就是解決線性回歸問題。

python實(shí)現(xiàn)

基本參數(shù)：
func:優(yōu)化的目標(biāo)函數(shù)
x0：初始化變量值
alpha：學(xué)習(xí)率，一般指定為（0-1），若不指定，則調(diào)取一維極值搜索法（黃金分割法）進(jìn)行求取最優(yōu)學(xué)習(xí)率值。黃金分割法代碼可參考我的博客：黃金分割法.
黃金分割法內(nèi)部嵌套了進(jìn)退法求取一個凸區(qū)間。進(jìn)退法代碼參考我的博客：進(jìn)退法.
epoch：最大迭代次數(shù)，若不指定默認(rèn)為1000
eps:精度，默認(rèn)為：1e-6

from sympy import * import numpy as np from mpl_toolkits.mplot3d import axes3d import matplotlib.pyplot as plt from matplotlib import cm class CyrusGradientDescent(object):"""func:優(yōu)化的目標(biāo)函數(shù)x0：初始化變量值alpha：學(xué)習(xí)率，一般指定為（0-1），若不指定，則調(diào)取一維極值搜索法（黃金分割法）進(jìn)行求取最優(yōu)學(xué)習(xí)率值黃金分割法代碼可參考我的博客：https://blog.csdn.net/Cyrus_May/article/details/105877363黃金分割法內(nèi)部嵌套了進(jìn)退法求取一個凸區(qū)間。進(jìn)退法代碼參考我的博客：https://blog.csdn.net/Cyrus_May/article/details/105821131epoch：最大迭代次數(shù)，若不指定默認(rèn)為1000eps:精度，默認(rèn)為：1e-6"""# 1、初始化輸入?yún)?shù)def __init__(self,func,x0,**kargs):self.var = [Symbol("x"+str(i+1)) for i in range(int(len(x0)))]func_input = "func(("for i in range(int(len(x0))):if i != int(len(x0))-1:func_input += "self.var[" + str(i) + "]" + ","else:func_input += "self.var[" + str(i) + "]" + "))"self.func = eval(func_input)self.x = np.array(x0).reshape(-1,1)if "alpha" in kargs.keys():self.alpha = kargs["alpha"]else:self.alpha = Noneif "epoch" in kargs.keys():self.epoch = kargs["epoch"]else:self.epoch = 1e3if "eps" in kargs.keys():self.eps = kargs["eps"]else:self.eps = 1e-6self.process = []self.process.append(self.x)# 2、定義計算函數(shù)值函數(shù)def cal_func_value(self,x):func = self.funcfor i in range(x.shape[0]):func = func.subs(self.var[i],x[i,0])return func# 3、定義計算雅克比矩陣，即梯度的函數(shù)def cal_gradient(self):f = Matrix([self.func])v = Matrix(self.var)gradient = f.jacobian(v)gradient_value = []for diff_func in list(gradient):for i in range(len(self.var)):diff_func = diff_func.subs(self.var[i],self.x[i,0])gradient_value.append(diff_func)return np.array(gradient_value).reshape(-1,1)# 4、定義 若未指定學(xué)習(xí)率α?xí)r，計算最優(yōu)學(xué)習(xí)率的函數(shù)def cal_alpha(self,gradient_value):if self.alpha != None:return self.alphaelse:def alpha_func(alpha):x = self.x - alpha*gradient_valuereturn self.cal_func_value(x)from minimize_golden import Minimize_Goldenreturn Minimize_Golden(func = alpha_func).run()[0] # 5、定義更新變量值的函數(shù)def update_x(self,alpha,gradient_value):self.x = self.x - alpha*gradient_valueself.process.append(self.x)# 6、定義可視化函數(shù)(當(dāng)目標(biāo)函數(shù)只有兩個自變量時才使用)def visual(self,x1,x2):X1,X2 = np.meshgrid(x1,x2)Z = np.ones(X1.shape)for i in range(X1.shape[0]):for j in range(X1.shape[1]):Z[i,j] = self.cal_func_value(np.array([X1[i,j],X2[i,j]]).reshape(-1,1))fig = plt.figure(figsize=(16,8))z = []x = []y = []for i in range(len(self.process)):z.append(self.cal_func_value(self.process[i]))x.append(self.process[i][0,0])y.append(self.process[i][1,0])ax = fig.add_subplot(1,1,1,projection = "3d")ax.plot_wireframe(X1,X2,Z,rcount = 20,ccount = 20)ax.plot(x,y,z,color = "r",marker = "*")# 7、統(tǒng)籌運(yùn)行def run(self):for i in range(int(self.epoch)):# 1、計算梯度gradient_value = self.cal_gradient()if (gradient_value == 0).all():return self.x,self.cal_func_value(self.x)# 2、計算學(xué)習(xí)率αalpha = self.cal_alpha(gradient_value)# 3、更新變量值x_old = self.xself.update_x(alpha,gradient_value)if np.abs(self.cal_func_value(x_old)-self.cal_func_value(self.x)) < self.eps:return self.x,self.cal_func_value(self.x)return self.x,self.cal_func_value(self.x)if __name__ == "__main__":def func(x):return x[0]**2+x[1]**2+100gd_model = CyrusGradientDescent(func = func,x0 = (-5,5),alpha = 0.1)x,y_min = gd_model.run()print("*"*10,"Gradient Descent Algorithm","*"*10)print("x:",x)print("y_min:",y_min)x1 = np.linspace(-5,5,100)x2 = np.linspace(-5,5,100)gd_model.visual(x1,x2)

實(shí)例運(yùn)行結(jié)果

********** Gradient Descent Algorithm ********** x: [[-0.000830767497365573][0.000830767497365573]] y_min: 100.000001380349

算法過程可視化

by CyrusMay 2020 05 08

直到文明又毀滅
一千世紀(jì)后的第一天
伊甸園里肩并肩
我們笑看太陽也熄滅

——五月天（一千個世紀(jì)）——

總結(jié)

以上是生活随笔為你收集整理的最优化算法python实现篇（4）——无约束多维极值（梯度下降法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。