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

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

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

稱為問題（4.1）的最優(yōu)解。由于帶有了約束，使得對約束最優(yōu)化問題（4.1）的求解變得比對無約束最優(yōu)化問題（3.1）的求解復(fù)雜得多，也困難得多。本章將討論求解約束最優(yōu)化問題常用的兩類最優(yōu)化方法。一類是所謂的容許方向法。它是一種直接處理約束的方法。另一類是所謂的罰函數(shù)法。相對前者而言，它是一種直接處理約束問題本身的方法，其主要特點(diǎn)是用一系列無約束問題的極小點(diǎn)去逼近約束問題的最優(yōu)點(diǎn)。在4.1節(jié)中將首先討論約束問題的最優(yōu)性條件，為后面算法的終止準(zhǔn)則提供理論依據(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)化問題的目標(biāo)函數(shù)與約束函數(shù)在最優(yōu)點(diǎn)所滿足的充分條件和必要條件。最優(yōu)性必要條件是指，最優(yōu)點(diǎn)應(yīng)該滿足的條件；最優(yōu)性充分條件是指，可使得某個容許點(diǎn)成為最優(yōu)點(diǎn)的條件。最優(yōu)性條件對于最優(yōu)化算法的終止判定和最優(yōu)化理論的推證都是至關(guān)重要的。本節(jié)僅講述最基本的結(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)性條件。設(shè)容許集仍用表示，即以下幾個概念是討論的基礎(chǔ)。定義4.1對于約束問題（4.7），設(shè)

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

，則該不等式約束稱為是關(guān)于容許點(diǎn)

的起作用約束；否則，若

則該不等式約束稱為是關(guān)于容許點(diǎn)的不起作用約束。

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

。對于，若當(dāng)

時，對于，必有

，則集合稱為以為頂點(diǎn)的錐。若錐是凸集，則稱為凸錐。

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

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

。對于非零

向量，若存在，當(dāng)時，必有

，則稱為點(diǎn)

的容許方向向量，其方向

稱為點(diǎn)的容許方向。由點(diǎn)的全部容許方向向量構(gòu)成的的容許方向錐，記作集合稱為點(diǎn)引理4.3設(shè)

；并設(shè)當(dāng)時，在點(diǎn)

處可微，當(dāng)時，

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

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

,例如，當(dāng)時，。

再考慮某個。因為

，且在點(diǎn)

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

時，對于所有的必有

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

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

就是點(diǎn)的一個容許

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

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

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

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

，則，

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

位于凸多面錐

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

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

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

，可使

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

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

其中稱為互補(bǔ)松弛條件。它表明：

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

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

（4.13b）

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

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

一關(guān)系表明，這就是說，

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

即不是Fritz-John點(diǎn)。Fritz-John條件僅是判斷容許點(diǎn)是否為最優(yōu)點(diǎn)的必要條件，而不是充分條件?？聪旅娴睦}。例4.3考慮約束問題解顯然是此問題的唯一最優(yōu)點(diǎn)。因為在直線上，約束

關(guān)于所有容許點(diǎn)的梯度都等于零，所以當(dāng)取時，總有（4.14）

如果除去點(diǎn)和點(diǎn)（這兩點(diǎn)的起作用約束不止）

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

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

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

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

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

）,，使得

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

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

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

確實(shí)是最優(yōu)點(diǎn)。但在

處，不在由

和所張成的凸錐之中，

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