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

凸優(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ù)。如果沒有約束(即)，我們稱問題(3.1.1)為無約束優(yōu)化問題。目標(biāo)函數(shù)和所有約束函數(shù)有定義的點(diǎn)的集合，(3.1.2)稱為優(yōu)化問題(3.1.1)的定義域。當(dāng)點(diǎn)且滿足約束條件和時，稱是可行點(diǎn)。3.1.1基本術(shù)語當(dāng)問題(3.1.1)至少有一個可行點(diǎn)時，我們稱該優(yōu)化問題是可行的，否則稱其是不可行的。所有可行點(diǎn)的集合稱為可行集或約束集。問題(3.1.1)的最優(yōu)值定義為(3.1.3)我們允許取值為。如果問題不可行，我們有(按慣例，空集的下確界為)。如果存在可行解滿足：當(dāng)時，，那么，此時我們稱問題(3.1.1)無下界。如果可行且，我們稱約束的第個不等式在處起作用。如果，則約束不起作用。如果去掉某個約束條件不改變可行集，我們稱該約束是冗余的。3.1.1基本術(shù)語最優(yōu)點(diǎn)與局部最優(yōu)點(diǎn)如果

是可行的并且

，稱

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

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

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

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

(其中

)的可行解

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

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

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

使

(3.1.5)即

是下面關(guān)于

的優(yōu)化問題的解

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

使

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

，其中

表示

，

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

，則

，

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

是一一映射，其值域包含原問題的定義域

，即

。定義函數(shù)

和

為

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

的優(yōu)化問題

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

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

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

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

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

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

(3.2.1)其中

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

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

(3.2.2)

(這是一個凸集合)、

個凸的水平集

以及

個超平面

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

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

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

是可行的并且對

，有

可行，

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

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

使

。顯然

，若該條件不成立，則有

?？紤]由

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

，我們有

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

是可行的。根據(jù)

的凸性，有

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

的可行解

，即

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

是可微的，對所有的

，有

(3.2.6)

令

表示其可行集，即

(3.2.7)那么，

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

且

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

，那么

在

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

由陰影表示，

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

是最優(yōu)解，

是

在

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

滿足條件(3.2.8)。如果

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

。這表明

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

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

，滿足

(3.2.9)

考慮點(diǎn)

，其中

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

在

和

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

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

。這證明

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

(3.2.10)

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

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

(即

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

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

為可行解，即

，且對于所有可行解

，都有

。因?yàn)?/p>

可微，其定義域是開集，所以所有充分靠近

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

，其中

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

為小的正數(shù)時，

是可行的，因此

(3.2.12)

因此

。例3.2.1解析中心。考慮關(guān)于凸函數(shù)

的無約束極小化問題。

(3.2.13)

其中

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

可微，因此

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

(3.2.14)

條件

即是

。如果

不可行，則

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

(3.2.15)

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

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

的

，有

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

可行，每個可行解

都可以寫作

的形式，其中

是A的零空間的向量，即

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

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

，我們有

，即

(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)爭資源調(diào)配等問題的刺激，運(yùn)籌學(xué)應(yīng)運(yùn)而生。線性規(guī)劃作為一類特殊的凸優(yōu)化問題被首先關(guān)注。它也是一只“會下金蛋的雞”，許多著名的優(yōu)化算法，如內(nèi)點(diǎn)法，首先為求解線性規(guī)劃問題而設(shè)計，隨后在求解其他更一般的凸優(yōu)化問題時也取得了成功。時至今日，人們已開發(fā)了眾多軟件包，可以高效求解大規(guī)模線性規(guī)劃問題。當(dāng)目標(biāo)函數(shù)和約束函數(shù)都是仿射函數(shù)時，相應(yīng)的優(yōu)化問題稱為線性規(guī)劃(linearprogram，LP)。線性規(guī)劃的一般形式如下。

(3.3.1)其中

，

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

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

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

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

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

是最優(yōu)解。3.3線性規(guī)劃圖3.3.1LP的幾何解釋常見的兩種線性規(guī)劃是標(biāo)準(zhǔn)型線性規(guī)劃和不等式線性規(guī)劃。在標(biāo)準(zhǔn)型線性規(guī)劃形式如下。(3.3.2)其中不等式表示是分量的非負(fù)約束。如果LP沒有等式約束，那么稱這類問題為不等式線性規(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)第二步是將變量

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

和

的差，即

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

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

和

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

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

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

和

的線性規(guī)劃來確定，(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)化問題(3.2.1)稱為二次規(guī)劃(quadraticprogram，QP)。二次規(guī)劃可以表示為以下形式。(3.4.1)其中。二次規(guī)劃實(shí)際上是在一個凸多面體上最小化一個凸二次函數(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)其中。這一問題稱為帶二次約束的二次規(guī)劃(quadraticallyconstrainedquadraticprogram，QCQP)。它的可行域是多面體與若干個橢球相交的部分(當(dāng))。在(3.4.2)式中取，得到二次規(guī)劃的特殊情況──線性規(guī)劃。在(3.4.2)中取，可以發(fā)現(xiàn)QCQP包括二次規(guī)劃，因此也包括線性規(guī)劃。3.4二次規(guī)劃模型最小二乘回歸凸二次函數(shù)的最小化問題

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

，其中

是矩陣

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

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

和

在

上的歐氏距離定義為

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

和

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

(3.4.6)

當(dāng)且僅當(dāng)其中一個多面體為空時，這個問題是不可行的。當(dāng)且僅當(dāng)多面體相交時，最優(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ī)劃求解上述兩個多面體之間距離的代碼。

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

和

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

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

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

可以表示為

，因?yàn)?/p>

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

的約束條件，其中

為多項(xiàng)式，

。類似地，若

和

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

表示為

(因?yàn)?/p>

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

，含有隱式約束

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

，則

。如果

是關(guān)于

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

，那么

(3.5.4)

其中

。變量變換

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

(3.5.5)

那么

(3.5.6)

其中

，且

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

的式子等價表示

(3.5.7)

其中

，

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

，將

映射為

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

，

，其中

為對角矩陣，

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

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

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

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

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

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

是點(diǎn)錐，

是

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

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

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

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

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

為

時，半正定

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

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

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

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

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

，

是

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

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

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

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

，邊的集合為

。設(shè)

為邊

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

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

，都有

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

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

到它的余集

(其中

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

)為最大割問題(

)提供了一個上界，即：事實(shí)上，可以證明下面的不等式成立這個結(jié)果表明半定規(guī)劃松弛問題的最優(yōu)值與最大割這一NP難問題的最優(yōu)值相差不超過13%。實(shí)例代碼3.6.1給出了半定規(guī)劃求解最大割問題的示例，其中有5個結(jié)點(diǎn)，如圖3-6所示。3.6.3組合優(yōu)化中的SDP圖3.6.1最大割問題示意圖實(shí)例代碼3.6.1調(diào)用cvxpy包求解最大割問題的半定規(guī)劃松弛問題。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分到另一類。謝謝觀看對偶理論最優(yōu)化模型與算法——基于Python實(shí)現(xiàn)第四章01Lagrange對偶函數(shù)考慮標(biāo)準(zhǔn)型的優(yōu)化問題：(4.1.1)其中，變量

，假設(shè)其定義域

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

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

定義為：

(4.1.2)

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

。將對應(yīng)于第

個不等式約束條件

中的

稱為Lagrange乘子；類似地，

是對應(yīng)于第

個等式約束

的Lagrange乘子。向量

和向量

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

定義為Lagrange函數(shù)關(guān)于

的最小值：對于

，

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

的Lagrange函數(shù)無下界時，其對偶函數(shù)取值為

即使當(dāng)問題(4.1.1)為非凸時，因?yàn)閷ε己瘮?shù)是仿射函數(shù)族

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

的下界：定理4.1.1對任意的

和任意的

，

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

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

和

，并且

，可得

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

(4.1.6)

因此

(4.1.7)

因?yàn)?/p>

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

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

并且有一個不等式約束的簡單問題解釋了不等式(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ù)

的最小值都比

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

且

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

，即

。因此將

且

的數(shù)對

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

。這個問題沒有不等式約束，只有

個線性的等式約束。Lagrange

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

。其對偶函數(shù)

。因?yàn)?/p>

是關(guān)于

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

(4.1.9)

找到最小值點(diǎn)

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

(4.1.10)是一個定義在

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

，有

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

，

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

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

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

，

和

稱為對偶可行的。正如名字所示，

對于對偶問題(4.2.1)是可行的。同時將問題(4.2.1)的最優(yōu)解

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

最大化

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

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

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

使得

(4.2.17)

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

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

個約束函數(shù)

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

，使得

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

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

使得

。可以證明，當(dāng)原問題是凸的且Slater條件成立時，強(qiáng)對偶性成立。4.2.3強(qiáng)對偶性與Slater約束規(guī)范03Lagrange對偶的理解對一組

，如果

(4.3.1)對所有

成立，我們稱

為

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

使

最小(對所有

)并且

使

最大(對所有

)：

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

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

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

和

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

,

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

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

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

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

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

，玩家2選擇

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

的報酬給玩家2。因此玩家1想要最小化

，而玩家2想要最大化

。因?yàn)?/p>

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

，因此會選擇能夠最大化

的

。最終的報酬為

，這取決于玩家1做出的選擇(我們在假設(shè)上確界能夠取到，如果不能，最優(yōu)的報酬能夠任意接近

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

來使支付給玩家2的報酬在最壞的情況下盡可能少。因此玩家1選擇

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

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

，隨后玩家1在知道

的情況下選擇

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

的

，這將使玩家1向玩家2支付的報酬為

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

是

關(guān)于

和

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

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

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