二次规划问题(qp)和序列二次规划问题(sqp)的简单理解

二次规划

二次规划问题(qp)是目标函数为二次函数，约束条件为线性约束的问题，可以简化为初中数学进行表达，即:

已知目标函数为:

     f 
    
   
     ( 
    
   
     x 
    
   
     ) 
    
   
     = 
    
    
    
      x 
     
    
      2 
     
    
   
     − 
    
   
     2 
    
   
     ∗ 
    
   
     x 
    
   
     + 
    
   
     1 
    
   
  
    f(x)=x^2-2*x+1 
   
  
f(x)=x2−2∗x+1


 
  
   
   
     x 
    
   
  
    x 
   
  
x需满足约束条件


 
  
   
   
     0 
    
   
     < 
    
   
     x 
    
   
     < 
    
   
     2 
    
   
  
    0<x<2 
   
  
0<x<2

求

     f 
    
   
     ( 
    
   
     x 
    
   
     ) 
    
   
  
    f(x) 
   
  
f(x)在 
 
  
   
   
     x 
    
   
  
    x 
   
  
x为多少时取最小值

以上即为最简单的一维的二次规划表达例子，扩展到高维的话，则

     x 
    
   
  
    x 
   
  
x为向量矩阵形式，但原理是一样的。

对于高维二次规划问题，求解过程并不像初中数学那样简单，因此会采用其他的方法，如内点法和有效集法等。

对于工程师而言，我们在编写代码的时候，并不关心二次规划问题的求解细节，所以一般是把二次规划问题建立好后，直接调用三方库进行求解。

目前常用的c++求解库是qpoases和osqp，MATLAB的话有个quadprog可用于求解qp。

二次规划问题是一个典型的非线性规划问题，与非线性规划相对的概念是线性规划，对，就是高中数学的学的那个。

二次规划问题还是一个典型的凸优化问题。凸优化问题(Convex optimization problem)要求目标函数为凸函数，而且定义域为凸集。这里的定义域指的就是约束，简单理解就是

      x 
     
    
      2 
     
    
   
     − 
    
   
     1 
    
   
     < 
    
   
     0 
    
   
  
    x^2-1<0 
   
  
x2−1<0就是凸集， 
 
  
   
    
    
      x 
     
    
      2 
     
    
   
     − 
    
   
     1 
    
   
     > 
    
   
     0 
    
   
  
    x^2-1>0 
   
  
x2−1>0就是非凸集。另外，凸优化还要求等式约束均为仿射函数。凸优化问题的特点是局部最优解就是全局最优解。

注意: 只要目标函数不是二次函数，或约束不是线性约束，满足其中任意一个，则此问题就不是二次规划问题。非二次规划问题可能是凸问题，也可能是非凸问题。

非二次规划问题求解思路如下:

1. 当目标函数仍为二次函数，但约束为非线性约束时，我们可采用ipopt三方库直接求解，或者用序列二次规划(sqp)进行求解，下节详细介绍。
2. 当目标函数不为二次函数，且约束为非线性约束时，我们似乎只能采用ipopt三方库进行求解了。

序列二次规划

当二次规划的约束为非线性约束时，通常会采用sqp进行求解，用连续求解qp的方法来得到非线性约束条件下的最优解，上述的qpoases和osqp均无法直接求解非线性约束问题，所以如果使用这两个库的话，
只能采用sqp的方法求解，sqp会求解一连串的qp问题。注意，sqp是结果，而不是原因，只有在非线性约束的情况下才会考虑sqp求解，如果问题本身就是线性约束，则直接用qp解就行。

我们将上述qp问题进行改造，得到一个非线性优化问题:

已知目标函数为:

     f 
    
   
     ( 
    
   
     x 
    
   
     ) 
    
   
     = 
    
    
    
      x 
     
    
      2 
     
    
   
     − 
    
   
     2 
    
   
     ∗ 
    
   
     x 
    
   
     + 
    
   
     1 
    
   
  
    f(x)=x^2-2*x+1 
   
  
f(x)=x2−2∗x+1


 
  
   
   
     x 
    
   
  
    x 
   
  
x需满足约束条件


 
  
   
    
    
      x 
     
    
      2 
     
    
   
     < 
    
   
     0.5 
    
   
  
    x^2<0.5 
   
  
x2<0.5

求

     f 
    
   
     ( 
    
   
     x 
    
   
     ) 
    
   
  
    f(x) 
   
  
f(x)在 
 
  
   
   
     x 
    
   
  
    x 
   
  
x为多少时取最小值

求解步骤如下:

1. 因为约束为非线性约束，所以先将约束进行线性化，约束原方程为 c ( x ) = x 2 c(x)=x^2 c(x)=x2，这里我们选择在 x = 10 x=10 x=10的位置进行线性化，根据泰勒展开 f ( x ) = f ( x 0 ) + f ′ ( x 0 ) 1 ! ( x − x 0 ) f(x)=f(x_0)+\frac{f'(x_0)}{1!}(x-x_0) f(x)=f(x0​)+1!f′(x0​)​(x−x0​)， 我们可以得到 c ( x ) = 20 x − 100 c(x)=20x-100 c(x)=20x−100，所以原约束条件变成了 20 x − 100 < 0.5 20x-100<0.5 20x−100<0.5
2. 步骤1将非线性约束转换成了线性约束，因此是标准qp，可以用三方库进行第一次qp求解，求解得到一个最优 x x x值，这里解出来最优解为 x = 1 x=1 x=1，记录此时目标函数值 f 1 = 0 f1=0 f1=0
3. 将非线性约束在第2步解出的 x x x处进行线性化，线性化后原约束变成了 2 x − 1 < 0.5 2x-1<0.5 2x−1<0.5，调用第三方库解第二次qp，这里解出来最优解为 x = 0.75 ， x=0.75， x=0.75，记录此时目标函数值 f 2 = 0.0625 f2=0.0625 f2=0.0625
4. 比较 f 1 f1 f1和 f 2 f2 f2的值的差距，发现差了0.0625，假设我们判断收敛的阈值为两次qp间解算的目标函数值差距不能超过0.001，则此时判断sqp并未收敛，继续计算
5. 将非线性约束在第3步解出的 x x x处进行线性化，调用第三方库解第三次qp，这里解出来最优解为 x = 0.7083 ， x=0.7083， x=0.7083，记录此时目标函数值 f 3 = 0.085 f3=0.085 f3=0.085
6. 将非线性约束在第5步解出的 x x x处进行线性化，调用第三方库解第四次qp，这里解出来最优解为 x = 0.7071 ， x=0.7071， x=0.7071，记录此时目标函数值 f 4 = 0.086 f4=0.086 f4=0.086
7. 将非线性约束在第6步解出的 x x x处进行线性化，调用第三方库解第五次qp，这里解出来最优解为 x = 0.7071 ， x=0.7071， x=0.7071，记录此时目标函数值 f 5 = 0.086 f5=0.086 f5=0.086
8. 比较 f 4 f4 f4和 f 5 f5 f5的值的差距，发现差距不到0.001了，此时我们认为sqp已经收敛了，此时得到的最优解 x x x即为整个sqp问题的最优解

仍无法理解的问题: 为什么连续求解qp直至最后收敛，其结果就是问题最优解，这个证明是怎么来的，有什么简单的理解方法吗? 欢迎大家讨论补充。