最優(yōu)化模型與算法-基于Python實(shí)現(xiàn) 教案 ch05 非凸優(yōu)化算法

非凸優(yōu)化算法基于牛頓法的迭代公式，設(shè)計(jì)計(jì)算()的迭代公式并編程實(shí)現(xiàn)。初始點(diǎn)需滿足什么條件以保證迭代點(diǎn)列收斂？建議選擇初始點(diǎn)的鄰近值作為初始點(diǎn)，以便更快地達(dá)到收斂。在本例中，初始點(diǎn)需選擇3a2．編程實(shí)現(xiàn)共軛梯度法，求解線性方程組 (5.11.1)略。3.已知，基于Lagrange乘子法求的最小值。首先，我們需要構(gòu)建拉格朗日函數(shù)?？紤]到約束條件a2+b2=1，我們引入拉格朗日乘子λ，定義拉格朗日函數(shù)：L(a,b,λ)=(a+1)(b+2)+λ(a2+b2-1)然后，我們求解該最小值問(wèn)題的駐點(diǎn)，即求解以下方程組：?L/?a=0,?L/?b=0,a2+b2-1=0對(duì)拉格朗日函數(shù)求偏導(dǎo)數(shù)并令其為零：?L/?a=b+2+2aλ=0...(1)?L/?b=a+1+2bλ=0...(2)a2+b2-1=0...(3)從方程(1)和(2)中可以解得：λ=-(a+1)/(2b)將λ代入方程(3)中，可以得到：(a+1)2/(4b2)+b2-1=0化簡(jiǎn)上述方程，得到：5a2+12a+8=0解這個(gè)二次方程，可以得到a的兩個(gè)解：a?=-1，a?=-4/5當(dāng)a=-1時(shí)，由方程(1)可以解得b=-3/2當(dāng)a=-4/5時(shí)，由方程(1)可以解得b=-3/10所以，駐點(diǎn)為(-1,-3/2)和(-4/5,-3/10)。接下來(lái)，我們需要判斷這些駐點(diǎn)是極小值還是極大值還是鞍點(diǎn)。我們可以通過(guò)二階偏導(dǎo)數(shù)的符號(hào)來(lái)判斷。計(jì)算L(a,b,λ)對(duì)a的二階偏導(dǎo)數(shù)：?2L/?a2=2λ計(jì)算L(a,b,λ)對(duì)b的二階偏導(dǎo)數(shù)：?2L/?b2=2λ計(jì)算L(a,b,λ)對(duì)a和b的混合二階偏導(dǎo)數(shù)：?2L/?a?b=2a由于?2L/?a2=2λ，?2L/?b2=2λ，?2L/?a?b=2a，均滿足二階偏導(dǎo)數(shù)存在且不為零。當(dāng)λ<0時(shí)，(a+1)(b+2)取得最小值；當(dāng)λ>0時(shí)，(a+1)(b+2)取得最大值；當(dāng)λ=0時(shí)，無(wú)法判斷最小值或最大值。因此，我們需要求出λ的值。將駐點(diǎn)代入方程(1)或(2)，可以得到：λ=-(a+1)/(2b)對(duì)于駐點(diǎn)(-1,-3/2)，代入得到λ=1/3>0；對(duì)于駐點(diǎn)(-4/5,-3/10)，代入得到λ=2/5>0。由上述結(jié)果可知，(a+1)(b+2)的最小值為：(-1+1)(-3/2+2)=0因此，(a+1)(b+2)的最小值為0。證明優(yōu)化問(wèn)題(5.9.9)的最優(yōu)解集是。略。5．證明BFGS更新的迭代公式為 (5.11.2)略。6．有限存貯BFGS法[2]對(duì)于大規(guī)模問(wèn)題，擬牛頓法的一個(gè)主要缺點(diǎn)是需要很大的存儲(chǔ)量。這激發(fā)了僅使用有限數(shù)量的向量和(例如，與當(dāng)前迭代最近的次迭代)來(lái)構(gòu)造擬牛頓方向的方法。這個(gè)練習(xí)展示了主要的算法設(shè)計(jì)思路。(a)BFGS迭代公式可以寫成 (5.11.3)其中 (5.11.4)(b)可使用和向量計(jì)算方向。略。7．編程實(shí)現(xiàn)CCCP算法，求解例5.9.1中的基于指數(shù)平方損失的回歸問(wèn)題。importnumpyasnp#定義指數(shù)平方損失函數(shù)defloss_function(y_true,y_pred):returnnp.exp(np.square(y_true-y_pred))#計(jì)算梯度defgradient(X,y,w):return2*np.dot(X.T,(np.exp(np.dot(X,w))-y)*np.exp(np.dot(X,w)))#CCCP算法defcccp_regression(X,y,iterations=100,learning_rate=0.01):#初始化權(quán)重w=np.random.randn(X.shape[1],1)foriinrange(iterations):#優(yōu)化凸函數(shù)部分convex_grad=gradient(X,y,w)w-=learning_rate*convex_grad#優(yōu)化凹函數(shù)部分y_pred=np.exp(np.dot(X,w))loss_grad=gradient(X,y_pred,w)w+=learning_rate*loss_gradreturnw#示例數(shù)據(jù)X=np.array([[1,2],[2,3],[