【正文】 ，故稱這一過(guò)程為一維搜索。因?yàn)檎嬲臉O值點(diǎn)在求解之前并不知道，因此只能根據(jù)相繼兩次迭代的結(jié)果來(lái)建立終止準(zhǔn)則。4一維搜索一維搜索即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)，一維搜索的方法很多，此教材只介紹斐波那契和黃金分割兩種方法。設(shè)某一單峰函數(shù)在上有一極小點(diǎn)，在此區(qū)間內(nèi)任意取兩點(diǎn)和，使，計(jì)算其函數(shù)值可能出現(xiàn)以下兩種情況：（1），如圖65所示；此時(shí)極小點(diǎn)必在內(nèi)。f(x)aa1x*b1bx圖65f(x)aa1x*b1bx圖66這說(shuō)明只要在區(qū)間內(nèi)任意取兩點(diǎn)和（）并計(jì)算其函數(shù)值加以比較，就可以把搜索區(qū)間縮減成或。由此可見，計(jì)算函數(shù)的次數(shù)越多，搜索區(qū)間就縮得越小，即區(qū)間的縮短率（縮短后的區(qū)間長(zhǎng)度與原區(qū)間長(zhǎng)度之比）與函數(shù)的計(jì)算次數(shù)有關(guān)。實(shí)際上這里的就是前面所說(shuō)的斐波那契數(shù)。斐波那契法使用對(duì)稱的搜索方式，逐步縮減搜索的區(qū)間，所采取的具體步驟可概括如下：（1） 根據(jù)相對(duì)精度或絕對(duì)精度，確定試點(diǎn)個(gè)數(shù)；（2） 確定兩個(gè)試點(diǎn)的位置、（對(duì)稱搜索，見圖67）；（3） 計(jì)算函數(shù)值和并比較其大小，從而縮減搜索區(qū)間；（4） 重復(fù)（2）、（3）兩步，直到得到近似最小點(diǎn)。解：容易證明函數(shù)在區(qū)間上是嚴(yán)格凸函數(shù)。已知d = 、a = b = 4，由式（63）有，即。從新的區(qū)間（，）開始，繼續(xù)選取對(duì)稱試點(diǎn)比較函數(shù)值，以使區(qū)間進(jìn)一步縮短。b1=b=a=1a1=Fn2=8Fn1=13a=1b=4a1=b1=Fn2Fn1圖68=a1=b1=a=b=圖69b1=a1=a1=a1=b1=新的試點(diǎn)，將原來(lái)的試點(diǎn)視為已知的試點(diǎn)。再?gòu)男碌膮^(qū)間（，）開始，繼續(xù)選取對(duì)稱試點(diǎn)比較函數(shù)值，以使區(qū)間進(jìn)一步縮短，直到區(qū)間長(zhǎng)度不大于。42黃金分割法用斐波那契法以個(gè)點(diǎn)縮減某一區(qū)間時(shí)，區(qū)間長(zhǎng)度的縮減率依次為。設(shè)當(dāng)時(shí)奇數(shù)項(xiàng) 偶數(shù)項(xiàng)由于故同理 將代入 ，求解有 若將代入，則有所以以不變的區(qū)間縮減率，代替斐波那契法每次不同的縮減率，就得到了黃金分割法。b1a1ba圖610[例67] 求函數(shù)在區(qū)間上的極小點(diǎn)，要求縮短后的區(qū)間長(zhǎng)度不大于原區(qū)間長(zhǎng)度的。a1=b1==20180。167。一般來(lái)講，直接法的收斂速度較慢，只有在變量較少時(shí)才能使用。51梯度法（最速下降法）1．基本原理假設(shè)無(wú)約束極值問(wèn)題的目標(biāo)函數(shù)有一階連續(xù)偏導(dǎo)數(shù)，且具有極小點(diǎn)；以表示極小點(diǎn)的第次近似，為了求其第次近似點(diǎn)，在點(diǎn)沿方向作射線+l，在此 l 稱為步長(zhǎng)并且l。對(duì)于充分小的 l ，只要 （64）即可保證l。現(xiàn)在考察不同的方向，假設(shè)的模一定且不為零，并設(shè)（否則是平穩(wěn)點(diǎn)）；那么，使式（64）成立的有無(wú)窮多個(gè)，為了使目標(biāo)函數(shù)能得到盡量大的改善，必須尋求能使取最小值的。被稱為負(fù)梯度方向，在的某一小的鄰域內(nèi)，負(fù)梯度方向是使函數(shù)值下降最快的方向。l的計(jì)算可以采用試算法，即首先選取一個(gè) l 值進(jìn)行試算，看它是否滿足不等式l；如果滿足就迭代下去，否則縮小 l 使不等式成立。另一種方法是通過(guò)在負(fù)梯度方向上的一維搜索，來(lái)確定使得l最小的lk，這種梯度法就是所謂的最速下降法。求步長(zhǎng)可以用一維搜索法、微分法，也可以利用試算法；若求最佳步長(zhǎng)，則只能選用前兩種方法。如此反復(fù)，直到達(dá)到要求的精度。[例68] 試用梯度法求的極小點(diǎn)，e。其實(shí)，對(duì)于等值線為圓的問(wèn)題，不管初始近似點(diǎn)選在哪里，負(fù)梯度方向總是直接指向圓心，一次迭代即能達(dá)到最優(yōu)。解：該二次函數(shù)的絕對(duì)最優(yōu)解，迭代過(guò)程見圖613，任何兩個(gè)相鄰點(diǎn)的梯度一定是正交的。下一個(gè)迭代點(diǎn)是這樣得到的：由有令函數(shù)對(duì)的導(dǎo)數(shù)為零，可求得最佳步長(zhǎng)于是有，同理可進(jìn)行后續(xù)的各步迭代。近似的極大點(diǎn)是。必須指出點(diǎn)處的梯度方向，僅在點(diǎn)的一個(gè)小鄰域內(nèi)才具有最速的性質(zhì)，而對(duì)于整個(gè)優(yōu)化過(guò)程來(lái)說(shuō)，那就是另外一回事了。因此，梯度法經(jīng)常與其他方法聯(lián)合使用，在前期使用梯度法，而在接近最優(yōu)點(diǎn)時(shí)使用其他方法。牛頓法是解非線性聯(lián)立方程的一種迭代程序，是前述梯度法的一部分。在這種情況下，從任意一點(diǎn)出發(fā)，用式（67）只要一步即可求出的極小點(diǎn)（假設(shè)海賽矩陣正定）。此時(shí)，按式（67）求得的極小點(diǎn)，只是的近似極小點(diǎn)。牛頓法收斂的速度很快，當(dāng)?shù)亩A導(dǎo)數(shù)及其海賽矩陣的逆矩陣便于計(jì)算時(shí)，這一方法非常有效。解： 是正定矩陣取，則：，因，故為的極小點(diǎn)，極小值是“0”。解： 是正定矩陣取，則：，因，故為的極小點(diǎn)，極小值是“1”。其主要的優(yōu)點(diǎn)是：既避免了計(jì)算二階導(dǎo)數(shù)矩陣及其求逆過(guò)程，又比梯度法收斂的速度快，特別是對(duì)高維問(wèn)題具有顯著的優(yōu)越性。由于實(shí)際問(wèn)題的目標(biāo)函數(shù)往往相當(dāng)復(fù)雜，計(jì)算二階導(dǎo)數(shù)矩陣及其逆矩陣相當(dāng)困難或根本不可能，因此，確定牛頓方向（見式（68））存在很大的障礙。為實(shí)現(xiàn)逼近的目的，的構(gòu)造應(yīng)遵循如下三條原則：（1）每一步均能按已有的信息確定下一個(gè)搜索方向；（2）每一步迭代均能使目標(biāo)函數(shù)有所下降；（3）近似矩陣最終應(yīng)收斂于解點(diǎn)處的海賽矩陣的逆矩陣。若令：則擬牛頓條件可變?yōu)椋含F(xiàn)設(shè)：=于是：或 （612）設(shè)想的一種簡(jiǎn)單形式為： （613）式（613）中和是兩個(gè)待定的向量，將式（613）代入式（612）可得：對(duì)照等式兩端，可以推斷： （614）由于應(yīng)為對(duì)稱矩陣，最簡(jiǎn)單的辦法就是?。? （615）將式（615）代入式（614）可得：設(shè)和均不為“0”，則有： （616）于是將式（615）、式（616）代入式（613）可得校正矩陣：從而可以得到： （617）式（617）被稱為尺度矩陣，在整個(gè)迭代過(guò)程中尺度矩陣是不斷變化的，因此該方法稱為變尺度法。下面通過(guò)例題來(lái)展示變尺度法的計(jì)算過(guò)程。解：，于是利用一維搜索 l0：l，可得 l0，于是：利用式（617）有：再利用一維搜索 l1：l，可得 l1，于是：于是即為極小點(diǎn)，函數(shù)的極小為。可以證明，如此構(gòu)造的尺度矩陣均為對(duì)稱正定陣，進(jìn)而可以確保搜索方向?yàn)橄陆捣较颉?約束極值問(wèn)題大多數(shù)的工程最優(yōu)化問(wèn)題，其變量的取值是受到一定限制的，這種限制是通過(guò)約束條件來(lái)實(shí)現(xiàn)的。求解約束極值問(wèn)題要比求解無(wú)約束極值問(wèn)題困難得多。為了簡(jiǎn)化優(yōu)化工作，通常采用如下解題思路：（1） 將約束極值問(wèn)題轉(zhuǎn)化為無(wú)約束極值問(wèn)題；（2） 將非線性規(guī)劃問(wèn)題轉(zhuǎn)化為線性規(guī)劃問(wèn)題；（3） 將復(fù)雜的問(wèn)題分解為若干簡(jiǎn)單問(wèn)題。現(xiàn)考慮某一不等式約束，滿足該不等式有兩種可能：（1），此時(shí)不在由該約束形成的可行域邊界上，因此該約束對(duì)的微小變動(dòng)不起限制作用，從而稱該約束為無(wú)效約束；（2），此時(shí)處在由該約束形成的可行域邊界上，因此該約束對(duì)的微小變動(dòng)會(huì)起某種限制作用，從而稱該約束為有效約束。是非線性規(guī)劃的一個(gè)可行解，對(duì)于此點(diǎn)的某一方向，若存在實(shí)數(shù) l0使任意 ll0均有l(wèi)，就稱方向是點(diǎn)的一個(gè)可行方向，此處代表非線性規(guī)劃的可行域。圖614另一方面，由泰勒展開式ll（l）可知對(duì)所有有效約束，當(dāng)l足夠小時(shí)，只要， （619）就有l(wèi)，此外，對(duì)點(diǎn)所有的無(wú)效約束來(lái)講，由于約束函數(shù)的連續(xù)性，當(dāng)l足夠小時(shí)，上式依然成立。非線性規(guī)劃的某一可行點(diǎn)，對(duì)該點(diǎn)的任一方向來(lái)說(shuō)，若存在實(shí)數(shù)l0使任意ll0均有l(wèi)，就稱方向是點(diǎn)的一個(gè)下降方向。如果方向既是點(diǎn)的一個(gè)可行方向又是一個(gè)下降方向，就稱是點(diǎn)的一個(gè)可行下降方向。[定理3] 設(shè)是非線性規(guī)劃的一個(gè)局部極小點(diǎn)，目標(biāo)函數(shù)在處可微，而且在處可微，當(dāng)時(shí)在處連續(xù)，當(dāng)時(shí)（此處代表在處有效約束的下標(biāo)集合）則在點(diǎn)不存在可行下降方向，從而不存在向量同時(shí)滿足， （621）事實(shí)上，若在點(diǎn)存在向量滿足式（621），則從點(diǎn)出發(fā)沿方向搜索可找到比點(diǎn)更好的點(diǎn)，這與點(diǎn)是一個(gè)局部極小點(diǎn)的假設(shè)相矛盾；所以這個(gè)定理是顯然成立的。假設(shè)