規(guī)劃模型專(zhuān)題二非線(xiàn)性規(guī)劃

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

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

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

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

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

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

邊界筑起一道“墻”，當(dāng)?shù)c(diǎn)靠近邊界時(shí)，目標(biāo)

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

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

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

那些不等式約束用3.混合罰函數(shù)法當(dāng)給定后，對(duì)等式約束和不被滿(mǎn)足的

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