優(yōu)化理論與最優(yōu)控制

優(yōu)化理論與最優(yōu)控制“優(yōu)化”與“最優(yōu)化”

優(yōu)化

“化”—加在名詞或形容詞后構成動詞,表示轉變成某種性質或狀態(tài)。比如：綠化、美化、丑化，自動化，優(yōu)化…

最優(yōu)化（值）

指在一定條件影響下所能得到的最佳值。它是一個相對的概念；不同于數(shù)學上的極值，但在很多情況下可以用最大值或最小值來表示。最優(yōu)化問題的控制方程調整（設計、策略、決策）變量

設計變量的數(shù)目稱為最優(yōu)化設計的維數(shù)。目標函數(shù)

在最優(yōu)化設計中，可將所追求的設計目標（最優(yōu)指標）用設計變量的函數(shù)（解析或隱含）形式表達出來，這一過程稱為建立目標函數(shù)。約束條件

在很多實際問題中，設計變量的取值范圍是有限制的或必須滿足一定的條件。以及其他方面的限制。最優(yōu)化問題的控制方程為：最優(yōu)化問題的數(shù)學模型調整參數(shù)：目標函數(shù):約束條件：X=[x1x2x3…xn]T,XDymin或

ymax=f(X)hv(X)=0,v=1,2,…,pgu(X)0,u=1,2,…,m幾點說明調整（決策、策略）變量

原則應選擇對目標函數(shù)影響大且獨立的變量；通常情況下，調整變量越多，優(yōu)化潛力越大，但優(yōu)化過程也越復雜。目標函數(shù)

單目標函數(shù)：只有一個目標函數(shù)；多目標函數(shù)：有多個目標函數(shù)。約束條件

{顯約束vs

隱約束}、{等式約束vs不等式約束}和{邊界約束vs

性態(tài)約束}。控制方程的解

調整（設計、策略、決策）變量組合vs

目標函數(shù)；最優(yōu)值的相對性與動態(tài)性等。約束條件目標函數(shù)取決于調整變量,而在工程實際問題中調整變量的取值范圍是有限制的或必須滿足一定的條件。

等式約束：對調整變量的約束嚴格，起著降低設計自由度的作用。

不等式約束

分類線性規(guī)劃：若都是調整變量

X的線性函數(shù)；非線性規(guī)劃：若它們不全是調整變量X的線

性函數(shù)；無約束規(guī)劃：

若。舉例說明（Ⅰ）小朋友算數(shù)

1)

2堆蘋果，每堆有3個，問2堆加起來一共有幾個蘋果？若有3堆，1000堆這樣的蘋果呢？

2）9個蘋果，3個小朋友分，問每人分幾個蘋果？若有18個，3000個蘋果呢？觀察到什么現(xiàn)象？發(fā)現(xiàn)什么問題？得到什么結論？舉例說明（Ⅱ）

一簡單的僅有兩個輸入變量x1、x2，一個輸出變量y的工業(yè)過程，即。在工程中，輸入變量即運行（工藝）參數(shù)x1、x2一般都有一定的取值范圍。不妨設其允許取值范圍分別為[a,b]、[c,d]。那么，圖中藍色方框中所有的x1、x2組合都能滿足系統(tǒng)正常運行的要求。

簡單的工業(yè)問題舉例說明（Ⅱ）請問在這無窮多個組合中，哪個組合y能取得最大值或最小值呢？無約束目標函數(shù)的極值點存在條件1

一元函數(shù)

任何一個單值、連續(xù)、可微分的不受任何約束的一元函數(shù)點處有極值的充分必要條件是：

2

二元函數(shù)

若二元函數(shù)點的某個領域內有連續(xù)二階偏導數(shù)，則在該點存在極值的充分必要條件是：且3

多元函數(shù)

n元函數(shù)在點M處存在極值的充分必要條件是：①在點M處函數(shù)的梯度為零向量：②Hessian矩陣為正定或負定：且當最優(yōu)化設計的數(shù)值計算方法1

解析法—間接最優(yōu)化方法

利用數(shù)學分析的方法,根據(jù)目標函數(shù)的變化規(guī)律與函數(shù)極值的關系,求目標函數(shù)的極值點.

尋找極值點

需要求解由目標函數(shù)的偏導數(shù)所組成的方程組或梯度。

然后用Hessian矩陣對所找到的穩(wěn)定點進行判斷，看它是否是最優(yōu)點。

當目標函數(shù)比較簡單時，求解上述方程組且用Hessian矩陣進行判斷并不困難。但當目標函數(shù)比較復雜時，就會遇到麻煩，甚至很難求解各項偏導數(shù)所組成的方程組，更不用說對Hessian矩陣進行判斷時將遇到的困難。數(shù)值計算方法—直接最優(yōu)化方法

它是根據(jù)目標函數(shù)的變化規(guī)律，以適當?shù)牟介L沿著能使目標函數(shù)值下降的方向，逐步向目標函數(shù)值的最優(yōu)點進行探索，逐步逼近到目標函數(shù)的最優(yōu)點。

步驟：①初選一個可能靠近最小點的初始點，從出發(fā)按照一定的原則尋找可行方向和初始步長，向前跨出一步達到點；②得到新點后再選擇一個新的使函數(shù)值迅速下降的方向及適當?shù)牟介L，從點出發(fā)再跨出一步，達到點，并依此類推，一步一步地向前探索并重復數(shù)值計算，最終達到目標函數(shù)的最優(yōu)點。

中間過程中每一步的迭代形式為：

式中：

-第k步迭代計算所得到的點；

-第k步迭代計算的步長；

-第k步迭代計算的探索方向。③每向前跨完一步，都應檢查所得到的新點能否滿足預定的計算精度，即

如滿足，則認為為局部最小點；

否則，應以為新的初始點，按上述方法繼續(xù)跨步探索。幾點討論

迭代過程中探索方向S的選擇

①保證沿此方向進行探索時，目標函數(shù)值是不斷下降的；②應盡可能地使其指向最優(yōu)點，以縮短探索的路程和時間，提高求優(yōu)過程的效率。

迭代的收斂性根據(jù)任意一個迭代式進行計算，不一定都能得到逼近精確解的近似解。①如果能夠計算出逼近精確解的近似解，即近似解序列有極限，則迭代是收斂的。②否則，迭代是發(fā)散的。

對于實際工程問題有時很難判斷其目標函數(shù)的極小值，而只能根據(jù)計算中的具體情況來進行判斷。

如滿足，則認為為局部最小點；

否則，應以為新的初始點，繼續(xù)跨步探索。

判斷是否應終止迭代的依據(jù)有三種形式：

①當設計變量在相鄰兩點之間的移動距離已充分小時，可用相鄰兩點的向量差的模作為終止迭代的判據(jù)：終止迭代的判斷依據(jù)

或用向量的所有坐標分量之差表示：

②當相鄰兩點目標函數(shù)值之差已達充分小時，即移動該步后目標函數(shù)值的下降量已充分小時，可用兩次迭代的目標函數(shù)值之差作為終止迭代的判據(jù)：

上述3種任何一種得到滿足，則認為目標函數(shù)值收斂于該函數(shù)的最小值。

③當?shù)c逼近極值點時，目標函數(shù)在該點的梯度將變得充分小，故目標函數(shù)在迭代點處的梯度達到充分小時，也可作為終止迭代的判據(jù)：幾點討論（2種特殊情況）★函數(shù)變化劇烈★函數(shù)變化緩慢為了防止當函數(shù)變化緩慢時，判據(jù)②雖已得到滿足，而所求得的最優(yōu)點與真正最優(yōu)點仍相距較遠，往往將判據(jù)①、②結合起來使用。

為了防止當函數(shù)變化劇烈時，判據(jù)①雖已得到滿足，而所求得的最優(yōu)值與真正最優(yōu)值仍相差較大；無約束最優(yōu)化方法的特點及應用范圍最優(yōu)化方法特點及應用范圍坐標輪換法(變量輪換法或降維法)不需求導數(shù)，方法易懂，程序設計容易，但迭代過程較長，收斂速度較慢，且問題的維數(shù)n愈多求解效率愈低，適用于n≤10的小型無約束最優(yōu)化問題，當函數(shù)的等值線為圓或為長短軸都平行于坐標軸的橢圓時此法很有效。最速下降法(一階梯度法)效率高于上法，尤其最初幾步迭代函數(shù)值下降很快，但愈靠近極值點愈慢。迭代計算簡單，占用計算機單元少，對初始點的選擇要求低。常與其它方法混用。牛頓法(Newton-Raphson法或二階梯度法)當初始點選得合適時是目前算法中收斂得最快的一種(尤其對二次函數(shù))，但當初始點選擇不當會影響到能否收斂或導致失敗。計算較繁且要求Hessian矩陣是非奇異的。計算量和存貯量都以維數(shù)n的平方(n2)比例增加，故當函數(shù)變量較多和因次較高時不宜采用此法。修正牛頓法(廣義牛頓法)即使初始點選擇不當，此法亦會成功，其它特點與牛頓法相同。共軛梯度法是對最速下降法在收斂速度上的重大改進，其收斂速度比最速下降法大為加快，而計算又比牛頓法大為簡化。計算簡單，所需的存儲量少，收斂速度快，常用于多變量的最優(yōu)化設計。共軛方向法及其改進—Powell法

不需求導數(shù)只需計算函數(shù)值，適用于中、小型問題的無約束最優(yōu)化問題。Powell法是一種求無約束最優(yōu)化問題較為有效的方法，適用于中小型無約束最優(yōu)化問題，但對于多維問題收斂速度較慢。無約束最優(yōu)化方法的特點及應用范圍(續(xù)表)最優(yōu)化方法特點及應用范圍變尺度法(DFP法及BFGS法)為求解無約束極值問題最有效的算法之一，可以用到維數(shù)n≥100的問題。對于高維的大型問題，(n>100)，由于收斂快，效果好，被認為是最好的優(yōu)化方法之一，但計算A(k)的程序較復雜，且需要較大的存貯量。DFP法也存在數(shù)值穩(wěn)定性不夠理想等情況，而BFGS．法則有較好的數(shù)值穩(wěn)定性。單純形法不需求導數(shù)，只需計算函數(shù)值。屬直接求優(yōu)法，這類方法甚至適用于未知目標函數(shù)的數(shù)學表達式而只知道它的具體算法的情況、程序簡單、收斂快、效果好，適用于中小型設計問題。Hooke-Jeeves法程序簡單，當變量較少時比較有效，適應性較強，收斂速度比坐標輪換法有所改善但仍較慢，不適于高維數(shù)的問題。Rosenbrock法可看成是對Hooke-Jeeves法的進一步改善與發(fā)展，比坐標輪換法顯著地提高了迭代效率和解題效能，同樣不適用于高維數(shù)的問題。Marquardt法集中了最速下降法及牛頓法的優(yōu)點，且算法簡單，接近極小點時收斂得非?？?，不需要一維探索。常用于求函數(shù)平方和的極小值的問題。最小二乘法(Gauss-Newton法)常用于求函數(shù)平方和的極小值問題，且不必計算二階偏導數(shù)矩陣，為線性收斂速度。單純形法基本思想：★不需要計算目標函數(shù)的導數(shù)；★實際的最優(yōu)化工程中，目標函數(shù)的導數(shù)往往很難求出甚至根本無法求出。①在n維空間中由n+1個線性獨立的點構成一個凸多面體；②求出這些頂點處的目標函數(shù)值并加以比較，確定它們當中有最大值的點以及函數(shù)值的下降方向，再設法找到一個新的比較好的點替換那個最差點，從而構成新的單純形；③隨著這種取代過程的不斷進行，新的單純形將向著極小點收縮。經(jīng)過一定次數(shù)的迭代，即可得到滿足收斂準則的近似解。

設有一個二維目標函數(shù)，在平面中為線性獨立（不在同一直線上）的三個點，并以它們?yōu)轫旤c構造單純形（三角形）。計算這三個頂點處的函數(shù)值并作比較：若，則說明點最差，最好。故應該拋棄點并形成新的單純形。算法思路：（3種類型的步驟—反射、擴張和壓縮）

為此要找出除以外的所有頂點的形心點，并在和連線的延長線上取一點，使最差點的反射點反射系數(shù)，一般取為1.0關于反射點的選?。孩偃舴瓷潼c的函數(shù)值小于最好點的函數(shù)值，即時，則表明所取的探索方向正確，可進一步擴大效果，繼續(xù)沿向前進行擴張，在更遠處取一點，并使擴展系數(shù)，大小一般在1.2~2.0之間圖示

若，說明擴張有利，就用代替最差點，構造新的單純形；若不成立，則不能擴張。此時，如果則用反射點替換最差點而形成新的單純形。

②若下式成立，即則表示點走得太遠，應該縮回一些，需要進行壓縮，且得到的壓縮點應為：壓縮系數(shù)，常取0.5圖示

若則用壓縮點代替，形成新的單純形③若反射點的函數(shù)值大于最差點的函數(shù)值，即時，應該壓縮得更多些，即將新點壓縮至與之間，這時所得的壓縮點應為：④如果在方向上所有點的函數(shù)值都大于，或式（6）不成立，則不能沿此方向探索。這時應使單純形向最好點進行收縮，即最好點不動，其余各頂點，皆向移近為原距離的一半，由原單純形收縮成新單純形

。

從以上各步得到新的單純形后，再重新開始各步，逐漸縮小單純形直至滿足精度要求為止。0x1x2XhXgXlXcXrXeXsXs’

返回返回單純形法的計算步驟

設目標函數(shù)為n元函數(shù)，即X為n維向量，因此單純形應有n+1個頂點。一般取值范圍為0.5~15.0;構成初試單純形時,h=1.6~1.7.

構造初始單純形時，先在n維空間中選取初始點（盡量靠近最優(yōu)點），然后從出發(fā)沿各坐標軸方向，以步長h找到其余n個頂點；ei0x1x2XhXgXlXg’Xh’

—表示第k輪探索時的最好點,即并令:

—為第k輪探索的第j頂點,其函數(shù)值為;

—表示第k輪探索時所有頂點中函數(shù)值最大的頂點,即最差點:

—為次差點,即比小,但比其余各頂點的函數(shù)值都大;

—為除最差點外,其余所有頂點的形心,其坐標可以按下式計算:式中，i=1,2,

,n為各坐標方向的序號；j為頂點號，或構成初始單純形后，即可進行以下步驟：①計算各頂點的函數(shù)值并進行比較，找出最好點，最差點，次差點，以及除最差點以外其余各頂點的形心。求對形心的反射點：②比較和，如果反射點比最好點還要好，即時，則進行擴張，得擴張點為（按式（2））：③將反射點與次差點比較，若，則用代替最差點，并轉入步驟⑤；若，則用代替后進行壓縮,否則直接進行壓縮，得壓縮點為：

得到擴張點后，如果，則用代替后轉入⑤。否則用

代替轉入⑤。

若，即反射點比最好點差，則轉下一步。⑤進行收斂性檢驗.若則停止迭代并輸出及,否則后轉第①步。④將壓縮點與最差點比較，若，則用代替最差點以后轉入下一步;否則使單純形向最好點收縮,收縮后的單純形頂點為:逐漸縮小單純形直至滿足精度要求為止。單純形程序框圖復合形法

★復合形法是求解約束非線性最優(yōu)化問題的一種重要的直接方法?！锼鼇碓从谟糜谇蠼饧s束非線性最優(yōu)化問題的單純形法，實際上是單純形法在約束問題中的發(fā)展。

初始復合形的產生方法：

設在可行域內先給定復合形的一個初始頂點，則其余個n頂點由下式確定：

—調整變量的解域或上下界；其中:

—為復合形頂點的標號;

—為調整變量的標號；

—為區(qū)間內服從均勻分布的偽隨機數(shù)。這樣產生的頂點雖能滿足調整變量的邊界約束條件，但不一定就能滿足性能約束條件。假定其中等q個點滿足全部約束條件，而其余點不滿足，為了使它們也能滿足，則可先求出所有滿足點的形心點：然后將這些不滿足約束條件的點向形心點靠攏，得新點：只要系數(shù)選擇得當（一般?。?，總可以使新點滿足全部約束條件，即這樣就可求得另外n-q+1個滿足全部約束條件的初始頂點。取得n+1個頂點后便可構成一個有n+1頂點的多面體—復合形。然后如下進行迭代計算：①計算復合形各頂點的目標函數(shù)值，找出其中的最差點：找出次差點:

找出最好點:②計算除最差點外其它各頂點的形心:

或

檢查點的可行性。③如果點在可行域內，則沿方向求反射點:

式中，可取，若為非可行點，則應將值減半，繼續(xù)計算，直至滿足全部約束條件為止。④如果點不在可行域內，為了將點移進可行域內，可在以點和點為界，重新利用偽隨機數(shù)產生n+1個新的頂點，構成新的復合形。此時變量的上下界改為：若，則取

否則相反。重復步驟①、②，直至點進入可行域為止。⑤計算點的目標函數(shù)值，如果時，則用反射點替換最差點組成新的復合形，完成一次迭代并轉入步驟①，否則轉入步驟⑥。

⑥如果則將值減半，重新計算反射點，這時若且為可行點，則轉向步驟⑤；否則應再將值減半，如此反復。如果經(jīng)過若干次減半值的計算并使值已縮小到給定的一個很小的正數(shù)（例如）以下仍無效，則可使復合形向最好點收縮，還可在三點所決定的平面中，將點繞點旋轉某一角度，并向最好點靠攏，得到新的點后構成新的復合形并轉入步驟②，重新進行迭代計算，直到滿足計算精度為止。

⑦若同時滿足收斂準則Ⅰ、Ⅱ時，則停止迭代，并取復合形的最小函數(shù)值的頂點作為最優(yōu)解。復合形程序框圖復合形程序框圖Ⅱ多目標函數(shù)的最優(yōu)化方法★前面介紹的最優(yōu)化方法，可直接用于僅含一個目標函數(shù)的所謂“單目標函數(shù)的最優(yōu)化設計問題”?！锏谠S多實際工程設計問題中，常常期望同時有幾項設計指標都達到最優(yōu)值，這就是所謂“多目標函數(shù)的最優(yōu)化問題”，其數(shù)學模型的一般表達式為:★各個目標f1(X)，f2(X)，…，fn(X)的優(yōu)化往往是互相矛盾的，即不能期望同時達到它們的最優(yōu)解；★甚至有時還會產生完全對立的情況，即對一個目標函數(shù)是優(yōu)點，對另一目標函數(shù)卻是劣點。☆這就需要在各個目標的最優(yōu)解之間進行協(xié)調，相互間作出適當“讓步”，以便取得整體最優(yōu)方案。由此也可以看出多目標函數(shù)的最優(yōu)化問題要比單目標函數(shù)的最優(yōu)化問題復雜得多，求解難度也較大。統(tǒng)一目標法統(tǒng)一目標法的實質就是將控制方程中的各個目標函數(shù)(或稱分目標函數(shù))

f1(X)，f2(X)，…，fn(X)

統(tǒng)一到一個總的“統(tǒng)一目標函數(shù)”

f(X)中，即令的型式，把多目標函數(shù)的最優(yōu)化問題轉變?yōu)閱文繕撕瘮?shù)的最優(yōu)化問題來求解。在極小化“統(tǒng)一目標函數(shù)”

f(X)的過程中，為了使各個分目標函數(shù)能均勻一致地趨向各自的最優(yōu)值，可采用如下的一些方法：加權組合法目標規(guī)劃法功效系數(shù)法乘除法加權組合法又稱線性組合法或加權因子法，即在將各個分目標函數(shù)組合為總的“統(tǒng)一目標函數(shù)”的過程中，引入加權因子，以考慮各個分目標函數(shù)在相對重要程度方面的差異及在量級和量綱上的差異。如第i項分目標函數(shù)fi(X)的加權因子，是一個大于零的數(shù)。在將各個分目標函數(shù)加權組合成總的統(tǒng)一目標函數(shù)的過程中，加權組合法又分為:直接加權法①直接加權法采用直接加權法來建立總的統(tǒng)一目標函數(shù)時，其加權因子wi的選取方法如下：若已知某分目標函數(shù)fi(X)的變動范圍為①直接加權法;②轉化設計指標法。則稱為該指標的的容限，于是可取該項指標的加權因子為這種取法是基于要求在統(tǒng)一目標函數(shù)中的各項指標(分目標函數(shù))趨于在數(shù)量級上達到統(tǒng)一平衡，因此，當某項設計指標的數(shù)值變化范圍愈寬時，其目標的容限就愈大，加權因子就取較小值；而數(shù)值變化范圍愈窄時，目標的容限就愈小，加權因子就取大值，以達到平衡各分目標函數(shù)量級的作用。另一種直接加權方法是把加權因子分為兩部分，即第i項設計指標的加權因子wi為式中

wi1—反映第i項目標(設計指標)相對重要性的加權因子，稱作本征權因子；

wi2—第i項目標的校正權因子，用于調整各目標間在量級差別方面的影響、并在迭代過程中逐步加以校正的加權因子。若用梯度來反映各個分目標函數(shù)fi(X)隨設計變量變化而有不同函數(shù)值的情況，則其校正權因子可取即：

fi(X)的函數(shù)值變化愈快，加權值愈應取小些；反之則應取大些。這樣就可使變化快慢不等的目標一起調整好。②轉化設計指標法先將各項設計指標都轉化為統(tǒng)一的無量綱值，并且將量級也限于某一規(guī)定范圍之內，使目標規(guī)格化，然后再根據(jù)各個目標(設計指標)的重要性用加權因子來組合“統(tǒng)一目標函數(shù)”。例如，若能預計各項設計指標的變動范圍，即已知★則可用右下圖所示的正弦函數(shù)將各項設計指標(分目標函數(shù))都轉換到在0~1的范圍內取值，使各目標規(guī)格化。當然也可以用其它合適的函數(shù)作為轉換函數(shù)?！镛D換函數(shù)中自變量的上下界應與原設計指標的上下界相對應。即0與2π應分別對應于αi及βi，則相應于fi(X)值轉換函數(shù)的自變量值為★令設計指標fi(X)在轉化后為fiT(X)

，則

因此，“統(tǒng)一目標函數(shù)”為

式中的加權因子wi(i=1,2,…,q)，是根據(jù)該項(第i項)設計指標在最優(yōu)化設計中所占的重要程度來確定?！锿ㄟ^上述換算，可使各項設計指標都轉化為無量綱且等量級的一個數(shù)。(2)目標規(guī)劃法先分別求出各個分目標函數(shù)的最優(yōu)值fi(X*)，然后根據(jù)多目標函數(shù)最優(yōu)化設計的總體要求，作適當調整，制定出理想的最優(yōu)值fi(o)

。則統(tǒng)一目標函數(shù)可按如下的平方和法來構成：這意味著當各項分目標函數(shù)分別達到各自的理想最優(yōu)值時，統(tǒng)一目標函數(shù)f(X)

為最小。此法的關鍵在于選擇恰當?shù)膄i(o)

(i=1,2,…,q)值。(3)功效系數(shù)法如果每個分目標函數(shù)fi(X)

都用一個稱為功效系數(shù)ηi

(i=1,2,…,q)并定義于0≤ηi≤1間的函數(shù)來表示該項設計指標的好壞(當ηi=1時