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

最優(yōu)化方法第四章第一頁(yè)，共二十四頁(yè)，編輯于2023年，星期六點(diǎn)

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

第二頁(yè)，共二十四頁(yè)，編輯于2023年，星期六4.1最優(yōu)性條件

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

（4.2）

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

P217Lagrange乘子法定義函數(shù)稱為L(zhǎng)agrange函數(shù)，其中稱為L(zhǎng)agrange乘子，則求解等式約束問(wèn)題（4.2）等價(jià)于求解無(wú)約束問(wèn)題(4.4)第四頁(yè)，共二十四頁(yè)，編輯于2023年，星期六Lagrange函數(shù)（4.4)的梯度是其中最優(yōu)性必要條件及第五頁(yè)，共二十四頁(yè)，編輯于2023年，星期六下面的定理給出了（4.2）的最優(yōu)性二階充分條件。定理4.2P218第六頁(yè)，共二十四頁(yè)，編輯于2023年，星期六2.不等式約束問(wèn)題的最優(yōu)性條件（1）幾何最優(yōu)性條件下面將給出約束問(wèn)題

（4.7）的最優(yōu)性條件。設(shè)容許集仍用表示，即以下幾個(gè)概念是討論的基礎(chǔ)。定義4.1

對(duì)于約束問(wèn)題（4.7），設(shè)

。若使得某個(gè)不等式約束有

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

的起作用約束；否則，若

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

，第七頁(yè)，共二十四頁(yè)，編輯于2023年，星期六例如，

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

設(shè)是中的非空集，且

。對(duì)于，若當(dāng)

時(shí)，對(duì)于，必有

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

第八頁(yè)，共二十四頁(yè)，編輯于2023年，星期六顯然，由維向量的全部非負(fù)組合構(gòu)成的集合是一個(gè)以原點(diǎn)為頂點(diǎn)的凸錐。由于這樣的凸錐的邊界是（超）平面或直線，所以也稱為由

凸多面錐。張成的定義4.3

設(shè)是中的非空集，且

。對(duì)于非零

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

，則稱為點(diǎn)

的容許方向向量，其方向

稱為點(diǎn)的容許方向。由點(diǎn)的全部容許方向向量構(gòu)成的的容許方向錐，記作集合稱為點(diǎn)第九頁(yè)，共二十四頁(yè)，編輯于2023年，星期六引理4.3

設(shè)

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

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

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

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

,例如，第十頁(yè)，共二十四頁(yè)，編輯于2023年，星期六當(dāng)時(shí)，。

再考慮某個(gè)。因?yàn)?/p>

，且在點(diǎn)

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

時(shí)，對(duì)于所有的必有

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

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

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

方向向量。換句話說(shuō)，約束曲面

把整個(gè)空間分成總是指向包含容許集的那一側(cè)。兩部分，梯度，第十一頁(yè)，共二十四頁(yè)，編輯于2023年，星期六由點(diǎn)的所有下降方向向量構(gòu)成的集合稱為點(diǎn)下降方向錐。的定理4.4

設(shè)在點(diǎn)處可微，則點(diǎn)下降方向向量必滿足的記，則定理4.4表明，既是點(diǎn)的下降方向錐。顯然是中的半空間。

下面的定理給出的約束問(wèn)題（4.7）的最優(yōu)性條件是僅借助點(diǎn)集的概念給出的，所以稱為幾何最優(yōu)性條件。定理4.5

在約束問(wèn)題（4.7）中，若是局部最優(yōu)點(diǎn)，處的容許方向錐和下降方向錐的交集是空集。則點(diǎn)這個(gè)定理表明：在最優(yōu)點(diǎn)處，一定不存在下降容許方向。

第十二頁(yè)，共二十四頁(yè)，編輯于2023年，星期六換句話說(shuō)，在最優(yōu)點(diǎn)處，或者不存在下降方向，或者任何下降方向都不是容許方向。定理4.6

在問(wèn)題（4.7）中，假設(shè)：i）是局部最優(yōu)點(diǎn)，ii）在點(diǎn)處可微；當(dāng)時(shí)，在點(diǎn)

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

，則，

從而。又根據(jù)定理4.5，有故必有。例4.1P222第十三頁(yè)，共二十四頁(yè)，編輯于2023年，星期六

定理4.5和定理4.6給出的最優(yōu)性條件僅僅是必要的，而不是充分的。習(xí)題4.6和習(xí)題4.7可以說(shuō)明這一點(diǎn)。幾何最優(yōu)性條件直觀易懂，但在實(shí)際計(jì)算中使用起來(lái)并不簡(jiǎn)便。以下討論的Fritz-John條件和Kuhn-Tucker條件是經(jīng)常用到的最優(yōu)性條件。（2）Fritz-John條件

首先介紹兩個(gè)引理，這兩個(gè)引理本身在最優(yōu)化理論中處于很重要的地位。引理4.7（Farkas）設(shè)和是維向量，則滿足的向量也滿足第十四頁(yè)，共二十四頁(yè)，編輯于2023年，星期六的充要條件是，存在非負(fù)數(shù)，使得Farkas引理的幾何解釋：Farkas引理指出，向量與凸多面錐（個(gè)半空間的交集）中任意向量都交成銳角或直角的充要條件是，向量

位于凸多面錐

第十五頁(yè)，共二十四頁(yè)，編輯于2023年，星期六之中。例如，見(jiàn)上圖，位于中，它與中的任意向量都交成銳角；

不在中，它就不與中的所有向量交成與交成鈍角。銳角或直角，如引理4.8（Gordan）設(shè)是維向量，使得則不存在向量成立的必要條件是，存在不全為零的非負(fù)數(shù)使得第十六頁(yè)，共二十四頁(yè)，編輯于2023年，星期六Gordan引理的幾何意義：不存在向量使得在幾何上表示向量

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

，可使

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

；在第十七頁(yè)，共二十四頁(yè)，編輯于2023年，星期六定理4.9（Fritz-John）在問(wèn)題（4.7）中，設(shè)是在點(diǎn)處可微。，使得局部最優(yōu)解，那么，存在不全為零的實(shí)數(shù)（4.9）

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

若，即，則必有；若，則，即。必有

這個(gè)定理給出了問(wèn)題（4.7）的一個(gè)最優(yōu)性必要條件。（4.9）稱為問(wèn)題（4.7）的Fritz-John條件，第十八頁(yè)，共二十四頁(yè)，編輯于2023年，星期六滿足Fritz-John條件的點(diǎn)稱為Fritz-John點(diǎn)。（4.9）中的也稱為L(zhǎng)agrange乘子。

例4.2

考慮約束問(wèn)題試驗(yàn)證是Fritz-John點(diǎn)，不是Fritz-John點(diǎn)。第十九頁(yè)，共二十四頁(yè)，編輯于2023年，星期六解參看例4.1，在點(diǎn)處，。計(jì)算取，則有這表明是Fritz-John點(diǎn)。再考慮點(diǎn)，這時(shí)。計(jì)算第二十頁(yè)，共二十四頁(yè)，編輯于2023年，星期六根據(jù)（4.11），只須說(shuō)明不存在不全為零的非負(fù)數(shù)，使得事實(shí)上，（4.12）式可寫為（4.12）（4.13a）

（4.13b）

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

，這若取非零值，則必異號(hào)。

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

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

第二十一頁(yè)，共二十四頁(yè)，編輯于2023年，星期六即不是Fritz-John點(diǎn)。Fritz-John條件僅是判斷容許點(diǎn)是否為最優(yōu)點(diǎn)的必要條件，而不是充分條件?？聪旅娴睦}。例4.3

考慮約束問(wèn)題解顯然是此問(wèn)題的唯一最優(yōu)點(diǎn)。因?yàn)樵谥本€上，約束

關(guān)于所有容許點(diǎn)的梯度都等于零，所以當(dāng)取時(shí)，總有第二十二頁(yè)，共二十四頁(yè)，編輯于2023年，星期六（4.14）

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

，那么（4.14）說(shuō)明在直線其余的容許點(diǎn)都滿足Fritz-John條件。但除了其它的點(diǎn)全不是最優(yōu)點(diǎn)。上，外，（3）Kuhn-Tucker條件首先討論一個(gè)例題。例4.4P227第二十三頁(yè)，共二十四頁(yè)，編輯于2023年，星期六

總結(jié)：Fritz-John條件失效的一個(gè)原因是，起作用約束函數(shù)的梯度線性相關(guān)。為保證

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

，這可以通過(guò)附加上起作用約束函數(shù)的