最優(yōu)化方法第四章概要課件

1、第 4 章 約束最優(yōu)化方法 在第2章中已討論過帶有約束的線性規(guī)劃問題，而本章要討論的則是帶有約束的非線性規(guī)劃問題，其一般形式為（4.1） 其中 。這個(gè)問題的求解是指，在容許集內(nèi)找一點(diǎn)，使得對(duì)于任意的，都有第 4 章 約束最優(yōu)化方法 在第2章中已討論過點(diǎn) 稱為問題（4.1）的最優(yōu)解。由于帶有了約束，使得對(duì)約束最優(yōu)化問題（4.1）的求解變得比對(duì)無約束最優(yōu)化問題（3.1）的求解復(fù)雜得多，也困難得多。本章將討論求解約束最優(yōu)化問題常用的兩類最優(yōu)化方法。一類是所謂的容許方向法。它是一種直接處理約束的方法。另一類是所謂的罰函數(shù)法。相對(duì)前者而言，它是一種直接處理約束問題本身的方法，其主要特點(diǎn)是用一系列無約束問

2、題的極小點(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ù)法和乘子法。 點(diǎn) 稱為問題（4.1）的最優(yōu)解。由于帶有了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)性充分條件是指，可使得某個(gè)容許點(diǎn)成為最優(yōu)點(diǎn)的條件。最優(yōu)性條件對(duì)于最優(yōu)化算法的終止判定和最優(yōu)化理論的推證都是至關(guān)

3、重要的。本節(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)性條件。我們將先從僅含等式約束或不等式約束的問題入手，然后自然過渡到一般約束問題。4.1 最優(yōu)性條件 所謂最優(yōu)性條件，就是最優(yōu)化1. 等式約束問題的最優(yōu)性條件考慮僅含等式約束的問題 （4.2） 這個(gè)問題的最優(yōu)性條件與求解方法在微積分中已從理論上得到了解決，這就是Lagrange定理和Lagrange乘子

4、法。定理4.1（Lagrange定理） P217Lagrange乘子法 定義函數(shù)稱為L(zhǎng)agrange函數(shù)，其中稱為L(zhǎng)agrange乘子，則求解等式約束問題（4.2）等價(jià)于求解無約束問題(4.4)1. 等式約束問題的最優(yōu)性條件考慮僅含等式約束的問題（4.2 Lagrange 函數(shù)（4.4)的梯度是其中最優(yōu)性必要條件及 Lagrange 函數(shù)（4.4)的下面的定理給出了（4.2）的最優(yōu)性二階充分條件。定理4.2 P218下面的定理給出了（4.2）的最優(yōu)性二階充分條件。定理4.2 2. 不等式約束問題的最優(yōu)性條件（1）幾何最優(yōu)性條件下面將給出約束問題 （4.7） 的最優(yōu)性條件。設(shè)容許集仍用表示，即以

5、下幾個(gè)概念是討論的基礎(chǔ)。定義4.1 對(duì)于約束問題（4.7），設(shè) 。若使得某個(gè)不等式約束有 ，則該不等式約束稱為是關(guān)于容許點(diǎn) 的起作用約束；否則，若 則該不等式約束稱為是關(guān)于容許點(diǎn)的不起作用約束。 ，2. 不等式約束問題的最優(yōu)性條件（1）幾何最優(yōu)性條件下面將給例如， 不等式約束關(guān)于容許集的任意內(nèi)點(diǎn)都是不起作用約束。只有容許集的邊界點(diǎn)才能使某個(gè)或某些不等式約束變?yōu)槠鹱饔眉s束。定義4.2 設(shè)是中的非空集，且 。對(duì)于，若當(dāng) 時(shí)，對(duì)于，必有 ，則集合稱為以為頂點(diǎn)的錐。若錐是凸集，則稱為凸錐。 例如， 不等式約束關(guān)于容許集的任意內(nèi)點(diǎn)都是不起顯然，由維向量的全部非負(fù)組合構(gòu)成的集合是一個(gè)以原點(diǎn)為頂點(diǎn)的凸錐。由

6、于這樣的凸錐的邊界是（超）平面或直線，所以也稱為由 凸多面錐。張成的定義4.3 設(shè)是中的非空集，且 。對(duì)于非零 向量，若存在，當(dāng)時(shí)，必有 ，則稱為點(diǎn) 的容許方向向量，其方向 稱為點(diǎn)的容許方向。由點(diǎn) 的全部容許方向向量構(gòu)成的的容許方向錐，記作集合稱為點(diǎn)顯然，由維向量的全部非負(fù)組合構(gòu)成的集合是一個(gè)以原點(diǎn)為頂點(diǎn)的凸引理4.3 設(shè) ；并設(shè)當(dāng)時(shí)，在點(diǎn) 處可微，當(dāng)時(shí)， 在點(diǎn)處連續(xù)。若對(duì)于所有的，向量使得，則是點(diǎn)的一個(gè)容許方向向量。證 考慮某個(gè) 。因?yàn)椋允窃邳c(diǎn)處的上升方向。根據(jù)定義1.10，存在 ,例如，引理4.3 設(shè) ；并設(shè)當(dāng)時(shí)，在點(diǎn) 處可微，當(dāng)時(shí)， 在點(diǎn)處連當(dāng)時(shí)，。 再考慮某個(gè)。因?yàn)?，且在點(diǎn) 處連

7、續(xù)，故存在，當(dāng)時(shí)，。取，則當(dāng) 時(shí)，對(duì)于所有的必有 ，即。根據(jù)定義4.3，即是點(diǎn)的容許方向向量。記，則依引理4.3可知，。由這個(gè)引理看到一個(gè)事實(shí)，若僅使某個(gè)約束，例如 ，變成起作用約束，且，而其它約束是不起作用約束，則 就是點(diǎn)的一個(gè)容許 方向向量。換句話說，約束曲面 把整個(gè)空間分成總是指向包含容許集的那一側(cè)。兩部分，梯度，當(dāng)時(shí)，。 再考慮某個(gè)。因?yàn)?，且在點(diǎn) 處連續(xù)，故存在，當(dāng)時(shí)，由點(diǎn)的所有下降方向向量構(gòu)成的集合稱為點(diǎn)下降方向錐。的定理4.4 設(shè)在點(diǎn)處可微，則點(diǎn)下降方向向量必滿足的記，則定理4.4表明，既是點(diǎn)的下降方向錐。顯然是中的半空間。 下面的定理給出的約束問題（4.7）的最優(yōu)性條件是僅借助

8、點(diǎn)集的概念給出的，所以稱為幾何最優(yōu)性條件。定理4.5 在約束問題（4.7）中，若是局部最優(yōu)點(diǎn)，處的容許方向錐和下降方向錐的交集是空集。則點(diǎn)這個(gè)定理表明：在最優(yōu)點(diǎn)處，一定不存在下降容許方向。 由點(diǎn)的所有下降方向向量構(gòu)成的集合稱為點(diǎn)下降方向錐。的定理4.換句話說，在最優(yōu)點(diǎn)處，或者不存在下降方向，或者任何下降方向都不是容許方向。定理4.6 在問題（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.1 P222換句話說，在最優(yōu)點(diǎn)處，或者不存在下降方向，或者任何下降方向都 定理4.5和

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

10、多面錐 的充要條件是，存在非負(fù)數(shù)，使得Farkas引理的幾何解釋：F之中。例如，見上圖，位于中，它與中的任意向量都交成銳角； 不在中，它就不與中的所有向量交成與交成鈍角。銳角或直角，如引理4.8（Gordan） 設(shè)是維向量，使得則不存在向量成立的必要條件是，存在不全為零的非負(fù)數(shù)使得之中。例如，見上圖，位于中，它與中的任意向量都交成銳角； 不Gordan引理的幾何意義：不存在向量使得在幾何上表示向量 的某一非負(fù)線性組合為零向量。例如，在左下圖中，取 ，可使 右下圖中，則找不到不全為零的非負(fù)數(shù)使得。 ；在Gordan引理的幾何意義：不存在向量使得在幾何上表示向量 定理4.9（Fritz-John）

11、 在問題（4.7）中，設(shè)是在點(diǎn)處可微。，使得局部最優(yōu)解，那么，存在不全為零的實(shí)數(shù)（4.9） 其中稱為互補(bǔ)松弛條件。它表明： 若，即，則必有；若，則，即。必有 這個(gè)定理給出了問題（4.7）的一個(gè)最優(yōu)性必要條件。（4.9）稱為問題（4.7）的Fritz-John條件，定理4.9（Fritz-John） 在問題（4.7）中，設(shè)滿足Fritz-John條件的點(diǎn)稱為Fritz-John點(diǎn)。（4.9）中的也稱為L(zhǎng)agrange乘子。 例4.2 考慮約束問題試驗(yàn)證是Fritz-John點(diǎn)，不是Fritz-John點(diǎn)。滿足Fritz-John條件的點(diǎn)稱為Fritz-John點(diǎn)。解 參看例4.1，在點(diǎn)處，。計(jì)算

12、取，則有這表明是Fritz-John點(diǎn)。再考慮點(diǎn)，這時(shí)。計(jì)算解 參看例4.1，在點(diǎn)處，。計(jì)算取，則有這表明是Fritz根據(jù)（4.11），只須說明不存在不全為零的非負(fù)數(shù)，使得事實(shí)上，（4.12）式可寫為（4.12） （4.13a） （4.13b） 由（4.13a）得，而由（4.13b）有 ，這若取非零值，則必異號(hào)。 一關(guān)系表明，這就是說， 不可能存在不全為零的非負(fù)數(shù)使得（4.12）成立， 根據(jù)（4.11），只須說明不存在不全為零的非負(fù)數(shù)，使得事實(shí)上即不是Fritz-John點(diǎn)。 Fritz-John條件僅是判斷容許點(diǎn)是否為最優(yōu)點(diǎn)的必要條件，而不是充分條件。看下面的例題。例4.3 考慮約束問題解

13、顯然是此問題的唯一最優(yōu)點(diǎn)。因?yàn)樵谥本€上，約束 關(guān)于所有容許點(diǎn)的梯度都等于零，所以當(dāng)取時(shí)，總有即不是Fritz-John點(diǎn)。 Fritz（4.14） 如果除去點(diǎn)和點(diǎn)（這兩點(diǎn)的起作用約束不止） ，那么（4.14）說明在直線其余的容許點(diǎn)都滿足Fritz-John條件。但除了其它的點(diǎn)全不是最優(yōu)點(diǎn)。上，外，（3）Kuhn-Tucker條件首先討論一個(gè)例題。例4.4 P227（4.14） 如果除去點(diǎn)和點(diǎn)（這兩點(diǎn)的起作用約束不止） ，那 總結(jié)：Fritz-John條件失效的一個(gè)原因是，起作用約束函數(shù)的梯度線性相關(guān)。為保證 一定在Fritz-John條件中出現(xiàn)，即必須保證 ，這可以通過附加上起作用約束函數(shù)的梯

14、度線性無關(guān)的條件Kuhn和Tucker提出的條件。實(shí)際上，為了保證 ，還可以對(duì)起作用約束函數(shù)的梯度附加其它形式的條件，這樣的一些條件在最優(yōu)化理論中稱為約束品性。定理4.10（Kuhn-Tucker） P227 在起作用約束函數(shù)的梯度線性無關(guān)的前提下，公式（4.15）稱為Kuhn-Tucker條件，而滿足此條件的點(diǎn)稱為Kuhn-Tucker點(diǎn)。 總結(jié)：Fritz-John條件失效的一個(gè)原因 Kuhn-Tucker條件的幾何意義：在公式（4.15）中，刪去不起作用約束項(xiàng)（注意，它們的系數(shù)是 Kuhn-Tucker條件可簡(jiǎn)寫為：存在 ）,，使得 （4.17） 該式在幾何上表示：若 是問題（4.7）的

15、最優(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)。就不滿足 Kuhn-Tucker條件的幾何意義：在公例4.5 說明例4.2中的是KuhnTucker點(diǎn)。解 由例4.2中的求解知是Fritz-John點(diǎn)，且。又是線性無關(guān)的，所以由是Kuhn-Tucker點(diǎn)。定理4.10可知，3. 一般約束問題的最優(yōu)性條件 現(xiàn)在給出一般約束