?? 本系列文章主要是我在學(xué)習(xí)《數(shù)值優(yōu)化》過程中的一些筆記和相關(guān)思考，主要的學(xué)習(xí)資料是深藍學(xué)院的課程《機器人中的數(shù)值優(yōu)化》和高立編著的《數(shù)值最優(yōu)化方法》等，本系列文章篇數(shù)較多，不定期更新，上半部分介紹無約束優(yōu)化，下半部分介紹帶約束的優(yōu)化，中間會穿插一些路徑規(guī)劃方面的應(yīng)用實例
?? 十八、帶約束優(yōu)化簡介
?? 1、簡單的例子看有無約束的區(qū)別
?? 在如下圖所示的表達式f（x）中，無約束優(yōu)化求得最最優(yōu)解位于原點處，即圖中的①處，若對該問題添加了不等式約束g（x）使解得范圍約束在圖中的紅色橢圓內(nèi)，此時，求得的最優(yōu)解，為圖中②處
?? 2、帶約束優(yōu)化的類別及復(fù)雜性
?? （1）、線性規(guī)劃LP
?? 目標函數(shù)是線性的，等式約束和不等式約束也是線性的，x是決策變量，c、d、A、b、G、h都是常數(shù)矩陣或向量
?? （2）、二次規(guī)劃QP
?? 目標函數(shù)含有二次項，一般情況下矩陣Q是半正定的，即Q>=0，等式約束或不等式約束一般是線性的。
?? （3）、錐規(guī)劃SOCP
?? 目標函數(shù)線性的，一般情況下，不等式約束由一個線性表達式的二范數(shù)小于等于另一個線性表達式的形式給出。
?? （4）、半定錐規(guī)劃SDP
?? 目標函數(shù)線性的，一般情況下，不等式約束由廣義的不等式形式給出，（喇叭形狀的大于等于號是半正定的意思）
?? （5）、一般形式的帶約束的優(yōu)化問題
?? 一般來說，不加說明的話，LP、SOCP、SDP的目標函數(shù)都是線性的，等式約束也是線性的，他們的差別在不等式約束上，一般來說LP的線性不等式約束區(qū)域是一個凸多面體，SOCP的不等式約束是一個錐的形狀，錐的表面和內(nèi)部都是可行解。
?? 最壞時間復(fù)雜度如上圖右側(cè)所示，其中m是問題的約束個數(shù)，n是x的維度，L是求解精度，比如10的負多少次方，即精確到小數(shù)點后幾位的位數(shù)。SOCP中的ki是錐的維度，m個錐的維度可能不同。SDP中的ki表示，m個廣義不等式中Ai或Bi的行向量或列向量的個數(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ī)劃中的一個重要分支，用于解決在給定一組線性約束條件下，優(yōu)化一個線性目標函數(shù)的問題。線性規(guī)劃在工程、經(jīng)濟、管理等領(lǐng)域有廣泛的應(yīng)用，它能夠找到最優(yōu)的決策方案，使得目標函數(shù)的值達到最大或最小。
?? 一般線性規(guī)劃問題可以表示為以下標準形式：
?? 最大化或最小化： f = c 1 x 1 + c 2 x 2 + … + c n x n + d f = c_1x_1 + c_2x_2 + \ldots + c_nx_n+d f=c1?x1?+c2?x2?+…+cn?xn?+d
?? 不等式約束為：
?? a 11 x 1 + a 12 x 2 + … + a 1 n x n ≤ b 1 a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1 a11?x1?+a12?x2?+…+a1n?xn?≤b1?
?? a 21 x 1 + a 22 x 2 + … + a 2 n x n ≤ b 2 a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n \leq b_2 a21?x1?+a22?x2?+…+a2n?xn?≤b2?
?? ? \vdots ?
?? a m 1 x 1 + a m 2 x 2 + … + a m n x n ≤ b m a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n \leq b_m am1?x1?+am2?x2?+…+amn?xn?≤bm?
?? 其中， f f f是要優(yōu)化的目標函數(shù)值， c 1 , c 2 , … , c n c_1, c_2, \ldots, c_n c1?,c2?,…,cn?是目標函數(shù)中各項的系數(shù)， x 1 , x 2 , … , x n x_1, x_2, \ldots, x_n x1?,x2?,…,xn?是決策變量， a i j a_{ij} aij?是約束條件矩陣的元素， b i b_i bi?是約束條件的右側(cè)常數(shù)項。上面的展開式形式可以寫成以下的矩陣形式：
?? min ? c T x + d s . t . A x ≤ b G x = h \min\quad c^\mathrm{T}x+d\quad\mathrm{s.t.}\quad Ax\leq b\quad Gx=h mincTx+ds.t.Ax≤bGx=h
?? 線性規(guī)劃的目標是找到一組決策變量 x 1 , x 2 , … , x n x_1, x_2, \ldots, x_n x1?,x2?,…,xn?，使得目標函數(shù) f f f的值最小化或最大化。同時，這組決策變量要滿足所有的約束條件。
?? 每個不等式約束在幾何上限制了一個半空間區(qū)域，半空間即線的某一側(cè)區(qū)域，所有的半空間取交集即下圖中藍紫色的可行域
?? 由不等式約束確定了可行域后，在可行域內(nèi)求解使得 f = c T x + d f=c^\mathrm{T}x+d f=cTx+d最大或最小，d為常量，即在可行域內(nèi)找到一個使得 c T x c^\mathrm{T}x cTx最大或最小的點 v o p t v_{opt} vopt?，使這樣一個內(nèi)積運算的值最大，即在可行域內(nèi)找一個點 v o p t v_{opt} vopt?，構(gòu)成一個向量x，使得其在c方向上的投影最大。
?? 此時，最大值 c T v o p t > = c T x c^\mathrm{T}v_{opt} >= c^\mathrm{T}x cTvopt?>=cTx，其中x是可行域內(nèi)任意一點，由該表達式可確定如下圖紅線及箭頭所表示的半空間，該半空間包含整個可行域，容易看出，LP問題的最優(yōu)解 v o p t v_{opt} vopt?常位于多邊形區(qū)域內(nèi)的某個頂點上。
?? 工程中的許多優(yōu)化問題都是線性規(guī)劃。其中一個比較精確的實用算法是單純形算法（Simplex Method）。單純形算法雖然是精確的，但在最壞的情況下，其復(fù)雜度可能是隨問題的參數(shù)指數(shù)增長的。也有一些偽多項式算法，比如內(nèi)點法（Interior point methods，IPM），只能提供近似解，計算強度也比較大。一般只在規(guī)模很大的情況下才用內(nèi)點法。在路徑規(guī)劃中，常處理維度較低（如1<=d<=10）,但約束個數(shù)較多的問題（m很大），往往需要高效率的去求解一些精確解。
?? （1）一維情況
?? 對于下面例子中給出的一維的情況，很容易在線性時間內(nèi)（O（n））得到其精確解，其中c、a1 ~ an，b1 ~ bn 為一維常數(shù)，x為一維變量
?? 假設(shè)存在如下圖所示的6個不等式約束，很容易得到如下圖中紅色區(qū)域所示的可行域
?? （2）二維情況
?? 對于下圖中所示的二維的情況，兩個不等式約束對應(yīng)的半空間的交集為可行域，即圖中綠色區(qū)域，c和x都是二維的，目標函數(shù)在紅線的上側(cè)取得最大值，可得精確解為圖中的v0點。
?? 若此時加入一個新的不等式約束h1，此時可行域變?yōu)橄聢D所示的綠色區(qū)域，加入約束h1之前得到的最優(yōu)解v0已經(jīng)不在可行域中，此時目標函數(shù)的最優(yōu)的精確解變?yōu)関1點，易知v1點必然位于新加入的約束h1的某個頂點處，再加入新的約束h2后，由于加入約束h2之前的最優(yōu)解v1依然在當(dāng)前可行域中，此時的精確解v2=v1，即加入新約束h2后，最優(yōu)解沒有改變，依次類推，再加入新的約束h3后，精確解變?yōu)関3，再加入新的約束h4后，精確解為v4=v3。
?? 我們對上述過程進行總結(jié)，當(dāng)我們加入一個新的約束 h i h_i hi?時，若已知在約束 h 1 h_1 h1? ~ h i ? 1 h_{i-1} hi?1?下的最優(yōu)解為 v i ? 1 v_{i-1} vi?1?，基于這些信息，如何獲取加入新的約束 h i h_i hi?后的最優(yōu)解 v i v_i vi?，可分為兩種情況：
?? ① 若 v i ? 1 v_{i-1} vi?1?屬于新加入的約束 h i h_i hi?對應(yīng)的半空間內(nèi)，即加入新約束 h i h_i hi?后， v i ? 1 v_{i-1} vi?1?依然在可行域中，此時最優(yōu)解不變， v i v_{i} vi?= v i ? 1 v_{i-1} vi?1?
?? ② 若 v i ? 1 v_{i-1} vi?1?不屬于新加入的約束 h i h_i hi?對應(yīng)的半空間內(nèi)，即加入新約束 h i h_i hi?后， v i ? 1 v_{i-1} vi?1?已經(jīng)不在可行域中了，此時新的最優(yōu)解 v i v_{i} vi?必然位于新加入的約束 h i h_i hi?的邊界與之前某個約束的邊界相交的頂點上，退一步來說，此時新的最優(yōu)解 v i v_{i} vi?必然位于新約束 h i h_i hi?的邊界 l i l_i li?上，此時，我們可以把之前所有的約束 h 1 h_1 h1? ~ h i ? 1 h_{i-1} hi?1?投影到 l i l_i li?上，轉(zhuǎn)化為上面介紹的一維的情況，即在一維線區(qū)域 l i l_i li?上尋求滿足各個約束投影的區(qū)間的交集，再配合目標函數(shù)，即可得到此時的最優(yōu)解 v i v_{i} vi?。
?? 如果我們隨機化約束條件的輸入順序，采用以上增量式方法進行求解，理論上期望的時間復(fù)雜度是線性的。
?? 可以使用Fisher-Yates算法對約束條件的順序進行打亂，F(xiàn)isher-Yates算法的目標是給定一個n，隨機生成一個1 ~ n 的排列，給定n后，有n！，即n的階乘種可能的排列，F(xiàn)isher-Yates算法生成任意一種排列的概率是相同的，每種排列的可能性都是1/（n!)
?? 用C++實現(xiàn)時，可以使用 < random >庫來實現(xiàn)生成1~m中任意一個整數(shù)的功能，來供Fisher-Yates算法調(diào)用。
?? Fisher-Yates算法的流程如下：
?? ①、首先初始化一個1~n的序列，該序列中第幾個位置上的數(shù)就是幾，如序列第n的位置上存放的數(shù)值就是n。
?? ②、隨機生成一個1~n之間的整數(shù)k1，將序列第k1位置上存放的數(shù)值，與序列第n個位置上存放的數(shù)值進行交換。
?? ③、隨機生成一個1~（n-1）之間的整數(shù)k2，將序列第k2位置上存放的數(shù)值，與序列第（n-1）位置上存放的數(shù)值進行交換。
?? …
?? …
?? …
?? 依次類推，直至隨機生成1~2之間的一個數(shù)（kn-1），將序列第（kn-1）位置上存放的數(shù)值，與序列第2個位置上存放的數(shù)值進行交換。完成后，F(xiàn)isher-Yates算法就生成了一個由整數(shù)1 ~ n構(gòu)成 的排列。
?? （3）更一般的d維情況（d一般是比較小的個位數(shù)）
?? d維的LP線性規(guī)劃的主要思想是，d維的線性規(guī)劃在遇到新加入的超平面是Exact時，將其轉(zhuǎn)換成d-1維的線性規(guī)劃，這跟上面2維線性規(guī)劃時轉(zhuǎn)換成1維線性規(guī)劃的思想是相同的，這種思想有點像遞歸的思想。
?? 上圖中給出的偽代碼中，輸入?yún)?shù)H即不等式約束 a T x < = b a^\mathrm{T}x<=b aTx<=b,也即一系列半空間，輸入?yún)?shù)c即 c T x c^\mathrm{T}x cTx中的系數(shù)，如果此時c的維度是一維的，則直接采用上文中介紹的一維情況的解決方法求解，若此時c不是一維的，則初始化一個空集 I I I，可以提前用Fisher-Yates算法對H的序列進行打亂，打亂后進行for循環(huán)時，每次依次從H中取一個h，然后判斷：
?? 情況1：若當(dāng)前最優(yōu)解屬于h，則當(dāng)前最優(yōu)解滿足約束h，不需要計算新的最優(yōu)解，直接將h添加到集合 I I I中，繼續(xù)進行下一輪for循環(huán)，處理下一個約束h
?? 情況2：若當(dāng)前的最優(yōu)解不屬于h，則需要計算一個新的最優(yōu)解x，將已經(jīng)加入到集合 I I I中的約束用高斯消元法投影到約束h的邊界上，得到低一個維度的H’，然后將c也用高斯消元法投影到h上，得到低一個維度的c’，然后將低一個維度的H’和c’作為參數(shù)遞歸調(diào)用SeidelLP()函數(shù)本身進行降維處理，直至降為1維情況。然后就可以得到新的最優(yōu)解x，此時約束h已經(jīng)滿足，將其添加到集合 I I I中，本輪循環(huán)結(jié)束，繼續(xù)進行下一輪for循環(huán)，處理下一個約束h。
?? for循環(huán)結(jié)束后，即可得到滿足所有約束hi的最優(yōu)解x
?? 當(dāng)d的維數(shù)較大時，比如d是20維的，深層次的遞歸調(diào)用可能出現(xiàn)復(fù)雜度爆炸，但當(dāng)d的維數(shù)是個位數(shù)時，可以高效率的得到精確解。
?? 接下來借助下圖中的例子，來看一下如何使用高斯消元法將d維的半空間，投影成d-1維的半空間：
?? Seidel′s LP線性規(guī)劃可以高效的處理維度不高，約束很多的情況，可以得到高效率的精確解。下圖給出了一些應(yīng)用實例
?? （1）線性可分問題：假設(shè)圖中紅色凸多邊形是障礙物，藍色凸多邊形是機器人或機器人的一部分，現(xiàn)在想要知道機器人是否與障礙物發(fā)生了碰撞，可以將障礙物的頂點及其內(nèi)部的一些冗余點vi與機器人的頂點及其內(nèi)部的一些冗余點wi，若他們不碰撞，那必然存在一個分離超平面，設(shè)該超平面為 a T x < = b a^\mathrm{T}x<=b aTx<=b，則機器人滿足 a T w i < = b a^\mathrm{T}w_{i}<=b aTwi?<=b，障礙物滿足 a T v i ＞ = b a^\mathrm{T}v_{i}＞=b aTvi?＞=b，在這兩組約束下，求解目標函數(shù) c T x c^\mathrm{T}x cTx，這里的x即為a，b構(gòu)成的向量，c可設(shè)成0向量?？汕蟮萌我庖粋€可行超平面，說明兩者沒有碰撞。Seidel′s LP線性規(guī)劃可以很好的用于檢測機器人是否與障礙物發(fā)生了碰撞。
?? （2）圓形可分問題，在工業(yè)流水線的機器視覺中有時需要判斷是否存在一個圓來分隔兩種點集，如下圖中的藍色點集和紅色點集
?? 可以進行升維處理，將圓形區(qū)域作為增加的維度，下圖等式中右側(cè)是一個線性可分問題，若右側(cè)表達式線性可分，則左側(cè)表達式存在圓形來分隔兩個點集
?? （3）在安全區(qū)域中找一個點，距離安全區(qū)域的邊界的距離最大化，即在安全區(qū)域中找一個圓，使得該圓的半徑最大化，即最小的碰撞距離最大化，此時圓心即為所求的最安全的點。
?? 參考資料：
?? 1、數(shù)值最優(yōu)化方法（高立 編著）文章來源：http://www.zghlxwxcb.cn/news/detail-698072.html
?? 2、機器人中的數(shù)值優(yōu)化文章來源地址http://www.zghlxwxcb.cn/news/detail-698072.html
到了這里，關(guān)于機器人中的數(shù)值優(yōu)化（十二）——帶約束優(yōu)化問題簡介、LP線性規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[足式機器人]Part3機構(gòu)運動微分幾何學(xué)分析與綜合Ch03-1 空間約束曲線與約束曲面微分幾何學(xué)——【讀書筆記】](https://imgs.yssmx.com/Uploads/2024/02/677088-1.png)
