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

1、會計(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)用第一頁，共73頁。 f ( x ) -目標(biāo)函數(shù)目標(biāo)函數(shù) g i ( X ) 和和 g e ( X ) - 約束條約束條件件第2頁/共73頁第二頁，共73頁。(1) 按約束的有無按約束的有無(yu w)，可分為：，可分為：無約束最優(yōu)化問題無約束最優(yōu)化問題有約束最優(yōu)化問題有約束最優(yōu)化問題準(zhǔn)無約束最優(yōu)化問題準(zhǔn)無約束最優(yōu)化問題第3頁/共73頁第三頁，共73頁。第4頁/共73頁第四頁，共73頁。對于線性規(guī)劃問題，單純形法十分對于線性規(guī)劃問題，單純形法十分(shfn)有效有效無約束非線性規(guī)劃問題無約束非線性規(guī)劃問題不利用梯度的算

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

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

4、搜索方向應(yīng)該和目標(biāo)這說明搜索方向應(yīng)該和目標(biāo)(mbio)函數(shù)負(fù)梯度方向夾函數(shù)負(fù)梯度方向夾角小于角小于90，這樣的方向稱之為下山方向。，這樣的方向稱之為下山方向。第7頁/共73頁第七頁，共73頁。第8頁/共73頁第八頁，共73頁。第9頁/共73頁第九頁，共73頁。第10頁/共73頁第十頁，共73頁。第11頁/共73頁第十一頁，共73頁。第12頁/共73頁第十二頁，共73頁。第13頁/共73頁第十三頁，共73頁。0.618法的基本思想法的基本思想是通過是通過(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頁/共73頁第十四頁，共73頁。第15頁/共73頁第十五頁，共73頁。插值法是一類插值法是一類(y li)重要的一維搜索方法。其基重要的一維搜索方法。其基本思想是在搜索區(qū)間中不斷用低次（通常不超過本思想是在搜索區(qū)間中不斷用低次（通常不超過三次）多項(xiàng)式來近似目標(biāo)函數(shù)，并逐漸用插值多三次）多項(xiàng)式來近似目標(biāo)函數(shù)，并逐漸用插值多項(xiàng)式的極小點(diǎn)來逼近一維搜索問題。當(dāng)函數(shù)具體項(xiàng)式的極小點(diǎn)來逼近一維搜索問題。當(dāng)函數(shù)具體比較好的解析性質(zhì)時

6、，插值法比直接方法效果更比較好的解析性質(zhì)時，插值法比直接方法效果更好。好。第16頁/共73頁第十六頁，共73頁。第17頁/共73頁第十七頁，共73頁。第18頁/共73頁第十八頁，共73頁。第19頁/共73頁第十九頁，共73頁。第20頁/共73頁第二十頁，共73頁。連續(xù)性連續(xù)性收斂性收斂性適用范圍適用范圍0.618法法0階0.618牛頓法牛頓法2階2二點(diǎn)二次插值法二點(diǎn)二次插值法1階1.618割線法割線法1階1.618第21頁/共73頁第二十一頁，共73頁。；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頁/共73頁第二十二頁，共73頁。由此可見，最速下降法走由此可見，最速下降法走的是的是“之之”字形字形最速下降法是一階線性收斂，最速下降法是一階線性收斂，收斂速度較慢。收斂速度較慢。最速下降法與變量長度有關(guān)，最速下降法與變量長度有關(guān)，即與變量尺度即與變量尺度(chd)關(guān)系很關(guā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頁/共73頁第二十三頁，共73頁。第24頁/共73頁第二十四頁，共73頁。第25頁/共73頁第二十五頁，共73頁。第26頁/共73頁第二十六頁，共73頁。第27頁/共73頁第二十七頁，共73頁。第28頁/共73頁第二十八頁，共73頁。第29頁/共73頁第二十九頁，共73頁。第30頁/共73頁第三十頁，共73頁。 這兩個條件這兩個條件(tiojin)的幾何意義是的幾何意義是: 目標(biāo)函目標(biāo)函數(shù)梯度向量和約束條件數(shù)梯度向量和約束條件(tiojin)梯度向量與梯度向量與方向向量之

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

10、，共73頁。第34頁/共73頁第三十四頁，共73頁。第35頁/共73頁第三十五頁，共73頁。第36頁/共73頁第三十六頁，共73頁。第37頁/共73頁第三十七頁，共73頁。第38頁/共73頁第三十八頁，共73頁。Z ( +1) = Z ( ) + P() 步長可以有兩種方法確定步長可以有兩種方法確定: (1) 沿沿 P()( 即即d )向量方向?qū)ο蛄糠较驅(qū)?求一維搜索最小點(diǎn)。求一維搜索最小點(diǎn)。這種方法對無約束條件下比較有效這種方法對無約束條件下比較有效(yuxio)； (2) 利用可行性條件求利用可行性條件求 。按按P() 行進(jìn)到兩條線性約束的交點(diǎn)時行進(jìn)到兩條線性約束的交點(diǎn)時, 首先要計(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)參, 要用要用上一個設(shè)計(jì)點(diǎn)上一個設(shè)計(jì)點(diǎn) Z () 沿沿 P() 進(jìn)行一維搜索求進(jìn)行一維搜索求 Z*, 或者利用或者利用 f ( Z* )T P(+1) = 0, 其中令其中令 Z* = Z () + (+1) P(+1) , 代入式中代入式中, 即可解得即可解得 (+1) .第39頁/共73頁第三十九頁，共73頁。第40頁/共73頁第四十頁，共73頁。第41頁/共

12、73頁第四十一頁，共73頁。第42頁/共73頁第四十二頁，共73頁。第43頁/共73頁第四十三頁，共73頁。第44頁/共73頁第四十四頁，共73頁。第45頁/共73頁第四十五頁，共73頁。上述不等式的解可借助于求解上述不等式的解可借助于求解(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頁/共73頁第四十六頁，共73頁。第47頁/共73頁第四十七頁，共73頁。第48頁/共73頁第四十八頁，共73頁。上述為典型的線性

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

14、第52頁/共73頁第五十二頁，共73頁。第53頁/共73頁第五十三頁，共73頁。第54頁/共73頁第五十四頁，共73頁。第55頁/共73頁第五十五頁，共73頁。第56頁/共73頁第五十六頁，共73頁。第57頁/共73頁第五十七頁，共73頁。第58頁/共73頁第五十八頁，共73頁。第59頁/共73頁第五十九頁，共73頁。第60頁/共73頁第六十頁，共73頁。第61頁/共73頁第六十一頁，共73頁。mjjXg1)(1第62頁/共73頁第六十二頁，共73頁。第63頁/共73頁第六十三頁，共73頁。第64頁/共73頁第六十四頁，共73頁。如圖所示，原規(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*在不可行域中，但處理問題的方式有相同之處。在不可行域中，但處理問題的方式有相同之處。第65頁/共73頁第六十五頁，共73頁。因此因此(ync)可以從一個單調(diào)上升的系數(shù)序列可以從一個單調(diào)上升的系數(shù)序列Mk中中逐個選取系數(shù)逐個選取系數(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*對應(yīng)對應(yīng)于下述

16、極限于下述極限第66頁/共73頁第六十六頁，共73頁。內(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)不能超過約束要控制設(shè)計(jì)點(diǎn)不能超過約束邊界；邊界；2)內(nèi)點(diǎn)法只能處理不等式約束內(nèi)點(diǎn)法只能處理不等式約束問題；問題；3)內(nèi)點(diǎn)法求解的極小點(diǎn)序列總內(nèi)點(diǎn)法求解的極小點(diǎn)序列總位于可行域內(nèi)，但總不在約位于可行域內(nèi)，但總不在約束邊界上，對某些工程設(shè)計(jì)束邊界上，對某些工程設(shè)計(jì)問題，可任選一個最優(yōu)解作問題，可任選一個最優(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)動軌跡位于可行設(shè)計(jì)點(diǎn)的運(yùn)動軌跡位于可行域外，迭代中向可行域靠近域外，迭代中向可行域靠近，最后趨近最優(yōu)點(diǎn)；，最后趨近最優(yōu)點(diǎn)；2)可以處理不等式約束，也可可以處理不等式約束，也可以處理等式約束；以處理等式約束；3)其極小點(diǎn)序列大部分落在不其極小點(diǎn)序列大部分落在不可行域中，只有當(dāng)某些約束可行域中，只有當(dāng)某些約束滿足時，可能到達(dá)約束邊界滿足時，可能到達(dá)約束邊界上，但其