【數學】數學規劃簡介

01-25

導語：在一定的資源和條件限制下，將某一個目標最大化或最小化，這就是數學規劃問題。

作者：肖睿編輯：宏觀經濟算命師本文由JoinQuant量化課堂推出，本文的難度屬於進階（上），深度為 level-0

前言

數學規劃(mathematical programming)，也稱數學優化(mathematical optimization)，是數學中的一個分支，它主要研究的目標在給定的區域中尋找可以最小化或最大化某一函數的最優解。數學規劃在幾乎所有的科學領域都有著不容忽視的應用，所以一直都是一門受到著重關注和研究的學科。本文是對數學規劃問題的一個淺顯的介紹，不涉及任何理論和演算法。

數學規劃

一個數學規劃問題一般具有以下形式

$ext{min} &&f(x)\ ext{s.t.} &&c_i (x) le b_i, i=1,dots,k \&&xin mathbb{R}^n$

在這裡面，函數 $f:R^n ightarrow R , c_i:R^n ightarrow R , b_i in R$ 。函數 f 是我們想最小化的目標函數(objective function)；而函數 $c_i$ 和常量 $b_i$ 則對可行集構成一些限制，不等式 $c_i(x) le b_i$ 叫做一個約束(constraint)，所有滿足這些約束的點的集合

$Omega={xin R^n:c_i(x) in b_i, i=1,dots ,m}$

被稱作這個問題的可行區域(feasible region)。

我們看一下實際應用中的問題是如何以數學規劃的方式表達。假設呢，現在我們有兩種金融資產可以進行選擇，第一個資產平均每年有 10% 的收益，但是在最壞情況下可能損失 20%；第二個資產每年平均有 5% 的收益，但最大損失也不會超過 5%。方便起見，假設這兩個資產是可以無限拆分的，也就是說我們可以買 1/2 個或者 $frac{e^{pi}}{1+sqrt{5}}$ 個。現在假設我們有本金 100，可以投資於這兩個資產；我們希望在最壞的情況下損失不超過本金的 10%，也就是 10，目標嘛，當然是要最大化預期收益率。

好喲。首先確定我們的問題，是這兩種資產要各配置多少錢。那麼，這個問題所在的空間是 $R^2$ ，對於裡面的一個向量 x，坐標 $x_1$ 和 $x_2$ 分別是兩種資產購買的凈值。其次，我們想最大化的是預期收益，也就是

$f(x_1,x_2)=0.1x_1+0.05x_2$

有兩個要求。第一個是購買的資產總值不可以超過起始資金 100。讓 $c_1$ 代表兩種資產價值總和的函數， $b_1$ 代表總值產100，有

$c_1(x_1,x_2)=x_1+x_2 le 100=b_1$

還有呢，最壞情況下損失不可以超過 10，那麼設 $c_2$ 為最大損失的函數，設 $b_2$ 等於 10，有

$c_2(x_1,x_2)=0.1x_1+0.05x_2 le 10=b_2$

好，新鮮的規劃問題就出爐了：

$ext{max} &&0.1x_1+0.05x_2\ ext{s.t.} &&x_1+x_2 le 100\&&0.1x_1+0.05x_2 le 10$

當然，也可以寫成矩陣的形式

$ext{max} &&egin{bmatrix}0.1 0.05end{bmatrix}egin{bmatrix}x_1\x_2end{bmatrix}\ ext{s.t.} &&egin{bmatrix} &1&1\&0.2&0.05end{bmatrix}egin{bmatrix}x_1\x_2end{bmatrix}leegin{bmatrix}100\10end{bmatrix}$

格式上的細節:

你說，啊，教程里都是騙人的。說好了的最小化 f(x)，為什麼上面的問題是最大化呢？
不，我才不會騙小孩。

上面的問題是可以轉換成最小化問題的，只需要在目標函數前加上一個負號，最大化 f(x) 和最小化 ?f(x) 是等同的，如果 $(x_1^?,x_2^?)$ 是 ?f 的最小解，那麼它也必定是 f 的最大解。同理的，如果有大於號的限制

$c_i(x) ge b_i$

加上負號就可以轉換為等同的小於號限制

$-c_i(x) le -b_i$

另外，如果我們需要等於號的限制

$c_i(x) =b_i$

也可以將它轉換為一個大於一個小於兩個限制的交集

$c_i(x) le b_i\c_i(x) ge b_i$

第二個大於有可以轉變成小於

$c_i(x) &&le b_i\-c_i(x) &&le -b_i$

同樣變成了上面的標準格式。

經過這些轉換的技巧，標準格式

$ext{min} &&f(x)\ ext{s.t.} &&c_i (x) le b_i, i=1,dots,k$

實際上可以表達各種各樣的問題。對於單獨的問題，我們一般會以最方便的方式寫出來，用大於號、等於號或最大化都沒有關係；但在整體地研究優化理論時，一般會用統一的問題格式，這樣研究和推導的過程會更方便。

規劃問題的分類

數學規劃問題可以分為很多很多種類，這裡我們將介紹四個最常用到的類別。這四類問題並不是並列關係，而是（很大程度上的）包含關係，其中更小的類別會包含更少的問題，但是由於這些問題普遍有著同樣的結構和性質，在這個類別中會有一致受用高效演算法；而更大的類別會包含更多的優化問題，但是由於缺乏良好的函數結構，解決起來一般會更麻煩。

線性規劃

如果一個規劃問題的目標函數 f 和約束函數 $c_i$ 都是線性函數，我們說它是一個線性規劃(linear programming)問題。線性規劃都可以寫成矩陣的形式：

$ext{min} &&c^Tx\ ext{s.t.} && Ax le b\&&xinmathbb{R}^n$

這裡， $cin mathbb{R}^n , Ain mathbb{R}^{m imes n}$ 並且 $b in mathbb{R}^m$ 。第2節中舉的例子就是一個線性規劃問題。

線性函數是在實數域上最容易分析的一類函數，它們有很強的結構性，直線嘛，從哪裡看都是一模一樣的。也正是因為如此，解決線性規劃問題也相對簡單，所有線性規劃問題都可以在多項式時間內找到最優解。

二次規劃

滿足以下格式的規劃問題都被稱作二次規劃(quadratic programming)：

$ext{min} && frac{1}{2}x^T Q x + c^Tx\ ext{s.t.} && Ax le b\&&xinmathbb{R}^n$

這裡， $Qin mathbb{R}^{n imes n}$ 是一個對稱矩陣（也就是說 $Q^T=Q$ ）， $cin mathbb{R}^{ n}$ ， $Ain mathbb{R}^{m imes n}$ 還有 $bin mathbb{R}^{m }$ 。二次規劃比線性規劃多出了一個 $x^TQx$ 項，也是由矩陣的乘積表示的，所以雖然不是線性函數，但是仍可以使用很多線性代數的技巧進行分析。二次規劃問題的難度取決於矩陣 Q：如果 Q 是正定矩陣（所有的特徵值都大於 0），那麼可以在多項式時間內找到最優解；如果 Q 是不定的（有小於 0 的特徵值），尋找最優解一般是 NP-難的。

應該指出，任何一個線性規劃問題都是二次規劃問題 --- 將二次項的 Q 設成零矩陣即可。

凸規劃

講到凸規劃，我們應該先了解凸函數什麼。如果 $f:R^n ightarrow R$ 是一個連續函數，並且對於任何 x, $x^Tin R^n$ 以及 $lambda in [0,1]$ ，滿足

$f(lambda x+(1-lambda)x$

我們說 ff 是一個凸函數(convex function)。在直觀的理解上，就是在這個函數的圖上的任意連點之間連一條直線，這個函數不會超過這條直線。

那麼，如果在一個規劃問題中，

$ext{min} &&f(x)\ ext{s.t.} &&c_i (x) le b_i, i=1,dots,k \&&xin mathbb{R}^n$

函數 f 和 $c_i$ 都是凸的，我們說它是一個凸規劃(convex programming)問題。凸函數有什麼好處呢，我們舉一個形象的例子：在上面的兩個函數曲線（紅色）上，我們在 f(x′) 的位置放一個圓珠，讓它自己滾下去。在第一個凸函數里，圓珠會一路滾下去並停在整個函數的最低點；而在第二個不凸的函數里，圓珠會停在右邊的局部低點裡，卻到不了全局的最低點。從這可以看出，如果 f 是凸函數，尋找它的最低點會更容易。但即便如此，很多凸規劃問題的最優解還是 NP-難的。

對於一個二次規劃問題，如果二次項的矩陣 Q 是半正定的，那麼它也是一個凸規劃問題；但是如果 Q 是不定的，那麼二次目標函數並不是一個凸函數。

非線性規劃

非線性規劃是一個非常大的問題類型，一般來說，如果規劃問題中

$ext{min} &&f(x)\ ext{s.t.} &&c_i (x) le b_i, i=1,dots,k \&&xin mathbb{R}^n$

函數 f 和 $c_i$ 都是連續的，它就是一個非線性規劃(non-linear programming)問題。也許這個類別的名字起得有點不恰當，因為線性規劃問題其實也屬於非線性規劃問題，而這個「非」字可以這麼理解：線性規劃是非線性規劃中極其小的一部分，如果我們有一個線性規劃問題，那麼用線性規劃的方法就可以很簡便地解決，並不需要非線性規劃的理論，所以非線性規劃實際研究的是線性規劃以外的問題。

非線性規劃的涉及面太廣，以至於很多未解的數學難題都可以寫做為非線性規劃的形式，可見普遍的非線性規劃問題有多難。因此，在研究非線性規劃問題時，我們一般會加上一些額外的條件限制，比如：目標函數 f 是可導的或是平滑的、 f 或 f 的導數是 Lipschitz 的、問題的可行區域是凸的，等等。不難看出，上面的所有其他類別的規劃問題都屬於非線性規劃問題。

結語

本文概括性地介紹了數學規劃的基本內容和一些問題的分類。在量化課堂未來的文章中，我們將介紹各類規劃問題的數學理論、解題演算法以及應用方法，敬請期待。

本文由JoinQuant量化課堂推出，版權歸JoinQuant所有，商業轉載請聯繫我們獲得授權，非商業轉載請註明出處。