凸優化筆記(2)幾類標準問題以及Linear Programming簡介

05-10

本文主要參考卡耐基梅隆大學(CMU)的Ryan Tibshirani教授在Convex Optimization(Course 10-725/36-725)課上(課程網站鏈接：Convex Optimization)的Lecture Notes。以及參考了現任職牛津大學的Dr. Paul Goulart，以前在ETH任教時Convex Optimization課的Lecture Notes。如有錯誤疏漏，煩請指出。如需轉載，請聯繫筆者，zhu.hathaway@gmail.com。

凸優化的標準問題有四類：

Linear Programming(LP)
Quadratic Programming(QP)
Semi-Definite Programming(SDP)
Cone Programming(CP)

而這四類的標準問題具有包含與被包含的關係，如下圖所示：

所以可以這麼說：LP是QP的一種特殊情況，QP又是SDP的一種特殊情況，SDP又是CP的一種特殊情況。它們的難易程度依次遞增。

回顧一下凸優化筆記(1)Why凸優化以及幾個基本概念中關於凸優化問題的定義：

$min_{xin D}{kern 25pt}f(x)\ old{subject{kern 3pt} to:} {kern 3pt} g_i(x)le 0(i=1,2,cdots,m)\ {kern 53pt} h_j(x)= 0(j=1,2,cdots,r)$

滿足以下四個條件：
1. $old{dom}(f) 是凸集$
2. objective function-> $f(x)$ 是凸函數
3. $g_i$ ->m個inequality constraints是convex function
4. $h_i$ ->r個equality constraints是affine的

如果上式的凸優化問題中的 $f(x)=c^Tx$ ， $g_i(x)=D_ix-d_i$ ， $h_j=A_jx-b_i$ ，也就是

$min_{xin D}{kern 25pt}c^Tx\ old{subject{kern 3pt} to:} {kern 3pt} Dxle d\ {kern 53pt} Ax= b$

其中矩陣D是由m行 $D_i$ (行向量)組成的矩陣，矩陣A是由r行 $A_i$ (行向量)組成的矩陣，那麼這種特殊情況下的凸優化問題，叫做Linear Programming問題。下圖給出了在二維的polytope的可行域內(大部分問題是n維的)，圖中的objective function(虛線所示，同一條虛線上 $f(x)$ 的值是相等的) $f(x)$ 的最優解在最下面的點 $x^{star}$ 。

Dr. Paul Goulart的圖

為什麼要把問題寫成standard form

為了讓人們方便利用計算機最快速的求解convex optimization問題，通常需要會把問題重新寫成standard form。為什麼要把問題寫成standard form，原因是我們求解優化問題是通過計算機來進行的，而常用的convex optimization tools，如cvx, yalmip(matlab)，cvxpy、picos(python)等求解優化問題的是分為兩步的：

檢驗問題是不是凸的
把問題轉化成這些tools內部的solver能夠方便求解的標準形式

Linear Programming的歷史請參照中華盛頓大學數學系的talks notes: Fast Times in Linear Programming: Early Success, Revolutions, and Mysteries--by Dr. Margaret Wright[牆裂推薦讀完]，寫出了從最初的simplex algorithm(基於最優點一定在corner points的intuition而設計的演算法)到內點法的各種八卦和新演算法設計的思考出發點。

Linear Programming的standard form

Linear Programming問題通常寫成如下的standard form：

$min_{xin D}{kern 25pt}c^Tx\ old{subject{kern 3pt} to:} {kern 3pt} Ax= b\ {kern 53pt} xge 0$

請大家一定注意非標準形式與標準形式的不同！！！它不是簡單地把 $Dxle d$ 變成了 $xge 0$ ，而是通過引入新的slack variable，每引入一個slack variable( $le$ )，就把一個不等式約束轉換成affine的等式約束，寫進 $Ax=b$ 。所以standard form的 $x$ 已經不是原來的 $x$ ，而是原來的 $x$ +slack variables。同樣地，standard form的等式約束 $Ax=b$ ，也是原來的 $（Ax=b）$ +（不等式約束轉換成affine的等式約束），下圖給出了引入slack varible的例子，圖中 $s_i$ 就是引入的slack varible，決策變數由原來的 $x$ 變成了 $(x,s_i)$ ，擴維了：

Remark: 其實我們在引入新的slack varible時，隱含一個問題是：擴維會不會改變該凸優化問題的凸性？答案是，不會。至於為什麼，就留給大家思考了。