凸優化筆記(6)無約束凸優化問題的演算法設計

05-18

來自專欄凸優化與非線性優化

本文主要參考密歇根大學(UMich)Marina A. Epelman教授在IOE 519: Introduction to Nonlinear Programming課上的handouts(Section 5)。如有錯誤疏漏，煩請指出。如需付費轉載，請聯繫筆者，zhu.hathaway@gmail.com。

我們分別在前面4講中，講述了LP、QP、SDP、CP，並理清了了它們之間的聯繫： $LPsubseteq convex{kern 3pt}QP subseteq convex{kern 3pt}QCQP subseteq SOCP subseteq SDPsubseteq CP$ 。今天我們將講述怎麼找到這些問題的最優解。首先我們講，無約束情況下的最優求解。

我們重新回顧一下一般的凸優化問題:

$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的

首先，如果沒有不等式約束 $g_i$ ，也沒有等式約束 $h_i$ ，那麼該問題就是一個無約束凸優化問題。

為什麼要設計iterative algorithms

對於無約束優化問題， $f(x)$ 又是凸函數，所以該問題的最優解就在 $abla f(x)=0$ 處。由於 $xin mathbb{R}^n$ ，那麼 $abla f(x)=0$ 就是n個方程，求解n個未知數。但是只有少數情況下，方程是可以直接求出解析解的，例如 $abla f(x)=Ax=0$ ，它是線性方程，有解析解。而大多數情況下，由於 $abla f(x)$ 是非線性的，很難得到解析解，所以需要設計iterative algorithms(迭代演算法)，利用計算機求解。

Iterative algorithms

通常一個優化問題的迭代演算法，有以下幾個步驟：

選取起始點
設計演算法，尋找下一個點
第2步反覆循環，直到滿足Termination Criterion(終止條件)

演算法設計的核心在於第2步，不同的演算法主要是在這一步的策略不同。而第2步通常又有兩個事情要做，一是往哪個方向邁步子，二是步子邁多大，有了邁步方向和步長，就唯一確定了下一個點在哪裡。因為你邁的步子本質來說就是個向量，決定向量的除了向量的幅值，還有向量的方向，也就是任意一個向量 $v$ 可以寫成它的幅值乘以它的單位向量所指的方向，即 $v=sqrt{v^Tv}*frac{v}{sqrt{v^Tv}}=alpha*d$ ，其中 $alpha$ 是它的幅值(標量)，d是它的單位化方向向量。所以總結有下圖：

Choosing Direction

我們知道Tylor series:

$f(x)=f(a)+[frac{ abla f(a)}{1!}]^T(x-a)+[frac{ abla^2 f(a)}{2!}]^T(x-a)^2+cdots+[frac{ abla^n f(a)}{n!}]^T(x-a)^n+cdots$

就是泰勒公式，是一個用函數在某點 $a$ 的信息描述其附近取值的公式。如果函數足夠平滑的話(也就是式中可以求從1到無窮階的導數)，在已知函數在某一點 $a$ 的各階導數值的情況之下，泰勒公式可以用這些導數值做係數構建一個多項式來近似函數在這一點的鄰域中的值。泰勒公式還給出了這個多項式和實際的函數值之間的偏差。

如果 $x-a$ 足夠小，那麼我們可以有一階近似：

$f(x)approx f(a)+{ abla f(a)^T}(x-a)$

所以假設我們目前在 $a=x^k$ ，那麼我們下一步 $f(x^{k+1})approx f(x^k)+{ abla f(x^k)^T}(x^{k+1}-x^k)$

其中 $(x^{k+1}-x^k)$ 就是我們邁的步子。令 $v=(x^{k+1}-x^k)$ ，那麼我們把 $v$ 就可以分解成它的幅值乘以它的單位化方向向量，即 $v=alpha*d$ 。所以我們要做的事情就是決定 $v=(x^{k+1}-x^k)$ 到底等於什麼，也就是怎麼從 $x^k$ 走到 $x^{k+1}$ 。由於 $xin mathbb{R}^n$ ，所以我們知道梯度 $abla f(x^k)$ 是個n維列向量。因為我們的優化問題是最小化f(x) ，我們希望下一步 $f(x^{k+1})<f(x^k)$ ，人們稱作該方向為descent direction(下降方向)。所以就是希望 $f(x^{k+1})-f(x^k)approx { abla f(x^k)^T}(x^{k+1}-x^k)<0$ 。細心觀察發現， ${ abla f(x^k)^T}(x^{k+1}-x^k)$ 其實就是向量 $abla f(x^k)$ 與向量 $(x^{k+1}-x^k) riangleq v riangleq alpha^k*d^k$ 的內積， $alpha^k$ 是步長， $d^k$ 是單位向量。如果我們邁的步子 $alpha^k$ 一樣長，那麼往哪個方向 $d^k$ 邁，可以最小化 ${ abla f(x^k)^T}(x^{k+1}-x^k)$ ？我們知道兩個向量的內積 $aullet b=left| a ight|left| b ight|cos( heta)$ ，要想 ${ abla f(x^k)^T}(x^{k+1}-x^k)$ 小於0，那麼 $heta$ 必須取為 $90^{circ}sim 180^{circ}$ 之間。而進一步我們可以推出，當 $heta=180^{circ}$ 時， ${ abla f(x^k)^T}(x^{k+1}-x^k)$ 最小，也就是邁步子的方向與 $abla f(x^k)$ 平行，但是方向相反，也就是單位向量 $d^k$ 具有以下形式： $d^{k}=-frac{ abla f(x^k)}{sqrt{[ abla f(x^k)]^T abla f(x^k)}}，k=0,1,2,cdots,n,cdots$

這就是為什麼人們把該方向叫做Steepest Descent Direction或者Gradient Descent(顯然是基於一階近似而言)。

同樣地，如果我們在 $x^k$ 對 $f(x)$ 做二階近似，我們有：

$f(x^{k+1})approx f(x^k)+{ abla f(x^k)^T}(x^{k+1}-x^k)+[frac{ abla^2 f(x^k)}{2!}]^T(x^{k+1}-x^{k})^2$

那麼因為我們的優化問題是 $min{kern 3pt} f(x)$ ，也就是我們希望下一步 $f(x^{k+1})<f(x^k)$ 。上式的二階近似是關於變數 $(x^{k+1}-x^k)$ 的quadratic函數。由於f $f(x)$ 是凸函數， $abla^2 f(x^k)ge 0$ ( $( abla^2 f(x^k)$ 是對稱矩陣)，所以上式凸的(如果 $abla^2 f(x^k)le 0$ 就是關於變數 $(x^{k+1}-x^k)$ 的凹函數了)。於是我們得到

${ abla f(x^k)}+[frac{ abla^2 f(x^k)}{2!}]^T(x^{k+1}-x^{k})*2=0\ Rightarrow (x^{k+1}-x^k)=-[ abla^2 f(x^k)]^{-1} abla f(x^k)$

也就是單位向量 $d^{k}$ 是

$d^{k}=-frac{-[ abla^2 f(x^k)]^{-1} abla f(x^k)}{sqrt{[[ abla^2 f(x^k)]^{-1} abla f(x^k)]^T[ abla^2 f(x^k)]^{-1} abla f(x^k)}}，k=0,1,2,cdots,n,cdots$

對應的 $f(x^{k+1})<f(x^k)$ ，因為

$f(x^{k+1})- f(x^k)\ approx -{ abla f(x^k)^T}[ abla^2 f(x^k)]^{-1} abla f(x^k)+frac{1}{2}{ abla f(x^k)^T}[ abla^2 f(x^k)]^{-1} abla f(x^k)\ approx -frac{1}{2}{ abla f(x^k)^T}[ abla^2 f(x^k)]^{-1} abla f(x^k){kern 133pt}<0$

所以該方向也是一個descent direction，這就是人們通常所說的Newton Direction。

以上Steepest Descent Direction與Newton Direction都是假定了 $f(x)$ 光滑的，具有一階或者二階的導數。如果 $f(x)$ 並不是可微的，怎麼辦？學者們提出了Subgradient，Quasi-Newton來解決。其他更advanced方法，就在這裡就不詳細講了。

Choosing Step Size

確定了方向 $d^k$ 之後，我們就需要確定步長 $alpha^k$ 了。我們現在基於一階近似來進行分析。選取步長 $alpha^k$ (標量)，其實就是已知 $x^k、d^k$ ，如何選擇步長 $alpha^k$ (標量)使得 $f(x^{k+1})=f(x^k+alpha^kd^k )$

最小？特別需要注意的是，這時候決策變數是 $alpha ^k$ 。這其中就有Fixed Step Size、Exact Line Search(Although usable, this method is not considered cost effective)、Backtracking Line Search(Large step lengths are tested before small ones. Thus, the step length will not be too small)等方法，下圖給出了Backtracking Line Search的選擇步長的策略，這裡暫時不詳細講了。

Choosing Termination Criterion

根據最優條件，我們知道凸函數 $f(x)$ 在最優點處滿足 $abla f(x^k)=0$ 或者 $abla^2 f(x^k)$ 是positive definite。然而在實際地利用計算機做迭代計算的過程中，這樣的精準的點通常無法恰好達到的，或者說可能要找到需要迭代無窮個步數，這是不切實際的。所以在實際中，為了求解，我們通常是允許一定範圍的小誤差(該誤差不同的演算法，有不同的選擇)，誤差如果那個範圍內，我們就停止。