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

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

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

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

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

4.1.1最優(yōu)化問題數(shù)學(xué)模型不帶約束條件的優(yōu)化問題稱為無約束最優(yōu)化問題；帶約束條件的優(yōu)化問題稱為約束最優(yōu)化問題。4.1最優(yōu)化方法基礎(chǔ)根據(jù)不同的標(biāo)準(zhǔn)，從不同角度對優(yōu)化問題進(jìn)行分類。幾種常見的分類如下：一、函數(shù)優(yōu)化和組合優(yōu)化根據(jù)決策變量是連續(xù)取值還是僅取一些離散值，將最優(yōu)化問題可以分為函數(shù)優(yōu)化問題和組合優(yōu)化問題兩大類。其中函數(shù)優(yōu)化的對象是一定區(qū)間的連續(xù)變量，而組合優(yōu)化的對象則是解空間中的離散狀態(tài)。4.1.2最優(yōu)化問題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例鑒于許多工程問題存在約束條件，受約束函數(shù)的優(yōu)化問題也一直是優(yōu)化領(lǐng)域關(guān)注的主要對象。但是對于受約束問題，除了局部極小解的存在，影響最優(yōu)化性能的因素很多，因此對函數(shù)優(yōu)化的討論通常以無約束問題為主。4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例2.組合優(yōu)化問題組合優(yōu)化問題是通過對數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)排序、分類或篩選等，所研究的問題涉及信息技術(shù)、經(jīng)濟(jì)管理、土木工程、交通運輸、生產(chǎn)調(diào)度等諸多領(lǐng)域。該問題的數(shù)學(xué)模型可表示為：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例典型的組合優(yōu)化問題有旅行商(Travelingsalesmanproblem,TSP)問題、生產(chǎn)調(diào)度問題(Schedulingproblem,如Flowshop,Jobshop)、0-1背包問題(Knapsackproblem)、裝箱問題(Binpackingproblem)、圖著色問題(Graphcoloringproblem)、聚類問題(Clusteringproblem)等。4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例2.組合優(yōu)化問題組合優(yōu)化問題是通過對數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)排序、分類或篩選等，所研究的問題涉及信息技術(shù)、經(jīng)濟(jì)管理、土木工程、交通運輸、生產(chǎn)調(diào)度等諸多領(lǐng)域。該問題的數(shù)學(xué)模型可表示為：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例數(shù)學(xué)模型描述如下：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例數(shù)學(xué)模型描述如下：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例二、線性優(yōu)化和非線性優(yōu)化目標(biāo)函數(shù)或者約束函數(shù)中存在非線性的函數(shù)，則此問題稱為非線性優(yōu)化，否則為線性優(yōu)化。1.線性優(yōu)化在一組線性的等式或不等式約束下，求一個線性函數(shù)的最小值。問題數(shù)學(xué)模型如下：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例2.非線性優(yōu)化如果線性優(yōu)化的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達(dá)到（特別是可行域的頂點上達(dá)到）；而非線性優(yōu)化的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點達(dá)到。4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例總的來說就是讓投資總額最小，投資總收益最大，即4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例三、無約束最優(yōu)化與有約束最優(yōu)化如果除了目標(biāo)函數(shù)外，對參與優(yōu)化的各變量沒有其他函數(shù)或者變量的約束，則稱為無約束最優(yōu)化問題，反之則是有約束最優(yōu)化問題。實際的最優(yōu)化問題一般除了目標(biāo)函數(shù)外都有其他約束條件，因此多為約束優(yōu)化問題。1.無約束優(yōu)化問題無約束優(yōu)化問題的一般形式為：4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例Sylvester問題：設(shè)平面上有m個點，找覆蓋這m個點的最小圓盤。4.1最優(yōu)化方法基礎(chǔ)4.1.2最優(yōu)化問題的分類及應(yīng)用案例2.有約束優(yōu)化問題約束優(yōu)化問題的約束條件一般分為等式約束和不等式約束。約束優(yōu)化問題通常寫為4.1最優(yōu)化方法基礎(chǔ)4.1.3數(shù)學(xué)基礎(chǔ)1.導(dǎo)數(shù)在許多實際問題中，不僅要研究變量之間的函數(shù)關(guān)系，還需要討論變量與變量之間相對的變化情況，這種變化情況可以通過導(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等等。安裝的過程中需要注意兩點，一是安裝的模塊版本必須與python版本和系統(tǒng)相對應(yīng)，其中包名中的cp37表示python3.7，amd64表示64位，win32表示32位。第二個需要注意的地方是，numpy模塊的安裝版本有很多，一定要選擇numpy+mkl模塊?；赾vxpy模塊的凸優(yōu)化問題求解，給出一個簡單的線性規(guī)劃的案例，代碼實現(xiàn)如下：4.2.4基于python語言的凸優(yōu)化問題求解4.2凸優(yōu)化fromcvxpyimport*#Createtwoscalaroptimizationvariables.#在CVXPY中變量有標(biāo)量(只有數(shù)值大小)，向量，矩陣。#在CVXPY中有常量(見下文的Parameter)x=Variable()y=Variable()4.2.4基于python語言的凸優(yōu)化問題求解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ōu)化問題求解4.2凸優(yōu)化運行結(jié)果為：4.2.4基于python語言的凸優(yōu)化問題求解4.3最小二乘法最小二乘法是一種數(shù)學(xué)優(yōu)化技術(shù)，用來做函數(shù)擬合或者求函數(shù)極值的方法。它是由勒讓德(A.M.Legendre)于1805年在其著作《計算慧星軌道的新方法》中提出的。主要思想就是最小化誤差平方和尋找數(shù)據(jù)的最佳匹配函數(shù)，利用最小二乘法求解未知參數(shù)，使得理論值與觀測值之差（即誤差，或者說殘差）的平方和達(dá)到最小。4.3最小二乘法4.3最小二乘法我們的目的是一條與這幾個點最匹配的直線，來表出這些數(shù)據(jù)之間的關(guān)系。從分析數(shù)據(jù)看出，這些點差不多分布在一條直線上，因此我們自然想到用線性式y(tǒng)=ax+b表示它們之間的關(guān)系。由如下方程組：4.3最小二乘法這就須定出參數(shù)a，b的值來。若存在這樣的a,b能夠滿足上面的方程，那么解答就很簡單了。但是，通常這樣的a,b時不存在的。也就是說找不到一條線，穿過所有的點，因為他們不在一條線上。如圖所示：4.3最小二乘法4.3最小二乘法4.3最小二乘法（1）和（2）兩個原則是很直觀的，也很理想，但很不好用；而原則（3）既直觀又很好用。按原則（3）確定待定參數(shù)，從而得到近似多項式的方法，就是通常所說的最小二乘法。回到所提出的問題上來，即用最小二乘法確定參數(shù)a,b。按最小二乘法，把每個點到直線的誤差平方加起來：取最小值。因此，應(yīng)有4.3最小二乘法由此，得到如下線性方程組：4.3最小二乘法經(jīng)過簡單計算，這個方程組成為4.3最小二乘法4.3最小二乘法4.3最小二乘法4.3最小二乘法例4.3.1從某所高中隨機抽取6個女生，測出她們的體重和身高如下表,現(xiàn)在來了一個60kg的女生,求問它的身高會有多高?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ù)號'-'顯示為方塊的問題4.3最小二乘法plt.figure()plt.title(u'女生的身高體重數(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梯度下降法梯度下降法是求解無約束優(yōu)化問題的一種簡單而有效的優(yōu)化方法。它是一種利用目標(biāo)函數(shù)的Taylor展式構(gòu)造搜索方向的方法。4.4梯度下降法梯度下降法三要素：出發(fā)點、下降方向、下降步長。用梯度下降法求解優(yōu)化問題的基本思想可以類比為一個下山的過程，可微分的函數(shù)，代表著一座山，我們的目標(biāo)就是尋找這個函數(shù)的最小值，也就是山底。假設(shè)有這樣的情況，一個人本困在山上，四周可視度比較低，無法確定下山的路徑和方向，此時必須利用周圍的一些信息來尋找下山的路。那么，他可以利用梯度下降法來幫助自己尋找下山的路徑。具體做法如下：4.4.1梯度下降思想4.4梯度下降法4.4.1梯度下降思想4.4梯度下降法函數(shù)f在點P沿著梯度方向最陡，也就是變化速率最快。這就是我們?yōu)槭裁匆Х桨儆嫷那笕√荻取Ｎ覀円竭_(dá)山底，需要每一步觀測到此時最陡峭的地方，梯度就恰巧告訴了我們這個方向。梯度的方向就是函數(shù)上升最快的方向，那么梯度的反方向就是給定函數(shù)在給定的下降最快的方向，所以我們沿著梯度相反的方向一直走，每走一段，重復(fù)上面的方法，最后成功抵達(dá)山谷，也就可求得函數(shù)的最小值。4.4.1梯度下降思想4.4梯度下降法假設(shè)我們要求函數(shù)f(x)的最小值，梯度下降法的步驟如下：4.4.2梯度下降法算法步驟4.4梯度下降法根據(jù)梯度下降時使用數(shù)據(jù)量的不同，梯度下降可以分為3類：批量梯度下降（BatchGradientDescent，BGD）、隨機梯度下降（StochasticGradientDescent，SGD）和小批量梯度下降（Mini-BatchGradientDescent,MBGD）1、全量梯度下降法（Batchgradientdescent，BGD）批量梯度下降每次都使用訓(xùn)練集中的所有樣本來更新參數(shù)，因此每次更新都會朝著正確的方向進(jìn)行，最后能夠保證收斂到極值點，凸函數(shù)收斂到全局最優(yōu)解，非凸函數(shù)收斂到局部最優(yōu)解。當(dāng)樣本數(shù)據(jù)集很大時，批量梯度下降的速度就會非常慢，學(xué)習(xí)時間太長，消耗大量內(nèi)存。4.4.3梯度算法分類4.4梯度下降法2、隨機梯度下降（StochasticGradientDescent，SGD）梯度下降過程都使用全部樣本數(shù)據(jù)可能會造成訓(xùn)練過程過慢，隨機梯度下降（SGD）每輪迭代只從樣本中只選擇一條數(shù)據(jù)進(jìn)行梯度下降，這樣經(jīng)過足夠多的迭代次數(shù)，SGD也可以發(fā)揮作用。SGD的缺點在于每次更新可能并不會按照正確的方向進(jìn)行，參數(shù)更新具有高方差，從而導(dǎo)致?lián)p失函數(shù)劇烈波動，不過，SGD可以使優(yōu)化方向從一個極小點跳到另一個極小點，對于非凸函數(shù)而言，可能會找到全局最優(yōu)點。4.4.3梯度算法分類4.4梯度下降法3、小批量梯度下降法（Mini-BatchGradientDescent，MBGD）BGD和SGD收斂速度快，但是收斂性不穩(wěn)定。MBGD是BGD和SGD之間的折中，MBGD每次迭代多個樣本。MBGD降低了了SGD訓(xùn)練過程的雜亂程度，同時也保證了速度。并且如果BatchSize選擇合理，不僅收斂速度比SGD更快、更穩(wěn)定，而且在最優(yōu)解附近的跳動也不會很大，甚至得到比BatchGradientDescent更好的解。這樣就綜合了SGD和BatchGradientDescent的優(yōu)點，同時弱化了缺點?？傊?，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法）求解無約束非線性規(guī)劃問題的Newton法是利用目標(biāo)函數(shù)的二次Taylor展式構(gòu)造搜索方向的方法?？紤]如下無約束非線性規(guī)劃問題，即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ì)上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當(dāng)前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之后，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠(yuǎn)一點，能更快地走到最底部。（牛頓法目光更加長遠(yuǎn)，所以少走彎路；相對而言，梯度下降法只考慮了局部的最優(yōu)，沒有全局思想。）4.5牛頓法（Newton法）4.5.3用Newton法求解無約束優(yōu)化問題4.5牛頓法（Newton法）4.5.3用Newton法求解無約束優(yōu)化問題4.5牛頓法（Newton法）4.5.3用Newton法求解無約束優(yōu)化問題上述問題式一個無約束凸二次規(guī)劃，用Newton法求解時，經(jīng)過一次迭代即可得到精確的最優(yōu)解。其實，對于一般的無約束凸二次規(guī)劃問題，用Newton法求解時，也有相同的結(jié)論，即Newton法具有二次終止性。4.5牛頓法（Newton法）4.5.3用Newton法求解無約束優(yōu)化問題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法求解無約束優(yōu)化問題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法求解無約束優(yōu)化問題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("運算結(jié)束，找到最優(yōu)值！")print("最優(yōu)值：X=%s"%x0)運行結(jié)果：次數(shù)：1,所得的值x:[[0.0.]]運算結(jié)束，找到最優(yōu)值！最優(yōu)值：X=[[0.0.]]4.6共軛梯度法共軛梯度法是利用目標(biāo)函數(shù)的梯度逐步產(chǎn)生共軛方向并將其作為搜索方向的方法。共軛梯度法是針對二次函數(shù)的無約束優(yōu)化問題?？紤]出一種搜索方向的合理選取方法，然后形式推廣到一般的無約束非線性規(guī)劃問題。此方法具有存儲變量少和收斂速度快的特點。4.6共軛梯度法4.6.1共軛方向4.6共軛梯度法4.6.1共軛方向在上述定義中，如果A為單位矩陣，則兩個方向關(guān)于A共軛等價于兩個方向正交，由此可見，共軛是正交概念的推廣。將一組共軛方向作為搜索方向?qū)o約束非線性規(guī)劃問題進(jìn)行求解的方法就稱為共軛方向法。共軛梯度法是將共軛方向法與梯度方法結(jié)合起來考慮的一種優(yōu)化方法。4.6共軛梯度法4.6.2共軛梯度法基本原理考慮無約束凸二次規(guī)劃問題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共軛梯度法基