??二次規(guī)化是非線性規(guī)化中的一種特殊情形，其目標(biāo)函數(shù)是二次實函數(shù)，約束是線性的。考試中會考到四種方法，分別為：Lagrange方法、起作用集方法、直接消去法和廣義消去法。前兩種在教材上有詳細(xì)描述，后面兩種出現(xiàn)在PPT上面。本節(jié)先介紹最簡單的方法：Lagrange方法。

一、Lagrange方法適用情形

??Lagrange方法適用于具有等式線性約束的二次規(guī)化問題：$$\begin{gathered} min\frac{1}{2}{x}^{T}Hx+c^{T}x \\ s.t.Ax=b \end{gathered}$$

二、Lagrange方法推導(dǎo)

??首先定義Lagrange函數(shù)，將約束式和目標(biāo)函數(shù)進(jìn)行合成：$$L(x,\lambda )=\frac{1}{2}{x}^{T}Hx+c^{T}x?{\lambda }^T(Ax?b)$$??之后令L函數(shù)關(guān)于$x$和$\lambda$的梯度分別為0，即${▽}_{x}L(x,\lambda )=0$,${▽}_{\lambda }L(x,\lambda )=0$，可以得到：$$\begin{gathered} Hx+c?A^T\lambda =0 \\ ?Ax+b=0 \end{gathered}$$??將$x$和$\lambda$視為變量，寫成矩陣形式則為：$$\left[\begin{array}{cc}H& ?A^T\\ ?A& 0\end{array}\right]\left[\begin{array}{c}x\\ \lambda \end{array}\right]=\left[\begin{array}{c}?c\\ ?b\end{array}\right]$$??其中左側(cè)矩陣稱為Lagrange矩陣。可以發(fā)現(xiàn)，如果兩側(cè)同時左乘Lagrange矩陣的逆，則可以直接得到$x$和$\lambda$的解，接下來定義逆陣：$${\left[\begin{array}{cc}H& ?A^T\\ ?A& 0\end{array}\right]}^T=\left[\begin{array}{cc}Q& ?R^T\\ ?R& S\end{array}\right]$$??逆陣快速計算方法如下：$$\begin{gathered} 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} \end{gathered}$$??好吧這個是真的不好記，我的方法如下：先記S，之后以H逆為中心元素左組合右組合，左組合先乘到右邊，右組合后乘到左邊，最后用H逆減去。
最后根據(jù)左乘后的式子進(jìn)行求解$x$和$\lambda$：$$\left[\begin{array}{c}\overline{x}\\ \overline{\lambda }\end{array}\right]=\left[\begin{array}{cc}Q& ?R^T\\ ?R& S\end{array}\right]\left[\begin{array}{c}?c\\ ?b\end{array}\right]$$

三、Lagrange方法另一種表現(xiàn)形式

??之所以提這個是因為起作用集方法中，乘子$\lambda$的解算用到了公式，所以在本節(jié)末尾給出。
??回顧上面的求解過程會發(fā)現(xiàn)，所有的運算都是在二次規(guī)劃中系數(shù)的基礎(chǔ)上進(jìn)行的，通過給定的系數(shù)直接解算$x$和$\lambda$。考慮如果給定了一個可行點$x^{(k)}$，則可以按照下面公式直接求解，其本質(zhì)是上一個求解公式的變形。$$\begin{gathered} \overline{x}=x^{(k)}?Q{g}_k \\ \overline{\lambda }=R{g}_k \end{gathered}$$??最后的公式在起作用集方法中有重要應(yīng)用。

總結(jié)

以上是生活随笔為你收集整理的二次规划_1_——Lagrange方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。