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

ゝ一世哀愁。 2023-03-13 03:02 46阅读 0赞

### 目录 ###

*   *  非线性最优化
     *   *  无约束二次最优化
     *  二次规划的一般形式
     *  二次规划的性质
     *  等式约束下的二次规划
     *  凸二次规划的有效集方法
     *   *  算法步骤（迭代法）：
         *  可行步长的选取：阻塞约束

## 非线性最优化 ##

最优化的问题的一般形式是：  
 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. aiTx≥bi,i∈IaiTx=bi,i∈E

## 二次规划的性质 ##

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

*  **K-T条件**是最优解的充要条件。
 *  局部最优解就是全局最优解。

## 等式约束下的二次规划 ##

问题（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,λ)=21xTHx\+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，即为上式的解。

## 凸二次规划的有效集方法 ##

*  直观解释：  
    将不起作用的约束去掉，将起作用约束作为等式约束，通过解一系列等式约束的二次规划来实现不等式约束的优化。
 *  基本原理：  
    若 x \\mathbf\{x\} x是问题（1）的最优解，则它也是问题（3）：  
     min ⁡ 1 2 x T H x + c T x s.t. a i T x = b i , i ∈ I \\begin\{array\}\{l\} \\min \\frac\{1\}\{2\} \\mathbf\{x\}^\{\\mathrm\{T\}\} H \\mathbf\{x\}+\\mathbf\{c\}^\{\\mathrm\{T\}\} \\mathbf\{x\} \\\\\\\\ \\text \{ s.t. \} \\mathbf\{a\}\_\{i\}^\{\\mathrm\{T\}\} \\mathbf\{x\}=b\_\{i\}, i \\in I \\end\{array\} min21xTHx\+cTx s.t. aiTx=bi,i∈I的最优解，其中 I I I是起作用约束指标集（有效集）。反之，若 x \\mathbf\{x\} x是问题（1）的可行解，又是（3）的K-T点，且相应的乘子 λ i ≥ 0 \\lambda\_\{i\} \\geq 0 λi≥0，则 x \\mathbf\{x\} x是问题（1）的最优解。

### 算法步骤（迭代法）： ###

*  设当前迭代点为 x k \\mathbf\{x\}\_k xk，它也是（1）的可行解。该点的有效集记作 I k I\_k Ik，为寻求 x k \\mathbf\{x\}\_k xk点的迭代方向 d \\mathbf\{d\} d，用乘子法求解  
     min ⁡ 1 2 ( x k + d ) T H ( x k + d ) + c T ( x k + d ) s.t. a i T d = 0 , i ∈ I k \\begin\{array\}\{l\} \\min \\frac\{1\}\{2\}\\left(\\mathbf\{x\}\_\{k\}+\\mathbf\{d\}\\right)^\{\\mathrm\{T\}\} H\\left(\\mathbf\{x\}\_\{k\}+\\mathbf\{d\}\\right)+\\mathbf\{c\}^\{\\mathrm\{T\}\}\\left(\\mathbf\{x\}\_\{k\}+\\mathbf\{d\}\\right) \\\\ \\\\\\text \{ s.t. \} \\mathbf\{a\}\_\{i\}^\{\\mathrm\{T\}\} \\mathbf\{d\}=0, i \\in I\_\{k\} \\end\{array\} min21(xk\+d)TH(xk\+d)\+cT(xk\+d) s.t. aiTd=0,i∈Ik
    
     *  若所得最优值 d k = 0 \\mathbf\{d\}\_k=0 dk=0，则 x k \\mathbf\{x\}\_k xk是（3）的最优解。
        
         *  为判断它是否（1）的最优解，考察对应于有效约束的乘子 λ i ≥ 0 \\lambda\_\{i\} \\geq 0 λi≥0是否成立。若成立，则 x k \\mathbf\{x\}\_k xk是**K-T**点，由二次规划性质 x k \\mathbf\{x\}\_k xk是（1）的最优解。
     *  若所得最优值 d k ≠ 0 \\mathbf\{d\}\_k≠0 dk=0，则取 x k + 1 = x k + α d k \\mathbf\{x\}\_\{k+1\}=\\mathbf\{x\}\_\{k\}+\\alpha \\mathbf\{d\}\_\{k\} xk\+1=xk\+αdk，在 x k + 1 \\mathbf\{x\}\_\{k+1\} xk\+1为可行点的条件下确定 d k \\mathbf\{d\}\_k dk方向的步长 α k \\alpha\_k αk
        
         *  如果存在 p p p不在 I k I\_\{k\} Ik中，使得 a p x k + 1 = b p \\mathbf\{a\}\_\{p\} \\mathbf\{x\}\_\{k+1\}=\\mathrm\{b\}\_\{p\} apxk\+1=bp，则将 p p p加入有效集
         *  如果存在 I k I\_\{k\} Ik中的指标 q q q，使得 λ i < 0 \\lambda\_i<0 λi<0，则 x k \\mathbf\{x\}\_\{k\} xk不是最优解，从有效集中去掉q。

### 可行步长的选取：阻塞约束 ###

α k = min ⁡ \{ 1 , min ⁡ i ∉ I k , a i T d k < 0 b i − a i T x k a i T d k \} \\alpha\_\{k\}=\\min \\left\\\{1, \\min \_\{i \\notin I\_\{k\}, \\mathbf\{a\}\_\{i\}^\{T\} \\mathbf\{d\}\_\{k\}<0\} \\frac\{b\_\{i\}-\\mathbf\{a\}\_\{i\}^\{T\} \\mathbf\{x\}\_\{k\}\}\{\\mathbf\{a\}\_\{i\}^\{T\} \\mathbf\{d\}\_\{k\}\}\\right\\\} αk=min\{ 1,i∈/Ik,aiTdk<0minaiTdkbi−aiTxk\}  
 α k = 1 \\alpha\_\{k\}=1 αk=1时，对应约束集不影响，保持不变  
 α k < 1 \\alpha\_\{k\}<1 αk<1时，对应约束称为阻塞约束，此时沿着 d k \\mathbf\{d\}\_\{k\} dk运动，会被不在指标集中的约束给阻塞了，约束集因此改变。