//Logo Image
最近更新:徐業良(2005-09-11)﹔推薦:徐業良(2005-09-11)
附註:本文為元智大學機械所最佳化設計課程教材。

第四章 最佳化條件與擴展的單調性原則

在建立了最佳化設計模型,且確認了這是一個限制條件完整的模型之後,下一個步驟自然是解出這個模型的最佳解。然而一個基本問題是,怎麼樣的設計點才是我們所要找的“最佳解”?進一步說,最佳解(包括有限制條件及沒有限制條件的狀況下)必須要滿足何種條件?了解最佳解必須要滿足的條件之後,後續才能繼續討論如何設計數值演算法,以搜尋滿足此條件的最佳解,因此本章前半部先要討論所謂「最佳化條件(optimality condition)

本章後半則要利用最佳化條件對先前所介紹的單調性分析法作更深入的討論、擴展、與總結。這裡我們可以看到,單調性原則事實上也可以被看成是最佳化條件的一種形態,是有單調性的最佳化設計模型要滿足最佳化條件時產生的必然結果,而單調性分析法可說是在檢查最佳化設計模型是否有可以滿足最佳化條件的設計點。本章後半將討論這些問題,並介紹所謂的「擴展的單調性分析(extended monotonicity analysis)

有一點要特別注意的是,前面章節的討論中並沒有要求最佳化設計模型中的目標函數或限制條件是連續、可微分的函數,從這一章起到後續討論數值最佳化演算法中所介紹的各種方法,則都假設最佳化設計模型中的目標函數或限制條件是連續、可微分的函數。這項假設,對我們所能處理的最佳化設計問題,尤其是工程最佳化設計問題,其實是一項非常嚴格的限制。

1.     無限制式函數最佳化條件

這一節裡要討論沒有限制條件的最佳化設計模型的最佳化條件。首先我們要複習一下微積分中學過的「泰勒展開式(Taylor’s expansion)」,及一些基本的向量、矩陣的定義。

1.1 泰勒展開式

最佳化條件乃至數值最佳化演算法的推導,常常用到許多「區域近似(local approximation)」的想法,泰勒展開式正是一個十分常用的區域近似方法。

一個單變數的函數f(x),在點x0的泰勒展開式可以寫成如下形式:

                                                                             (1)

當然,這裡的基本假設是這個函數是n次可微分。泰勒展開式以多項式近似f(x),式(1)中高次項越多,泰勒展開式對函數f(x)的近似也越準確,然而計算這些高階導數也將變得十分繁雜,因此實用上我們通常都只考慮一次近似式(2),或二次近似式(3)

                                                                       (2)

                                    (3)

泰勒展開式也可以輕易地擴展到多變數的函數,例如對於一個n變數函數f(x),在點的一次及二次近似式可以表示如下:

                                                                  (4)

            (5)

(4)(5)顯然過度複雜而不容易閱讀,我們也可以把這兩個式子改寫如下簡潔的向量、矩陣形式:

                                                                             (6)

                                                    (7)

其中稱作「梯度向量(gradient vector)H叫做Hessian矩陣」,而則稱作「擾動向量(perturbation vector),三者定義分別為:

                                                                         (8)

                                                             (9)

                                                                                                      (10)

此處黑體字代表向量或矩陣,符號表示“定義為”。另外值得注意的,是Hessian矩陣H是一個對稱矩陣(symmetric matrix)

(6)式和(7)式的向量、矩陣形式展開,即可還原成為(4)(5)這兩個式子。而多變數函數的向量、矩陣泰勒近似式(6)式和(7)式,與單變數函數的近似式(2)式和(3)式的形式非常相似。

考慮以下的函數實例,可能對前面的推導會有更清楚的了解:

◇例題1

       

       

時,,而,故在此點的一次近似式為,二次近似式則為

       

在這個例子中,函數f為一曲面,函數fx0的一次近似式實為此曲面在x0的切平面,而因為f是一二次式,因此泰勒展開式計算出的二次近似式便是函數本身。◇

1.2 無限制式函數區域最小點一次必要條件

由式(6)的一次近似式可知,在一設計點施一擾動,對函數值所造成的變化量

                                                                      (11)

假設f(x)有一「區域最小值(local minimum),則點附近的點函數值都比高,也就是說,對點所作的任何擾動,應該都會造成函數值增加,即

                                                              (12)

然而擾動向量可以是任意向量,如果,我們必然可以找到一個與方向相反的擾動向量,使得,如果要滿足式(12)必須等於零向量。因此對於一個無限制式函數的區域最小值,我們可以得到如下函數值區域最小點的「一次必要條件(first order necessary condition)

◇無限制式函數區域最小值的一次必要條件

若函數有一內部最小點,且為連續可微分,則

                                                                                              (13)

基本邏輯學上,(若PQ)這個敘述,Q稱作P的「必要條件(necessary condition)」,P則稱作Q的「充分條件(sufficient condition)」。例如“若下雨則帶傘”這個敘述,“下雨”是“帶傘”的充分條件(只要下雨就一定會帶傘),而“帶傘”是“下雨”的必要條件(帶傘只是證實下雨的起碼條件)。此外這個敘述為真時,這個敘述並不為真(“若帶傘則下雨”這個敘述是錯誤的),但(若非Q則非P)這個敘述為真(“若沒帶傘則沒下雨”這個敘述是正確的)。

(13)僅是“函數有一內部最小點”的必要條件而非充分條件,即若並不能推論是函數的內部最小點。這可以很容易由圖1中看出,在這個單變數的函數中,一次微分為零的點可能是區域最小值(點A)、區域最大值(點C)、或「鞍點(saddle point)」(點B),因此式(13)通常也叫做「靜止條件(stationary condition),滿足這個條件的設計點也稱作「靜止點(stationary point)」。

1. 一次微分為零可能的三種情況

注意這裡一直提到點A及點C僅為區域最小、最大值,而非「全域最小值(global minimum)或最大值。也就是說函數值僅在該點的附近區域為最小值,而非在變數x整個定義域為最小值,事實上全域最小值在一般函數中是很難證明的。另外鞍點B在此處既非區域最小點,也不是區域最大點。鞍點名稱的由來,可以從在一個二變數的函數,如圖2所示馬鞍狀的函數看出,鞍點D方向(“馬頭”的方向)是區域最小值,在方向(“騎士跨坐”的方向)卻是區域最大值。

2. 馬鞍狀函數與其等高線圖

(13)也可以被用來求無限制條件函數的靜止點,如以下例題2所示。

◇例題2

例題1,令

,此時f有最小值,為。◇

在這個例子中求出的靜止點之後,如何可以證明此點為最小點,而非最大點或鞍點?這便牽涉到泰勒展開式的二次項了。下一節中將進一步討論無限制式函數最小點之二次充分條件。

1.3 無限制式函數最小點之二次充分條件

前面提到,式(13)僅是必要條件,滿足式(13)的靜止點的一次近似式為零。由式(7)的二次近似式可知,在靜止點施一擾動,消去一次近似式之後,得到對函數所造成的擾動值

                                                                (14)

因此如果,靜止點是一個最小點,即Hessian矩陣是一個「正定矩陣(positive definite matrix)時,靜止點是一個最小點。正定矩陣定義及測試方式如下[Strang, 1980]

◇定義1

以下四個測試每一個都是實數對稱矩陣A為正定矩陣的充要條件:

(I) 對於所有非零向量x

(II) A的所有特徵值均大於零。

(III) A的所有次矩陣,...,行列式值均為正。

(IV) A的所有樞(pivot)均為正。◇

所以對於一個無限制式函數的區域最小值,我們可以得到如下函數值區域最小點的「二次充分條件(second order sufficient condition)

◇無限制式函數區域最小值之二次充分條件

若在函數靜止點Hessian矩陣為一正定矩陣,則為函數之區域最小點。◇

除了正定矩陣之外,Hessian矩陣還可能是「半正定矩陣(semi-definite matrix)」、「負定矩陣(negative definite matrix)」、「半負定矩陣(semi-negative definite matrix)」、或「不定矩陣(indefinite matrix)」。表1列出這些矩陣的定義,以及其所對應靜止點的性質。

1. 不同性質的Hessian矩陣,所對應的靜止點性質

Hessian矩陣

半正定矩陣

負定矩陣

半負定矩陣

不定矩陣

< 0

不一定

特徵值

為正值,但部分為零

全部為負

為負值,但部分為零

部分為正,部分為負

靜止點性質

(valley)

最大點

(ridge)

鞍點

◇例題3

例題1中,為正定矩陣,故靜止點為最小點。◇

通常滿足二次充分條件的靜止點,僅是區域最小點,但如例題3函數的Hessian矩陣為一常數矩陣,即在x為任意值時均為正定矩陣,這樣的函數稱作「凸函數(convex function)。因此凸函數中不存在區域最大點或鞍點,對此函數找出之靜止點必為最小點,且凸函數的靜止點只有一個,自然也必為全域最小點,這是凸函數一個十分特別且重要的性質。

◇例題4

2中,為不定矩陣,故靜止點為鞍點,且在方向是最小值,在方向是最大值。◇

◇作業1

用函數值區域最小點一次必要條件求下列各函數的靜止點,並用二次充分條件來判斷這些靜止點是最大點、最小點,還是鞍點、山脊、或山谷。

(a)   

(b)   

(c)   

(d)   

◇作業2

如圖3所示,設計一個等截面的水溝槽,使其流動速率最大[Stark and Nicholls, 1972]。三個設計變數dbf如圖所示,已知流動速率與水溝槽全邊長成反比,設此水溝槽截面積A1m2

(a)         列出最佳化設計模型,將等式限制條件帶入消去後,以無限制式函數區域最小值的一次必要條件和二次充分條件求此最佳設計。

(b)        證明你求出的最佳點是全域最佳點。

(c)         參數截面積A為一可變動數值,列出最佳點之通式。                     

3. 排水溝槽截面的最佳化設計

2.     有限制式模型之最佳化條件

這一節裡我們考慮有限制式之最佳化設計模型的最佳點,必須要滿足的最佳化條件。在最佳點時,如果所有限制式都是無效的,那麼這是一個內部最佳點,其最佳化條件與無限制式時完全相同。因此這裡我們假設至少有一限制式為有效,也就是說,最佳點對於至少一個設計變數來說是邊界最佳點。此時目標函數在最佳點的梯度向量就不見得為零了,而判別一設計點是否為最佳點,與這個點上的「下降方向(descent direction)」及「可行方向(feasible direction)」有關。

2.1 下降方向與可行方向

在一設計點上的下降方向是可使目標函數值繼續降低的方向。由式(11),在這個下降方向上的擾動,必須使得,因此下降方向可以定義如下:

◇定義2

滿足下式的向量s,稱作函數f的下降方向。

                                                                                          (15)

在一設計點上的可行方向,顧名思義是不會違反限制條件的方向。假設限制條件在設計點上為有效,即,那麼與前面的推導相似,設計點在可行方向上的擾動,必須使得,才不至違反限制條件。因此可行方向的定義如下:

◇定義3

滿足下式的向量s,稱作在的可行方向。

        ,                                                         (16)

如圖4所示,從幾何意義上來考慮,向量是函數f在設計點上函數的梯度向量,是函數值持續增加的方向,而滿足的向量s都落在和向量夾角大於90度的半空間(half space),是函數f的下降方向,而所有下降方向組成的集合,稱作「下降區間(descent sector)。同理,向量是限制條件在設計點上函數的梯度向量,是函數值持續增加的方向,而滿足的向量s都落在和向量夾角大於90度的半空間,是對限制條件的可行方向,而所有可行方向組成的集合,稱作「可行區間(feasible sector)。由設計點往下降區間搜尋,目標函數值才有可能繼續減小,而往可行區間搜尋,才不至違反限制條件。下降區間和可行區間有交集時,由設計點出發可以繼續搜尋到目標函數值更小、且為可行解的設計點,下降區間和可行區間的交集便稱作搜尋的「可用區間(usable sector)

在有限制條件的情況下,如果一個設計點的周圍,搜尋的可用區間為空集合,亦即此設計點的周圍可以使目標函數值下降的擾動方向都會違反某個限制條件,而不違反限制條件的擾動方向又都無法進一步減小目標函數,則這一個設計點是區域最佳點。因此在有限制條件的情況下,最佳點的下降區間及可行區間的交集必定為空集合。瞭解了有限制條件的情況下最佳解的概念,接下來便要討論如何用數學方式描述這個概念。

4. 下降區間、可行區間、及可用區間

2.2 KKT最佳化條件

如圖5所示,在設計點x0只有一個有效的限制條件的情況,下降區間及可行區間的交集為空集合唯一的可能性,是向量和向量恰巧在相反方向,也就是

                                                                                     (17)

5. 只有一個有效限制條件時最佳點的狀況

而在設計點有兩個有效限制條件的狀況,則如圖6所示,區間ABC為可行區域,其中區間AB角度和為90度,區間AC角度和亦為90度。如果落在圖中所示區間B中,則下降區間(和向量夾角大於90度的半空間)與可行區間C仍然有交集,而如果落在圖中所示區間C中,則下降區間與可行區間B仍然有交集,也就是說這兩種狀況能夠找到一個可以使目標函數下降,卻又不違反限制條件的搜尋方向,因此此時設計點並非最佳點。反之如果設計點為最佳點,必須在圖中所示的區間A之內,如此下降區間及可行區間的交集才有可能是空集合。

6. 有二個有效限制條件時最佳點的狀況

在這個狀況下,相反方向之間,此時的線性組合,也就是三個向量滿足

        ,                                                     (18)

(17)(18)可以繼續推展到有n個有效限制條件,包括等式及不等式限制條件的狀況,便得到所謂的Karush-Kuhn-Tucker最佳化條件(KKT條件),正式介紹如下。

前面提到過最佳化設計數學模型能表示成下列標準形式:

        min.  f(x)

        s.t.    ,

                ,

                xX                                                                                      (19)

(19)的最小點x*必須滿足如下之Karush-Kuhn-Tucker最佳化條件:

Karush-Kuhn-Tucker最佳化條件

1.     , ,

2.     ,

        , , .                                                     (20)

KKT最佳化條件是Karush[1939]以及KuhnTucker[1951]先後獨立發表出來的。這組最佳化條件在KuhnTucker發表之後才逐漸受到重視,因此許多書只記載成「Kuhn-Tucker最佳化條件(Kuhn-Tucker conditions)」。

KKT條件第一項是說最佳點必須滿足所有等式及不等式限制條件,也就是說最佳點必須是一個可行解,這一點自然是毋庸置疑的。第二項條件則是前面討論到式(17)(18)的延伸,亦即在最佳點x*f必須是的線性組合都叫作「拉氏乘數(Lagrange multiplier),所不同的是不等式限制條件有方向性,所以每一個都必須大於或等於零,而等式限制條件沒有方向性,所以沒有符號的限制,其符號要視等式限制條件的寫法而定。對於等式限制條件最後得出拉氏乘數的符號,與單調性分析中對等式限制條件處理“賦予其方向性”意義十分接近,在下一節裡會作進一步討論。

最後這個條件,則叫作「互補鬆弛條件(complimentary slackness condition),其意義是說,某一個不等式限制條件及其所對應的拉氏乘數,兩者至少有一個必須等於零。在前面的推導中,f僅必須是有效限制條件梯度向量的線性組合,因此如果限制條件是有效的,= 0,則可大於零,但是如果限制條件是無效的,<0,則必須等於零,也就是說無效的限制條件在KKT最佳化條件中根本不必出現。

KKT條件僅是最佳點的一次必要條件,圖7是一個簡單的滿足此必要條件的設計點,卻並非最佳點的例子。圖中在設計點fg方向正好相反,滿足最佳化條件,然而我們可以輕易找到如點A、點B的目標函數值比設計點小。

7. 滿足KKT條件,卻並非最佳點

有限制條件模型最佳點的二次充分條件推導上十分複雜,故不擬在此討論,有興趣的讀者可參考“Introduction to Optimum Design”[Arora, 1989]“Principles of Optimum Design”[Papalambros and Wilde, 1988]等書籍。

◇作業3

列出以下各問題的最佳化條件,嘗試求出滿足最佳化條件之所有解,繪出其圖形,何者才是最佳解?

(1)    min. 

        s.t.    ,

(2)    min. 

        s.t.    ,

                .

有限制條件時的最佳化條件,乍看之下與第一節中介紹的,無限制式時的最佳化條件,形式上完全不同。但此處可以用另一種形式來表現KKT條件,你可以看到兩者在本質上其實還是十分類似的。

重新考慮式(19)中的最佳化數學模型標準形式,我們可以定義一個新的函數

                                                 (21)

其中lm分別為拉氏乘數所組成的向量,這個新的函數通常也叫作「拉氏函數(Lagrangian)

如果把lm也都看成變數,且假設在式(21)中所有不等式限制條件均為有效(無效的不等式限制條件拉氏乘數為零,此處暫時可視為不存在),則滿足最小點的一次必要條件為

                                                                              (22)

                                                                             (23)

                                           (24)

將這三個式子和KKT條件作一對照,可以發現式(22)(23)即為KKT條件中的第一項,而式(24)則為KKT條件中的第二項!

因此對KKT條件一個簡便的看法,是增加了p個有效的等式限制條件h(x)=0q個有效的不等式限制條件g(x)0之後,最佳化設計模型的目標函數擴大為,變數的數目增加了p+q個,而其最小點的一次必要條件則和無限制式時是相同的

和無限制條件時最小點的一次必要條件類似,KKT條件也可以用來求有限制條件最佳化設計模型之最小點。以下便以先前曾經討論過的一個簡單的線性規劃例子,解釋如何以KKT條件求有限制條件最佳化設計模型之最佳解,尤其要強調的是,當一個解並非最佳解時,其所對應之拉氏乘數有何變化,如何可用KKT條件逐步找到最佳解。

◇例題5

        min. 

        s.t.   

                ,

                                                                                   (25)

定義拉氏函數

(26)

使用KKT條件解最佳解,首先要假設哪些限制條件為有效。在兩個變數的問題,最多只有兩個限制條件為有效。這個問題前面曾經以單調性分析中的有條件式分析解過,最後有效的限制條件是,此處為了說明起見,刻意假設錯誤的一組為有效限制條件,也就是說先假設。此時KKT條件為

       

       

       

                                                                                (27)

(27)中四式聯立求解可得f=0.50。其中,違反KKT條件,這告訴我們限制條件可能並非有效,鬆弛此限制條件應會進一步降低目標函數值。因此接下來假設為有效限制條件,也就是說假設。此時KKT條件為

       

       

       

                                                                               (28)

(28)四式聯立求解可得f=-1.18。這組解滿足被鬆弛的限制條件,且滿足KKT必要條件,故可能為此模型之最佳解。◇

事實上KKT條件一般並不用來求有限制條件最佳化設計模型最佳解,解有限制條件的最佳化設計模型時,通常還是採取後面將要介紹的數值搜尋方法。主要是因為以KKT條件求最小點,在非線性問題中,列出最佳化設計模型的KKT條件後,解多變數非線性聯立方程式是一個相當困難的問題,且可能有重根。另外為了滿足KKT條件中的互補鬆弛條件,我們必須先猜測哪些不等式限制條件為有效,設其拉氏乘數為零,然後才能進一步求解,可能需要解好幾次非線性聯立方程式。最後此法求出之數值解僅滿足最小點之必要條件,仍不見得必定是此模型之最小點。因此通常還是以數值搜尋方法得到一數值解之後,KKT條件才用來檢驗此數值解是否為最佳點

在以KKT條件求最佳解過程中,你也許會提議,何不先用單調性分析法,判別哪些是有效的限制條件?如此為了滿足KKT條件中的互補鬆弛條件所作的“猜測”程序應該會比較有效率。不錯,下一節中我們便可以看到,單調性分析原則事實上可以視為KKT最佳化條件另一種形式,而單調性分析程序是為了滿足KKT條件所推論的必然結果。下一節中將由KKT條件來推導單調性原則,並將單調性原則擴展到不具單調性的變數。

3.     以最佳化條件推導單調性分析原則

這一節裡將由KKT條件出發,重新証明先前介紹的單調性分析原則,說明兩者之間的關係。不過由於KKT條件假設目標函數和限制條件有一次微分,因此略失一般性。先前所介紹的單調性分析法,侷限在有單調性的變數,而HensenJaumard、和Lu[1989],則推導出「擴展的單調性原則(extended monotonicity principles),使單調性分析的應用範圍更為廣泛。擴展的單調性原則也可以很容易由KKT最佳化條件來證明、解釋。

KKT條件僅是最佳點的必要條件而非充分條件。同樣的,單調性分析原則或擴展的單調性分析原則,是建立在“如果最佳化設計模型限制條件完整”的前提下,這些分析原則也只是必要條件而非充分條件。然而一般在對最佳化設計模型作單調性分析時,設計者不可能事先知道最佳化設計模型是否限制良好,事實上單調性分析一個很重要的目的,便是去判斷最佳化設計模型是否限制良好,如果最佳化設計模型本身並非限制條件完整的模型,應用單調性分析很可能導出錯誤的推論。這一節中也將以例題說明,如果將單調性原則運用在限制條件不足的模型上,可能會發生的錯誤,以及檢驗的方法。

3.1 單調性第一原則

在單調性分析裡,對等式限制條件的處理通常是將等號「賦予其方向性」,以有效的不等式限制條件來替代。在KKT條件中,拉氏乘數的差異在於符號限制(),很明顯的,單調性分析中對等式限制條件符號變換的程序,基本上便是對l加上與m同樣的符號限制。在等式限制條件被賦予方向之後,可以用處理不等式限制條件的相同方法來處理。因此在以下的討論裡,我們僅考慮不等式限制條件的情形。

◇單調性第一原則(MP1)

在一個限制條件完整的最佳化設計模型中,每一個在目標函數中單調遞增(遞減)的變數,都必須被至少一個有效的限制條件從下(上)界限住。

【証明】

對一限制條件完整的求最小值問題,至少存在一組變數x,能夠滿足式(20)KKT最佳化條件。而對一個嚴格遞增的變數xi而言,KKT條件中的第二項可寫為

                                                                             (29)

其中。但是因為xif中是嚴格遞增的,故。所以要滿足式(29),則至少有一限制條件gk,其對變數xi的一次微分,且。◇

將等式限制條件賦予其方向性的程序,也就是在視的符號,給予正號或負號,以嘗試滿足KKT條件。

同樣的証明也可以用在Hansen等人所提的擴展的單調性第一原則(Extended First Monotonicity Principle)[Hensen, Jaumard, Lu, 1989]

◇擴展的單調性第一原則(EMP1)

f(x1, x2,..., xn)中的xk在定義域X上對函數f是單調的,且所有包括xkgi(x1, x2,..., xn)X上是連續的。那麼不是X=,就是存在一個整體最佳解,在此解上至少有一個有效的限制條件,對xk有與f不同的單調性。

【証明】

在此擴展原則中,當f中的xi是嚴格遞增時,其有效限制條件中的xi可為嚴格遞減或者不具單調性(non-monotonic)。先前證明的最後部分裡,已同時包括此兩種情形。◇

較諸MP1EMP1最大的進展,便是對某一在目標函數中具有單調性的變數而言,其只要求單調性“不同”的有效限制條件,因此把不具單調性的限制條件也包括在內,大大增加了其應用範圍。但是EMP1也只是必要條件而非充分條件,應用EMP1在非限制條件完整的問題時,有可能得到錯誤推論,必須特別注意。下面便舉一個簡單的單變數例子,來說明EMP1應用在非限制條件完整的問題時,如何可能錯誤推論出最大值解。

◇例題6

        min.  x

        s.t.    g(x)=

由於變數x在目標函數中為嚴格遞增,從EMP1可得知限制條件g(x)是有效的限制條件。令g(x)=0,可得x=2。然而x=2是此問題的最大值解而非最小值解,求函數f最小值時,變數x會一直變小,直到違反了集合限制條件(x>0),故此例題實為限制條件不足的問題。◇

在這個例題中,我們依照EMP1的推論,結果卻得到一組最大值解。探討其原因,在EMP1的證明中,我們需要為負值,以滿足KKT條件,在這個例題中,因為g(x)是非單調性函數,所以可能為正值,可能為負值,然而在x=2時,,而變數x需小於才為負值。也就是說,因為g(x)是非單調性函數,有可能滿足KKT條件,然而在x=2時的單調性,與滿足KKT條件所需的單調性不符,因此g(x)並非有效的限制條件。在沒有其他限制條件存在的情況下,這個問題是一個限制條件不足的問題。

因此如果以EMP1推導出某非單調性限制條件gj可能為有效時,必須在這個推論下產生的“最佳點”加以檢驗,只有當在最佳解點有正確的單調性符號時,非單調性限制條件gj才能成為有效的限制條件。也就是說,非單調性的限制條件必須有正確的「局部單調性(local monotonicity)」來界限住一個變數,才能成為有效的限制條件

◇例題7

        min. 

        s.t.   

EMP1可推論出限制條件g是有效的,且最佳解點是x*=(0,1)。檢驗在這個點上的局部單調性,,因此對於在目標函數中嚴格遞增的變數x1與嚴格遞減的變數x2,此限制條件有正確對應的單調性,因此EMP1的推論是正確的。◇

3.2 單調性第二原則

先前談到的單調性第二原則,尤其是MP2b,在直覺上並不容易了解,這一小節裡由KKT條件出發重新證明,你可以看到MP2在數學上其實是十分簡單而清楚的。

◇單調性第二原則(Second Monotonicity Principle, MP2)

在一個限制條件完整的最佳化設計模型中,每一個不在目標函數中的單調變數,都必須滿足下列條件之一:

a.     這個變數是不相關的,也就是說,這個變數和其所出現的所有限制條件,都可從問題中刪去。

b.    這個變數是相關的,而且被兩個有效限制條件分別從上和下界限住。

【証明】

在一受良好限制的問題中,至少存在一組變數x,其滿足式(20)的最佳化條件。對於在限制條件中有單調性的非目標變數xi而言,在式(20)的第二個情況可寫為

                                                                                            (30)

因為xi不在目標函數中,,但,所以有兩種情況能滿足式(30)

a.  ,但。也就是說,所有包含非目標變數xi的限制條件都是無效的,變數xi對此問題是不相關的,並且可被刪除。

b. xi在限制條件gk中是嚴格遞增的,且(即gk為有效),則。因此至少必須存在一個限制條件gl,在其中xi是嚴格遞減的且gl為有效),如此才可能滿足式(30)。◇

先前提到,單調性第二原則主要的功能,是在判定一個不在目標函數中的設計變數是否相關。MP2b所推導的限制條件有效性,都可以由應用MP1次同樣推導出來,因此一般不用MP2來推導限制條件的有效性。事實上MP2也只是必要條件,MP2的基本假設也是最佳化設計模型是限制條件完整,若將MP2應用在限制條件不足的最佳化設計模型中,可能會錯誤推論出求得最大解的有效限制條件。接著看底下這個例子:

◇例題8

        min.  x1

        s.t.    g1=-x1+2x2-40

                g2=x1-x2-60

MP1得知,g1對變數x1是有效的,變數x2出現在有效限制條件g1中,因此變數x2在此問題中是相關的。而由MP2b得知,如果此模型限制條件完整,限制條件g1g2對變數x2應都是有效的。令g1=0g2=0聯立求解,可得到(x1,x2)=(16,10)

然而例題6的情況相似,(x1,x2)=(16,10)是此問題的最大值解而非最小值解,這個例題事實上是一個限制條件不足的問題。◇

這種情形可很容易地由KKT條件來做解釋。以此例而言,式(29)可寫成。解此方程組,可得到,此與KKT條件中對於不等式限制條件對應的拉氏乘數符號的要求()不合。觀察式(30),當兩個包含非目標變數的限制條件單調性相反時,兩個負值的拉氏乘數亦可滿足式(30)。也就是說,在MP2推論出滿足KKT條件的“有效”限制條件的最佳解點上,有可能其所對應的拉氏乘數是負的。

前面提到任何從MP2所求得的結論,亦可應用MP1次推導出來,如果不以MP2來判定限制條件的有效性,便可以避免例題8中的問題,MP2則主要用來判斷非目標變數是否和問題相關。

◇例題8(a)

        min.  x1

        s.t.    g1=-x1+2x2-40

                g2=x1-x2-60

MP1得知,g1對變數x1是有效的,消去變數x1及限制條件g1,我們可以得到如下的子問題:

        min.  2x2-4

        s.t.    g2=x2-100

注意在限制條件g2中變數x2的單調性是由遞減變為遞增。再次應用MP1,我們可以結論出這個例題是限制條件不足的問題。◇

Hansen[1989]等人也將單調性第二原則的應用範圍,擴展到非單調性的函數上,其證明與MP2類似,故在此略之。

◇擴展的單調性第二原則(Extended Second Monotonicity Principle, EMP2)

f(x1, x2,..., xn)不包含變數xk,並且所有包含xk的限制條件g(x1, x2,..., xn)X區間上是連續的。那麼不是X=,就是存在一個整體最佳解,在此解上至少有一個有效的限制條件,對xk是非單調遞增的,且至少有一個有效的限制條件,對xk是非單調遞減的。◇

對於一個不在目標函數中的變數而言,EMP2僅要求至少存在一個非單調遞增及一個非單調遞減的有效限制條件。而一個不具單調性的限制條件,同時是“非單調遞增”以及“非單調遞減”的,因此在一限制條件完整的最佳化設計模型中,如果一個非目標變數出現在僅有一個限制條件的模型裡,則若此限制條件對此變數不具單調性,那麼此變數仍然有可能對這個最佳化設計模型是相關的。底下的例題9即是這種情形。

◇例題9

        min.  x1

        s.t.    -x1+(x2-1)2+10

這個問題中,雖然非目標變數x2僅出現在唯一的一個限制條件裡,其在此問題中仍然是相關的,且這個限制條件是有效的。這個問題的最小點為(1,1),在這個最小點上,,所以KKT條件中式(30)仍然能被滿足。◇

這兩小節中討論的重點,可以大略總結如下:

l    當一個非單調的限制條件由EMP1推論得知其為有效時,在最佳解點上應該要檢查看看是否有正確的局部單調性。

l    MP2應當只被用來決定非目標變數是否和問題是相關的,而非推論出限制條件的有限性。

l    如果一個非目標變數出現在僅有一個非單調限制條件的問題中,則此變數對此最佳化問題仍有可能是相關的。

下一節中我們可以看到,先前所討論的內隱式消去法,也可以由KKT最佳化條件出發,作更嚴謹的推導。

3.3 以最佳化條件推導內隱式消去法

內隱式消去法的消去過程也可以從KKT條件推導得到。假設限制條件gp對一個單調變數xq而言是具關鍵性的,令式(29)中的xi=xq,解得限制條件gp的拉氏乘數

                  (31)

將式(31)代回式(29)中,可得

                   (32)

其中即為消去限制條件gp和單調變數xq後,變數xi在目標函數f中單調性的新符號,而則為變數xi在限制條件gj中單調性的新符號。注意這兩個項的形式其實是完全一致的,由這兩個項,我們也可以推導出內隱式消去法的規則:

在消去限制條件gp與變數xq之後,將和有相同的符號,若且唯若

(1)   ,即fxq無關或是gpxi無關。

(2)    有相反的符號時,,即fxixq有相反的單調性,而gpxixq有相同的單調性。

(3)   有相同的符號時,,即fxixq有相同的單調性,而gpxixq有相反的單調性。

注意其中23和先前內隱式消去法推導出的性質相同。另外若xi是非目標變數,,則消去限制條件gp與變數xq之後,fxi的單調性將是

(1)   零,如果在三項中的任一項是零的話;

(2)   負的,如果所有三項皆有正的符號,或者其中兩項有負的符號;

(3)   正的,如果所有三項皆有負的符號,或者其中兩項有正的符號。

如果不在以上幾種情況之內,則消去限制條件gp與變數xq之後各變數的單調性,須視實際函數形式而定,無法光以函數單調性來判別,通常此函數可能根本不具單調性了。

內隱式消去法在單調性分析中是十分重要的,尤其在有效限制條件無法直接代入消去時,內隱式消去法大大增加了單調性分析的應用範圍。內隱式消去法也是在將單調性分析過程電腦化的一個重要關鍵,許多單調性分析的電腦程式均試圖整合符號處理的程式,作外顯形式的消去法,使用內隱式消去法則簡潔、快速得多。

4.     單調性分析程序

這一節裡最後將單調性分析程序總結如下:

(1)    將最佳化設計模型寫成標準形式

(2)    列出單調性分析表

(3)    反覆運用所有單調性原則,將等式限制條件儘可能作賦予其方向性處理。

(4)    檢查所有不在目標函數中的設計變數,運用MP2EMP2,判斷其是否為不相關變數,如是,將此變數與所有包含此變數之限制條件自模型中刪除。

(5)    選擇一個在目標函數中的設計變數,運用MP1EMP1,判斷是否有具關鍵性的限制條件,如是,將此變數與具關鍵性的限制條件自模型中消去得到新的單調性分析表。如使用EMP1,特別標註下來以便檢查其區域單調性。

(6)    在此時單調性表中剩下的設計變數,在目標函數一欄的單調性符號是否均為“i”?如是,單調性分析完成,否則回到步驟2,開始下一個分析循環。如果剩下的設計變數同時有兩個以上具有關鍵性的限制條件,則繼續作有條件式關鍵性分析,否則檢查剩下具有單調性的設計變數是否限制不良或無界限。

(7)   檢查所有具關鍵性限制條件,是否能聯立解出部分設計變數最佳值?

(8)    返回原先的設計問題,探討具單調性的變數為何限制不良或無界限,並將具關鍵性、條件式關鍵性的限制條件轉釋成一般的設計法則。

其中步驟二到步驟五的分析循環,可以寫成如下的「虛擬程式(pseudo code)」,了解這個虛擬程式,應該有助於更嚴謹了解單調性分析程序的邏輯性。

procedure Analysis_Cycle;

  begin

      input: monotonicity table;

      for i =1 to number-of-non-objective-variable do

      begin

           Direct the equality constraint where applicable (MP1, MP2, EMP1, EMP2);

           if  is an irrelevant variable by MP2 then

           begin

                Delete  and the constraints it is in;

                Update monotonicity table;

           end;

      end;

      for i = 1 to number-of-variable do

      begin

           Direct the equality constraint where applicable (MP1, MP2, EMP1, EMP2);

           if  has a critical constraint by MP1 or EMP1 then

           begin

                Eliminate  and the critical constraint;

                Update monotonicity table using implicit elimination;

                if EMP1 was used then mark "check local monotonicity";

           end;

      end;

  end.

◇作業4

以單調性分析法解下列問題(所有變數均為正),如有可能,解出這個問題的數值最佳解。

(1)    min. 

         s.t.    ,

                 ,

                 ,

                 .

(2)    min. 

         s.t.    ,

                 ,

                 .

參考資料

Arora, J. S. 1989. Introduction to Optimum Design, McGraw-Hill, New York.

Hansen, P., Jaumard, B., and Lu, S. H., 1989. “Some Further Results on Monotonicity in Globally Optimal Design.” ASME Journal of Mechanisms, Transmissions, and Automation in Design, Vol. 111, No. 3, pp. 353-361.

Karush, W., 1939. Minimum of Functions of Several Variables with Inequalities as Side Conditions, MS Thesis, Dept. of Mathematics, University of Chicago, Chicago, Illinois.

Kuhn, H. W., and Tucker, A. W., 1951. “Nonlinear Programming.” In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability (J. Neyman ed.). University of California Press, Berkeley, California.

Stark, R. M., and Nichols, R. L., 1972. Mathematical Foundations for Design: Civil Engineering Systems, McGraw-Hill, New York.

Strang, G., 1980. Linear Algebra and Its Applications, 2nd ed, Academic Press, New York.

Papalambros, P. and Wilde, D. J., 1988. Principles of Optimal Design.  Cambridge University Press, Cambridge.