二次规划的整标集法与可分解的二次规划

一般二次规划(qp)常用fletcher算法或简约梯度法求解,只能得1个kt点,未必是整体最优解.根据求解线性互补问题全部解的整标集法,文中提出求解二次规划的整标集法,即将(qp)转化为线性互补问题,求出全部互补可行解,得到(qp)的全部kt点,通过比较得整体最优解.此法不需初始可行点,简便可行,适用于一般二次规划.结合算例将整标集法与fletcher算法、简约梯度法进行比较.该例用此法求解得7个kt点,且目标函数值相差甚远.另一例具有无穷多个kt点.算例表明:对于小规模问题,此法优于fletcher算法和简约梯度法.文中还提出二次规划可分解的条件,据此可将一类规模较大的问题分解成规模较小的问题,降低了难度.