一、Lagrange 對偶函式

1.1 拉格朗日函式

1.2 拉格朗日對偶函式

二、標準形式線性規劃拉格朗日對偶

m i n C T x s . t . A x = b x ≥ 0 min C^Tx\\s.t. Ax=b\\x\ge0 minCTxs.t.Ax=bx≥0

• 構建拉格朗日運算式

在標準優化形式中， f ( x ) ≤ 0 f(x)\le0 f(x)≤0，因此將滿足條件的第二條轉換為 ? x ≤ 0 -x\le0 ?x≤0,那么函式運算式如下：
L ( x , λ , μ ) = C T x + ∑ λ i ( ? x i ) + ∑ μ i ( A x i ? b ) = C T x ? λ T x + u T ( A x ? b ) = ( C T ? λ T + μ T A ) x ? μ T b \begin{aligned} L(x,\lambda,\mu)&=C^Tx+\sum\lambda_i(-x_i)+\sum \mu_i(Ax_i-b)\\&=C^Tx-\lambda^Tx+u^T(Ax-b)\\&=(C^T-\lambda^T+\mu^TA)x-\mu^Tb \end{aligned} L(x,λ,μ)?=CTx+∑λi?(?xi?)+∑μi?(Axi??b)=CTx?λTx+uT(Ax?b)=(CT?λT+μTA)x?μTb?
因此令 ? L ( x , λ , μ ) ? x = 0 \frac{\partial L(x,\lambda,\mu)}{\partial x}=0 ?x?L(x,λ,μ)?=0,那么 L ( x , λ , μ ) = ? u T b L(x,\lambda,\mu)=-u^Tb L(x,λ,μ)=?uTb

因此其對偶函式如下：

三、三個實體

3.1 線性方程的最小二乘解

m i n x T x s . t . A x = b minx^Tx\\s.t. Ax=b minxTxs.t.Ax=b
第一步構造拉格朗日方程：
L ( x , μ ) = x T x + u T ( A x ? b ) ? L ( x , μ ) ? x = 0 , ? L ( x , μ ) ? μ = 0 L(x,\mu)=x^Tx+u^T(Ax-b)\\ \frac{\partial L(x,\mu)}{\partial x}=0,\frac{\partial L(x,\mu)}{\partial \mu}=0 L(x,μ)=xTx+uT(Ax?b)?x?L(x,μ)?=0,?μ?L(x,μ)?=0
由于忘記矩陣的求導法則了，翻看一下矩陣分析，有如下兩個公式
? x T A x ? x = 2 A x [ 注 ： A 為 對 稱 陣 ] \frac{\partial x^TAx}{\partial x}=2Ax [注：A為對稱陣]\\ ?x?xTAx?=2Ax[注：A為對稱陣]
? b T x ? x = b [ 注 ： 轉 置 了 一 下 ] \frac{\partial b^Tx}{\partial x}=b [注：轉置了一下] ?x?bTx?=b[注：轉置了一下]
因此求解計算如下
? L ( x , μ ) ? x = 2 x + A T μ = 0 x = ? 1 2 A T μ \begin{aligned} \frac{\partial L(x,\mu)}{\partial x}=2x+A^T\mu=0 \\ x=-\frac{1}{2}A^T\mu \end{aligned} ?x?L(x,μ)?=2x+ATμ=0x=?21?ATμ?
那么代回原方程有
L ( x , μ ) = x T x + u T ( A x ? b ) = ( ? 1 2 A T μ ) T ( ? 1 2 A T μ ) + μ T ( A ( ? 1 2 A T μ ) ? b ) = 1 4 μ T A A T μ ? 1 2 μ T A A T μ ? μ T b = ? 1 4 μ T A A T μ ? μ T b \begin{aligned} L(x,\mu)&=x^Tx+u^T(Ax-b)\\&=(-\frac{1}{2}A^T\mu)^T(-\frac{1}{2}A^T\mu)+\mu^T(A(-\frac{1}{2}A^T\mu)-b)\\ &=\frac{1}{4}\mu^TAA^T\mu-\frac{1}{2}\mu^TAA^T\mu-\mu^Tb\\&=-\frac{1}{4}\mu^TAA^T\mu-\mu^Tb \end{aligned} L(x,μ)?=xTx+uT(Ax?b)=(?21?ATμ)T(?21?ATμ)+μT(A(?21?ATμ)?b)=41?μTAATμ?21?μTAATμ?μTb=?41?μTAATμ?μTb?

3.2 二次規劃QP

m i n x T P x s . t . A x ≤ b minx^TPx\\s.t. Ax \le b minxTPxs.t.Ax≤b
同樣可以計算出

S + + S_{++} S++?表示正定矩陣，而 S + S_{+} S+?表示半正定矩陣，
推導時候由于正定矩陣是對稱矩陣，那么有 P T = P P^T=P PT=P

3.3 二次約束二次規劃的QCQP