數(shù)學(xué)規(guī)劃法在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中應(yīng)用學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)學(xué)規(guī)劃法在結(jié)構(gòu)優(yōu)化設(shè)計(jì)數(shù)學(xué)規(guī)劃法在結(jié)構(gòu)優(yōu)化設(shè)計(jì)(shj)中應(yīng)用中應(yīng)用第一頁(yè)，共73頁(yè)。 f ( x ) -目標(biāo)函數(shù)目標(biāo)函數(shù) g i ( X ) 和和 g e ( X ) - 約束條約束條件件第2頁(yè)/共73頁(yè)第二頁(yè)，共73頁(yè)。(1) 按約束的有無(wú)按約束的有無(wú)(yu w)，可分為：，可分為：無(wú)約束最優(yōu)化問(wèn)題無(wú)約束最優(yōu)化問(wèn)題有約束最優(yōu)化問(wèn)題有約束最優(yōu)化問(wèn)題準(zhǔn)無(wú)約束最優(yōu)化問(wèn)題準(zhǔn)無(wú)約束最優(yōu)化問(wèn)題第3頁(yè)/共73頁(yè)第三頁(yè)，共73頁(yè)。第4頁(yè)/共73頁(yè)第四頁(yè)，共73頁(yè)。對(duì)于線性規(guī)劃問(wèn)題，單純形法十分對(duì)于線性規(guī)劃問(wèn)題，單純形法十分(shfn)有效有效無(wú)約束非線性規(guī)劃問(wèn)題無(wú)約束非線性規(guī)劃問(wèn)題不利用梯度的算

2、法：不利用梯度的算法：0.618法、單純形法、法、單純形法、Powell法和隨機(jī)搜索法和隨機(jī)搜索法法利用梯度的算法：最速下降法、共軛梯度法、牛頓法、擬牛頓利用梯度的算法：最速下降法、共軛梯度法、牛頓法、擬牛頓法法有約束非線性規(guī)劃問(wèn)題有約束非線性規(guī)劃問(wèn)題轉(zhuǎn)化法：內(nèi)罰函數(shù)法、外罰函數(shù)法轉(zhuǎn)化法：內(nèi)罰函數(shù)法、外罰函數(shù)法直接法：可行方向法、最佳矢量法、梯度投影法直接法：可行方向法、最佳矢量法、梯度投影法序列近似規(guī)劃法：序列二次規(guī)劃方法、序列線性規(guī)劃方法序列近似規(guī)劃法：序列二次規(guī)劃方法、序列線性規(guī)劃方法第5頁(yè)/共73頁(yè)第五頁(yè)，共73頁(yè)。第6頁(yè)/共73頁(yè)第六頁(yè)，共73頁(yè)。在數(shù)學(xué)規(guī)劃中，一般迭代格式可以寫(xiě)成：

3、在數(shù)學(xué)規(guī)劃中，一般迭代格式可以寫(xiě)成： x (k+1) = x (k)+ P(k) , - 步長(zhǎng)步長(zhǎng)( Step length )，正標(biāo)量，正標(biāo)量 P(k) - 方向向量方向向量( Directional vector ) 因此目標(biāo)因此目標(biāo)(mbio)函數(shù)的下降要求可以改寫(xiě)成：函數(shù)的下降要求可以改寫(xiě)成： f(x (k)+ P(k) ) f(x(k)如果函數(shù)如果函數(shù)f(x)在在x(k)是一次可微的，則對(duì)足夠下小的是一次可微的，則對(duì)足夠下小的有：有： f(x (k)+ P(k) )- f(x(k) Tf(x(k) P(k) 0由于由于是正標(biāo)量，所以：是正標(biāo)量，所以：Tf(x(k) P(k) 0這說(shuō)明

4、搜索方向應(yīng)該和目標(biāo)這說(shuō)明搜索方向應(yīng)該和目標(biāo)(mbio)函數(shù)負(fù)梯度方向夾函數(shù)負(fù)梯度方向夾角小于角小于90，這樣的方向稱之為下山方向。，這樣的方向稱之為下山方向。第7頁(yè)/共73頁(yè)第七頁(yè)，共73頁(yè)。第8頁(yè)/共73頁(yè)第八頁(yè)，共73頁(yè)。第9頁(yè)/共73頁(yè)第九頁(yè)，共73頁(yè)。第10頁(yè)/共73頁(yè)第十頁(yè)，共73頁(yè)。第11頁(yè)/共73頁(yè)第十一頁(yè)，共73頁(yè)。第12頁(yè)/共73頁(yè)第十二頁(yè)，共73頁(yè)。第13頁(yè)/共73頁(yè)第十三頁(yè)，共73頁(yè)。0.618法的基本思想法的基本思想是通過(guò)是通過(guò)(tnggu)取取試探點(diǎn)和進(jìn)行函數(shù)試探點(diǎn)和進(jìn)行函數(shù)值比較，使包含極值比較，使包含極小點(diǎn)的搜索區(qū)間不小點(diǎn)的搜索區(qū)間不斷縮短，從而各點(diǎn)斷縮短，從而各

5、點(diǎn)可以看作為極小點(diǎn)可以看作為極小點(diǎn)的近似。這類方法的近似。這類方法僅需計(jì)算函數(shù)值，僅需計(jì)算函數(shù)值，用途廣泛，尤其適用途廣泛，尤其適用于非光滑函數(shù)形用于非光滑函數(shù)形式。式。第14頁(yè)/共73頁(yè)第十四頁(yè)，共73頁(yè)。第15頁(yè)/共73頁(yè)第十五頁(yè)，共73頁(yè)。插值法是一類插值法是一類(y li)重要的一維搜索方法。其基重要的一維搜索方法。其基本思想是在搜索區(qū)間中不斷用低次（通常不超過(guò)本思想是在搜索區(qū)間中不斷用低次（通常不超過(guò)三次）多項(xiàng)式來(lái)近似目標(biāo)函數(shù)，并逐漸用插值多三次）多項(xiàng)式來(lái)近似目標(biāo)函數(shù)，并逐漸用插值多項(xiàng)式的極小點(diǎn)來(lái)逼近一維搜索問(wèn)題。當(dāng)函數(shù)具體項(xiàng)式的極小點(diǎn)來(lái)逼近一維搜索問(wèn)題。當(dāng)函數(shù)具體比較好的解析性質(zhì)時(shí)

6、，插值法比直接方法效果更比較好的解析性質(zhì)時(shí)，插值法比直接方法效果更好。好。第16頁(yè)/共73頁(yè)第十六頁(yè)，共73頁(yè)。第17頁(yè)/共73頁(yè)第十七頁(yè)，共73頁(yè)。第18頁(yè)/共73頁(yè)第十八頁(yè)，共73頁(yè)。第19頁(yè)/共73頁(yè)第十九頁(yè)，共73頁(yè)。第20頁(yè)/共73頁(yè)第二十頁(yè)，共73頁(yè)。連續(xù)性連續(xù)性收斂性收斂性適用范圍適用范圍0.618法法0階0.618牛頓法牛頓法2階2二點(diǎn)二次插值法二點(diǎn)二次插值法1階1.618割線法割線法1階1.618第21頁(yè)/共73頁(yè)第二十一頁(yè)，共73頁(yè)。；n計(jì)算計(jì)算f(x(k)若若f(x(k) 成立，則成立，則x*=x(k)，停機(jī)，停機(jī)，否則轉(zhuǎn)下一步；否則轉(zhuǎn)下一步；n求求P(k) = -f(x

7、(k) ，求，求(k)=min f(x (k)- f(x(k)；n調(diào)整設(shè)計(jì)調(diào)整設(shè)計(jì)x (k+1) x (k)- f(x(k)，回第，回第(2)步。步。第22頁(yè)/共73頁(yè)第二十二頁(yè)，共73頁(yè)。由此可見(jiàn)，最速下降法走由此可見(jiàn)，最速下降法走的是的是“之之”字形字形最速下降法是一階線性收斂，最速下降法是一階線性收斂，收斂速度較慢。收斂速度較慢。最速下降法與變量長(zhǎng)度有關(guān)，最速下降法與變量長(zhǎng)度有關(guān)，即與變量尺度即與變量尺度(chd)關(guān)系很關(guān)系很大。大。最速下降法迭代過(guò)程簡(jiǎn)單，不最速下降法迭代過(guò)程簡(jiǎn)單，不受初始點(diǎn)位置限制。因此雖受初始點(diǎn)位置限制。因此雖然該方法有收斂慢，依賴于然該方法有收斂慢，依賴于變量的尺

8、度變量的尺度(chd)等缺點(diǎn)，等缺點(diǎn)，但這些缺點(diǎn)往往在最優(yōu)點(diǎn)附但這些缺點(diǎn)往往在最優(yōu)點(diǎn)附近表現(xiàn)得才明顯。近表現(xiàn)得才明顯。第23頁(yè)/共73頁(yè)第二十三頁(yè)，共73頁(yè)。第24頁(yè)/共73頁(yè)第二十四頁(yè)，共73頁(yè)。第25頁(yè)/共73頁(yè)第二十五頁(yè)，共73頁(yè)。第26頁(yè)/共73頁(yè)第二十六頁(yè)，共73頁(yè)。第27頁(yè)/共73頁(yè)第二十七頁(yè)，共73頁(yè)。第28頁(yè)/共73頁(yè)第二十八頁(yè)，共73頁(yè)。第29頁(yè)/共73頁(yè)第二十九頁(yè)，共73頁(yè)。第30頁(yè)/共73頁(yè)第三十頁(yè)，共73頁(yè)。 這兩個(gè)條件這兩個(gè)條件(tiojin)的幾何意義是的幾何意義是: 目標(biāo)函目標(biāo)函數(shù)梯度向量和約束條件數(shù)梯度向量和約束條件(tiojin)梯度向量與梯度向量與方向向量之

9、間的夾角均大于方向向量之間的夾角均大于900. 根據(jù)上述要求根據(jù)上述要求, 可以有三條路線來(lái)完成調(diào)參可以有三條路線來(lái)完成調(diào)參: 1. 沿等重線沿等重線(面面)側(cè)移；側(cè)移； 2. 沿約束邊界側(cè)移梯度投影法沿約束邊界側(cè)移梯度投影法( Gradient projection method )； 3. 沿可用可行方向沿可用可行方向 P 側(cè)移可行方向法側(cè)移可行方向法 ( Feasible directional method )。由此構(gòu)成三種不同形式的可行方向法。由此構(gòu)成三種不同形式的可行方向法。第31頁(yè)/共73頁(yè)第三十一頁(yè)，共73頁(yè)。第32頁(yè)/共73頁(yè)第三十二頁(yè)，共73頁(yè)。第33頁(yè)/共73頁(yè)第三十三頁(yè)

10、，共73頁(yè)。第34頁(yè)/共73頁(yè)第三十四頁(yè)，共73頁(yè)。第35頁(yè)/共73頁(yè)第三十五頁(yè)，共73頁(yè)。第36頁(yè)/共73頁(yè)第三十六頁(yè)，共73頁(yè)。第37頁(yè)/共73頁(yè)第三十七頁(yè)，共73頁(yè)。第38頁(yè)/共73頁(yè)第三十八頁(yè)，共73頁(yè)。Z ( +1) = Z ( ) + P() 步長(zhǎng)可以有兩種方法確定步長(zhǎng)可以有兩種方法確定: (1) 沿沿 P()( 即即d )向量方向?qū)ο蛄糠较驅(qū)?求一維搜索最小點(diǎn)。求一維搜索最小點(diǎn)。這種方法對(duì)無(wú)約束條件下比較有效這種方法對(duì)無(wú)約束條件下比較有效(yuxio)； (2) 利用可行性條件求利用可行性條件求 。按按P() 行進(jìn)到兩條線性約束的交點(diǎn)時(shí)行進(jìn)到兩條線性約束的交點(diǎn)時(shí), 首先要計(jì)算首先

11、要計(jì)算出下一輪側(cè)移向量出下一輪側(cè)移向量, 并加以判斷并加以判斷:若若 f ( Z (+1) )T P(+1) 0 可沿可沿 P(+1) 進(jìn)一步進(jìn)一步調(diào)參調(diào)參;若若 f ( Z (+1) )T P(+1) 0 則不能繼續(xù)調(diào)參則不能繼續(xù)調(diào)參, 要用要用上一個(gè)設(shè)計(jì)點(diǎn)上一個(gè)設(shè)計(jì)點(diǎn) Z () 沿沿 P() 進(jìn)行一維搜索求進(jìn)行一維搜索求 Z*, 或者利用或者利用 f ( Z* )T P(+1) = 0, 其中令其中令 Z* = Z () + (+1) P(+1) , 代入式中代入式中, 即可解得即可解得 (+1) .第39頁(yè)/共73頁(yè)第三十九頁(yè)，共73頁(yè)。第40頁(yè)/共73頁(yè)第四十頁(yè)，共73頁(yè)。第41頁(yè)/共

12、73頁(yè)第四十一頁(yè)，共73頁(yè)。第42頁(yè)/共73頁(yè)第四十二頁(yè)，共73頁(yè)。第43頁(yè)/共73頁(yè)第四十三頁(yè)，共73頁(yè)。第44頁(yè)/共73頁(yè)第四十四頁(yè)，共73頁(yè)。第45頁(yè)/共73頁(yè)第四十五頁(yè)，共73頁(yè)。上述不等式的解可借助于求解上述不等式的解可借助于求解(qi ji)下述線性子規(guī)劃下述線性子規(guī)劃 min s. t. f ( X ( ) )T P( ) + 0 g j ( x ( ) )T P( ) + j , j = 1, NC | P( ) i | 1, i = 1, n第46頁(yè)/共73頁(yè)第四十六頁(yè)，共73頁(yè)。第47頁(yè)/共73頁(yè)第四十七頁(yè)，共73頁(yè)。第48頁(yè)/共73頁(yè)第四十八頁(yè)，共73頁(yè)。上述為典型的線性

13、規(guī)劃上述為典型的線性規(guī)劃(xin xn u hu)問(wèn)題問(wèn)題, 可用單純型法求解可用單純型法求解.第49頁(yè)/共73頁(yè)第四十九頁(yè)，共73頁(yè)。步長(zhǎng)步長(zhǎng) 的選取的選取: (1) 一維尋查一維尋查 ( 對(duì)無(wú)約束問(wèn)題對(duì)無(wú)約束問(wèn)題 ); (2) 計(jì)算計(jì)算(j sun)最小截?cái)嗑嚯x最小截?cái)嗑嚯x ( 對(duì)帶約束的優(yōu)化問(wèn)題對(duì)帶約束的優(yōu)化問(wèn)題, 此法更合適此法更合適 )?？尚蟹较蚍ㄋ?jì)算的子規(guī)劃問(wèn)題可行方向法所計(jì)算的子規(guī)劃問(wèn)題(wnt), 不是求解問(wèn)題不是求解問(wèn)題(wnt)本身本身, 而是做一個(gè)子規(guī)劃而是做一個(gè)子規(guī)劃, 求求 P ( ) !第50頁(yè)/共73頁(yè)第五十頁(yè)，共73頁(yè)。第51頁(yè)/共73頁(yè)第五十一頁(yè)，共73頁(yè)。

14、第52頁(yè)/共73頁(yè)第五十二頁(yè)，共73頁(yè)。第53頁(yè)/共73頁(yè)第五十三頁(yè)，共73頁(yè)。第54頁(yè)/共73頁(yè)第五十四頁(yè)，共73頁(yè)。第55頁(yè)/共73頁(yè)第五十五頁(yè)，共73頁(yè)。第56頁(yè)/共73頁(yè)第五十六頁(yè)，共73頁(yè)。第57頁(yè)/共73頁(yè)第五十七頁(yè)，共73頁(yè)。第58頁(yè)/共73頁(yè)第五十八頁(yè)，共73頁(yè)。第59頁(yè)/共73頁(yè)第五十九頁(yè)，共73頁(yè)。第60頁(yè)/共73頁(yè)第六十頁(yè)，共73頁(yè)。第61頁(yè)/共73頁(yè)第六十一頁(yè)，共73頁(yè)。mjjXg1)(1第62頁(yè)/共73頁(yè)第六十二頁(yè)，共73頁(yè)。第63頁(yè)/共73頁(yè)第六十三頁(yè)，共73頁(yè)。第64頁(yè)/共73頁(yè)第六十四頁(yè)，共73頁(yè)。如圖所示，原規(guī)劃如圖所示，原規(guī)劃(guhu)最優(yōu)解在最優(yōu)解在x*

15、點(diǎn)，而罰函數(shù)點(diǎn)，而罰函數(shù)F(x,M)的最的最優(yōu)解在罰函數(shù)等值線中心優(yōu)解在罰函數(shù)等值線中心x*處，兩者有一定的距離。與內(nèi)點(diǎn)法不處，兩者有一定的距離。與內(nèi)點(diǎn)法不同，同， x*在不可行域中，但處理問(wèn)題的方式有相同之處。在不可行域中，但處理問(wèn)題的方式有相同之處。第65頁(yè)/共73頁(yè)第六十五頁(yè)，共73頁(yè)。因此因此(ync)可以從一個(gè)單調(diào)上升的系數(shù)序列可以從一個(gè)單調(diào)上升的系數(shù)序列Mk中中逐個(gè)選取系數(shù)逐個(gè)選取系數(shù)Mk,求得相應(yīng)目標(biāo)函數(shù)求得相應(yīng)目標(biāo)函數(shù)F(x,Mk)的極小值及設(shè)計(jì)最的極小值及設(shè)計(jì)最優(yōu)點(diǎn)優(yōu)點(diǎn)x(K)的序列的序列x(1), x(2) , x(K)，則原規(guī)劃的最優(yōu)點(diǎn)，則原規(guī)劃的最優(yōu)點(diǎn)x*對(duì)應(yīng)對(duì)應(yīng)于下述

16、極限于下述極限第66頁(yè)/共73頁(yè)第六十六頁(yè)，共73頁(yè)。內(nèi)點(diǎn)法外點(diǎn)法1)設(shè)計(jì)點(diǎn)一定要是可行內(nèi)點(diǎn)，設(shè)計(jì)點(diǎn)一定要是可行內(nèi)點(diǎn)，要控制設(shè)計(jì)點(diǎn)不能超過(guò)約束要控制設(shè)計(jì)點(diǎn)不能超過(guò)約束邊界；邊界；2)內(nèi)點(diǎn)法只能處理不等式約束內(nèi)點(diǎn)法只能處理不等式約束問(wèn)題；問(wèn)題；3)內(nèi)點(diǎn)法求解的極小點(diǎn)序列總內(nèi)點(diǎn)法求解的極小點(diǎn)序列總位于可行域內(nèi)，但總不在約位于可行域內(nèi)，但總不在約束邊界上，對(duì)某些工程設(shè)計(jì)束邊界上，對(duì)某些工程設(shè)計(jì)問(wèn)題，可任選一個(gè)最優(yōu)解作問(wèn)題，可任選一個(gè)最優(yōu)解作為較好的設(shè)計(jì)；為較好的設(shè)計(jì)；4)內(nèi)點(diǎn)法盡管內(nèi)點(diǎn)法盡管F(x,r)和和f(x)的偏的偏導(dǎo)數(shù)階數(shù)相同，但靠近約束導(dǎo)數(shù)階數(shù)相同，但靠近約束邊界處并不連續(xù)。邊界處并不連續(xù)。1)設(shè)計(jì)點(diǎn)的運(yùn)動(dòng)軌跡位于可行設(shè)計(jì)點(diǎn)的運(yùn)動(dòng)軌跡位于可行域外，迭代中向可行域靠近域外，迭代中向可行域靠近，最后趨近最優(yōu)點(diǎn)；，最后趨近最優(yōu)點(diǎn)；2)可以處理不等式約束，也可可以處理不等式約束，也可以處理等式約束；以處理等式約束；3)其極小點(diǎn)序列大部分落在不其極小點(diǎn)序列大部分落在不可行域中，只有當(dāng)某些約束可行域中，只有當(dāng)某些約束滿足時(shí)，可能到達(dá)約束邊界滿足時(shí)，可能到達(dá)約束邊界上，但其