【计算机数学】二次规划（QP）问题

最优化的问题的一般形式是： Min ⁡ f ( x )   s.t.  x ∈ X \operatorname{Min} f(\mathbf{x}) \ \text { s.t. }\mathbf{x} \in X Minf(x)  s.t. x∈X f ( x ) f(\mathbf{x}) f(x)为目标函数， x ∈ E n \mathbf{x}\in E^n x∈En为可行域。如果 x = E n \mathbf{x}=E^n x=En，则以上最优化问题为无约束最优化问题。

约束最优化问题通常写为： Min ⁡ f ( x )  s.t.  c i ( x ) = 0 , i ∈ E c i ( x ) ≥ 0 , i ∈ I \begin{array}{l} \operatorname{Min} f(\mathbf{x}) \\\\ \text { s.t. } \mathrm{c}_{i}(\mathbf{x})=0, i \in E \\\\ \quad \mathrm{c}_{i}(\mathbf{x}) \geq 0, i \in I \end{array} Minf(x) s.t. ci​(x)=0,i∈Eci​(x)≥0,i∈I​ 其中 E , I E,I E,I分别为等式约束的指标集和不等式约束的指标集， c i ( x ) c_i(\mathbf{x}) ci​(x)是约束函数。

min ⁡ f ( x ) = 1 / 2 x T H x + c T x , x ∈ R n \min f(\mathbf{x})=1 / 2 \mathbf{x}^{\mathrm{T}} H \mathbf{x}+\mathbf{c}^{\mathrm{T}} \mathbf{x}, \mathbf{x} \in R^{n} minf(x)=1/2xTHx+cTx,x∈Rn H H H是对称矩阵。 基本解法：求导然后找局部极值。

min ⁡ f ( x ) = 1 / 2 x T H x + c T x , x ∈ R n  s.t.  A x ≤ b \begin{aligned} &\min f(\mathbf{x})=1 / 2 \mathbf{x}^{\mathrm{T}} H \mathbf{x}+\mathbf{c}^{\mathrm{T}} \mathbf{x}, \mathbf{x} \in R^{n}\\\\ &\text { s.t. } A \mathbf{x} \leq \mathbf{b} \end{aligned} ​minf(x)=1/2xTHx+cTx,x∈Rn s.t. Ax≤b​ 当 H H H为对称矩阵时，被称为二次规划（Quadratic Programming，QP）。 特别地，当H正定时，目标函数为凸函数，线性约束下可行域又是凸集。上式被称为凸二次规划。 问题（1）： min ⁡ f ( x ) = 1 / 2 x T H x + c T x , x ∈ R n  s.t.  a i T x ≥ b i , i ∈ I a i T x = b i , i ∈ E \begin{array}{l} \min f(\mathbf{x})=1 / 2 \mathbf{x}^{\mathrm{T}} H \mathbf{x}+\mathbf{c}^{\mathrm{T}} \mathbf{x}, \mathbf{x} \in R^{n} \\\\ \text { s.t. } \boldsymbol{a}_{i}^{T} \boldsymbol{x} \geq b_{i}, i \in I \\\\ \quad\quad \boldsymbol{a}_{i}^{T} \boldsymbol{x}=b_{i}, i \in E \end{array} minf(x)=1/2xTHx+cTx,x∈Rn s.t. aiT​x≥bi​,i∈IaiT​x=bi​,i∈E​

QP是一种最简单的非线性规划。QP有如下良好的性质，当H是半正定时：

问题（2）： min ⁡ f ( x ) = 1 / 2 x T H x + c T x , x ∈ R n  s.t.  A x = b \begin{aligned} &\min f(\mathbf{x})=1 / 2 \mathbf{x}^{\mathrm{T}} H \mathbf{x}+\mathbf{c}^{\mathrm{T}} \mathbf{x}, \mathbf{x} \in R^{n}\\ &\text { s.t. } A \mathbf{x}=\mathbf{b} \end{aligned} ​minf(x)=1/2xTHx+cTx,x∈Rn s.t. Ax=b​ 求解方法：Lagrange乘子法，求解以下无约束二次最优化问题。 L ( x , λ ) = 1 2 x T H x + c T x + λ T ( A x − b ) L(\mathbf{x}, \lambda)=\frac{1}{2} \mathbf{x}^{\mathrm{T}} H \mathbf{x}+\mathbf{c}^{\mathrm{T}} \mathbf{x}+\lambda^{\mathrm{T}}(A \mathbf{x}-\mathbf{b}) L(x,λ)=21​xTHx+cTx+λT(Ax−b) 令 L ( x , λ ) L(\mathbf{x}, \lambda) L(x,λ)对 x , λ \mathbf{x},\lambda x,λ的导数为零，得到线性方程组： H x + c T + A T λ = 0 A x − b = 0 \begin{aligned} &H \mathbf{x}+\mathbf{c}^{\mathrm{T}}+A^{\mathrm{T}} \lambda=0\\ &A \mathbf{x}-\mathbf{b}=\mathbf{0} \end{aligned} ​Hx+cT+ATλ=0Ax−b=0​ 可解得 x \mathbf{x} x，即为上式的解。