《Python人工智能》第4章-最優(yōu)化方法

第四章最優(yōu)化方法最優(yōu)化方法的概念最優(yōu)化就是在有限種或者無(wú)限種可能的方案中選擇一個(gè)最好的方案，以達(dá)到最優(yōu)目標(biāo)。它是數(shù)學(xué)的一個(gè)重要分支。在日常生活和許多學(xué)科中，總會(huì)遇到最優(yōu)化問(wèn)題。人們?cè)谧鋈魏我患虑闀r(shí)，總是希望在可能（現(xiàn)有）的條件下，從眾多可能方案中選擇一個(gè)方案，使事情的結(jié)果與自己的期望值最為符合。如交通運(yùn)輸中路徑的選擇、投資理財(cái)中收益的多少以及調(diào)度生產(chǎn)中時(shí)間的長(zhǎng)短等問(wèn)題。總是期望以最小的代價(jià)取得最大的收益。如何達(dá)到此效果，而這個(gè)選擇最優(yōu)方案的行為或過(guò)程就是一個(gè)最優(yōu)化的過(guò)程，從而形成了最優(yōu)化與最優(yōu)控制理論與方法產(chǎn)生的基礎(chǔ)。4.1最優(yōu)化方法基礎(chǔ)最優(yōu)化問(wèn)題數(shù)學(xué)模型的一般形式為：

4.1.1最優(yōu)化問(wèn)題數(shù)學(xué)模型4.1最優(yōu)化方法基礎(chǔ)最優(yōu)化問(wèn)題的數(shù)學(xué)模型包含三個(gè)要素：變量、目標(biāo)函數(shù)、約束條件。1.變量：最優(yōu)化問(wèn)題中待確定的某些量一個(gè)優(yōu)化問(wèn)題的優(yōu)化解是由一組參數(shù)的最優(yōu)組合來(lái)表示的。這些設(shè)計(jì)參數(shù)可以概括的劃分為兩類：一個(gè)是可以根據(jù)客觀規(guī)律、具體條件、已有的數(shù)據(jù)等預(yù)先給定的參數(shù)，統(tǒng)稱為常量；另一類是在優(yōu)化過(guò)程中經(jīng)過(guò)逐步調(diào)整，最后達(dá)到最優(yōu)值的獨(dú)立參數(shù)，稱為變量。優(yōu)化問(wèn)題的目的就是使各變量達(dá)到最優(yōu)化組合。變量的個(gè)數(shù)稱為優(yōu)化問(wèn)題的維數(shù)。例如有個(gè)變量的優(yōu)化問(wèn)題就是在維空間中尋找最優(yōu)解。當(dāng)變量是連續(xù)量時(shí)，稱為連續(xù)變量；若變量只能離散取值，稱為離散變量。

4.1.1最優(yōu)化問(wèn)題數(shù)學(xué)模型4.1最優(yōu)化方法基礎(chǔ)2.目標(biāo)函數(shù)目標(biāo)函數(shù)值的大小是用來(lái)評(píng)價(jià)優(yōu)化方案的好壞。按照規(guī)范化的形式，一般把優(yōu)化問(wèn)題歸結(jié)為求目標(biāo)函數(shù)的極小化問(wèn)題，即目標(biāo)函數(shù)值越小，優(yōu)化方案越好。對(duì)于某些目標(biāo)函數(shù)值的最大化問(wèn)題，可以轉(zhuǎn)化成求其負(fù)值的最小化問(wèn)題。即

4.1.1最優(yōu)化問(wèn)題數(shù)學(xué)模型假如優(yōu)化問(wèn)題只有一個(gè)目標(biāo)函數(shù)，稱為單目標(biāo)優(yōu)化，若優(yōu)化問(wèn)題同時(shí)追求多個(gè)目標(biāo)，則該問(wèn)題為多目標(biāo)優(yōu)化。4.1最優(yōu)化方法基礎(chǔ)3.約束條件變量本身應(yīng)該遵循的限制條件的數(shù)學(xué)表達(dá)式稱為約束條件或約束函數(shù)。約束條件按其表達(dá)式分為等式約束和不等式約束兩種，即

4.1.1最優(yōu)化問(wèn)題數(shù)學(xué)模型不帶約束條件的優(yōu)化問(wèn)題稱為無(wú)約束最優(yōu)化問(wèn)題；帶約束條件的優(yōu)化問(wèn)題稱為約束最優(yōu)化問(wèn)題。4.1最優(yōu)化方法基礎(chǔ)根據(jù)不同的標(biāo)準(zhǔn)，從不同角度對(duì)優(yōu)化問(wèn)題進(jìn)行分類。幾種常見(jiàn)的分類如下：一、函數(shù)優(yōu)化和組合優(yōu)化根據(jù)決策變量是連續(xù)取值還是僅取一些離散值，將最優(yōu)化問(wèn)題可以分為函數(shù)優(yōu)化問(wèn)題和組合優(yōu)化問(wèn)題兩大類。其中函數(shù)優(yōu)化的對(duì)象是一定區(qū)間的連續(xù)變量，而組合優(yōu)化的對(duì)象則是解空間中的離散狀態(tài)。4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例鑒于許多工程問(wèn)題存在約束條件，受約束函數(shù)的優(yōu)化問(wèn)題也一直是優(yōu)化領(lǐng)域關(guān)注的主要對(duì)象。但是對(duì)于受約束問(wèn)題，除了局部極小解的存在，影響最優(yōu)化性能的因素很多，因此對(duì)函數(shù)優(yōu)化的討論通常以無(wú)約束問(wèn)題為主。4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例2.組合優(yōu)化問(wèn)題組合優(yōu)化問(wèn)題是通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)排序、分類或篩選等，所研究的問(wèn)題涉及信息技術(shù)、經(jīng)濟(jì)管理、土木工程、交通運(yùn)輸、生產(chǎn)調(diào)度等諸多領(lǐng)域。該問(wèn)題的數(shù)學(xué)模型可表示為：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例典型的組合優(yōu)化問(wèn)題有旅行商(Travelingsalesmanproblem,TSP)問(wèn)題、生產(chǎn)調(diào)度問(wèn)題(Schedulingproblem,如Flowshop,Jobshop)、0-1背包問(wèn)題(Knapsackproblem)、裝箱問(wèn)題(Binpackingproblem)、圖著色問(wèn)題(Graphcoloringproblem)、聚類問(wèn)題(Clusteringproblem)等。4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例2.組合優(yōu)化問(wèn)題組合優(yōu)化問(wèn)題是通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)排序、分類或篩選等，所研究的問(wèn)題涉及信息技術(shù)、經(jīng)濟(jì)管理、土木工程、交通運(yùn)輸、生產(chǎn)調(diào)度等諸多領(lǐng)域。該問(wèn)題的數(shù)學(xué)模型可表示為：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例數(shù)學(xué)模型描述如下：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例數(shù)學(xué)模型描述如下：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例二、線性優(yōu)化和非線性優(yōu)化目標(biāo)函數(shù)或者約束函數(shù)中存在非線性的函數(shù)，則此問(wèn)題稱為非線性優(yōu)化，否則為線性優(yōu)化。1.線性優(yōu)化在一組線性的等式或不等式約束下，求一個(gè)線性函數(shù)的最小值。問(wèn)題數(shù)學(xué)模型如下：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例2.非線性優(yōu)化如果線性優(yōu)化的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達(dá)到（特別是可行域的頂點(diǎn)上達(dá)到）；而非線性優(yōu)化的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點(diǎn)達(dá)到。4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例總的來(lái)說(shuō)就是讓投資總額最小，投資總收益最大，即4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例三、無(wú)約束最優(yōu)化與有約束最優(yōu)化如果除了目標(biāo)函數(shù)外，對(duì)參與優(yōu)化的各變量沒(méi)有其他函數(shù)或者變量的約束，則稱為無(wú)約束最優(yōu)化問(wèn)題，反之則是有約束最優(yōu)化問(wèn)題。實(shí)際的最優(yōu)化問(wèn)題一般除了目標(biāo)函數(shù)外都有其他約束條件，因此多為約束優(yōu)化問(wèn)題。1.無(wú)約束優(yōu)化問(wèn)題無(wú)約束優(yōu)化問(wèn)題的一般形式為：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例Sylvester問(wèn)題：設(shè)平面上有m個(gè)點(diǎn)，找覆蓋這m個(gè)點(diǎn)的最小圓盤。4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問(wèn)題的分類及應(yīng)用案例2.有約束優(yōu)化問(wèn)題約束優(yōu)化問(wèn)題的約束條件一般分為等式約束和不等式約束。約束優(yōu)化問(wèn)題通常寫(xiě)為4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)1.導(dǎo)數(shù)在許多實(shí)際問(wèn)題中，不僅要研究變量之間的函數(shù)關(guān)系，還需要討論變量與變量之間相對(duì)的變化情況，這種變化情況可以通過(guò)導(dǎo)數(shù)描述。4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)

2.偏導(dǎo)數(shù)、梯度4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)3.Hessian矩陣4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)3.Hessian矩陣4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)4.Taylor展式多元函數(shù)的Taylor展式在最優(yōu)化方法中十分重要，許多方法及其收斂性的證明都是從它出發(fā)的，這里給出Taylor展式定理及其證明。4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)4.2凸優(yōu)化4.2.1凸集4.2凸優(yōu)化4.2.1凸集4.2凸優(yōu)化4.2.1凸集4.2凸優(yōu)化4.2.1凸集4.2凸優(yōu)化4.2.1凸集4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化4.2.2凸函數(shù)4.2凸優(yōu)化

定義4.2.3f是非凸集合C上的函數(shù)，則形式如4.2.3凸優(yōu)化4.2凸優(yōu)化4.2.3凸優(yōu)化4.2凸優(yōu)化4.2.3凸優(yōu)化4.2凸優(yōu)化matlab中cvx工具包，是解決凸函數(shù)的工具包。而python中也有成型的處理凸函數(shù)的模塊cvxpy。cvxpy模塊所依賴的模塊有很多，有numpy+mkl,scipy,cvxopt,scs,ecos,和osqp等等。安裝的過(guò)程中需要注意兩點(diǎn)，一是安裝的模塊版本必須與python版本和系統(tǒng)相對(duì)應(yīng)，其中包名中的cp37表示python3.7，amd64表示64位，win32表示32位。第二個(gè)需要注意的地方是，numpy模塊的安裝版本有很多，一定要選擇numpy+mkl模塊?；赾vxpy模塊的凸優(yōu)化問(wèn)題求解，給出一個(gè)簡(jiǎn)單的線性規(guī)劃的案例，代碼實(shí)現(xiàn)如下：4.2.4基于python語(yǔ)言的凸優(yōu)化問(wèn)題求解4.2凸優(yōu)化fromcvxpyimport*#Createtwoscalaroptimizationvariables.#在CVXPY中變量有標(biāo)量(只有數(shù)值大小)，向量，矩陣。#在CVXPY中有常量(見(jiàn)下文的Parameter)x=Variable()y=Variable()4.2.4基于python語(yǔ)言的凸優(yōu)化問(wèn)題求解4.2凸優(yōu)化constraints=[x+y==1,x-y>=1]obj=Minimize(square(x-y))prob=Problem(obj,constraints)prob.solve()#Returnstheoptimalvalueprint("status:",prob.status)#求解狀態(tài)print("optimalvalue",prob.status)#目標(biāo)函數(shù)優(yōu)化值print("optimalvar",x.value,y.value)#優(yōu)化變量的值，相應(yīng)變量加.value4.2.4基于python語(yǔ)言的凸優(yōu)化問(wèn)題求解4.2凸優(yōu)化運(yùn)行結(jié)果為：4.2.4基于python語(yǔ)言的凸優(yōu)化問(wèn)題求解4.3最小二乘法最小二乘法是一種數(shù)學(xué)優(yōu)化技術(shù)，用來(lái)做函數(shù)擬合或者求函數(shù)極值的方法。它是由勒讓德(A.M.Legendre)于1805年在其著作《計(jì)算慧星軌道的新方法》中提出的。主要思想就是最小化誤差平方和尋找數(shù)據(jù)的最佳匹配函數(shù)，利用最小二乘法求解未知參數(shù)，使得理論值與觀測(cè)值之差（即誤差，或者說(shuō)殘差）的平方和達(dá)到最小。4.3最小二乘法4.3最小二乘法我們的目的是一條與這幾個(gè)點(diǎn)最匹配的直線，來(lái)表出這些數(shù)據(jù)之間的關(guān)系。從分析數(shù)據(jù)看出，這些點(diǎn)差不多分布在一條直線上，因此我們自然想到用線性式y(tǒng)=ax+b表示它們之間的關(guān)系。由如下方程組：4.3最小二乘法這就須定出參數(shù)a，b的值來(lái)。若存在這樣的a,b能夠滿足上面的方程，那么解答就很簡(jiǎn)單了。但是，通常這樣的a,b時(shí)不存在的。也就是說(shuō)找不到一條線，穿過(guò)所有的點(diǎn)，因?yàn)樗麄儾辉谝粭l線上。如圖所示：4.3最小二乘法4.3最小二乘法4.3最小二乘法（1）和（2）兩個(gè)原則是很直觀的，也很理想，但很不好用；而原則（3）既直觀又很好用。按原則（3）確定待定參數(shù)，從而得到近似多項(xiàng)式的方法，就是通常所說(shuō)的最小二乘法?；氐剿岢龅膯?wèn)題上來(lái)，即用最小二乘法確定參數(shù)a,b。按最小二乘法，把每個(gè)點(diǎn)到直線的誤差平方加起來(lái)：取最小值。因此，應(yīng)有4.3最小二乘法由此，得到如下線性方程組：4.3最小二乘法經(jīng)過(guò)簡(jiǎn)單計(jì)算，這個(gè)方程組成為4.3最小二乘法4.3最小二乘法4.3最小二乘法4.3最小二乘法例4.3.1從某所高中隨機(jī)抽取6個(gè)女生，測(cè)出她們的體重和身高如下表,現(xiàn)在來(lái)了一個(gè)60kg的女生,求問(wèn)它的身高會(huì)有多高?importmatplotlibimportmatplotlib.pyplotaspltfrommatplotlib.font_managerimportFontPropertiesfromscipy.optimizeimportleastsqfromsklearn.linear_modelimportLinearRegressionfromscipyimportsparseimportnumpyasnp4.3最小二乘法#擬合函數(shù)deffunc(a,x):k,b=areturnk*x+b#殘差defdist(a,x,y):returnfunc(a,x)-y4.3最小二乘法font=FontProperties()plt.rcParams['font.sans-serif']=['SimHei']plt.rcParams['font.sans-serif']=['DroidSansFallback']#指定默認(rèn)字體plt.rcParams['font.sans-serif']=['SimHei']plt.rcParams['axes.unicode_minus']=False#解決保存圖像是負(fù)號(hào)'-'顯示為方塊的問(wèn)題4.3最小二乘法plt.figure()plt.title(u'女生的身高體重?cái)?shù)據(jù)')plt.xlabel(u'x體重')plt.ylabel(u'y身高')plt.axis([40,80,140,200])plt.grid(True)x=np.array([48.0,57.0,50.0,54.0,64.0,61.0,43.0,59.0])y=np.array([165.0,165.0,157.0,170.0,175.0,165.0,155.0,170.0])plt.plot(x,y,'k.')4.3最小二乘法param=[0,0]var=leastsq(dist,param,args=(x,y))k,b=var[0]print(k,b)plt.plot(x,k*x+b,'o-')plt.show()4.3最小二乘法k和b的值分別為：0.7514124562779751124.298021132850374.3最小二乘法4.4梯度下降法梯度下降法是求解無(wú)約束優(yōu)化問(wèn)題的一種簡(jiǎn)單而有效的優(yōu)化方法。它是一種利用目標(biāo)函數(shù)的Taylor展式構(gòu)造搜索方向的方法。4.4梯度下降法梯度下降法三要素：出發(fā)點(diǎn)、下降方向、下降步長(zhǎng)。用梯度下降法求解優(yōu)化問(wèn)題的基本思想可以類比為一個(gè)下山的過(guò)程，可微分的函數(shù)，代表著一座山，我們的目標(biāo)就是尋找這個(gè)函數(shù)的最小值，也就是山底。假設(shè)有這樣的情況，一個(gè)人本困在山上，四周可視度比較低，無(wú)法確定下山的路徑和方向，此時(shí)必須利用周圍的一些信息來(lái)尋找下山的路。那么，他可以利用梯度下降法來(lái)幫助自己尋找下山的路徑。具體做法如下：4.4.1梯度下降思想4.4梯度下降法4.4.1梯度下降思想4.4梯度下降法函數(shù)f在點(diǎn)P沿著梯度方向最陡，也就是變化速率最快。這就是我們?yōu)槭裁匆Х桨儆?jì)的求取梯度。我們要到達(dá)山底，需要每一步觀測(cè)到此時(shí)最陡峭的地方，梯度就恰巧告訴了我們這個(gè)方向。梯度的方向就是函數(shù)上升最快的方向，那么梯度的反方向就是給定函數(shù)在給定的下降最快的方向，所以我們沿著梯度相反的方向一直走，每走一段，重復(fù)上面的方法，最后成功抵達(dá)山谷，也就可求得函數(shù)的最小值。4.4.1梯度下降思想4.4梯度下降法假設(shè)我們要求函數(shù)f(x)的最小值，梯度下降法的步驟如下：4.4.2梯度下降法算法步驟4.4梯度下降法根據(jù)梯度下降時(shí)使用數(shù)據(jù)量的不同，梯度下降可以分為3類：批量梯度下降（BatchGradientDescent，BGD）、隨機(jī)梯度下降（StochasticGradientDescent，SGD）和小批量梯度下降（Mini-BatchGradientDescent,MBGD）1、全量梯度下降法（Batchgradientdescent，BGD）批量梯度下降每次都使用訓(xùn)練集中的所有樣本來(lái)更新參數(shù)，因此每次更新都會(huì)朝著正確的方向進(jìn)行，最后能夠保證收斂到極值點(diǎn)，凸函數(shù)收斂到全局最優(yōu)解，非凸函數(shù)收斂到局部最優(yōu)解。當(dāng)樣本數(shù)據(jù)集很大時(shí)，批量梯度下降的速度就會(huì)非常慢，學(xué)習(xí)時(shí)間太長(zhǎng)，消耗大量?jī)?nèi)存。4.4.3梯度算法分類4.4梯度下降法2、隨機(jī)梯度下降（StochasticGradientDescent，SGD）梯度下降過(guò)程都使用全部樣本數(shù)據(jù)可能會(huì)造成訓(xùn)練過(guò)程過(guò)慢，隨機(jī)梯度下降（SGD）每輪迭代只從樣本中只選擇一條數(shù)據(jù)進(jìn)行梯度下降，這樣經(jīng)過(guò)足夠多的迭代次數(shù)，SGD也可以發(fā)揮作用。SGD的缺點(diǎn)在于每次更新可能并不會(huì)按照正確的方向進(jìn)行，參數(shù)更新具有高方差，從而導(dǎo)致?lián)p失函數(shù)劇烈波動(dòng)，不過(guò)，SGD可以使優(yōu)化方向從一個(gè)極小點(diǎn)跳到另一個(gè)極小點(diǎn)，對(duì)于非凸函數(shù)而言，可能會(huì)找到全局最優(yōu)點(diǎn)。4.4.3梯度算法分類4.4梯度下降法3、小批量梯度下降法（Mini-BatchGradientDescent，MBGD）BGD和SGD收斂速度快，但是收斂性不穩(wěn)定。MBGD是BGD和SGD之間的折中，MBGD每次迭代多個(gè)樣本。MBGD降低了了SGD訓(xùn)練過(guò)程的雜亂程度，同時(shí)也保證了速度。并且如果BatchSize選擇合理，不僅收斂速度比SGD更快、更穩(wěn)定，而且在最優(yōu)解附近的跳動(dòng)也不會(huì)很大，甚至得到比BatchGradientDescent更好的解。這樣就綜合了SGD和BatchGradientDescent的優(yōu)點(diǎn)，同時(shí)弱化了缺點(diǎn)?？傊?，Mini-Batch比SGD和BatchGradientDescent都好。4.4.3梯度算法分類4.4梯度下降法4.4.3梯度算法分類fromrandomimportrandomdefgradient_decent(fn,partial_derivatives,n_variables,lr=0.1,max_iter=10000,tolerance=1e-5):theta=[random()for_inrange(n_variables)]y_cur=fn(*theta)

4.4梯度下降法4.4.3梯度算法分類foriinrange(max_iter):#Calculategradientofcurrenttheta.gradient=[f(*theta)forfinpartial_derivatives]#Updatethethetabythegradient.forjinrange(n_variables):theta[j]-=gradient[j]*lr#Checkifconvergedornot.y_cur,y_pre=fn(*theta),y_curifabs(y_pre-y_cur)<tolerance:breakreturntheta,y_cur4.4梯度下降法4.4.3梯度算法分類deff(x,y):return(x+y-3)**2+(x+2*y-5)**2+2defdf_dx(x,y):return2*(x+y-3)+2*(x+2*y-5)defdf_dy(x,y):return2*(x+y-3)+4*(x+2*y-5)4.4梯度下降法4.4.3梯度算法分類defmain():print("Solvetheminimumvalueofquadraticfunction:")n_variables=2theta,f_theta=gradient_decent(f,[df_dx,df_dy],n_variables)theta=[round(x,3)forxintheta]print("Thesolutionis:theta%s,f(theta)%.2f.\n"%(theta,f_theta))4.4梯度下降法梯度下降的求解結(jié)果如下Solvetheminimumvalueofquadraticfunction:Thesolutionis:theta[1.028,1.983],f(theta)2.00.4.4.3梯度算法分類4.5牛頓法（Newton法）求解無(wú)約束非線性規(guī)劃問(wèn)題的Newton法是利用目標(biāo)函數(shù)的二次Taylor展式構(gòu)造搜索方向的方法。考慮如下無(wú)約束非線性規(guī)劃問(wèn)題，即4.5牛頓法（Newton法）4.5.1Newton法的基本原理4.5牛頓法（Newton法）4.5.1Newton法的基本原理4.5牛頓法（Newton法）4.5.1Newton法的基本原理4.5牛頓法（Newton法）4.5.1Newton法的基本原理4.5牛頓法（Newton法）4.5.2Newton法的步驟4.5牛頓法（Newton法）4.5.2Newton法的步驟從本質(zhì)上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說(shuō)的話，比如你想找一條最短的路徑走到一個(gè)盆地的最底部，梯度下降法每次只從你當(dāng)前所處位置選一個(gè)坡度最大的方向走一步，牛頓法在選擇方向時(shí)，不僅會(huì)考慮坡度是否夠大，還會(huì)考慮你走了一步之后，坡度是否會(huì)變得更大。所以，可以說(shuō)牛頓法比梯度下降法看得更遠(yuǎn)一點(diǎn)，能更快地走到最底部。（牛頓法目光更加長(zhǎng)遠(yuǎn)，所以少走彎路；相對(duì)而言，梯度下降法只考慮了局部的最優(yōu)，沒(méi)有全局思想。）4.5牛頓法（Newton法）4.5.3用Newton法求解無(wú)約束優(yōu)化問(wèn)題4.5牛頓法（Newton法）4.5.3用Newton法求解無(wú)約束優(yōu)化問(wèn)題4.5牛頓法（Newton法）4.5.3用Newton法求解無(wú)約束優(yōu)化問(wèn)題上述問(wèn)題式一個(gè)無(wú)約束凸二次規(guī)劃，用Newton法求解時(shí)，經(jīng)過(guò)一次迭代即可得到精確的最優(yōu)解。其實(shí)，對(duì)于一般的無(wú)約束凸二次規(guī)劃問(wèn)題，用Newton法求解時(shí)，也有相同的結(jié)論，即Newton法具有二次終止性。4.5牛頓法（Newton法）4.5.3用Newton法求解無(wú)約束優(yōu)化問(wèn)題importnumpyasnpdeffd(x):t=np.asarray([2,4])#y=np.dot(x.T,t)y=x.T*treturnydeffdd():#ys=12*x**2-24*x-124.5牛頓法（Newton法）4.5.3用Newton法求解無(wú)約束優(yōu)化問(wèn)題a=np.asarray([[2,0],[0,4]])A=np.matrix(a)returnA.Ifdd()i=1x0=np.asarray([1,2])#3.000004.5牛頓法（Newton法）4.5.3用Newton法求解無(wú)約束優(yōu)化問(wèn)題ans=pow(10,-6)fd0=fd(x0)fdd0=fdd()whilenp.linalg.norm(fd0)>ans:x1=x0-(fd0*fdd0)x0=x1print("次數(shù)：%s,所得的值x:%s"%(i,x1))i=i+1fd0=fd(x0)fdd0=fdd()else:print("運(yùn)算結(jié)束，找到最優(yōu)值！")print("最優(yōu)值：X=%s"%x0)運(yùn)行結(jié)果：次數(shù)：1,所得的值x:[[0.0.]]運(yùn)算結(jié)束，找到最優(yōu)值！最優(yōu)值：X=[[0.0.]]4.6共軛梯度法共軛梯度法是利用目標(biāo)函數(shù)的梯度逐步產(chǎn)生共軛方向并將其作為搜索方向的方法。共軛梯度法是針對(duì)二次函數(shù)的無(wú)約束優(yōu)化問(wèn)題。考慮出一種搜索方向的合理選取方法，然后形式推廣到一般的無(wú)約束非線性規(guī)劃問(wèn)題。此方法具有存儲(chǔ)變量少和收斂速度快的特點(diǎn)。4.6共軛梯度法4.6.1共軛方向4.6共軛梯度法4.6.1共軛方向在上述定義中，如果A為單位矩陣，則兩個(gè)方向關(guān)于A共軛等價(jià)于兩個(gè)方向正交，由此可見(jiàn)，共軛是正交概念的推廣。將一組共軛方向作為搜索方向?qū)o(wú)約束非線性規(guī)劃問(wèn)題進(jìn)行求解的方法就稱為共軛方向法。共軛梯度法是將共軛方向法與梯度方法結(jié)合起來(lái)考慮的一種優(yōu)化方法。4.6共軛梯度法4.6.2共軛梯度法基本原理考慮無(wú)約束凸二次規(guī)劃問(wèn)題4.6共軛梯度法4.6.2共軛梯度法基本原理4.6共軛梯度法4.6.2共軛梯度法基本原理4.6共軛梯度法4.6.2共軛梯度法基本原理4.6共軛梯度法4.6.2共軛梯度法基本原理4.6共軛梯度法4.6.2共軛梯度法基本原理4.6共軛梯度法4.6.2共軛梯度法基