規(guī)劃模型專題二非線性規(guī)劃

規(guī)劃模型專題二非線性規(guī)劃第一頁，共六十頁，2022年，8月28日第一部分非線性規(guī)劃前面有老師介紹了線性規(guī)劃問題，典型的問題“下料問題”、“運輸問題”等，這些問題都比較簡單。但實際中的問題不僅僅是簡單的線性規(guī)劃問題，可能是比較繁雜的非線性規(guī)劃問題。下面我們從一個競賽題目出發(fā)，以理解非線性規(guī)劃的定義、建模過程及其求解過程。第二頁，共六十頁，2022年，8月28日在約1萬米的高空的某邊長為160km的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機作水平飛行，區(qū)域內(nèi)每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù)，以便進行飛行管理。當一架欲進入該區(qū)域的飛機到達區(qū)域邊緣時，計算機記錄其數(shù)據(jù)后，要立即計算并判斷是否會發(fā)生碰撞。若會發(fā)生碰撞，則應(yīng)計算如何調(diào)整各架飛機（包括新進入的飛機）飛行的方向角，以避免碰撞，且使飛機的調(diào)整的幅度盡量小，例11995年全國數(shù)學(xué)建模A題：飛行管理問題一、例題講解第三頁，共六十頁，2022年，8月28日該題比較有意思的一句話是：“使調(diào)整弧度最小”開放性的一句話，沒有限制得很死，較靈活，給參賽者的創(chuàng)新空間比較大一些，使得構(gòu)建模型的目標函數(shù)表現(xiàn)形式很多，再加上模型求解方法（算法）的多樣性，從而可以呈現(xiàn)出五花八門的論文。第四頁，共六十頁，2022年，8月28日不碰撞的標準為任意兩架飛機的距離大于8km;假設(shè)條件：飛機飛行的方向角調(diào)整幅度不應(yīng)超過；（因飛機飛行的速度變化不大）所有飛機的飛行速度v均為800km/h;有時需要通過查閱文獻、資料給出合理假設(shè)注：第五頁，共六十頁，2022年，8月28日進入該區(qū)域的飛機在到達區(qū)域邊緣時，與區(qū)域內(nèi)飛機的距離應(yīng)在60km以上；最多需考慮六架飛機；不必考慮飛機離開此區(qū)域后的狀況。根據(jù)當年競賽題目給出的數(shù)據(jù)，可以驗證新進入的飛機與區(qū)域內(nèi)的飛機的距離超過60公里。根據(jù)當年競賽題目給出的數(shù)據(jù)，可以驗證區(qū)域內(nèi)的飛機不超過架(包括新進入的)。第六頁，共六十頁，2022年，8月28日個人的想法不同，隊友之間爭執(zhí)不下的情況下，若時間允許，都可一一寫到論文中去，建立的模型一、模型二……；或者經(jīng)討論后，選擇一個認為更合理的。費時較多的是計算（那時侯是自己編程解NLP）現(xiàn)在看來，無論是構(gòu)建模型，還是計算，都不太難。本例題未給出數(shù)據(jù)，將重點放在如何構(gòu)建模型上第七頁，共六十頁，2022年，8月28日解：(1)不考慮飛機的尺寸，用點代表飛機；(2)已在區(qū)域內(nèi)的5架飛機按給定的方向角作直線飛行，則必不會碰撞，也不會發(fā)生意外；(應(yīng)該根據(jù)題目中所給出的數(shù)據(jù)簡單的驗證一下)(3)飛機調(diào)整方向角的過程可在瞬間完成,(不計調(diào)整方向所花費的時間)。為解決該問題，補充假設(shè)：第八頁，共六十頁，2022年，8月28日變量、參數(shù)的符號假設(shè)（為了建模）在區(qū)域內(nèi)飛行飛時間（可以根據(jù)數(shù)據(jù)算出來）第九頁，共六十頁，2022年，8月28日說明：用初等數(shù)學(xué)的知識即可完成，思考：在哪個時間段某兩架飛機可能相撞？Infact,我們只需考慮兩架飛機同時在區(qū)域內(nèi)飛行時的情況，也就是說，才是同在區(qū)域內(nèi)的狀況。記為第十頁，共六十頁，2022年，8月28日根據(jù)題目條件，需計算第架飛機之間的最短距離第十一頁，共六十頁，2022年，8月28日為此，我們可以給出原問題的模型如下：思考：是否還有其他的表達形式？非線性規(guī)劃模型分別從目標函數(shù)和約束條件角度思考第十二頁，共六十頁，2022年，8月28日首先思考一下目標函數(shù)是否有其它的表達？同學(xué)們首先想到的可能是Oh,Sorry!有正有負抵消第十三頁，共六十頁，2022年，8月28日最小一乘法最小二乘法因最小一乘法帶絕對值，不好計算，以上兩式，比較而言，后者較好。為了避免抵消or第十四頁，共六十頁，2022年，8月28日有的隊員這樣考慮：令為,轉(zhuǎn)化為二次規(guī)劃用到經(jīng)驗?zāi)Ｐ椭写_定參數(shù)的近似準則:就所有飛機而言，讓調(diào)整弧度最大的即盡可能小，Chebshavf準則第十五頁，共六十頁，2022年，8月28日全國數(shù)學(xué)建模競賽開展之初,競賽題大多是優(yōu)化類型的題目,那時的計算機性能沒有現(xiàn)在好,速度也沒有現(xiàn)在快,因此在模型的計算方面花的培訓(xùn)時間比較多。雖然目前可供選擇的軟件比較多，但是必要的優(yōu)化知識是必須掌握的。第十六頁，共六十頁，2022年，8月28日其次討論一下約束條件是否有其它表達？若考慮區(qū)域內(nèi)不發(fā)生碰撞(若時間允許，也可以考慮出了區(qū)域的情況，另外建模)、錯層飛行(飛高或者飛低避免碰撞)，進行模型的進一步改進，重點應(yīng)放在解決問題的方法上。第十七頁，共六十頁，2022年，8月28日第十八頁，共六十頁，2022年，8月28日無論選擇哪一種表達，怎樣考慮約束條件，目標函數(shù)都不可能是線性的?，F(xiàn)在看來，那年的題目建模不難，只是在條件的考慮上和建模中目標函數(shù)的表達方面較難一點。但在當時不然。是一個帶不等式約束的非線性規(guī)劃問題。而且不可能轉(zhuǎn)化成線性的形式。第十九頁，共六十頁，2022年，8月28日

若目標函數(shù)或約束條件中含有非線性函數(shù)，則稱這種模型問題為非線性規(guī)劃（Non-LinearProg-ramming），簡記為NLP。NLP的一般形式其中，中至少有一個是非線性函數(shù)。第二十頁，共六十頁，2022年，8月28日

無約束極值問題是NLP的一種特殊形式如數(shù)據(jù)擬合的最小二乘問題就是一個無約束極值問題。其思想是：觀察點（實驗數(shù)據(jù)點）到曲線的距離的平方之和最小二、無約束極值問題第二十一頁，共六十頁，2022年，8月28日理論上無約束極值問題可化成求解即解一個n元方程組，且往往是非線性方程組。而一般說來，非線性方程組的求解并不比求無約束極值容易。第二十二頁，共六十頁，2022年，8月28日求解無約束極值問題的基本方法：迭代法從一個給定的初始可行點出發(fā)，依次產(chǎn)生一個可行點列的一個極小值點,恰好是使得某個基本思路：或收斂于,稱具有這種性質(zhì)的算法是收斂的.第二十三頁，共六十頁，2022年，8月28日由迭代到時,記即其中向量為搜索方向,實數(shù)稱為步長,確定以后,由可唯一地確定從出發(fā)就可確定點列第二十四頁，共六十頁，2022年，8月28日迭代的方法很多,各種迭代法的區(qū)別在于選取的方式不同,而尤為關(guān)鍵.一般要求遞減,具有這種性質(zhì)的算法叫做下降算法.下面介紹的迭代法均為下降算法第二十五頁，共六十頁，2022年，8月28日若已得下降得最多,并確定了的可行下降方向上選取步長則在射線使且使即求求的過程稱為一維搜索.1.下降算法第二十六頁，共六十頁，2022年，8月28日于是一維搜索歸結(jié)為求解一維無約束極值問題:其算法有Newton法、平分法、黃金分割法（0.618法）、分數(shù)法（Fibonacci法）、拋物線法（二次插值法）等，前兩種算法需計算的導(dǎo)數(shù)，后三種算法只需計算的函數(shù)值。下面僅介紹Newton法，對其他方法的了解可參考有關(guān)書籍。第二十七頁，共六十頁，2022年，8月28日按給定初始可行點和控制誤差，迭代格式迭代，當時，即求得的最優(yōu)解的近似解停止計算。Newton法介紹第二十八頁，共六十頁，2022年，8月28日

♂一個好的算法必須以較快的速度收斂到最優(yōu)解。設(shè)算法產(chǎn)生的點列收斂于最優(yōu)解若存在及使則稱為p階收斂的。該算法也是p階收斂的。第二十九頁，共六十頁，2022年，8月28日稱為線性收斂；當且時，稱為超線性收斂；當時，稱為平方收斂；當時，第三十頁，共六十頁，2022年，8月28日一個算法是否收斂，往往與的選取有關(guān)①若當充分接近時，由算法產(chǎn)生的點列才收斂于則稱該算法為具有局部收斂性的算法；②若對則稱該算法為具有全局收斂性的算法。由算法產(chǎn)生的點列均收斂于第三十一頁，共六十頁，2022年，8月28日Newton法是平方收斂的，具有局部收斂性；拋物線法是超線性收斂的，具有全局收斂性；平分法、黃金分割法、分數(shù)法是線性收斂的，具有全局收斂性。常見一維搜索算法的收斂性第三十二頁，共六十頁，2022年，8月28日當具有多個極小值點時，則算法求得的往往是的一個局部極小值點。此時可改變的取值，重新迭代求解。若求得多個極小值點，則從中選擇一個較滿意的結(jié)果。

♂說明：第三十三頁，共六十頁，2022年，8月28日在多數(shù)情況下，一維搜索的一個基本工具，而此時一維搜索的精度并不要求很高，故一維搜索實現(xiàn)的方便性更重要些。第三十四頁，共六十頁，2022年，8月28日1847年Cauchy提出了第一個無約束極值問題的算法——梯度法或最速下降法：其中給定初始點和控制誤差求當時，即得的最優(yōu)解的近似解停止計算。2.梯度法第三十五頁，共六十頁，2022年，8月28日該算法具有全局收斂性，是線性收斂的，但有時是很慢的線性收斂，這似乎與“最速下降”矛盾。其實不然，最速下降方向函數(shù)在某點處的局部性質(zhì)，對局部來說是最速下降方向，對全局來說卻不一定是最速下降方向，故梯度法不是有效的實用算法。通過對它改進或利用它與其他收斂快的算法相結(jié)合可得Newton法、Fletcher-Reeves共軛梯度法、變尺度法和Powell法等有效算法。第三十六頁，共六十頁，2022年，8月28日下面僅介紹前兩者，對后兩者的了解可參閱有關(guān)書籍。當時，則。其中稱為在處的Hesse矩陣。①Newton法第三十七頁，共六十頁，2022年，8月28日該算法是平方收斂的，具有局部收斂性。對Newton法進行改進，可得具有超線性收斂的且具有全局收斂性的阻尼Newton法或修正Newton法：當時，有。第三十八頁，共六十頁，2022年，8月28日②Fletcher-Reeves共軛梯度法當時，有。該算法的收斂速度介于梯度法和Newton法其中之間，既克服了前者的慢收斂性，又避免了后者計算量大和僅具有局部收斂性的缺陷。第三十九頁，共六十頁，2022年，8月28日求解無約束極值問題的算法非常多，不同算法的效果和實際效率也可能與所求解的問題有關(guān)，軟件包中往往提供了多種算法。后面將有教練專講如何使用軟件包求解非線性規(guī)劃問題。第四十頁，共六十頁，2022年，8月28日求解一般的NLP比求解的無約束極值問題和LP都要復(fù)雜，雖然目前已發(fā)展了許多NLP的算法，但不象LP那樣有通用的單純形法，而是各種算法都有特定的使用范圍。即便如此，NLP的實際應(yīng)用還是相當廣泛的。三、有約束極值問題第四十一頁，共六十頁，2022年，8月28日首先回顧“NLP的一般形式”其中，中至少有一個是非線性函數(shù)。第四十二頁，共六十頁，2022年，8月28日由于無約束極值問題的求解目前已有許多有效的算法，因此很自然想到把它們推廣到有約束的NLP，但存在不少困難，特別是對于非線性約束，困難更大。（一）罰函數(shù)法一種可行的方法是根據(jù)約束問題的求解，構(gòu)造某種“懲罰”函數(shù)，把它加到目標函數(shù)中去，將約束問題的求解轉(zhuǎn)化為一系列無約束問題的求解。在無約束問題處，“懲罰”項必須趨于0，而約束條件要近似地滿足。第四十三頁，共六十頁，2022年，8月28日外罰函數(shù)法令通常取稱之為罰函數(shù)，則約束問題轉(zhuǎn)化為無約束問題其中M>0為罰因子.顯然,符合上述懲罰策略,即第四十四頁，共六十頁，2022年，8月28日當為可行解時,不受“懲罰”;當為非可行解時,M越大,“懲罰”越重.因此,當M充分大時,要使極小,則應(yīng)充分小,從而的極小值點充分逼近可行域,的最優(yōu)解逼近的最優(yōu)解.第四十五頁，共六十頁，2022年，8月28日給定(可為非可行解點),可以取小一些初始懲罰因子(如取),迭代過程中M不斷增加,放大系數(shù)c>1(可取c

=10).令k=0,以為初始點求得最優(yōu)解若則;否則,令以為初始點求該算法所得是從可行域外部故又稱為外罰函數(shù)法或外點法.趨于第四十六頁，共六十頁，2022年，8月28日說明外罰函數(shù)的構(gòu)造形式有多種,迭代格式也有多種,目前有不少專家在做這方面的工作;對于最優(yōu)解靠近邊界的情況不太好;對保證在可行域內(nèi)迭代很有效.第四十七頁，共六十頁，2022年，8月28日而只是近似滿足約束，這是某些實際問題不能“擋”在可行域內(nèi)了.這種方法稱為內(nèi)罰函數(shù)法或外點法的每個迭代點往往不是可行解,接受的.為使迭代點總是可行解,在可行域的

邊界筑起一道“墻”，當?shù)c靠近邊界時，目標

函數(shù)值陡然增大，以示懲罰，于是迭代點就被內(nèi)點法.只適用于不等式約束問題2.內(nèi)罰函數(shù)法第四十八頁，共六十頁，2022年，8月28日當從可行域內(nèi)部趨于邊界時,至少有某個內(nèi)罰函數(shù)：趨于0,無限增大.于是所求解的有約束問題轉(zhuǎn)化為求解如下的無約束問題其中r>0為罰因子.可實現(xiàn)上述“懲罰”第四十九頁，共六十頁，2022年，8月28日而r

很小,幾乎不受懲罰;策略，即無限增大，當為可行域的內(nèi)點時，為有限正數(shù)，施以重罰,迫使迭代點落在可行域內(nèi)，的最優(yōu)解.當接近可行域的邊界時，最終逼近第五十頁，共六十頁，2022年，8月28日給定初始可行點,初始懲罰因子(可取),縮小系數(shù)0<c<1令k=0,以為初始點求得最優(yōu)解.若則;否則,令以為初始點求(可取c

=0.1).縮小到原來的1/10控制在誤差范圍之內(nèi)，從而使得之間的誤差也在控制范圍內(nèi)第五十一頁，共六十頁，2022年，8月28日困難的。因此可將內(nèi)點法和外點法結(jié)合起來使用，外點法，內(nèi)點法，即令內(nèi)點法要求為可行域的內(nèi)點,有時這是很得到所謂的混合罰函數(shù)法。

那些不等式約束用3.混合罰函數(shù)法當給定后，對等式約束和不被滿足的

而對被滿足的那些不等式約束用第五十二頁，共六十頁，2022年，8月28日為簡便起見，取平方其中r充分小，1/r充分大，這樣少用一個參數(shù)第五十三頁，共六十頁，2022年，8月28日罰函數(shù)法中的罰因子的選取對方法的收斂快慢有較大影響，尤其是當M不斷增大和r不斷減少時，越來越“病態(tài)”，使得求解無約束問題很困難。為此，人們提出了許多改進的方法，其中最有效的是“乘子法”。需要詳細了解時參閱相關(guān)書籍。4.其他方法第五十四頁，共六十頁，2022年，8月28日罰函數(shù)法要用到目標函數(shù)和約束函數(shù)的偏導(dǎo)數(shù)，而某些實際問題中出現(xiàn)的函數(shù)很復(fù)雜，甚至難以解析表達，無法求得函數(shù)的偏導(dǎo)數(shù)，此時常用直接法(主要跟函數(shù)的函數(shù)值打交道)。這一類方法一般算法簡單，直觀性強，對函數(shù)無特殊要求，但計算量隨維數(shù)和約束條件數(shù)的增加而成指數(shù)增大，故對維數(shù)