?? 本系列文章主要是我在學(xué)習(xí)《數(shù)值優(yōu)化》過程中的一些筆記和相關(guān)思考，主要的學(xué)習(xí)資料是深藍(lán)學(xué)院的課程《機(jī)器人中的數(shù)值優(yōu)化》和高立編著的《數(shù)值最優(yōu)化方法》等，本系列文章篇數(shù)較多，不定期更新，上半部分介紹無約束優(yōu)化，下半部分介紹帶約束的優(yōu)化，中間會(huì)穿插一些路徑規(guī)劃方面的應(yīng)用實(shí)例

---

---

?? 十八、帶約束優(yōu)化簡介

?? 1、簡單的例子看有無約束的區(qū)別

?? 在如下圖所示的表達(dá)式f（x）中，無約束優(yōu)化求得最最優(yōu)解位于原點(diǎn)處，即圖中的①處，若對(duì)該問題添加了不等式約束g（x）使解得范圍約束在圖中的紅色橢圓內(nèi)，此時(shí)，求得的最優(yōu)解，為圖中②處

---

?? 2、帶約束優(yōu)化的類別及復(fù)雜性

?? （1）、線性規(guī)劃LP

?? 目標(biāo)函數(shù)是線性的，等式約束和不等式約束也是線性的，x是決策變量，c、d、A、b、G、h都是常數(shù)矩陣或向量

?? （2）、二次規(guī)劃QP

?? 目標(biāo)函數(shù)含有二次項(xiàng)，一般情況下矩陣Q是半正定的，即Q>=0，等式約束或不等式約束一般是線性的。

?? （3）、錐規(guī)劃SOCP

?? 目標(biāo)函數(shù)線性的，一般情況下，不等式約束由一個(gè)線性表達(dá)式的二范數(shù)小于等于另一個(gè)線性表達(dá)式的形式給出。

?? （4）、半定錐規(guī)劃SDP

?? 目標(biāo)函數(shù)線性的，一般情況下，不等式約束由廣義的不等式形式給出，（喇叭形狀的大于等于號(hào)是半正定的意思）

?? （5）、一般形式的帶約束的優(yōu)化問題

---

?? 一般來說，不加說明的話，LP、SOCP、SDP的目標(biāo)函數(shù)都是線性的，等式約束也是線性的，他們的差別在不等式約束上，一般來說LP的線性不等式約束區(qū)域是一個(gè)凸多面體，SOCP的不等式約束是一個(gè)錐的形狀，錐的表面和內(nèi)部都是可行解。

---

?? 最壞時(shí)間復(fù)雜度如上圖右側(cè)所示，其中m是問題的約束個(gè)數(shù)，n是x的維度，L是求解精度，比如10的負(fù)多少次方，即精確到小數(shù)點(diǎn)后幾位的位數(shù)。SOCP中的ki是錐的維度，m個(gè)錐的維度可能不同。SDP中的ki表示，m個(gè)廣義不等式中Ai或Bi的行向量或列向量的個(gè)數(shù)。從LP→SOCP→SDP復(fù)雜度是增長的。

?? 另一類分類方式是按照近似優(yōu)化算法和精確優(yōu)化算法劃分的，精確優(yōu)化算法可以在有限次迭代后精確的收斂到最優(yōu)解，而近似優(yōu)化算法可以不斷的逼近最優(yōu)解。

---

?? 十九、低維度LP線性規(guī)劃

?? 線性規(guī)劃（Linear Programming，簡稱LP）是數(shù)學(xué)規(guī)劃中的一個(gè)重要分支，用于解決在給定一組線性約束條件下，優(yōu)化一個(gè)線性目標(biāo)函數(shù)的問題。線性規(guī)劃在工程、經(jīng)濟(jì)、管理等領(lǐng)域有廣泛的應(yīng)用，它能夠找到最優(yōu)的決策方案，使得目標(biāo)函數(shù)的值達(dá)到最大或最小。

?? 一般線性規(guī)劃問題可以表示為以下標(biāo)準(zhǔn)形式：

?? 最大化或最小化：$f=c_1{x}_1+c_2{x}_2+\dots +c_n{x}_n+d$

?? 不等式約束為：

?? $a_{11}{x}_1+a_{12}{x}_2+\dots +a_{1n}{x}_n\le b_1$

?? $a_{21}{x}_1+a_{22}{x}_2+\dots +a_{2n}{x}_n\le b_2$

?? $?$

?? $a_{m1}{x}_1+a_{m2}{x}_2+\dots +a_{mn}{x}_n\le b_m$

?? 其中，$f$是要優(yōu)化的目標(biāo)函數(shù)值，$c_1,c_2,\dots ,c_n$是目標(biāo)函數(shù)中各項(xiàng)的系數(shù)，$x_1,x_2,\dots ,x_n$是決策變量，$a_{ij}$是約束條件矩陣的元素，$b_i$是約束條件的右側(cè)常數(shù)項(xiàng)。上面的展開式形式可以寫成以下的矩陣形式：

?? $$\min c^{\mathrm{T}}x+ds.t.Ax\le bGx=h$$

?? 線性規(guī)劃的目標(biāo)是找到一組決策變量$x_1,x_2,\dots ,x_n$，使得目標(biāo)函數(shù)$f$的值最小化或最大化。同時(shí)，這組決策變量要滿足所有的約束條件。

?? 每個(gè)不等式約束在幾何上限制了一個(gè)半空間區(qū)域，半空間即線的某一側(cè)區(qū)域，所有的半空間取交集即下圖中藍(lán)紫色的可行域

---

?? 由不等式約束確定了可行域后，在可行域內(nèi)求解使得$f=c^{\mathrm{T}}x+d$最大或最小，d為常量，即在可行域內(nèi)找到一個(gè)使得$c^{\mathrm{T}}x$最大或最小的點(diǎn)$v_{opt}$，使這樣一個(gè)內(nèi)積運(yùn)算的值最大，即在可行域內(nèi)找一個(gè)點(diǎn)$v_{opt}$，構(gòu)成一個(gè)向量x，使得其在c方向上的投影最大。

?? 此時(shí)，最大值$c^{\mathrm{T}}{v}_{opt}>=c^{\mathrm{T}}x$，其中x是可行域內(nèi)任意一點(diǎn)，由該表達(dá)式可確定如下圖紅線及箭頭所表示的半空間，該半空間包含整個(gè)可行域，容易看出，LP問題的最優(yōu)解$v_{opt}$常位于多邊形區(qū)域內(nèi)的某個(gè)頂點(diǎn)上。

---

?? 工程中的許多優(yōu)化問題都是線性規(guī)劃。其中一個(gè)比較精確的實(shí)用算法是單純形算法（Simplex Method）。單純形算法雖然是精確的，但在最壞的情況下，其復(fù)雜度可能是隨問題的參數(shù)指數(shù)增長的。也有一些偽多項(xiàng)式算法，比如內(nèi)點(diǎn)法（Interior point methods，IPM），只能提供近似解，計(jì)算強(qiáng)度也比較大。一般只在規(guī)模很大的情況下才用內(nèi)點(diǎn)法。在路徑規(guī)劃中，常處理維度較低（如1<=d<=10）,但約束個(gè)數(shù)較多的問題（m很大），往往需要高效率的去求解一些精確解。

?? （1）一維情況

?? 對(duì)于下面例子中給出的一維的情況，很容易在線性時(shí)間內(nèi)（O（n））得到其精確解，其中c、a1 ~ an，b1 ~ bn 為一維常數(shù)，x為一維變量

?? 假設(shè)存在如下圖所示的6個(gè)不等式約束，很容易得到如下圖中紅色區(qū)域所示的可行域

?? （2）二維情況

?? 對(duì)于下圖中所示的二維的情況，兩個(gè)不等式約束對(duì)應(yīng)的半空間的交集為可行域，即圖中綠色區(qū)域，c和x都是二維的，目標(biāo)函數(shù)在紅線的上側(cè)取得最大值，可得精確解為圖中的v0點(diǎn)。

?? 若此時(shí)加入一個(gè)新的不等式約束h1，此時(shí)可行域變?yōu)橄聢D所示的綠色區(qū)域，加入約束h1之前得到的最優(yōu)解v0已經(jīng)不在可行域中，此時(shí)目標(biāo)函數(shù)的最優(yōu)的精確解變?yōu)関1點(diǎn)，易知v1點(diǎn)必然位于新加入的約束h1的某個(gè)頂點(diǎn)處，再加入新的約束h2后，由于加入約束h2之前的最優(yōu)解v1依然在當(dāng)前可行域中，此時(shí)的精確解v2=v1，即加入新約束h2后，最優(yōu)解沒有改變，依次類推，再加入新的約束h3后，精確解變?yōu)関3，再加入新的約束h4后，精確解為v4=v3。

?? 我們對(duì)上述過程進(jìn)行總結(jié)，當(dāng)我們加入一個(gè)新的約束$h_i$時(shí)，若已知在約束$h_1$ ~ $h_{i?1}$下的最優(yōu)解為$v_{i?1}$，基于這些信息，如何獲取加入新的約束$h_i$后的最優(yōu)解$v_i$，可分為兩種情況：

?? ① 若$v_{i?1}$屬于新加入的約束$h_i$對(duì)應(yīng)的半空間內(nèi)，即加入新約束$h_i$后，$v_{i?1}$依然在可行域中，此時(shí)最優(yōu)解不變，$v_i$=$v_{i?1}$

?? ② 若$v_{i?1}$不屬于新加入的約束$h_i$對(duì)應(yīng)的半空間內(nèi)，即加入新約束$h_i$后，$v_{i?1}$已經(jīng)不在可行域中了，此時(shí)新的最優(yōu)解$v_i$必然位于新加入的約束$h_i$的邊界與之前某個(gè)約束的邊界相交的頂點(diǎn)上，退一步來說，此時(shí)新的最優(yōu)解$v_i$必然位于新約束$h_i$的邊界$l_i$上，此時(shí)，我們可以把之前所有的約束$h_1$ ~ $h_{i?1}$投影到$l_i$上，轉(zhuǎn)化為上面介紹的一維的情況，即在一維線區(qū)域$l_i$上尋求滿足各個(gè)約束投影的區(qū)間的交集，再配合目標(biāo)函數(shù)，即可得到此時(shí)的最優(yōu)解$v_i$。

?? 如果我們隨機(jī)化約束條件的輸入順序，采用以上增量式方法進(jìn)行求解，理論上期望的時(shí)間復(fù)雜度是線性的。

?? 可以使用Fisher-Yates算法對(duì)約束條件的順序進(jìn)行打亂，Fisher-Yates算法的目標(biāo)是給定一個(gè)n，隨機(jī)生成一個(gè)1 ~ n 的排列，給定n后，有n！，即n的階乘種可能的排列，Fisher-Yates算法生成任意一種排列的概率是相同的，每種排列的可能性都是1/（n!)

?? 用C++實(shí)現(xiàn)時(shí)，可以使用 < random >庫來實(shí)現(xiàn)生成1~m中任意一個(gè)整數(shù)的功能，來供Fisher-Yates算法調(diào)用。

?? Fisher-Yates算法的流程如下：

?? ①、首先初始化一個(gè)1~n的序列，該序列中第幾個(gè)位置上的數(shù)就是幾，如序列第n的位置上存放的數(shù)值就是n。

?? ②、隨機(jī)生成一個(gè)1~n之間的整數(shù)k1，將序列第k1位置上存放的數(shù)值，與序列第n個(gè)位置上存放的數(shù)值進(jìn)行交換。

?? ③、隨機(jī)生成一個(gè)1~（n-1）之間的整數(shù)k2，將序列第k2位置上存放的數(shù)值，與序列第（n-1）位置上存放的數(shù)值進(jìn)行交換。

?? …

?? …

?? …

?? 依次類推，直至隨機(jī)生成1~2之間的一個(gè)數(shù)（kn-1），將序列第（kn-1）位置上存放的數(shù)值，與序列第2個(gè)位置上存放的數(shù)值進(jìn)行交換。完成后，Fisher-Yates算法就生成了一個(gè)由整數(shù)1 ~ n構(gòu)成 的排列。

---

?? （3）更一般的d維情況（d一般是比較小的個(gè)位數(shù)）

?? d維的LP線性規(guī)劃的主要思想是，d維的線性規(guī)劃在遇到新加入的超平面是Exact時(shí)，將其轉(zhuǎn)換成d-1維的線性規(guī)劃，這跟上面2維線性規(guī)劃時(shí)轉(zhuǎn)換成1維線性規(guī)劃的思想是相同的，這種思想有點(diǎn)像遞歸的思想。

?? 上圖中給出的偽代碼中，輸入?yún)?shù)H即不等式約束$a^{\mathrm{T}}x<=b$,也即一系列半空間，輸入?yún)?shù)c即$c^{\mathrm{T}}x$中的系數(shù)，如果此時(shí)c的維度是一維的，則直接采用上文中介紹的一維情況的解決方法求解，若此時(shí)c不是一維的，則初始化一個(gè)空集$I$，可以提前用Fisher-Yates算法對(duì)H的序列進(jìn)行打亂，打亂后進(jìn)行for循環(huán)時(shí)，每次依次從H中取一個(gè)h，然后判斷：

?? 情況1：若當(dāng)前最優(yōu)解屬于h，則當(dāng)前最優(yōu)解滿足約束h，不需要計(jì)算新的最優(yōu)解，直接將h添加到集合$I$中，繼續(xù)進(jìn)行下一輪for循環(huán)，處理下一個(gè)約束h

?? 情況2：若當(dāng)前的最優(yōu)解不屬于h，則需要計(jì)算一個(gè)新的最優(yōu)解x，將已經(jīng)加入到集合$I$中的約束用高斯消元法投影到約束h的邊界上，得到低一個(gè)維度的H’，然后將c也用高斯消元法投影到h上，得到低一個(gè)維度的c’，然后將低一個(gè)維度的H’和c’作為參數(shù)遞歸調(diào)用SeidelLP()函數(shù)本身進(jìn)行降維處理，直至降為1維情況。然后就可以得到新的最優(yōu)解x，此時(shí)約束h已經(jīng)滿足，將其添加到集合$I$中，本輪循環(huán)結(jié)束，繼續(xù)進(jìn)行下一輪for循環(huán)，處理下一個(gè)約束h。

?? for循環(huán)結(jié)束后，即可得到滿足所有約束hi的最優(yōu)解x

---

?? 當(dāng)d的維數(shù)較大時(shí)，比如d是20維的，深層次的遞歸調(diào)用可能出現(xiàn)復(fù)雜度爆炸，但當(dāng)d的維數(shù)是個(gè)位數(shù)時(shí)，可以高效率的得到精確解。

---

?? 接下來借助下圖中的例子，來看一下如何使用高斯消元法將d維的半空間，投影成d-1維的半空間：

---

?? Seidel′s LP線性規(guī)劃可以高效的處理維度不高，約束很多的情況，可以得到高效率的精確解。下圖給出了一些應(yīng)用實(shí)例

?? （1）線性可分問題：假設(shè)圖中紅色凸多邊形是障礙物，藍(lán)色凸多邊形是機(jī)器人或機(jī)器人的一部分，現(xiàn)在想要知道機(jī)器人是否與障礙物發(fā)生了碰撞，可以將障礙物的頂點(diǎn)及其內(nèi)部的一些冗余點(diǎn)vi與機(jī)器人的頂點(diǎn)及其內(nèi)部的一些冗余點(diǎn)wi，若他們不碰撞，那必然存在一個(gè)分離超平面，設(shè)該超平面為$a^{\mathrm{T}}x<=b$，則機(jī)器人滿足$a^{\mathrm{T}}{w}_i<=b$，障礙物滿足$a^{\mathrm{T}}{v}_i＞=b$，在這兩組約束下，求解目標(biāo)函數(shù)$c^{\mathrm{T}}x$，這里的x即為a，b構(gòu)成的向量，c可設(shè)成0向量?？汕蟮萌我庖粋€(gè)可行超平面，說明兩者沒有碰撞。Seidel′s LP線性規(guī)劃可以很好的用于檢測機(jī)器人是否與障礙物發(fā)生了碰撞。

---

?? （2）圓形可分問題，在工業(yè)流水線的機(jī)器視覺中有時(shí)需要判斷是否存在一個(gè)圓來分隔兩種點(diǎn)集，如下圖中的藍(lán)色點(diǎn)集和紅色點(diǎn)集

?? 可以進(jìn)行升維處理，將圓形區(qū)域作為增加的維度，下圖等式中右側(cè)是一個(gè)線性可分問題，若右側(cè)表達(dá)式線性可分，則左側(cè)表達(dá)式存在圓形來分隔兩個(gè)點(diǎn)集

---

?? （3）在安全區(qū)域中找一個(gè)點(diǎn)，距離安全區(qū)域的邊界的距離最大化，即在安全區(qū)域中找一個(gè)圓，使得該圓的半徑最大化，即最小的碰撞距離最大化，此時(shí)圓心即為所求的最安全的點(diǎn)。

---

---

?? 參考資料：

?? 1、數(shù)值最優(yōu)化方法（高立 編著）

?? 2、機(jī)器人中的數(shù)值優(yōu)化

---

---