運(yùn)籌學(xué)無約束非線性規(guī)劃約束非線性優(yōu)化

運(yùn)籌學(xué)無約束非線性規(guī)劃約束非線性優(yōu)化第一頁，共一百零二頁，編輯于2023年，星期二

凸函數(shù)定義：設(shè)

為定義在n維歐氏空間E中某個凸集R上的函數(shù)，若對任何實(shí)數(shù)

以及R中的任意兩點(diǎn)

和

，恒有：則稱

為定義在R上的凸函數(shù)。則稱

為定義在R上的嚴(yán)格凸函數(shù)。第二頁，共一百零二頁，編輯于2023年，星期二凸函數(shù)性質(zhì)：性質(zhì)1：設(shè)

為定義在凸集R上的凸函數(shù)，則對任意實(shí)數(shù),函數(shù)也是定義在R上的凸函數(shù)。性質(zhì)2：設(shè)

和為定義在凸集R上的凸函數(shù)，則其和,任是定義在R上的凸函數(shù)。第三頁，共一百零二頁，編輯于2023年，星期二凸函數(shù)性質(zhì)：性質(zhì)3：設(shè)

為定義在凸集R上的凸函數(shù)，則對任意實(shí)數(shù),集合：是凸集。稱為水平集。第四頁，共一百零二頁，編輯于2023年，星期二凸函數(shù)性質(zhì)：推論：有限個凸函數(shù)的非負(fù)線性組合：仍為凸函數(shù)。第五頁，共一百零二頁，編輯于2023年，星期二函數(shù)凸性的判別：一階條件:設(shè)R為n維歐氏空間En上的開凸集，

在R上具有一階連續(xù)偏導(dǎo)數(shù)，則

為R上的凸函數(shù)的充要條件是，對任意兩個不同點(diǎn)

和

，恒有：第六頁，共一百零二頁，編輯于2023年，星期二函數(shù)凸性的判別：二階條件:設(shè)R為n維歐氏空間En上的開凸集，

在R上具有二階連續(xù)偏導(dǎo)數(shù)，則

為R上的凸函數(shù)的充要條件是：的海賽矩陣在R上處處半正定。第七頁，共一百零二頁，編輯于2023年，星期二凸函數(shù)的極值：定理：設(shè)

為定義在凸集R上的凸函數(shù)，則它的任一極小值就是它在R上的最小點(diǎn)（全局極小點(diǎn)），而且它的極小點(diǎn)形成一個凸集。定理：設(shè)

為定義在凸集R上的可微凸函數(shù)，若存在點(diǎn)

，使得對于所有的有：則

是

的R上的最小點(diǎn)（全局極小點(diǎn)）第八頁，共一百零二頁，編輯于2023年，星期二凸規(guī)劃：定義：若

為凸集，

是R上的凸函數(shù)，則稱規(guī)劃：為凸規(guī)劃定義：若規(guī)劃問題：其中為凸函數(shù)，為凹函數(shù)（或?yàn)橥购瘮?shù)），則該規(guī)劃問題為凸規(guī)劃。第九頁，共一百零二頁，編輯于2023年，星期二練習(xí)判斷下述非線性規(guī)劃是否是凸規(guī)劃

s.t.第十頁，共一百零二頁，編輯于2023年，星期二下降迭代算法：迭代法的基本思想：為了求函數(shù)

的最優(yōu)解，首先給定一個初始估計(jì)

，然后按照某種算法找出比

更好的解

；1.對于極小化問題：2.對于極大化問題：如此可以得到一個解的序列

。若這個解序列有極限

，即：則稱它收斂于第十一頁，共一百零二頁，編輯于2023年，星期二下降迭代算法：下降迭代算法的步驟：選定某一初始點(diǎn)

，令k：=0；確定搜索方向

；從

出發(fā)，沿方向

求步長

，以產(chǎn)生下一個迭代點(diǎn)

；檢查得到的新點(diǎn)x是否為極小值點(diǎn)或近似極小值點(diǎn)。若是，停止迭代。否則，令k：=k+1，回2步繼續(xù)迭代。第十二頁，共一百零二頁，編輯于2023年，星期二確定最優(yōu)步長求以

為變量的一元函數(shù)

的極小值點(diǎn)

（一維搜索）一維搜索重要性質(zhì)：在搜索方向上所得最優(yōu)點(diǎn)處的梯度和該搜索方向正交。第十三頁，共一百零二頁，編輯于2023年，星期二第十四頁，共一百零二頁，編輯于2023年，星期二迭代終止準(zhǔn)則絕對誤差：相對誤差：目標(biāo)函數(shù)梯度：

為事先給定的足夠小的正數(shù)。第十五頁，共一百零二頁，編輯于2023年，星期二一維搜索一維搜索是所有非線性規(guī)劃迭代算法都要遇到的共同問題，而且相對于構(gòu)造搜索方向問題比較簡單。因此我們在這一部分先介紹求解一維搜索問題的方法。主要有斐波那契法、0.618法、插值法、求根法（二分法）等。一維搜索主要針對單峰函數(shù)。什么是單峰函數(shù)？第十六頁，共一百零二頁，編輯于2023年，星期二單峰函數(shù)及其性質(zhì)定義:設(shè)函數(shù)：，閉區(qū)間，若存在點(diǎn)，使在上嚴(yán)格遞減，在上嚴(yán)格遞增，則稱函數(shù)為上的單峰函數(shù)，為的單峰區(qū)間，如下圖第十七頁，共一百零二頁，編輯于2023年，星期二單峰區(qū)間和單峰函數(shù)具有如下性質(zhì)：若是單峰區(qū)間上的單峰函數(shù)，極小點(diǎn)為，在中任取兩點(diǎn)，，且，則（1）當(dāng)時(shí)，；（2）當(dāng)時(shí)，。這個性質(zhì)說明了，經(jīng)過函數(shù)值的比較后，我們可以把單峰函數(shù)的單峰區(qū)間進(jìn)行縮小，或者或者，而仍在區(qū)間內(nèi)。

第十八頁，共一百零二頁，編輯于2023年，星期二

二分法步驟如下：第一步：選取初始數(shù)據(jù)，確定初始搜索區(qū)間，給出最后區(qū)間精度。第二步：計(jì)算初始試點(diǎn)：，計(jì)算，并令k:=0。第三步：如果，則令ak+1=tk,bk+1=bk,tk+1=(ak+1+bk+1)/2；否則，

ak+1=ak,bk+1=tk,tk+1=(ak+1+bk+1)/2。第四步：計(jì)算精度，若(bk+1-ak+1)/(b0-a0)<δ,則停止計(jì)算，取λ*=

tk+1。否則計(jì)算新的一對試點(diǎn)。二分法：第十九頁，共一百零二頁，編輯于2023年，星期二采用二分法求解下列問題：初始區(qū)間[-1,1],精度0.15kabtf'(t)精度1-110-122010.521300.50.250.50.5400.250.125-0.250.2550.1250.25

0.125例第二十頁，共一百零二頁，編輯于2023年，星期二黃金分割法也稱為0.618法，屬于區(qū)間收縮法。首先找出包含極小點(diǎn)的初始搜索區(qū)間，然后按黃金分割點(diǎn)通過對函數(shù)值得比較不斷縮小搜索區(qū)間。當(dāng)然要保證極小點(diǎn)始終在搜索區(qū)間內(nèi)，當(dāng)區(qū)間長度小到精度范圍之內(nèi)時(shí)，可以粗略的認(rèn)為區(qū)間端點(diǎn)的平均值就是極小點(diǎn)的近似值。黃金分割法適用于單峰函數(shù)。0.618法(黃金分割法)第二十一頁，共一百零二頁，編輯于2023年，星期二t1t2t2新搜索區(qū)間為[a,t2]新搜索區(qū)間為[t1,b]t1abab假定：已經(jīng)確定了單谷區(qū)間[a,b]第二十二頁，共一百零二頁，編輯于2023年，星期二縮短比例滿足：每次插入搜索點(diǎn)使得兩個區(qū)間[a,t2]和[t1,b]相等；每次迭代都以相等的比例縮小區(qū)間。區(qū)間縮小比例的確定：區(qū)間縮短比例為(t2-a)/(b-a)縮短比例為(b-t1)/(b-a)t1t2ababt1t20.618法第二十三頁，共一百零二頁，編輯于2023年，星期二確定[a,b],計(jì)算探索點(diǎn)t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解題步驟：否是是停止，輸出t2否以[t1,b]為新的搜索區(qū)間是停止，輸出t1否以[a,t2]為新的搜索區(qū)間第二十四頁，共一百零二頁，編輯于2023年，星期二例：解：t1t230t1、第一輪：a=0,t1=1.146,t2=1.854,b=3

t2－0>0.5第二十五頁，共一百零二頁，編輯于2023年，星期二3、第三輪：a=0,t1=0.438,t2=0.708,b=1.146b-t1=1.146-0.438>0.51.4160tt2t1t2－0=1.146>0.51.8540tt2t12、第二輪：a=0,t1=0.708,t2=1.146,b=1.854第二十六頁，共一百零二頁，編輯于2023年，星期二4、第四輪：a=0.438,t1=0.708,t2=0.876,b=1.146

b-t1=1.146-0.708<0.5輸出：t*=t2=0.876為最優(yōu)解，最優(yōu)值為-0.079801.416tt1t2第二十七頁，共一百零二頁，編輯于2023年，星期二kabt1t2f(t1)f(t2)精度1-11-0.2360.236-0.653-1.12522-0.23610.2360.528-1.125-0.971.2363-0.2360.5280.0560.236-1.05-1.1250.76440.0560.5280.2360.348-1.125-1.1060.47250.0560.3480.1680.236-1.112-1.1250.29260.1680.3480.2360.279-1.125-1.1230.1870.1680.2790.111采用黃金分割法求解下列問題：初始區(qū)間[-1,1],精度0.15練習(xí)第二十八頁，共一百零二頁，編輯于2023年，星期二無約束優(yōu)化問題的求解算法

此類無約束最優(yōu)化問題的求解已被各國學(xué)者廣泛地研究并取得了豐富的研究成果，至今已有許多有效算法被提出。一般說來，求解此類問題的算法被分成兩大類，一類要求導(dǎo)數(shù)的信息，而另一類則不要求導(dǎo)數(shù)的信息。第一類方法包括最速下降法、廣義牛頓法、共軛方向法以及變尺度方法等；第二類方法通常指搜索法，包括Hooke-Jeeves直接搜索法和隨機(jī)搜索法等?？紤]如下無約束優(yōu)化問題第二十九頁，共一百零二頁，編輯于2023年，星期二梯度法（最速下降法）1.梯度法的基本原理：目標(biāo)函數(shù)

有一階連續(xù)偏導(dǎo)數(shù)，具有極小值點(diǎn)以表示極小值點(diǎn)的第k次近似，為了求其第k+1次近似點(diǎn)

，我們在

點(diǎn)沿方向

做射線：將

在

點(diǎn)處展成泰勒級數(shù)：第三十頁，共一百零二頁，編輯于2023年，星期二將

在

點(diǎn)處展成泰勒級數(shù)：對于充分小的，只要：即可保證：這時(shí)若?。壕湍苁鼓繕?biāo)函數(shù)值得到改善。即：第三十一頁，共一百零二頁，編輯于2023年，星期二2.梯度法的方向確定（負(fù)梯度方向）使上式成立的

有無限多個。為了使目標(biāo)函數(shù)值能得到盡量大的改善，必須尋求使

取最小值的

。由線性代數(shù)得：為向量與的夾角。當(dāng)向量與取反向時(shí)取最小值第三十二頁，共一百零二頁，編輯于2023年，星期二3.梯度法的步長確定（一維搜索）若

具有二階連續(xù)偏導(dǎo)數(shù)，在

作

的泰勒展開對求導(dǎo)并令其等于零，則得到近似最佳步長：第三十三頁，共一百零二頁，編輯于2023年，星期二梯度法（最速下降法）考慮如下無約束優(yōu)化問題：其中函數(shù)f(x)具有一階連續(xù)偏導(dǎo)數(shù)。(1)最速下降法采用目標(biāo)函數(shù)的負(fù)梯度方向?yàn)橄陆捣较颍?2)一維搜索確定步長(3)收斂準(zhǔn)則第三十四頁，共一百零二頁，編輯于2023年，星期二例題例：試用最速下降法求下例優(yōu)化問題的極小點(diǎn)解：取初始近似點(diǎn)第三十五頁，共一百零二頁，編輯于2023年，星期二第三十六頁，共一百零二頁，編輯于2023年，星期二第三十七頁，共一百零二頁，編輯于2023年，星期二第三十八頁，共一百零二頁，編輯于2023年，星期二第三十九頁，共一百零二頁，編輯于2023年，星期二第四十頁，共一百零二頁，編輯于2023年，星期二第四十一頁，共一百零二頁，編輯于2023年，星期二采用最速下降法求解：選初始點(diǎn)X(0)=(2,-2,1)T。要求做三次迭代。第四十二頁，共一百零二頁，編輯于2023年，星期二Newton型算法(牛頓法)第四十三頁，共一百零二頁，編輯于2023年，星期二第四十四頁，共一百零二頁，編輯于2023年，星期二牛頓方向!第四十五頁，共一百零二頁，編輯于2023年，星期二第四十六頁，共一百零二頁，編輯于2023年，星期二例考慮如下無約束優(yōu)化問題：選取初始點(diǎn)x1=(0,0)T，目標(biāo)函數(shù)在x1處的梯度和Hessian矩陣分別為：牛頓方向：令：則x*=(0.7732,-1.1546)T第四十七頁，共一百零二頁，編輯于2023年，星期二第五章約束極值問題最優(yōu)性條件1.起作用約束:設(shè)

為非線性規(guī)劃的一個可行解，滿足所有條件。不起作用約束（無效約束）起作用約束（有效約束）顯而易見，等式約束對所有可行點(diǎn)來說都是起作用約束。第四十八頁，共一百零二頁，編輯于2023年，星期二最優(yōu)性條件2.可行下降方向:設(shè)是非線性規(guī)劃的一個可行點(diǎn)，現(xiàn)考慮此點(diǎn)的某一方向D，若存在實(shí)數(shù)，使對任意均有：就稱方向D為點(diǎn)的一個可行方向。第四十九頁，共一百零二頁，編輯于2023年，星期二

設(shè)是非線性規(guī)劃的一個可行點(diǎn)，現(xiàn)考慮此點(diǎn)的某一方向D，若存在實(shí)數(shù)，使對任意均有：就稱方向D為點(diǎn)的一個可行方向。只要：那么：設(shè)是非線性規(guī)劃的一個可行點(diǎn)，對該點(diǎn)的任一方向D，若存在實(shí)數(shù)，使對任意均有：那么就稱方向D為點(diǎn)的一個下降方向。第五十頁，共一百零二頁，編輯于2023年，星期二泰勒展開只要：即可保證：即可保證D必為

點(diǎn)的下降方向。如果方向D為

點(diǎn)的可行方向，又是這個點(diǎn)的下降方向，就稱它是該點(diǎn)的可行下降方向。第五十一頁，共一百零二頁，編輯于2023年，星期二定理：設(shè)

是非線性規(guī)劃的一個局部極小點(diǎn)，目標(biāo)函數(shù)

在

處可微，而且：在

處可微，當(dāng)在

處連續(xù)，當(dāng)則在點(diǎn)不存在可行下降方向，從而不存在向量D同時(shí)滿足：第五十二頁，共一百零二頁，編輯于2023年，星期二庫恩-塔克條件（kuhn-Tucker,K-T條件）設(shè)

是上式非線性規(guī)劃的一個極小點(diǎn)。1.若該點(diǎn)位于可行域的內(nèi)部，該線性規(guī)劃問題為無約束問題。2.若點(diǎn)位于可行域的邊界上…假設(shè)點(diǎn)位于某個約束條件的邊界上：如果點(diǎn)是極小點(diǎn)，則：與必須在一條直線上，且方向相反，否則在該點(diǎn)就一定存在可行下降方向。第五十三頁，共一百零二頁，編輯于2023年，星期二如果點(diǎn)有兩個起作用約束，如：若點(diǎn)為極小值點(diǎn)，那么必處于和的夾角之內(nèi)。否則在點(diǎn)一定存在可行下降方向。有一個起作用約束條件：有兩個起作用約束條件：第五十四頁，共一百零二頁，編輯于2023年，星期二有多個起作用約束條件：將不起作用約束條件包括進(jìn)上式：增加條件：庫恩-塔克條件(K-T條件):注：K-T條件是確定某點(diǎn)為最優(yōu)點(diǎn)的必要條件。對于凸規(guī)劃，K-T條件是確定某點(diǎn)為最優(yōu)點(diǎn)的充要條件第五十五頁，共一百零二頁，編輯于2023年，星期二為可行方向。為下降方向。為的可行下降方向。第五十六頁，共一百零二頁，編輯于2023年，星期二K-T條件定義：設(shè)

是非線性規(guī)劃問題的極小值點(diǎn)，而且

點(diǎn)的所有起作用約束的梯度線性無關(guān)，則存在向量：使下述條件成立：廣義拉格朗日（Lagrange）乘子。K-T條件第五十七頁，共一百零二頁，編輯于2023年，星期二先將該非線性規(guī)劃問題寫成以下形式：寫出其目標(biāo)函數(shù)和約束函數(shù)的梯度：引入拉格朗日乘子引入拉格朗日乘子第五十八頁，共一百零二頁，編輯于2023年，星期二K-T條件第五十九頁，共一百零二頁，編輯于2023年，星期二約束非線性優(yōu)化問題的求解方法Zoutendijk可行方向法Frank-Wolfe算法MSA算法懲罰函數(shù)法(SUMT外點(diǎn)法)障礙函數(shù)法(SUMT內(nèi)點(diǎn)法)第六十頁，共一百零二頁，編輯于2023年，星期二Zoutendijk可行方向法可行方向法定義設(shè)

為非線性規(guī)劃：的一個可行解，但不是要求的極小點(diǎn)。為了求它的極小點(diǎn)或近似極小點(diǎn)，應(yīng)在點(diǎn)的可行下降方向中選取某一方向

，并確定步長

，使：若滿足精度要求，迭代停止，

就是所要的點(diǎn)。否則，從

出發(fā)繼續(xù)進(jìn)行迭代，直到滿足要求為止。第六十一頁，共一百零二頁，編輯于2023年，星期二Zoutendijk可行方向法：設(shè)

點(diǎn)的起作用約束集非空，為求

點(diǎn)的可行下降方向，可由下述不等式組來確定向量

：這等價(jià)于由下面的不等式組求向量

和實(shí)數(shù)

：第六十二頁，共一百零二頁，編輯于2023年，星期二現(xiàn)在使和（對所有）的最大值極小化，即可將上述選取搜索方向的工作，轉(zhuǎn)換為求解下述線性規(guī)劃問題：為向量

的分量若最優(yōu)解為，如果求出的，則

點(diǎn)不存在可行下降方向。如果求出的，則得到可行下降方向。第六十三頁，共一百零二頁，編輯于2023年，星期二Zoutendijk可行方向法步驟：1.確定允許誤差和，選初始近似點(diǎn)，并令。2.確定起作用約束指標(biāo)集：（1）.若，而且，停止迭代，得點(diǎn)。（2）.若，而且，則取搜索方向，然后轉(zhuǎn)向5步。（3）.若，轉(zhuǎn)下一步。3.求解線性規(guī)劃：第六十四頁，共一百零二頁，編輯于2023年，星期二4.檢查是否停止：若滿足則停止迭代，得到點(diǎn)

；否則，以

為搜索方向，并轉(zhuǎn)下一步。5.解下述一維極值問題：此處：6.令：轉(zhuǎn)回2步。第六十五頁，共一百零二頁，編輯于2023年，星期二解下述非線性規(guī)劃問題：解：取初始可行點(diǎn)：由于所以

不是極小點(diǎn)。第六十六頁，共一百零二頁，編輯于2023年，星期二現(xiàn)取搜索方向：從而分別代入約束條件和目標(biāo)函數(shù)：從而第六十七頁，共一百零二頁，編輯于2023年，星期二求解下述線性規(guī)劃問題：由此：第六十八頁，共一百零二頁，編輯于2023年，星期二點(diǎn)為可行點(diǎn)所以…繼續(xù)迭代下去,最優(yōu)解：第六十九頁，共一百零二頁，編輯于2023年，星期二Frank-Wolfe算法Frank和Wolfe于1956年提出求解線性約束問題的一種算法，通常簡稱F-W算法。考慮最優(yōu)化問題其中是矩陣，秩為，是維列向量，是連續(xù)可微函數(shù)?？尚杏蛴洖椋?1)第七十頁，共一百零二頁，編輯于2023年，星期二

第七十一頁，共一百零二頁，編輯于2023年，星期二第七十二頁，共一百零二頁，編輯于2023年，星期二第七十三頁，共一百零二頁，編輯于2023年，星期二第七十四頁，共一百零二頁，編輯于2023年，星期二第七十五頁，共一百零二頁，編輯于2023年，星期二第七十六頁，共一百零二頁，編輯于2023年，星期二第七十七頁，共一百零二頁，編輯于2023年，星期二第七十八頁，共一百零二頁，編輯于2023年，星期二第七十九頁，共一百零二頁，編輯于2023年，星期二第八十頁，共一百零二頁，編輯于2023年，星期二第八十一頁，共一百零二頁，編輯于2023年，星期二第八十二頁，共一百零二頁，編輯于2023年，星期二第八十三頁，共一百零二頁，編輯于2023年，星期二第八十四頁，共一百零二頁，編輯于2023年，星期二第八十五頁，共一百零二頁，編輯于2023年，星期二MSA算法通常稱為相繼平均法（MethodofSuccessiveAverages

）?？紤]下面的最優(yōu)化問題

可行域記為?？梢杂肕SA算法進(jìn)行迭代求解。MSA算法第八十六頁，共一百零二頁，編輯于2023年，星期二假定在任意點(diǎn)，通過求解下面的線性