二次規劃_1_——Lagrange方法

  二次規化是非線性規化中的一種特殊情形，其目标函數是二次實函數，限制是線性的。考試中會考到四種方法，分别為：Lagrange方法、起作用集方法、直接消去法和廣義消去法。前兩種在教材上有較長的描述，後面兩種出現在PPT上面。本節先介紹最簡單的方法：Lagrange方法。

一、Lagrange方法适用情形

  Lagrange方法适用于具有等式線性限制的二次規化問題： m i n     1 2 x T H x + c T x s . t .     A x = b min \ \ \ \frac{1}{2}x^T Hx+c^Tx \\ s.t. \ \ \ Ax=b min   21​xTHx+cTxs.t.   Ax=b

二、Lagrange方法推導

  首先定義Lagrange函數，将限制式和目标函數進行合成： L ( x , λ ) = 1 2 x T H x + c T x − λ T ( A x − b ) L(x,\lambda)=\frac {1}{2}x^THx+c^Tx-\lambda^T(Ax-b) L(x,λ)=21​xTHx+cTx−λT(Ax−b)  之後令L函數關于 x x x和 λ \lambda λ的梯度分别為0，即 ▽ x L ( x , λ ) = 0 \triangledown_x L(x,\lambda)=0 ▽x​L(x,λ)=0, ▽ λ L ( x , λ ) = 0 \triangledown_\lambda L(x,\lambda)=0 ▽λ​L(x,λ)=0，可以得到： H x + c − A T λ = 0 − A x + b = 0 Hx+c-A^T\lambda=0 \\ -Ax+b=0 Hx+c−ATλ=0−Ax+b=0  将 x x x和 λ \lambda λ視為變量，寫成矩陣形式則為： [ H − A T − A 0 ] [ x λ ] = [ − c − b ] \begin{bmatrix} H&-A^T \\ -A&0 \end{bmatrix}\begin{bmatrix} x\\ \lambda \end{bmatrix}=\begin{bmatrix} -c\\ -b \end{bmatrix} [H−A​−AT0​][xλ​]=[−c−b​]  其中左側矩陣稱為Lagrange矩陣。可以發現，如果兩側同時左乘Lagrange矩陣的逆，則可以直接得到 x x x和 λ \lambda λ的解，接下來定義逆陣： [ H − A T − A 0 ] T = [ Q − R T − R S ] \begin{bmatrix} H&-A^T \\ -A&0 \end{bmatrix}^T=\begin{bmatrix} Q&-R^T \\ -R&S \end{bmatrix} [H−A​−AT0​]T=[Q−R​−RTS​]  逆陣快速計算方法如下： Q = H − 1 − H − 1 A T ( A H − 1 A T ) − 1 A H − 1 R = ( A H − 1 A T ) − 1 A H − 1 S = − ( A H − 1 A T ) − 1 Q=H^{-1}-H^{-1}A^T(AH^{-1}A^T)^{-1}AH^{-1} \\ R=(AH^{-1}A^T)^{-1}AH^{-1}\\ S=-(AH^{-1}A^T)^{-1} Q=H−1−H−1AT(AH−1AT)−1AH−1R=(AH−1AT)−1AH−1S=−(AH−1AT)−1  好吧這個是真的不好記，我的方法如下：先記S，之後以H逆為中心元素左組合右組合，左組合先乘到右邊，右組合後乘到左邊，最後用H逆減去。

最後根據左乘後的式子進行求解 x x x和 λ \lambda λ： [ x ‾ λ ‾ ] = [ Q − R T − R S ] [ − c − b ] \begin{bmatrix} \overline{x}\\ \overline{\lambda} \end{bmatrix}=\begin{bmatrix} Q&-R^T \\ -R&S \end{bmatrix}\begin{bmatrix} -c\\ -b \end{bmatrix} [xλ​]=[Q−R​−RTS​][−c−b​]

三、Lagrange方法另一種表現形式

  之是以提這個是因為起作用集方法中，乘子 λ \lambda λ的解算用到了公式，是以在本節末尾給出。

  回顧上面的求解過程會發現，所有的運算都是在二次規劃中系數的基礎上進行的，通過給定的系數直接解算 x x x和 λ \lambda λ。考慮如果給定了一個可行點 x ( k ) x^{(k)} x(k)，則可以按照下面公式直接求解，其本質是上一個求解公式的變形。 x ‾ = x ( k ) − Q g k λ ‾ = R g k \overline{x}=x^{(k)}-Qg_k \\ \overline{\lambda}=Rg_{k} x=x(k)−Qgk​λ=Rgk​  最後的公式在起作用集方法中有重要應用。