最優(yōu)化方法第四章

第4章約束最優(yōu)化方法在第2章中已討論過帶有約束的線性規(guī)劃問題，而本章要討論的則是帶有約束的非線性規(guī)劃問題，其一般形式為（4.1）其中

。這個問題的求解是指，在容許集內(nèi)找一點，使得對于任意的，都有點

稱為問題（4.1）的最優(yōu)解。由于帶有了約束，使得對約束最優(yōu)化問題（4.1）的求解變得比對無約束最優(yōu)化問題（3.1）的求解復雜得多，也困難得多。本章將討論求解約束最優(yōu)化問題常用的兩類最優(yōu)化方法。一類是所謂的容許方向法。它是一種直接處理約束的方法。另一類是所謂的罰函數(shù)法。相對前者而言，它是一種直接處理約束問題本身的方法，其主要特點是用一系列無約束問題的極小點去逼近約束問題的最優(yōu)點。在4.1節(jié)中將首先討論約束問題的最優(yōu)性條件，為后面算法的終止準則提供理論依據(jù)；在4.2-4.3節(jié)中將討論二種容許方向法，包括Zoutendijk容許方向法、Rosen梯度投影法；在4.6-4.8節(jié)中將討論三種罰函數(shù)法，它們是外部罰函數(shù)法、內(nèi)部罰函數(shù)法和乘子法。

4.1最優(yōu)性條件所謂最優(yōu)性條件，就是最優(yōu)化問題的目標函數(shù)與約束函數(shù)在最優(yōu)點所滿足的充分條件和必要條件。最優(yōu)性必要條件是指，最優(yōu)點應該滿足的條件；最優(yōu)性充分條件是指，可使得某個容許點成為最優(yōu)點的條件。最優(yōu)性條件對于最優(yōu)化算法的終止判定和最優(yōu)化理論的推證都是至關重要的。本節(jié)僅講述最基本的結論。在第2章和第1章中，已經(jīng)分別討論過線性規(guī)劃問題和無約束問題的最優(yōu)性條件。定理2.9是線性規(guī)劃問題的最優(yōu)性充分條件。定理1.15、定理1.17和定理1.18以及推論1.16分別是無約束問題的最優(yōu)性必要條件、充分條件以及充分且必要條件。本節(jié)主要討論一般約束問題的最優(yōu)性條件。我們將先從僅含等式約束或不等式約束的問題入手，然后自然過渡到一般約束問題。1.等式約束問題的最優(yōu)性條件考慮僅含等式約束的問題

（4.2）這個問題的最優(yōu)性條件與求解方法在微積分中已從理論上得到了解決，這就是Lagrange定理和Lagrange乘子法。定理4.1（Lagrange定理）

P217Lagrange乘子法定義函數(shù)稱為Lagrange函數(shù)，其中稱為Lagrange乘子，則求解等式約束問題（4.2）等價于求解無約束問題(4.4)Lagrange函數(shù)（4.4)的梯度是其中最優(yōu)性必要條件及下面的定理給出了（4.2）的最優(yōu)性二階充分條件。定理4.2P2182.不等式約束問題的最優(yōu)性條件（1）幾何最優(yōu)性條件下面將給出約束問題

（4.7）的最優(yōu)性條件。設容許集仍用表示，即以下幾個概念是討論的基礎。定義4.1對于約束問題（4.7），設

。若使得某個不等式約束有

，則該不等式約束稱為是關于容許點

的起作用約束；否則，若

則該不等式約束稱為是關于容許點的不起作用約束。

，例如，不等式約束關于容許集的任意內(nèi)點都是不起作用約束。只有容許集的邊界點才能使某個或某些不等式約束變?yōu)槠鹱饔眉s束。定義4.2設是中的非空集，且

。對于，若當

時，對于，必有

，則集合稱為以為頂點的錐。若錐是凸集，則稱為凸錐。

顯然，由維向量的全部非負組合構成的集合是一個以原點為頂點的凸錐。由于這樣的凸錐的邊界是（超）平面或直線，所以也稱為由

凸多面錐。張成的定義4.3設是中的非空集，且

。對于非零

向量，若存在，當時，必有

，則稱為點

的容許方向向量，其方向

稱為點的容許方向。由點的全部容許方向向量構成的的容許方向錐，記作集合稱為點引理4.3設

；并設當時，在點

處可微，當時，

在點處連續(xù)。若對于所有的，向量使得，則是點的一個容許方向向量。證考慮某個

。因為，所以是在點處的上升方向。根據(jù)定義1.10，存在

,例如，當時，。

再考慮某個。因為

，且在點

處連續(xù)，故存在，當時，。取，則當

時，對于所有的必有

，即。根據(jù)定義4.3，即是點的容許方向向量。記，則依引理4.3可知，。由這個引理看到一個事實，若僅使某個約束，例如

，變成起作用約束，且，而其它約束是不起作用約束，則

就是點的一個容許

方向向量。換句話說，約束曲面

把整個空間分成總是指向包含容許集的那一側。兩部分，梯度，由點的所有下降方向向量構成的集合稱為點下降方向錐。的定理4.4設在點處可微，則點下降方向向量必滿足的記，則定理4.4表明，既是點的下降方向錐。顯然是中的半空間。下面的定理給出的約束問題（4.7）的最優(yōu)性條件是僅借助點集的概念給出的，所以稱為幾何最優(yōu)性條件。定理4.5在約束問題（4.7）中，若是局部最優(yōu)點，處的容許方向錐和下降方向錐的交集是空集。則點這個定理表明：在最優(yōu)點處，一定不存在下降容許方向。

換句話說，在最優(yōu)點處，或者不存在下降方向，或者任何下降方向都不是容許方向。定理4.6在問題（4.7）中，假設：i）是局部最優(yōu)點，ii）在點處可微；當時，在點

可微，當時，在點處連續(xù)。那么，處證根據(jù)引理4.3，若

，則，

從而。又根據(jù)定理4.5，有故必有。例4.1P222定理4.5和定理4.6給出的最優(yōu)性條件僅僅是必要的，而不是充分的。習題4.6和習題4.7可以說明這一點。幾何最優(yōu)性條件直觀易懂，但在實際計算中使用起來并不簡便。以下討論的Fritz-John條件和Kuhn-Tucker條件是經(jīng)常用到的最優(yōu)性條件。（2）Fritz-John條件首先介紹兩個引理，這兩個引理本身在最優(yōu)化理論中處于很重要的地位。引理4.7（Farkas）設和是維向量，則滿足的向量也滿足的充要條件是，存在非負數(shù)，使得Farkas引理的幾何解釋：Farkas引理指出，向量與凸多面錐（個半空間的交集）中任意向量都交成銳角或直角的充要條件是，向量

位于凸多面錐

之中。例如，見上圖，位于中，它與中的任意向量都交成銳角；

不在中，它就不與中的所有向量交成與交成鈍角。銳角或直角，如引理4.8（Gordan）設是維向量，使得則不存在向量成立的必要條件是，存在不全為零的非負數(shù)使得Gordan引理的幾何意義：不存在向量使得在幾何上表示向量

的某一非負線性組合為零向量。例如，在左下圖中，取

，可使

右下圖中，則找不到不全為零的非負數(shù)使得。

；在定理4.9（Fritz-John）在問題（4.7）中，設是在點處可微。，使得局部最優(yōu)解，那么，存在不全為零的實數(shù)（4.9）

其中稱為互補松弛條件。它表明：

若，即，則必有；若，則，即。必有這個定理給出了問題（4.7）的一個最優(yōu)性必要條件。（4.9）稱為問題（4.7）的Fritz-John條件，滿足Fritz-John條件的點稱為Fritz-John點。（4.9）中的也稱為Lagrange乘子。

例4.2考慮約束問題試驗證是Fritz-John點，不是Fritz-John點。解參看例4.1，在點處，。計算取，則有這表明是Fritz-John點。再考慮點，這時。計算根據(jù)（4.11），只須說明不存在不全為零的非負數(shù)，使得事實上，（4.12）式可寫為（4.12）（4.13a）

（4.13b）

由（4.13a）得，而由（4.13b）有

，這若取非零值，則必異號。

一關系表明，這就是說，

不可能存在不全為零的非負數(shù)使得（4.12）成立，

即不是Fritz-John點。Fritz-John條件僅是判斷容許點是否為最優(yōu)點的必要條件，而不是充分條件。看下面的例題。例4.3考慮約束問題解顯然是此問題的唯一最優(yōu)點。因為在直線上，約束

關于所有容許點的梯度都等于零，所以當取時，總有（4.14）

如果除去點和點（這兩點的起作用約束不止）

，那么（4.14）說明在直線其余的容許點都滿足Fritz-John條件。但除了其它的點全不是最優(yōu)點。上，外，（3）Kuhn-Tucker條件首先討論一個例題。例4.4P227總結：Fritz-John條件失效的一個原因是，起作用約束函數(shù)的梯度線性相關。為保證

一定在Fritz-John條件中出現(xiàn)，即必須保證

，這可以通過附加上起作用約束函數(shù)的梯度線性無關的條件——Kuhn和Tucker提出的條件。實際上，為了保證

，還可以對起作用約束函數(shù)的梯度附加其它形式的條件，這樣的一些條件在最優(yōu)化理論中稱為約束品性。定理4.10（Kuhn-Tucker）P227在起作用約束函數(shù)的梯度線性無關的前提下，公式（4.15）稱為Kuhn-Tucker條件，而滿足此條件的點稱為Kuhn-Tucker點。Kuhn-Tucker條件的幾何意義：在公式（4.15）中，刪去不起作用約束項（注意，它們的系數(shù)是

Kuhn-Tucker條件可簡寫為：存在

）,，使得

（4.17）該式在幾何上表示：若是問題（4.7）的最優(yōu)點，則根據(jù)Farkas引理可知，目標函數(shù)在該點的梯度必位于由起作用約束函數(shù)的梯度所張成的凸錐之中。例如，書上圖4-9顯示，在點

處處于由和張成的凸錐之中，因此

滿足Kuhn-Tucker條件，所以它有可能是最優(yōu)點。如圖所示，

確實是最優(yōu)點。但在

處，不在由

和所張成的凸錐之中，

Kuhn-Tucker條件，因此肯定不是最優(yōu)點。就不滿足例4.5說明例4.2中的是Kuhn－Tucker點。解由例4.2中的求解知是Fritz-John點，且。又是線性無關的，所以由是Kuhn-Tucker點。定理4.10可知，3