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

摘要：

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

关键词：一般二次规划、整体最优解、线性互补问题、整标集法、可分解的二次规划

所属期刊栏目：37

分类号：O221(运筹学)

资助基金：南开大学校科研和教改项目

在线出版日期：2004-12-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：934-940