最優(yōu)化模型與算法-基于Python實(shí)現(xiàn) 課件 第3、4章 凸優(yōu)化模型、對(duì)偶理論

凸優(yōu)化模型最優(yōu)化模型與算法——基于Python實(shí)現(xiàn)第三章01優(yōu)化模型大部分優(yōu)化模型可以表示為如下形式(3.1.1)該模型表示在所有滿足及的中尋找函數(shù)的最小值。我們稱為優(yōu)化變量，稱函數(shù)為目標(biāo)函數(shù)，不等式稱為不等式約束，相應(yīng)的函數(shù)稱為不等式約束函數(shù)。方程稱為等式約束，相應(yīng)的函數(shù)稱為等式約束函數(shù)。如果沒(méi)有約束(即)，我們稱問(wèn)題(3.1.1)為無(wú)約束優(yōu)化問(wèn)題。目標(biāo)函數(shù)和所有約束函數(shù)有定義的點(diǎn)的集合，(3.1.2)稱為優(yōu)化問(wèn)題(3.1.1)的定義域。當(dāng)點(diǎn)且滿足約束條件和時(shí)，稱是可行點(diǎn)。3.1.1基本術(shù)語(yǔ)當(dāng)問(wèn)題(3.1.1)至少有一個(gè)可行點(diǎn)時(shí)，我們稱該優(yōu)化問(wèn)題是可行的，否則稱其是不可行的。所有可行點(diǎn)的集合稱為可行集或約束集。問(wèn)題(3.1.1)的最優(yōu)值定義為(3.1.3)我們?cè)试S取值為。如果問(wèn)題不可行，我們有(按慣例，空集的下確界為)。如果存在可行解滿足：當(dāng)時(shí)，，那么，此時(shí)我們稱問(wèn)題(3.1.1)無(wú)下界。如果可行且，我們稱約束的第個(gè)不等式在處起作用。如果，則約束不起作用。如果去掉某個(gè)約束條件不改變可行集，我們稱該約束是冗余的。3.1.1基本術(shù)語(yǔ)最優(yōu)點(diǎn)與局部最優(yōu)點(diǎn)如果

是可行的并且

，稱

為最優(yōu)解。所有最優(yōu)解的集合稱為最優(yōu)解集，記為

(3.1.4)如果問(wèn)題(3.1.1)存在最優(yōu)解，我們稱最優(yōu)值是可達(dá)的，并稱問(wèn)題可解。如果

是空集，我們稱最優(yōu)值是不可達(dá)的。對(duì)于最優(yōu)值不可達(dá)的情況，可以考慮

-次優(yōu)解，即滿足

(其中

)的可行解

。上述最優(yōu)解，或

-次優(yōu)解的概念是在整個(gè)可行域中考慮的。相對(duì)的，稱可行解

為局部最優(yōu)解，如果存在

使

(3.1.5)即

是下面關(guān)于

的優(yōu)化問(wèn)題的解

(3.1.6)直觀上，這意味著點(diǎn)

使

在一點(diǎn)的鄰域且在可行集內(nèi)取到最小值?！叭肿顑?yōu)”常被用來(lái)代替“最優(yōu)”以區(qū)分“局部最優(yōu)”和“最優(yōu)”。在本書(shū)中，最優(yōu)意味著全局最優(yōu)?！啊?.1.1基本術(shù)語(yǔ)一般地，可以采用變量變換的方法將優(yōu)化問(wèn)題進(jìn)行變形，轉(zhuǎn)化為與之等價(jià)的但更加易于求解的優(yōu)化問(wèn)題。變量變換例3.1.1考慮單項(xiàng)式函數(shù)的極小化問(wèn)題，

，其中

表示

，

。該問(wèn)題的目標(biāo)函數(shù)通常不是凸函數(shù)，定義變量

，則

，

。這是一個(gè)凸函數(shù)。設(shè)

是一一映射，其值域包含原問(wèn)題的定義域

，即

。定義函數(shù)

和

為

(3.1.7)考慮關(guān)于

的優(yōu)化問(wèn)題

(3.1.8)稱標(biāo)準(zhǔn)形式問(wèn)題(3.1.1)和問(wèn)題(3.1.8)通過(guò)變量變換或變量代換

相聯(lián)系。這兩個(gè)問(wèn)題明顯等價(jià)：如果

是問(wèn)題(3.1.1)的最優(yōu)解，那么

是問(wèn)題(3.1.8)的最優(yōu)解；如果

是問(wèn)題(3.1.8)的最優(yōu)解，那么

是問(wèn)題(3.1.1)的最優(yōu)解。3.1.2等價(jià)問(wèn)題目標(biāo)函數(shù)與約束函數(shù)的變換例3.1.2最小化范數(shù)。作為一個(gè)簡(jiǎn)單的例子，考慮無(wú)約束的歐幾里得范數(shù)極小化問(wèn)題(3.1.9)其優(yōu)化變量為。因?yàn)榉稊?shù)總是非負(fù)的，所以我們可以等價(jià)地求解問(wèn)題(3.1.10)問(wèn)題(3.1.9)和問(wèn)題(3.1.10)顯然是等價(jià)的，最優(yōu)解相同。但是，這兩個(gè)問(wèn)題是不相同的。例如問(wèn)題(3.1.9)的目標(biāo)函數(shù)在任意滿足的處都是不可微的，但問(wèn)題(3.1.10)的目標(biāo)函數(shù)對(duì)所有的都是可微的。如果令，，在上單調(diào)增大，則等價(jià)于。一般地，可以對(duì)目標(biāo)函數(shù)和約束條件實(shí)施類似的變換。3.1.2等價(jià)問(wèn)題松弛變量要注意等價(jià)于存在滿足。利用這個(gè)變換，我們可以將優(yōu)化問(wèn)題(3.1.1)變形為(3.1.11)其中。這個(gè)問(wèn)題有個(gè)變量，個(gè)不等式約束(關(guān)于的非負(fù)約束)和個(gè)等式約束。新的變量稱為對(duì)應(yīng)原不等式約束的松弛變量。通過(guò)引入松弛變量，可以將每個(gè)不等式約束替換為一個(gè)等式和一個(gè)非負(fù)約束。問(wèn)題(3.1.11)與原標(biāo)準(zhǔn)形式問(wèn)題(3.1.1)是等價(jià)的。是原問(wèn)題(3.1.1)的最優(yōu)解當(dāng)且僅當(dāng)是問(wèn)題(3.1.11)的最優(yōu)解，其中。3.1.2等價(jià)問(wèn)題02凸優(yōu)化模型凸優(yōu)化問(wèn)題的形式如下

(3.2.1)其中

為凸函數(shù)。和一般的標(biāo)準(zhǔn)形式(3.1.1)比較，凸優(yōu)化問(wèn)題有三個(gè)額外的要求：目標(biāo)函數(shù)是凸函數(shù)。不等式約束函數(shù)是凸函數(shù)。等式約束函數(shù)

是仿射函數(shù)。注意到一個(gè)重要的性質(zhì)：凸優(yōu)化問(wèn)題的可行集是凸的，因?yàn)榭尚屑菃?wèn)題定義域

(3.2.2)

(這是一個(gè)凸集合)、

個(gè)凸的水平集

以及

個(gè)超平面

的交集。不失一般性地假設(shè)

。因此，凸優(yōu)化問(wèn)題本質(zhì)上是在一個(gè)凸集合上極小化一個(gè)凸的目標(biāo)函數(shù)。3.2.1標(biāo)準(zhǔn)形式的凸優(yōu)化問(wèn)題凸優(yōu)化問(wèn)題的一個(gè)重要性質(zhì)是其任意局部最優(yōu)解也是全局最優(yōu)解。這一點(diǎn)是凸優(yōu)化模型在實(shí)踐中取得成功的關(guān)鍵。為理解這點(diǎn)，設(shè)

是凸優(yōu)化問(wèn)題的局部最優(yōu)解，即

是可行的并且對(duì)

，有

可行，

(3.2.3)現(xiàn)在假設(shè)

不是全局最優(yōu)解，即存在一個(gè)可行的

使

。顯然

，若該條件不成立，則有

?？紤]由

(3.2.4)給出的點(diǎn)

，我們有

。根據(jù)可行集的凸性，

是可行的。根據(jù)

的凸性，有

(3.2.5)這與式(3.2.3)矛盾。因此不存在滿足

的可行解

，即

是全局最優(yōu)解。對(duì)于一般的非凸優(yōu)化問(wèn)題，局部最優(yōu)解是全局最優(yōu)解這一性質(zhì)未必成立。基于這一性質(zhì)，讀者在建立優(yōu)化模型時(shí)，在可能的情形下，應(yīng)優(yōu)先構(gòu)建凸優(yōu)化模型。否則，經(jīng)典的優(yōu)化算法通常僅能求解得到一個(gè)駐點(diǎn)或局部最優(yōu)點(diǎn)，離全局最優(yōu)點(diǎn)可能很遠(yuǎn)，不能保證應(yīng)用于實(shí)際問(wèn)題的效果。3.2.2局部最優(yōu)解與全局最優(yōu)解可微函數(shù)f0的最優(yōu)性準(zhǔn)則設(shè)凸優(yōu)化問(wèn)題的目標(biāo)函數(shù)

是可微的，對(duì)所有的

，有

(3.2.6)

令

表示其可行集，即

(3.2.7)那么，

是最優(yōu)解當(dāng)且僅當(dāng)

且

(3.2.8)這個(gè)最優(yōu)性準(zhǔn)則可以從幾何上進(jìn)行解釋：如果

，那么

在

處定義了可行集的一個(gè)支撐超平面，如圖3.2.1所示，其中可行集

由陰影表示，

的等值曲線由虛線顯示，點(diǎn)

是最優(yōu)解，

是

在

處的一個(gè)支撐超平面的法向量。3.2.3最優(yōu)性條件圖3.2.1最優(yōu)性條件的幾何解釋最優(yōu)性條件的證明首先假設(shè)

滿足條件(3.2.8)。如果

，根據(jù)(3.2.6)式，我們有

。這表明

是問(wèn)題(3.1.1)的一個(gè)最優(yōu)解。反之，設(shè)

是最優(yōu)解但條件(3.2.8)不成立，則存在

，滿足

(3.2.9)

考慮點(diǎn)

，其中

為參數(shù)。因?yàn)?/p>

在

和

之間的線段上，而可行集是凸集合，因此

可行。對(duì)于較小的正數(shù)t，有

。這證明

不是最優(yōu)的。為說(shuō)明這一點(diǎn)，注意到

(3.2.10)

所以，對(duì)于較小的正數(shù)t，有

。證畢。我們將在后面章節(jié)中深入探討最優(yōu)性條件，在這里考察幾個(gè)簡(jiǎn)單的例子。3.2.3最優(yōu)性條件無(wú)約束優(yōu)化問(wèn)題對(duì)于無(wú)約束凸優(yōu)化問(wèn)題

(即

)，最優(yōu)性條件簡(jiǎn)化為

(3.2.11)這是一個(gè)眾所周知的凸優(yōu)化問(wèn)題的充要條件。有必要考察它是如何從條件(3.2.8)中得到的。設(shè)

為可行解，即

，且對(duì)于所有可行解

，都有

。因?yàn)?/p>

可微，其定義域是開(kāi)集，所以所有充分靠近

的點(diǎn)都是可行的，取

，其中

為參數(shù)。當(dāng)

為小的正數(shù)時(shí)，

是可行的，因此

(3.2.12)

因此

。例3.2.1解析中心?？紤]關(guān)于凸函數(shù)

的無(wú)約束極小化問(wèn)題。

(3.2.13)

其中

表示A的行向量。函數(shù)

可微，因此

是最優(yōu)解的充要條件為

(3.2.14)

條件

即是

。如果

不可行，則

的定義域?yàn)榭铡?.2.3最優(yōu)性條件只含等式約束的問(wèn)題考慮只含等式約束的凸優(yōu)化問(wèn)題。

(3.2.15)

該問(wèn)題的可行集是仿射集。假設(shè)

是上述問(wèn)題的最優(yōu)解，則對(duì)任意滿足

的

，有

(3.2.16)都成立。因?yàn)?/p>

可行，每個(gè)可行解

都可以寫(xiě)作

的形式，其中

是A的零空間的向量，即

，因此，最優(yōu)性條件可表示為

(3.2.17)如果一個(gè)線性函數(shù)在子空間中非負(fù)，則它在子空間上必恒等于零。因此，對(duì)于任意

，我們有

，即

(3.2.18)

由

得，最優(yōu)性條件可表示為

，即存在

，使

(3.2.19)

再加上可行性條件

，便是經(jīng)典的Lagrange乘子最優(yōu)性條件。我們將在后面章節(jié)中更詳細(xì)地研究這一條件。3.2.3最優(yōu)性條件03線性規(guī)劃二戰(zhàn)中，受戰(zhàn)爭(zhēng)資源調(diào)配等問(wèn)題的刺激，運(yùn)籌學(xué)應(yīng)運(yùn)而生。線性規(guī)劃作為一類特殊的凸優(yōu)化問(wèn)題被首先關(guān)注。它也是一只“會(huì)下金蛋的雞”，許多著名的優(yōu)化算法，如內(nèi)點(diǎn)法，首先為求解線性規(guī)劃問(wèn)題而設(shè)計(jì)，隨后在求解其他更一般的凸優(yōu)化問(wèn)題時(shí)也取得了成功。時(shí)至今日，人們已開(kāi)發(fā)了眾多軟件包，可以高效求解大規(guī)模線性規(guī)劃問(wèn)題。當(dāng)目標(biāo)函數(shù)和約束函數(shù)都是仿射函數(shù)時(shí)，相應(yīng)的優(yōu)化問(wèn)題稱為線性規(guī)劃(linearprogram，LP)。線性規(guī)劃的一般形式如下。

(3.3.1)其中

，

。線性規(guī)劃問(wèn)題是特殊的凸優(yōu)化問(wèn)題。通常省略目標(biāo)函數(shù)的常數(shù)

，因?yàn)樗挥绊懽顑?yōu)集。LP的幾何解釋見(jiàn)圖3.3.1，其中，可行集

是多面體，目標(biāo)函數(shù)

是線性函數(shù)，它的等值線是與

正交的超平面(用虛線表示)，點(diǎn)

是最優(yōu)解。3.3線性規(guī)劃圖3.3.1LP的幾何解釋常見(jiàn)的兩種線性規(guī)劃是標(biāo)準(zhǔn)型線性規(guī)劃和不等式線性規(guī)劃。在標(biāo)準(zhǔn)型線性規(guī)劃形式如下。(3.3.2)其中不等式表示是分量的非負(fù)約束。如果LP沒(méi)有等式約束，那么稱這類問(wèn)題為不等式線性規(guī)劃，記為：

(3.3.3)3.3.1標(biāo)準(zhǔn)型線性規(guī)劃和不等式線性規(guī)劃為使用標(biāo)準(zhǔn)型線性規(guī)劃算法，需要將一般的線性規(guī)劃(3.3.1)轉(zhuǎn)化為標(biāo)準(zhǔn)型(3.3.2)。第一步是為不等式引入松弛變量

。

(3.3.4)第二步是將變量

表示為兩個(gè)非負(fù)變量

和

的差，即

。這就得到了下面的線性規(guī)劃

(3.3.5)這是一個(gè)標(biāo)準(zhǔn)型線性規(guī)劃，包含變量

和

。3.3.2線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)型線性規(guī)劃在很多領(lǐng)域都有應(yīng)用，下面給出一個(gè)典型的例子。例3.3.1線性規(guī)劃求解切比雪夫中心考慮在多面體中尋找最大的歐式球問(wèn)題?？梢杂镁€性不等式描述這個(gè)多面體。(3.3.6)最大球的中心稱為多面體的切比雪夫中心，它是多面體內(nèi)部最深處的點(diǎn)，即距離邊界最遠(yuǎn)的點(diǎn)?？梢园亚虮硎緸?3.3.7)這個(gè)問(wèn)題中的變量是中心，半徑為，希望在約束的基礎(chǔ)上能夠最大化。先考慮一個(gè)較簡(jiǎn)單的約束條件，即位于一個(gè)半空間內(nèi)，即(3.3.8)因此(3.3.9)可以將(3.3.9)式寫(xiě)成關(guān)于和的不等式(3.3.10)即由約束不等式?jīng)Q定的球在半空間上的約束可以寫(xiě)成一個(gè)線性不等式。3.3.3線性規(guī)劃應(yīng)用舉例因此

當(dāng)且僅當(dāng)(3.3.10)式對(duì)所有

都成立。切比雪夫中心可以通過(guò)求解下述關(guān)于

和

的線性規(guī)劃來(lái)確定，(3.3.11)考慮下面的線性不等式組定義的多面體P：(3.3.12)實(shí)例代碼3.3.1給出了基于線性規(guī)劃求解該多面體的切比雪夫中心的代碼。多面體及求得的切比雪夫中心，如圖3.3.2所示。圖3.3.2切比雪夫中心3.3.3線性規(guī)劃應(yīng)用舉例04二次規(guī)劃模型數(shù)據(jù)科學(xué)和機(jī)器學(xué)習(xí)中的許多模型，如最小二乘回歸，支持向量機(jī)，均可以化為二次規(guī)劃模型。如果目標(biāo)函數(shù)為凸二次函數(shù)，約束函數(shù)為仿射函數(shù)，那么凸優(yōu)化問(wèn)題(3.2.1)稱為二次規(guī)劃(quadraticprogram，QP)。二次規(guī)劃可以表示為以下形式。(3.4.1)其中。二次規(guī)劃實(shí)際上是在一個(gè)凸多面體上最小化一個(gè)凸二次函數(shù)，如圖3.4.1所示，其中，多面體表示可行集，目標(biāo)函數(shù)的等值線用虛線表示，點(diǎn)是最優(yōu)解。圖3.4.1二次規(guī)劃的幾何圖解3.4二次規(guī)劃模型上述二次規(guī)劃的不等式約束為線性約束，如果不等式約束函數(shù)是凸二次函數(shù)，則二次規(guī)劃拓展為下述形式。(3.4.2)其中。這一問(wèn)題稱為帶二次約束的二次規(guī)劃(quadraticallyconstrainedquadraticprogram，QCQP)。它的可行域是多面體與若干個(gè)橢球相交的部分(當(dāng))。在(3.4.2)式中取，得到二次規(guī)劃的特殊情況──線性規(guī)劃。在(3.4.2)中取，可以發(fā)現(xiàn)QCQP包括二次規(guī)劃，因此也包括線性規(guī)劃。3.4二次規(guī)劃模型最小二乘回歸凸二次函數(shù)的最小化問(wèn)題

(3.4.3)是一個(gè)無(wú)約束的QP。它應(yīng)用于很多領(lǐng)域，并有解析解

，其中

是矩陣

的偽逆。當(dāng)含有線性不等式約束時(shí)，這個(gè)問(wèn)題被稱為帶約束的回歸問(wèn)題或約束最小二乘，不再有簡(jiǎn)單的解析解。下面的例子是變量有上下界的一個(gè)回歸問(wèn)題，也是一個(gè)二次規(guī)劃問(wèn)題。

(3.4.4)多面體之間的距離多面體

和

在

上的歐氏距離定義為

(3.4.5)如果多面體相交，則距離為零。通過(guò)求解下面的二次規(guī)劃可以得到

和

之間的距離，優(yōu)化變量

(3.4.6)

當(dāng)且僅當(dāng)其中一個(gè)多面體為空時(shí)，這個(gè)問(wèn)題是不可行的。當(dāng)且僅當(dāng)多面體相交時(shí)，最優(yōu)值為零，在這種情況下，最優(yōu)解

和

相等(并且是

和

的交點(diǎn))，否則最優(yōu)解

和

分別是

和中彼此最接近的點(diǎn)。3.4.1二次規(guī)劃的例子例3.4.1二次規(guī)劃求多面體間的距離考慮多面體和多面體之間的距離。(3.4.7)(3.4.8)實(shí)例代碼3.4.1給出了基于二次規(guī)劃求解上述兩個(gè)多面體之間距離的代碼。

3.4.1二次規(guī)劃的例子代碼第13行輸出求得的最優(yōu)解為：[5.30e-04，1.00e+00，5.78e-04，2.00e+00]，表示兩個(gè)多面體相距最近的兩個(gè)點(diǎn)近似為

和

。圖3.4.2展示了這兩個(gè)多面體及其最相距最近的兩個(gè)點(diǎn)。圖3.4.2二次規(guī)劃求多面體間的距離結(jié)果圖3.4.1二次規(guī)劃的例子與二次規(guī)劃密切相關(guān)的問(wèn)題是二階錐規(guī)劃(second-orderconeprogram，SOCP)。(3.4.9)其中是優(yōu)化變量，。將如下約束形式稱為二階錐約束(3.4.10)其中。二階錐約束要求仿射函數(shù)位于空間的二階錐上。當(dāng)時(shí)，SOCP(3.4.9)等價(jià)于QCQP。另外，如果，那么SOCP(3.4.9)就退化為線性規(guī)劃問(wèn)題3.4.2二階錐規(guī)劃例3.4.2考慮下面的二階錐規(guī)劃問(wèn)題(3.4.11)我們通過(guò)調(diào)用Cvxopt包求解上述問(wèn)題，見(jiàn)實(shí)例代碼3.4.2，所求得的最優(yōu)解為[5.01e+00，5.77e+00，8.52e+00]。05幾何規(guī)劃幾何規(guī)劃是一類可以轉(zhuǎn)化為凸優(yōu)化問(wèn)題的模型，它在許多實(shí)際問(wèn)題中有廣泛應(yīng)用。稱為關(guān)于x的單項(xiàng)式，，，。多個(gè)單項(xiàng)式的和稱為的多項(xiàng)式。下述關(guān)于多項(xiàng)式和單項(xiàng)式的優(yōu)化問(wèn)題稱為幾何規(guī)劃(geometricprogram，GP)。(3.5.1)其中為多項(xiàng)式，為單項(xiàng)式。該問(wèn)題的定義域?yàn)?，隱式約束為。3.5幾何規(guī)劃有一些形式的問(wèn)題很容易轉(zhuǎn)化為幾何規(guī)劃。如果

是一個(gè)多項(xiàng)式，

是一個(gè)單項(xiàng)式，那么約束

可以表示為

，因?yàn)?/p>

是一個(gè)多項(xiàng)式，這就轉(zhuǎn)化為一個(gè)形如

的約束條件，其中

為多項(xiàng)式，

。類似地，若

和

都是非零單項(xiàng)式函數(shù)，那么我們可以將等式約束

表示為

(因?yàn)?/p>

也是單項(xiàng)式)。另外，如果想要最大化一個(gè)非零的單項(xiàng)式目標(biāo)函數(shù)，可以通過(guò)最小化它的逆實(shí)現(xiàn)。例如下面的問(wèn)題(3.5.2)變量

，含有隱式約束

。將上面的模型進(jìn)行簡(jiǎn)單的轉(zhuǎn)換，就可以得到等價(jià)的標(biāo)準(zhǔn)形式的幾何規(guī)劃。(3.5.3)3.5.1幾何規(guī)劃的擴(kuò)展一般情況下的幾何規(guī)劃不是凸優(yōu)化問(wèn)題，但可以通過(guò)變量變換等方法轉(zhuǎn)化為凸優(yōu)化問(wèn)題。定義變量

，則

。如果

是關(guān)于

的單項(xiàng)式函數(shù)，

，那么

(3.5.4)

其中

。變量變換

可將單項(xiàng)式轉(zhuǎn)換成一個(gè)仿射函數(shù)的指數(shù)函數(shù)(凸函數(shù))。類似地，對(duì)于多項(xiàng)式

(3.5.5)

那么

(3.5.6)

其中

，且

。在變量轉(zhuǎn)換后，多項(xiàng)式變成了仿射函數(shù)的指數(shù)和。幾何規(guī)劃(3.5.1)可以用關(guān)于新變量

的式子等價(jià)表示

(3.5.7)

其中

，

。通過(guò)取對(duì)數(shù)變換，得到如下問(wèn)題。3.5.2幾何規(guī)劃轉(zhuǎn)化為凸優(yōu)化問(wèn)題添加標(biāo)題(3.5.8)由于是凸函數(shù)，是仿射的，所以這是一個(gè)關(guān)于的凸優(yōu)化問(wèn)題，稱其為凸優(yōu)化形式的幾何規(guī)劃，也稱為正項(xiàng)幾何規(guī)劃。注意，多項(xiàng)式幾何規(guī)劃(3.5.1)與凸形式的幾何規(guī)劃(3.5.8)之間的轉(zhuǎn)換不涉及任何計(jì)算，這兩個(gè)問(wèn)題是等價(jià)的。另外，如果多項(xiàng)式目標(biāo)和約束函數(shù)都只有一項(xiàng)，即為單項(xiàng)式，則凸形式的幾何規(guī)劃(3.5.8)簡(jiǎn)化為線性規(guī)劃。因此可以認(rèn)為幾何規(guī)劃是線性規(guī)劃的推廣。3.5.2幾何規(guī)劃轉(zhuǎn)化為凸優(yōu)化問(wèn)題考慮矩陣

，將

映射為

?？s放坐標(biāo)，把變量變換為

，

，其中

為對(duì)角矩陣，

。在新坐標(biāo)下，

?？紤]選擇一種縮放方式，使矩陣

很小。使用Frobenius范數(shù)的平方來(lái)度量矩陣的大小。(3.5.9)其中

。這是關(guān)于d的一個(gè)多項(xiàng)式，因此選擇尺d來(lái)最小化Frobenius范數(shù)的問(wèn)題是一個(gè)無(wú)約束的幾何規(guī)劃。

(3.5.10)變量為d，這個(gè)幾何規(guī)劃中的指數(shù)是

。請(qǐng)讀者嘗試調(diào)用cvxopt包求解上述問(wèn)題對(duì)應(yīng)的凸形式的幾何規(guī)劃。3.5.3幾何規(guī)劃的例子06廣義不等式約束若不等式約束函數(shù)為向量值，并在約束中使用廣義不等式，可以得到標(biāo)準(zhǔn)型凸優(yōu)化問(wèn)題(3.2.1)的一個(gè)重要的推廣。(3.6.1)其中

是點(diǎn)錐，

是

-凸錐。把這個(gè)問(wèn)題稱為帶有廣義不等式約束的標(biāo)準(zhǔn)型凸優(yōu)化問(wèn)題。若

，則問(wèn)題(3.6.1)退化為標(biāo)準(zhǔn)型凸優(yōu)化問(wèn)題(3.2.1)。具有廣義不等式約束的優(yōu)化問(wèn)題具有一般凸優(yōu)化問(wèn)題的很多性質(zhì)，例如：可行集、任意水平集、最優(yōu)集均為凸集。問(wèn)題(3.6.1)的任何局部最優(yōu)的點(diǎn)都是全局最優(yōu)點(diǎn)。對(duì)于可微函數(shù)

在3.2.3節(jié)中給出的最優(yōu)性條件仍然成立。實(shí)際上，帶有廣義不等式約束的凸優(yōu)化問(wèn)題通常像普通的凸優(yōu)化問(wèn)題一樣容易求解。3.6廣義不等式約束在帶廣義不等式的凸優(yōu)化問(wèn)題中，最簡(jiǎn)單的是線性錐規(guī)劃問(wèn)題，它有一個(gè)線性目標(biāo)和一個(gè)仿射的不等式約束函數(shù)(因此是

-凸錐)。(3.6.2)當(dāng)

為非負(fù)卦限(錐)時(shí)，錐規(guī)劃問(wèn)題退化為線性規(guī)劃問(wèn)題?？梢园丫€性錐規(guī)劃問(wèn)題視為線性規(guī)劃的一種推廣。類似于線性規(guī)劃，下面的錐規(guī)劃問(wèn)題稱為標(biāo)準(zhǔn)型線性錐規(guī)劃問(wèn)題。(3.6.3)下面的問(wèn)題稱為不等式形式的線性錐規(guī)劃問(wèn)題。(3.6.4)3.6.1錐規(guī)劃問(wèn)題當(dāng)

為

時(shí)，半正定

矩陣聯(lián)合錐規(guī)劃問(wèn)題稱為半定規(guī)劃(Semi-definiteProgramming，SDP)，具有如下形式。(3.6.5)其中

。這里的不等式是一個(gè)線性矩陣不等式。如果

矩陣都是對(duì)角矩陣，那么(3.6.5)中的線性矩陣不等式等價(jià)于

個(gè)線性不等式，SDP(3.6.5)退化為線性規(guī)劃。3.6.2半定規(guī)劃標(biāo)準(zhǔn)型SDP和不等式構(gòu)成的SDP與線性規(guī)劃類似，標(biāo)準(zhǔn)型SDP有線性等式約束，對(duì)變量

有非負(fù)矩陣性束。(3.6.6)其中

，

是

上的一般實(shí)值線性函數(shù)形式。與標(biāo)準(zhǔn)型線性規(guī)劃(3.3.2)比較，在LP和SDP的標(biāo)準(zhǔn)型中，目標(biāo)函數(shù)都是變量的線性函數(shù)，變量有

個(gè)線性等式約束和一個(gè)非負(fù)約束。與不等式線性規(guī)劃(3.3.3)類似，不等式形式的SDP沒(méi)有等式約束，只有一個(gè)線性矩陣不等式約束。(3.6.7)其中

。3.6.2半定規(guī)劃SDP在組合優(yōu)化中具有廣泛的應(yīng)用。許多NP-難組合優(yōu)化問(wèn)題進(jìn)行凸松弛后可以化為半定規(guī)劃問(wèn)題。許多實(shí)例進(jìn)行SDP松弛后，所得到的界是非常緊的。特別是在某些實(shí)例中，SDP松弛問(wèn)題的最優(yōu)解可以轉(zhuǎn)換成原來(lái)問(wèn)題的一個(gè)可行解，并且可以證明這個(gè)可行解具有較好的目標(biāo)函數(shù)值。下面是組合優(yōu)化中應(yīng)用SDP的一個(gè)例子。最大割問(wèn)題的半定規(guī)劃松弛設(shè)

是一個(gè)無(wú)向圖，頂點(diǎn)集合為

，邊的集合為

。設(shè)

為邊

上的權(quán)值，其中

。假設(shè)對(duì)于所有的

，都有

。最大割問(wèn)題是指確定頂點(diǎn)集合N的一個(gè)子集

，使連接頂點(diǎn)子集

到它的余集

(其中

)的所有的邊權(quán)值之和最大。3.6.3組合優(yōu)化中的SDP若，則令，否則，令，可以將最大割問(wèn)題描述為如下的整數(shù)規(guī)劃問(wèn)題。(3.6.8)令，其中。令為權(quán)矩陣，即其第行，第列的元素為，則最大割問(wèn)題可以等價(jià)地描述為(3.6.9)注意到在上述問(wèn)題中第一部分約束等價(jià)于，因此可得(3.6.10)最后注意到矩陣是一個(gè)秩為1的半正定矩陣，如果將這一條件進(jìn)行松弛，即去掉秩為1這一限制，則可以得到如下的最大割問(wèn)題的半定規(guī)劃松弛問(wèn)題。(3.6.11)3.6.3組合優(yōu)化中的SDP已知松弛問(wèn)題(

)為最大割問(wèn)題(

)提供了一個(gè)上界，即：事實(shí)上，可以證明下面的不等式成立這個(gè)結(jié)果表明半定規(guī)劃松弛問(wèn)題的最優(yōu)值與最大割這一NP難問(wèn)題的最優(yōu)值相差不超過(guò)13%。實(shí)例代碼3.6.1給出了半定規(guī)劃求解最大割問(wèn)題的示例，其中有5個(gè)結(jié)點(diǎn)，如圖3-6所示。3.6.3組合優(yōu)化中的SDP圖3.6.1最大割問(wèn)題示意圖實(shí)例代碼3.6.1調(diào)用cvxpy包求解最大割問(wèn)題的半定規(guī)劃松弛問(wèn)題。3.6.3組合優(yōu)化中的SDP實(shí)例代碼3.6.1所求得的最優(yōu)值是-20.1334，最優(yōu)解X為[[1.0.59829309-0.83092504-0.886349620.82789529][0.598293091.-0.9429549-0.901301540.94474659][-0.83092504-0.94295491.0.99410527-0.99998527][-0.88634962-0.901301540.994105271.-0.99350263][0.827895290.94474659-0.99998527-0.993502631.]]從結(jié)果可以看出節(jié)點(diǎn)0,1,4應(yīng)該分為一類，節(jié)點(diǎn)2,3分到另一類。謝謝觀看對(duì)偶理論最優(yōu)化模型與算法——基于Python實(shí)現(xiàn)第四章01Lagrange對(duì)偶函數(shù)考慮標(biāo)準(zhǔn)型的優(yōu)化問(wèn)題：(4.1.1)其中，變量

，假設(shè)其定義域

為非空，將該問(wèn)題的最優(yōu)值記作

，我們不對(duì)這個(gè)問(wèn)題作凸性的假設(shè)。Lagrange對(duì)偶性的基本思想是運(yùn)用(4.1.1)中約束條件的加權(quán)求和對(duì)目標(biāo)函數(shù)進(jìn)行擴(kuò)充，從而將約束條件考慮在內(nèi)。問(wèn)題(4.1.1)的Lagrange函數(shù)

定義為：

(4.1.2)

其定義域?yàn)?/p>

。將對(duì)應(yīng)于第

個(gè)不等式約束條件

中的

稱為L(zhǎng)agrange乘子；類似地，

是對(duì)應(yīng)于第

個(gè)等式約束

的Lagrange乘子。向量

和向量

稱為優(yōu)化問(wèn)題(4.1.1)的對(duì)偶變量或Lagrange乘子向量。4.1.1Lagrange函數(shù)定義4.1.1Lagrange對(duì)偶函數(shù)(簡(jiǎn)稱對(duì)偶函數(shù))

定義為L(zhǎng)agrange函數(shù)關(guān)于

的最小值：對(duì)于

，

，(4.1.3)當(dāng)關(guān)于

的Lagrange函數(shù)無(wú)下界時(shí)，其對(duì)偶函數(shù)取值為

即使當(dāng)問(wèn)題(4.1.1)為非凸時(shí)，因?yàn)閷?duì)偶函數(shù)是仿射函數(shù)族

的逐點(diǎn)下確界，所以對(duì)偶函數(shù)是凹函數(shù)。4.1.2Lagrange對(duì)偶函數(shù)對(duì)偶函數(shù)給出了問(wèn)題(4.1.1)的最優(yōu)值

的下界：定理4.1.1對(duì)任意的

和任意的

，

(4.1.4)證明：假設(shè)

是問(wèn)題(4.1.1)的一個(gè)可行點(diǎn)，即滿足

和

，并且

，可得

(4.1.5)因?yàn)榈谝豁?xiàng)求和中的每一項(xiàng)都是非正的，并且第二項(xiàng)求和中的每一項(xiàng)都為零，所以

(4.1.6)

因此

(4.1.7)

因?yàn)?/p>

對(duì)所有的可行點(diǎn)

都成立，故不等式(4.1.4)成立?！啊?.1.3最優(yōu)值的下界圖4.1.1用

并且有一個(gè)不等式約束的簡(jiǎn)單問(wèn)題解釋了不等式(4.1.4)中的下界，實(shí)線表示目標(biāo)函數(shù)

，虛線表示約束函數(shù)

?？尚屑蠟閰^(qū)間[-1,1]，由兩條垂直的點(diǎn)線表示。最優(yōu)點(diǎn)和最優(yōu)值分別是

(如圖中圓點(diǎn)所示)。由點(diǎn)組成的曲線表示當(dāng)

時(shí)的

。由于在可行集合上對(duì)

有

，因此每一個(gè)函數(shù)

的最小值都比

小。圖4.1.1一個(gè)對(duì)偶可行點(diǎn)的下界不等式(4.1.4)成立，但是，只有當(dāng)

且

時(shí)對(duì)偶函數(shù)能夠給出非平凡下界

，即

。因此將

且

的數(shù)對(duì)

稱為對(duì)偶可行的，下節(jié)中將給出更清晰的表述。4.1.3最優(yōu)值的下界在此給出一個(gè)可以推導(dǎo)出Lagrange對(duì)偶函數(shù)的解析表達(dá)式的例子：線性方程的最小二乘解。考慮如下問(wèn)題(4.1.8)其中

。這個(gè)問(wèn)題沒(méi)有不等式約束，只有

個(gè)線性的等式約束。Lagrange

，其定義域?yàn)?/p>

。其對(duì)偶函數(shù)

。因?yàn)?/p>

是關(guān)于

的二次凸函數(shù)，所以可以通過(guò)最優(yōu)性條件

(4.1.9)

找到最小值點(diǎn)

。因此，對(duì)偶函數(shù)

(4.1.10)是一個(gè)定義在

上的凹二次函數(shù)。下界性質(zhì)(4.1.4)表明，對(duì)任意

，有

(4.1.11)4.1.4Lagrange對(duì)偶函數(shù)的例子02Lagrange對(duì)偶問(wèn)題對(duì)于每一組

，

，Lagrange對(duì)偶函數(shù)給出了優(yōu)化問(wèn)題(4.1.1)的最優(yōu)值

的下界，因此能夠得到依賴于某些參數(shù)

的下界。一個(gè)很自然的問(wèn)題是：能夠從Lagrange對(duì)偶函數(shù)中求得的最好的下界是什么？由此產(chǎn)生了下面的優(yōu)化問(wèn)題(4.2.1)這個(gè)問(wèn)題被稱為問(wèn)題(4.1.1)的Lagrange對(duì)偶問(wèn)題。初始問(wèn)題(4.1.1)通常被稱為原問(wèn)題。數(shù)對(duì)

，

和

稱為對(duì)偶可行的。正如名字所示，

對(duì)于對(duì)偶問(wèn)題(4.2.1)是可行的。同時(shí)將問(wèn)題(4.2.1)的最優(yōu)解

稱作對(duì)偶最優(yōu)解或最優(yōu)Lagrange乘子。Lagrange對(duì)偶問(wèn)題(4.2.1)是一個(gè)凸優(yōu)化問(wèn)題，因?yàn)樗畲蠡嫉哪繕?biāo)函數(shù)，而且它的約束是凸函數(shù)。因此，無(wú)論原問(wèn)題(4.1.1)是否是凸的，對(duì)偶問(wèn)題都是凸優(yōu)化問(wèn)題。4.2Lagrange對(duì)偶問(wèn)題上面的例子表明，對(duì)偶函數(shù)的定義域(4.2.2)其維度通常小于。在很多情況下，可以識(shí)別出的仿射包，并且將其描述為線性等式約束的集合。例如，在這些等式約束明確作為約束而給出的情況下，能夠得到一個(gè)有等式約束的優(yōu)化問(wèn)題。下面的例子將闡釋這一點(diǎn)。LP標(biāo)準(zhǔn)型的Lagrange對(duì)偶LP標(biāo)準(zhǔn)型為(4.2.3)其Lagrange對(duì)偶函數(shù)為(4.2.4)嚴(yán)格來(lái)講，LP標(biāo)準(zhǔn)型的Lagrange對(duì)偶問(wèn)題是在的約束下最大化對(duì)偶函數(shù)，(4.2.5)只有當(dāng)時(shí)，是有限的。通過(guò)明確這些等式約束，可以構(gòu)造一個(gè)等價(jià)問(wèn)題：(4.2.6)通過(guò)變換，這個(gè)問(wèn)題等價(jià)地表述為(4.2.7)這就是LP的不等式形式。4.2.1對(duì)偶約束注意這三個(gè)問(wèn)題之間的細(xì)微區(qū)別。LP標(biāo)準(zhǔn)型(4.2.3)的Lagrange對(duì)偶是問(wèn)題(4.2.4)，這與問(wèn)題(4.2.6)和(4.2.7)等價(jià)，但并不相同。問(wèn)題(4.2.6)或問(wèn)題(4.2.7)稱作LP標(biāo)準(zhǔn)型(4.2.3)的Lagrange對(duì)偶。不等式形式LP的Lagrange對(duì)偶同樣地，能夠得到不等式形式LP的Lagrange對(duì)偶問(wèn)題(4.2.8)Lagrange函數(shù)為(4.2.9)所以其對(duì)偶函數(shù)是(4.2.10)一個(gè)線性函數(shù)除了當(dāng)其恒等于零這一特殊情況，其下確界是，所以對(duì)偶函數(shù)可寫(xiě)作(4.2.11)當(dāng)且時(shí)，其對(duì)偶變量是可行的。4.2.1對(duì)偶約束LP的Lagrange對(duì)偶(4.2.8)是對(duì)所有的

最大化

。類似地，可以通過(guò)明確地將對(duì)偶可行性條件作為約束條件包含進(jìn)去，來(lái)重新構(gòu)造對(duì)偶函數(shù)如下(4.2.12)該問(wèn)題正是標(biāo)準(zhǔn)型LP。注意到LP標(biāo)準(zhǔn)型和不等式形式LP以及他們的對(duì)偶函數(shù)之間的對(duì)稱性：LP標(biāo)準(zhǔn)型的對(duì)偶問(wèn)題是一個(gè)只有不等式約束的LP，反之亦然。亦可以證明，問(wèn)題(4.2.12)的Lagrange對(duì)偶問(wèn)題等價(jià)于原問(wèn)題(4.2.8)。4.2.1對(duì)偶約束定理4.2.1Lagrange對(duì)偶問(wèn)題的最優(yōu)值，用來(lái)表示，是能夠從Lagrange對(duì)偶函數(shù)中得到的中最好的下界，即有如下不等式(4.2.13)即使原問(wèn)題是非凸的，該不等式依然成立，這個(gè)性質(zhì)叫作弱對(duì)偶性。這個(gè)性質(zhì)雖然簡(jiǎn)單但是非常重要。當(dāng)和無(wú)限時(shí)，弱對(duì)偶不等式(4.2.13)依然成立。例如，如果原問(wèn)題無(wú)下界，即，則必有，即Lagrange對(duì)偶問(wèn)題是不可行的。相反地，如果對(duì)偶問(wèn)題無(wú)上界，即，則必有，即原問(wèn)題是不可行的。4.2.2弱對(duì)偶性將兩者的差值稱為原問(wèn)題的最優(yōu)對(duì)偶間隙，因?yàn)樗o出了原問(wèn)題的最優(yōu)值與從Lagrange對(duì)偶函數(shù)給出的最優(yōu)下界之間的距離。最優(yōu)對(duì)偶間隙總是非負(fù)的。弱對(duì)偶性有時(shí)可以被用來(lái)尋找難以解決的問(wèn)題的最優(yōu)值下界，因?yàn)槠鋵?duì)偶問(wèn)題總是凸的，并且很多情況下能夠有效求解并找到。例如，考慮雙向分配問(wèn)題，其對(duì)偶問(wèn)題是半正定規(guī)劃，(4.2.14)其中變量。對(duì)于相對(duì)較大的值，比如，這個(gè)問(wèn)題也能被有效解決。最優(yōu)值是雙向分配問(wèn)題的最優(yōu)值的很好的下界。4.2.2弱對(duì)偶性如果等式

(4.2.15)成立，即最優(yōu)對(duì)偶間隙為0，則稱強(qiáng)對(duì)偶性成立。這意味著通過(guò)Lagrange對(duì)偶函數(shù)得到的最優(yōu)下界是緊的。通常情況下，強(qiáng)對(duì)偶性未必成立。如果原問(wèn)題(4.1.1)是凸的，即滿足如下形式(4.2.16)其中

是凸函數(shù)。為了使強(qiáng)對(duì)偶性成立，要求問(wèn)題(4.2.16)的可行域滿足一些假設(shè)條件。這些條件稱為約束規(guī)范。一個(gè)簡(jiǎn)單的約束規(guī)范是Slater條件：存在

使得

(4.2.17)

4.2.3強(qiáng)對(duì)偶性與Slater約束規(guī)范這樣的點(diǎn)有時(shí)被稱為嚴(yán)格可行的，因?yàn)椴坏仁郊s束在嚴(yán)格不等式時(shí)成立。Slater定理表明，當(dāng)Slater條件成立并且問(wèn)題是凸問(wèn)題時(shí)，強(qiáng)對(duì)偶性成立。如果一些不等式約束函數(shù)

是仿射函數(shù)，Slater條件可以進(jìn)一步弱化。若前

個(gè)約束函數(shù)

是仿射的，則在下面較弱的條件成立時(shí)，強(qiáng)對(duì)偶性成立：存在

，使得

(4.2.18)即仿射不等式不需要與嚴(yán)格不等式同時(shí)成立。Slater條件以及弱化的條件(4.2.18)不僅蘊(yùn)含了凸問(wèn)題的強(qiáng)對(duì)偶性，它還表明當(dāng)

是有限值時(shí)能夠取得對(duì)偶最優(yōu)值，即存在一組對(duì)偶可行的

使得

?？梢宰C明，當(dāng)原問(wèn)題是凸的且Slater條件成立時(shí)，強(qiáng)對(duì)偶性成立。4.2.3強(qiáng)對(duì)偶性與Slater約束規(guī)范03Lagrange對(duì)偶的理解對(duì)一組

，如果

(4.3.1)對(duì)所有

成立，我們稱

為

的鞍點(diǎn)。換言之，

使

最小(對(duì)所有

)并且

使

最大(對(duì)所有

)：

(4.3.2)這表明強(qiáng)最大最小性質(zhì)

(4.3.3)成立，它們的共同值是

。對(duì)于Lagrange對(duì)偶可以發(fā)現(xiàn)，如果

和

是一個(gè)滿足強(qiáng)對(duì)偶性問(wèn)題的原始最優(yōu)點(diǎn)與對(duì)偶最優(yōu)點(diǎn)，則(

,

)構(gòu)成Lagrange函數(shù)的鞍點(diǎn)，反之仍然成立。如果

是Lagrange函數(shù)的鞍點(diǎn)，那么

為原始最優(yōu)解，

為對(duì)偶最優(yōu)解，并且最優(yōu)對(duì)偶間隙為0。4.3.1鞍點(diǎn)可以將最大最小不等式

(4.3.4)和最大最小等式(4.3.3)以及鞍點(diǎn)性質(zhì)，表述為連續(xù)的零和博弈。如果玩家1選擇

，玩家2選擇

，那么玩家1支付數(shù)量為

的報(bào)酬給玩家2。因此玩家1想要最小化

，而玩家2想要最大化

。因?yàn)?/p>

是連續(xù)的，所以這個(gè)博弈稱作連續(xù)博弈。假設(shè)玩家1首先做出決定，隨后玩家2在了解了玩家1的選擇后制定選擇。玩家2想要最大化得到報(bào)酬

，因此會(huì)選擇能夠最大化

的

。最終的報(bào)酬為

，這取決于玩家1做出的選擇(我們?cè)诩僭O(shè)上確界能夠取到，如果不能，最優(yōu)的報(bào)酬能夠任意接近

)。假設(shè)玩家1知道玩家2會(huì)跟隨其做出策略，因此會(huì)選擇

來(lái)使支付給玩家2的報(bào)酬在最壞的情況下盡可能少。因此玩家1選擇

(4.3.5)這將使玩家1向玩家2支付的報(bào)酬為

(4.3.6)4.3.2博弈論解讀4.3.2博弈論解讀現(xiàn)在假設(shè)玩家順序相反：玩家2必須首先選擇

，隨后玩家1在知道

的情況下選擇

。按照同樣的分析，如果玩家們遵循最優(yōu)策略，玩家2會(huì)選擇能夠最大化

的

，這將使玩家1向玩家2支付的報(bào)酬為

(4.3.7)最大最小不等式(4.3.4)表明這樣一個(gè)直觀上明顯的事實(shí)。對(duì)于玩家來(lái)說(shuō)，第二個(gè)進(jìn)行選擇更好，或者說(shuō)，在選擇之前已經(jīng)知道對(duì)手選擇的玩家更有利，即如果玩家1先選擇，那么玩家2得到的報(bào)酬更大。但當(dāng)鞍點(diǎn)性質(zhì)(4.3.3)成立時(shí)，第二個(gè)選擇的玩家實(shí)際上沒(méi)有優(yōu)勢(shì)。如果

是

關(guān)于

和

的鞍點(diǎn)，那么它被稱為博弈的解。

叫作玩家1的最優(yōu)選擇或最優(yōu)策略，

叫作玩家2的最優(yōu)選擇或最優(yōu)策略。在這種情況下，第二個(gè)選擇的玩家沒(méi)有優(yōu)勢(shì)?，F(xiàn)在考慮特殊情況，支付