約束問(wèn)題的線性化方法第1頁(yè)，共49頁(yè)，2023年，2月20日，星期六非線性約束問(wèn)題求解策略轉(zhuǎn)化為無(wú)約束問(wèn)題Lagrange乘子法懲罰函數(shù)法線性化直接搜索等其它方法第2頁(yè)，共49頁(yè)，2023年，2月20日，星期六線化方法：Taylor展開(kāi)第3頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.1線性逐次逼近算法線性約束問(wèn)題非線性約束問(wèn)題第4頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.1.1線性約束問(wèn)題在初始點(diǎn)x0線化第5頁(yè)，共49頁(yè)，2023年，2月20日，星期六線性約束問(wèn)題算法第6頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：三級(jí)壓縮機(jī)優(yōu)化設(shè)計(jì)目標(biāo)：選擇中間級(jí)大力，最大限度節(jié)能第7頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：三級(jí)壓縮機(jī)優(yōu)化設(shè)計(jì)第8頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.1.2非線性約束問(wèn)題在點(diǎn)x(t)線化第9頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：弱非線性問(wèn)題的逐次線化求解線化應(yīng)用線性規(guī)劃算法求解第10頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：弱非線性問(wèn)題的逐次線化求解…第11頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.1.2非線性約束問(wèn)題對(duì)于較強(qiáng)的非線性問(wèn)題，逐次線化方法會(huì)導(dǎo)致發(fā)散，解決辦法：限制步長(zhǎng)：區(qū)域越小線性近似越準(zhǔn)確使用懲罰函數(shù)第12頁(yè)，共49頁(yè)，2023年，2月20日，星期六懲罰逐次線性規(guī)劃算法第13頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：懲罰逐次線性規(guī)劃方法限制步長(zhǎng)求解線化第14頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：懲罰逐次線性規(guī)劃方法x(1)點(diǎn)的懲罰函數(shù)計(jì)算在x(1)點(diǎn)線化求解：第15頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：懲罰逐次線性規(guī)劃方法在x(2)點(diǎn)線化求解：在x(3)點(diǎn)線化求解：…第16頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.2可分離規(guī)劃：分段線性近似分段線性逼近第17頁(yè)，共49頁(yè)，2023年，2月20日，星期六單變量分段線性近似第18頁(yè)，共49頁(yè)，2023年，2月20日，星期六多變量可分離規(guī)劃前提：函數(shù)可分離第19頁(yè)，共49頁(yè)，2023年，2月20日，星期六多變量可分離規(guī)劃第20頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：多變量函數(shù)線性近似第21頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：可分離規(guī)劃求解第22頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：可分離規(guī)劃求解x1的網(wǎng)格點(diǎn)選取：函數(shù)的分段線性近似：第23頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：可分離規(guī)劃求解線化之后的線性規(guī)劃標(biāo)準(zhǔn)形式：?jiǎn)渭冃畏椒ㄇ蠼猓壕_解第24頁(yè)，共49頁(yè)，2023年，2月20日，星期六總結(jié)逐次線性逼近算法步長(zhǎng)限制，懲罰函數(shù)適用于非線性不強(qiáng)的問(wèn)題分段線性逼近算法精度隨格點(diǎn)數(shù)增加而增加要求函數(shù)可分離第25頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3搜索方向的線性化生成第26頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3.1可行方向算法第27頁(yè)，共49頁(yè)，2023年，2月20日，星期六可行方向算法第28頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：可行方向算法第29頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：可行方向算法第30頁(yè)，共49頁(yè)，2023年，2月20日，星期六例：可行方向算法…第31頁(yè)，共49頁(yè)，2023年，2月20日，星期六可行方向算法修正ε微擾法Topkis–Veinott方法第32頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3.2單純形方法推廣單純形方法回顧約束標(biāo)準(zhǔn)型：基本解：相對(duì)收益：基本變量的選取與替換：新的可行基本解：最優(yōu)化準(zhǔn)則：

所有非基本變量的相對(duì)收益大于或等于0第33頁(yè)，共49頁(yè)，2023年，2月20日，星期六單純形方法推廣到線性約束問(wèn)題：凸單純形方法相對(duì)收益：最優(yōu)化準(zhǔn)則：最優(yōu)解可能不在頂點(diǎn)，非基本變量可能不為0約束標(biāo)準(zhǔn)型：基本解：相對(duì)收益：最優(yōu)化準(zhǔn)則：

線性搜索第34頁(yè)，共49頁(yè)，2023年，2月20日，星期六凸單純形算法第35頁(yè)，共49頁(yè)，2023年，2月20日，星期六凸單純形算法第36頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3.3既約(Reduced)梯度方法類似于無(wú)約束優(yōu)化的梯度算法（Cauchy算法）。搜索方向d為梯度的負(fù)方向約化梯度為，即凸單純形算法中非基本量的相對(duì)收益?？梢宰C明，它實(shí)際上是在約束條件(m個(gè))下的以非基本變量為獨(dú)立變量(n-m)的梯度：稱為約化梯度，是在非基本變量子空間中的梯度。第37頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3.3既約(Reduced)梯度方法基本量的變化：非基本量子空間中的搜索方向：保證x在定義域內(nèi)：確定搜索方向第38頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3.3既約(Reduced)梯度方法第39頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3.3既約(Reduced)梯度方法約化梯度方法的加速共軛梯度準(zhǔn)牛頓方法第40頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3.4廣義既約梯度(GRG)方法推廣約化梯度方法到一般的非線性優(yōu)化問(wèn)題GRG基本思想：等式約束可以通過(guò)消元的辦法化為無(wú)約束問(wèn)題將等式約束線化消元化為無(wú)約束形式應(yīng)用無(wú)約束的基于梯度算法第41頁(yè)，共49頁(yè)，2023年，2月20日，星期六11.3.4廣義既約梯度(GRG)方法首先考慮等式約束問(wèn)題，目標(biāo)函數(shù)和約束都是非線性的：第42頁(yè)，共49頁(yè)，2023年，2月20日，星期六基本GRG算法1、約束的線化2、選擇獨(dú)立變量，即分解為基本量與非基本變量基本量，即非獨(dú)立變量的系數(shù)矩陣：非基本量，即獨(dú)立變量的系數(shù)矩陣：第43頁(yè)，共49頁(yè)，2023年，2月20日，星期六基本GRG算法3、以非基本變量為獨(dú)立變量，在線化的約束中解出基本量，實(shí)現(xiàn)消元4、計(jì)算目標(biāo)函數(shù)的梯度（獨(dú)立變量為非基本變量為），即線性規(guī)劃中的相對(duì)收益5、梯度為0即是最優(yōu)化的必要條件，可作為收斂準(zhǔn)則≤第44頁(yè)，共49頁(yè)，2023年，2月20日，星期六基本GRG算法6、確定搜索方向7、在搜索方向上線性搜索返回4第45頁(yè)，共49頁(yè)，2023年，2月20日，星期六基本GRG算法修正問(wèn)題：搜索方向d具有下降的性質(zhì)，這是由于是下降的，而一般不具有這個(gè)性質(zhì)，因此會(huì)導(dǎo)致在d方向上搜索會(huì)違反約束解決辦法：將往約束曲面上投影，在投影上進(jìn)行線性搜索：具體方法：（1）給定α，解出（2）調(diào)變?chǔ)?，使f(x)最速下降第46頁(yè)，共49頁(yè)，2023年，2月20日，星期六完整GRG算法第47頁(yè)，共49頁(yè)，2023年，2月20日，星期六完整GRG算法第48頁(yè)，共49頁(yè)，2023年，2月