第２７卷 第２期 哈尔滨师范大学自然科学学报 ＮＡＴＵＲＡＬ ＳＣＩＥＮＣＥＳ ＪＯＵＲＮＡＬ ＯＦ ＨＡＲＢＩＮ ＮＯＲＭＡＬ ＵＮＩＶＥＲＳＩＴＹ Ｖｏ１．２７．Ｎｏ．２ ２０１１ 求解凸二次规划的主对偶积极集法 刘 颖，赵 迪 （哈尔滨师范大学） 【摘要】 介绍了求解带有不等式约束凸二次规划的一种主对偶积极集法．通 过凸二次规划ＫＫＴ条件中的一阶最优性条件和补条件计算出主对偶对（ ，ｓ）的 值，若（ ，ｓ）不可行则确定新的积极集，算法继续迭代；算法经有限步迭代后，一定 能得到最优解，使算法停止． 关键词：凸二次规划；积极集；主对偶对 法思路，笔者也采用了这种先求部分分量，再求 向量对的想法，考虑带有更一般约束条件Ａｘ≤ｂ ０ 引言 二次规划是非线性规划中的一种特殊形式， 由于二次规划比较简单，便于求解，且一些非线 性规划可以转化为一系列二次规划问题，因此二 的凸二次规划问题．可以说此算法是对文献［１］ 中算法的延伸和拓展，进而使得算法应用更加广 泛． 次规划算法较早引起了人们的重视．求解一般约 束二次规划问题的算法较多，如积极集法、对偶 方法、Ｌｅｍｋｅ方法和路径跟踪法等等． １ ＝ ＋ ｈ在这里，笔者提出了一种适用于求解当约束 函数个数等于解的分量个数时的凸二次规划问 题（Ｐ）的方法，把它称作主对偶积极集法．这篇 （Ｐ） 文章的创作来源于文献［１］，文献［１］主要讨论 了求解形如 １ ． 其中Ｑ是ｎ×ｎ阶正定阵 ＝（薹］是ｎ×ｎ阶方 （ＫＫＴ系统） ｑ（ ）＝ ｓ．ｔ． ≤ｂ ＋ ｄ， 、 １／０ 凸二次规划问题（Ｐ）的相应的ＫＫＴ系统是 Ｑ ＋ｄ＋Ａｓ＝０ 的带有简单盒约束 ≤ｂ凸二次规划的一种不可 行积极集法．首先利用积极集的性质直接得到该 ｓｉ（ａ；ｘ－ｂｉ）＝０， ，２，…，ｎ≤ｂ 问题主对偶对（ ，ｓ）的部分分量的值；然后又利 用盒约束的约束特点通过简单计算得到了其余 分量的值；最后验证主对偶对（ ，ｓ）是否是ＫＫＴ 系统的可行点，来判断是否为最优解，如果（ ，ｓ） ｓ≥０ 其中ｓ∈Ｒ 是相应的Ｌａｇｒａｎｇｅ乘子，且称 ＋ｄ ＋Ａｓ＝０为一阶最优性条件，称ｓ （０ 一ｂ ）＝０，ｉ ＝１，２，…， 为补条件．因为（Ｐ）是凸二次规划， 所以它的ＫＫＴ系统的解就是它的最优解．笔者 是不可行点则算法继续迭代．基于文献［１］的算 收稿日期：２０１１—０１—２２ 第２期 求解凸二次规划的主对偶积极集法 ４１ 都是通过求解此ＫＫＴ系统来得到问题的最优 解． 该文中主要用到下列符号：．， Ｎ＝｛１，２， …，ｎ｝是指标集；，＝Ⅳ＼＇，；Ｉ川指集合中元素个数 ； ＝（ ｌ， ２，…， ） ∈Ｒ ； ，＝（ ，） 是指向量 中指标取自Ｊ中所有分量 组成的Ｉｌ，ｆ维向量； Ｑ＝（ｑ ） 表示１７，阶正定阵；Ｑｕ＝（ｑ ） Ｊ Ｊ是 指行指标取自，，列指标取自Ｊ的Ｑ中元素组成 的ＩＩＩ×Ｉ．，Ｉ阶矩阵，特别的，当，＝Ｊ时，Ｑ，，简记 为Ｑ，；Ａ ＝（０，Ｔ） 指Ａ中Ｊ∈Ｊ行向量组成的ｌ＿， ｌ×ｎ矩阵． ２ 主对偶积极集法的主要思路和具 体步骤 ２．１算法的主要思路 首先，确定初始积极集Ｊ＝｛ｉ：ａ［ｘ＝ｂ ｝和非 积极集，＝｛ｉ：ｎ Ｔ ≠ｂ ｝．显然Ａ ＝ｂ，，又由ＫＫＴ 中补条件，易知ｓ的非积极指标下的分量ｓ，＝０． 其次，选择 的１．，１个分量｛ｘｊ： ∈Ｊ｝使得线 性方程组Ａ ＝ｂ，对应的系数矩阵 ，７是可逆的． 不妨设Ｊ：Ｊ，否则可以交换方程组的列使之对 应．于是线性方程组Ａ ＝ｂ，可以改写为Ａ ，＝ ｂ Ｊ—Ａ Ｊｌ。ｃｌ，也就奄ｘ Ｊ＝Ａ １《、ｂ Ｊ－Ａ｜Ｉｘｌ ． 再由分块矩阵的性质和ＫＫＴ系统中的一阶 最优性条件 ＋ｄ＋Ａｘ＝０，又分别得到了 和ｓ 的其余分量 ，和ｓ，的值，事实上，因为 ＋ｄ＋ Ａｓ＝０，把它写成分块矩阵的形式就是 （Ｑ ）（ ：）＋（兰：）＋（三 ）（ ：）＝。 即 ＩＱ Ｊ Ｊ＋Ｑ Ｊｌｘ｜＋ｄ Ｊ＋Ａ Ｊｓｊ＋Ａ ＪＩｓＩ ０ ＱｌＪｘｊ＋ＱｌｘＩ＋ｄｌ＋ＡＩＪｓ Ｊ＋ＡＩｓｌ＝ｏ 因为ｓ，＝０， ，＝Ａ （ｂＪ—Ａ ，）代入方程组，就 有： Ｉ（、Ｑｊｌ—Ｑ ＪＡ ｌＡ Ｊ｜ ｌ＋Ａ Ｊｓｌ＝一ｄ Ｊ—ＱｊＡ ｌｂ｜ Ｑｌ—Ｑ｜ＪＡ Ａ｜Ｉ ｘｉ＋Ａ｜Ｊｓ Ｊ＝一ｄｌ—ＱｌＪＡ ｔｂ Ｊ 再化回分块矩阵的形式就是： （＼ＪＱｊ， Ｑｌ一－ ＱｕｊＡｒｆ ＩＡ Ａｊ１ ＝ⅣＪ，）／（＼ｘ．．，ｉ， ）（＼ 进而就可以得到 ，和ｓ，值： （ ）＝Ｑｊ！－ＱｊＡ ｒ１Ａ ｊ，—．…．三二）一 （一－ｄ，ｊ一－ＱⅣｊＡ４ｆ ＇ ｂ６ｊ ，Ｉ 最后，只需验证（ ，ｓ）满足非积极指标下的 约束Ａ ≤ｂ，和积极指标下的ｓ，＞１０这ｎ个分量 不等式，即可判断 为最优解．如果上面条件成 立， 即为最优解，停止迭代．否则，重新确定积 极集．， 循环迭代． ２．２算法的具体步骤 步骤１确定积极集Ｊ＝｛ ：ｎ Ｔ ＝ｂ ｝，非积 极集，＝Ⅳ＼ 步骤２计算 （ －ｄｊ－ ＱｊＡｆｌ，ｂ，） 及ｘ Ｊ＝Ａｊｌ ｂ广Ａ Ｊｌｘｌ、） 然后结合分量 ，， ，得到整体向量 的值． 步骤３若Ａ ≤６，且ｓ，＞１０停止迭代；否则 令Ｊ ＝｛ｉ：０ｉＴ ＞ｂ 或ｓ ＞０｝，Ｊ＝Ｊ 转步骤１． 在这里值得注意的是，选取初始积极集时必 须保证由它迭代产生的所有Ａ，和 （吕 乏 可 硎 值计算不出来，致使算法在找到最优解之前就中 止了运行，如果出现这种情况，就要重新选取初 始积极集，再执行算法程序，因为共有 个约束 函数，所以初始积极集一共有２ 种选择，在这其 中总会有一个初始积极集，能保证由它迭代产生 的所有这些矩阵都是可逆的，进而使算法能顺利 运行，找到最优解． 下面的定理说明，除非算法停止，否则每次 迭代中的积极集都会改变，这样就保证了即使两 次连续迭代中产生同样的主对偶对（ ，ｓ），算法 也不会陷入套牢状态，即总会找到最优点使算法 停 ３ 算法的终止性 定理１ Ｊ和＇， 是算法中两次连续迭代产 生的积极集，则或者当前主对偶对（ ，ｓ）满足 ＫＫＴ系统或者Ｊ＃Ｊ ． 证明在这里不妨设定Ｊ＝Ｊ ，来证（ ，ｓ） 满足ＫＫＴ系统． 因为在算法过程中（ ，ｓ）的表达式是由一阶 最优性条件和补条件得到的，显然（ ，ｓ）也满足 这两个条件，所以只需证明Ａ ≤ｂ和ｓ＞１０即可． 事实上，因为Ｊ：｛ｉ：ａ［ｘ＝ｂ ｝，Ｊ ＝｛ ：０ Ｔ ＞ｂ 或ｓ ＞０｝，相应的，＝｛ｉ：ａ［ｘ≠ｂ ｝，， ＝｛ｉ： 。 ≤ｂ 且Ｓ ≤０｝，所以一方面，由Ｊ：Ｊ 和， 的 定义可知，Ｖ ∈Ｊ ｕ， 都一定不存在０ Ｔ ＞ｂ ， ４２ 哈尔滨师范大学自然科学学报 ２０１１年第２７卷 即Ａｘ￣＜ｂ．另一方面，由ｌ， 的定义Ｖ ｉ∈．， ，ｓ ＞０， 划的最优解，从下面运行结果的表格中可看出。 且已知补条件Ｖ ｉ∈Ｎ，ｓ （ａｒｘ—ｂ ）＝０，则对Ｖ ｉ ∈，＝， 时ｓｉ＝０，即Ｖｉ∈Ｎ，ｓ Ｉ＞０，也就是ｓＩ＞０． 在应用主对偶积极集法求解这些凸二次规划时， 算法分别经过四至一次迭代就得到了最优解，由 此说明，笔者的算法比文献［１］中算法应用更加 广泛，且算法效率同样较高． 例１ 求解约束矩阵Ａ可逆时的凸二次规 划，见表１． ４具体数值例子 最后将主对偶积极集法的具体步骤转换成 了Ｍａｔｌａｂ程序语言，并且用Ｍａｔｌａｂ应用程序求 出了当约束矩阵／ｌ可逆和不可逆时的凸二次规 表１ 输入 输出 Ｑ ｄ Ａ ｂ Ｊ 最优解 迭代次数 ３阶 Ｉ １ ２ ２ ｌ Ｉ１ ２ ３ｊ Ｉ，，２ Ｉ １ １、 ４ ，，１ １ １、 厂１ ０ ０、 ｊ 、 —ｌ （１） ４ ｌ ｌ ２ １ １ ｌ ｌ １ １ ２ｒ，一２ —３ ｌ ，一０．５４３４、 ０．４５６５ 阶 ｆＩ Ｉ ｌ ２ Ｉ ｌ Ｊ ６ ，３ 一：－ｌ一ｌ ２—３ ２ １ Ｉ ｆ ｌ ２ ｌ （１） Ｏ．４７８３ ｌ ｏ ３ ｌ 一２／ｌ １、 １．８０４３ ｌ ４ ６ —５、 ２、 ，２ —５ —６ ４ ／一０．４１８３、 一２ ４ ５ ３ ｓ７ ６ —４ ８ —３ ３ Ｉ ２ ５—０．１７１ｌ ５阶 —７ ２ １ ３ ４ ８ ２ ５ —６ ２ ４ Ｉ ４ ６ ５ —６ ４ ７ ４ ８ 一ｌ 一０．４５２６ ０．５８４５ １．９２７５ ２ ５ ３ ２—１ ２ 例２ 求解约束矩阵Ａ不可逆时的凸二次规划，见表２． 表２ 输入 输出 Ｑ ｄ Ａ ６ Ｊ 最优解 迭代次数 ３阶 ｆ ２ １ —２ Ｉ Ｊ 一３ Ｉ 一ｆ， ２ －４、 ５ ０、 ｒ，１ ５ ４、 ４ —２ ｊ １ －７Ｊ Ｊ ４ ６ ２ Ｉ ６ ９ ３，Ｊ （１） Ｉ ｏ．５２３８ Ｉ ｊ ｏ 厂一０．６１９０、 ２ ４阶 ，Ｉ ３１６ｌ —２４３ １—１５６ ３ —４７ ２ 、／ Ｉ４ １ １ ３］ ｒ 厂０．４４３０、 （ ） ｌＩ １．３２３８ Ｉ 一１．ｏｌｌ４ —ｏ．５２４３Ｊ Ｉ ３ ● ５阶 ｌ『 １ｌ ２ ３ ３ ３ ｌ ７ ｌ ｛ 一４ ３ —２ —６ ４ ２ ３ ４ ４ ｌ —４ ｌ ｌ ３ —２ ０ ４ ３ ｌ ２ ３ ４ ５Ｉ １ ２ ２ ２ ２ ｌ 、 ，一１、 ３ ｌ Ｉ ２ 一ｌ ５ ２ —２ ，，１ ４ ２ —３ ４、 、 ，一７９．９７５０、 一５３．３５０ｏ （４） ７ ｔ０．４３７５ ３３．０１２５ ２ ／ ２ ／ ５ —４ ｏ ８ —５ ５１４．５２５０ 社，１９９７． 参 考 文 献 ［１］ Ｋｕｎｉｓｅｈ Ｋ，Ｒｅｎｄｌ Ｆ．Ａｎ ｉｎｆｅａｓｉｂｌｅ ａｃｔｉｖｅ ｓｅｔ ｍｅｔｈｏｄ ｆｏｒ ｑｕａｄｒａｔｉｃ ｐｒｏｂｌｅｍｓ ｗｉｔｈ ｓｉｍｐｌｅ ｂｏｕｎｄｓ［Ｊ］．Ｓｉａｍｊ Ｏｐｔｉｍ． １４（１）：３５—５２． ［３］ 陈宝林．最优化理论与算法：第２版［Ｍ］．北京：清华大学 出版社． ［４］ 张禾瑞，高等代数［Ｍ］．北京：高等教育出版社． ［５］ 刘卫国，陈昭平，张颖．ＭＡＴＬＡＢ程序设计与应用［Ｍ］．北 京：高等教育出版社． ［２］ 袁亚湘，孙文瑜．最优化理论与方法［Ｍ］．北京：科学出版 第２期 求解凸二次规划的主对偶积极集法 ４３ Ａ Ｐｒｉｍａ１．．．Ｄｕａｌ Ａｃｔｉｖｅ Ｓｅｔ Ｍｅｔｈｏｄ ｆｏｒ Ｑｕａｄｒａｔｉｃ Ｐｒｏｂｌｅｍｓ Ｌｉｕ Ｙｉｎｇ，Ｚｈａｏ Ｄｉ （Ｈａｒｂｉｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ） ＡＢＳＴＲＡＣＴ Ａ Ｄｒｉｍａ１一ｄｕａｌ ａｃｔｉｖｅ ｓｅｔ ｍｅｔｈｏｄ ｆｏｒ ｑｕａｄｒａｔｉｃ ｐｒｏｂｌｅｍｓ ｉｓ ｐｒｅｓｅｎｔｅｄ．Ａ ｐｒｉｍａｌ—ｄｕａｌ ｐａｉｒ（ ，５） ｉｓ ｃ０ｍｐｕｔｅｄ ｔｈａｔ ｓａｔｉｓｆｉｅｓ ｔｈｅ ｆｉｒｓｔ ｏｒｄｅｒ ｏｐｔｉｍａｌｉｔｙ ｃｏｎｄｉｔｉｏｎ ａｎｄ ｔｈｅ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｃｏｎｄｉｔｉｏｎ．Ｉｆ（ ， ）ｉｓ ｎｏｔ ｆｅａＳｉｂｌｅ。ａ ｎｅｗ ａｃｔｉｖｅ ｓｅｔ ｉｓ ｄｅｔｅｒｍｉｎｅｄ，ａｎｄ ｔｈｅ ｐｒｏｃｅｓｓ ｉｓ ｉｔｅｒａｔｅｄ． Ｓｕｆｆｉｃｉｅｎｔ ｃｏｎｄｉｔｉｏｎｓ ｆｏｒ ｔｈｅ ｉｔｅｒａｔｉｏｎｓ ｔ０ ｓｔｏＤ ｉｎ ａ ｆｉｎｉｔｅ ｎｕｍｂｅｒ ｏｆ ｓｔｅｐｓ ｗｉｔｈ ａｎ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ａｒｅ ｐｒｏｖｉｄｅｄ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｅｘｐｅｒｉｅｎｃｅ ｉｎｄｉｃａｔｅｓ ｔｈｉｓ ｍｅｔｈｏｄ ｉｓ ｐｒａｃｔｉｃａ１． Ｋｅｙｗｏｒｄｓ：Ｃｏｎｖｅｘ ｑｕａｄｒａｔｉｃ ｐｒｏｇｒａｍｍｉｎｇ；Ａｃｔｉｖｅ ｓｅｔ；Ｐｒｉｍａｌ—ｄｕａｌ ｐａｉｒ （责任编辑：季春阳） （上接第３９页） 出子图连通，即Ｇ中任意４个点的导出子图连 通，所以图Ｇ是４一点连通图，则由定理３的结 论便得推论．证明结束． 此推论说明了图的连通度较高时，图的关于 完全圈可扩的性质． 参考文献 Ｊ Ａ，Ｍｕｒｔｙ Ｕ Ｓ Ｒ．Ｇｒａｐｈ Ｔｈｅｏｒｙ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ ［１］ Ｂｏｎｄｙ 『Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｍａｃｍｉｌｌａｎ Ｌｏｎｄｏｎ ａｎｄ Ｅｌｓｅｖｉｅｒ，１９７６． Ｈｅｎｄｒｙ Ｇ Ｒ Ｔ．Ｅｘｔｅｎｄｉｎｇ ｃｙｃｌｅｓ ｉｎ ｇｒａｐｈｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ Ｍａｔｈ，１９９０，（８５）：５９—７２． 石玉华，曲晓英．强半无爪图的完全圈可扩性［Ｊ］．山东师 范大学学报：自然科学版，２００６，２１（２）：５—７． Ｆｕｌｌｙ Ｃｙｃｌｅ Ｅｘｔｅｎｓｉｂｉｌｉｔｙ ｏｆ ４一Ｖｅｒｔｉｃｅｓ Ｃｏｎｎｅｃｔｅｄ Ｇｒａｐｈｓ Ｌｉｕ Ｘｉａｏｙａｎ，Ｇａｏ Ｇｕｏｃｈｅｎｇ，Ｓｈｉ Ｚｈｏｕ （Ｓｈａｎｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ） ＡＢＳＴＲＡＣＴ Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｔｈｅ ｆｕｌｌｙ ｃｙｃｌｅ ｅｘｔｅｎｓｉｂｉｌｉｔｙ ｏｆ ４一ｖｅｒｔｉｃｅｓ ｃｏｎｎｅｃｔｅｄ ｇｒａｐｈ ｉｓ ｓｔｕｄｉｅｄ，ａｎｄ ａ ４一ｖｅｒｔｉｃｅｓ ｃｏｎｎｅｃｔｅｄ ｇｒａｐｈ ｗｈｏｓｅ ｏｒｄｅｒ ｉｓｎ’ｔ ｌｅｓｓ ｔｈａｎ ７ ｉｓ ｐｒｏｖｅｄ ｔｏ ｂｅ ｆｕｌｌｙ ｃｙｃｌｅ ｅｘｔｅｎｓｉｂｌｅ．Ｔｈｅｎ ｓｏｍｅ ｋｎｏｗｎ ｒｅｓｕｌｔｓ ｏｆ Ｈｅｎｄｒｙ ａｎｄ Ｓｈｉ Ｙｕｈｕａ ａｒｅ ｇｅｎｅｒａｌｉｚｅｄ．Ａｎｄ ａｎ ｉｎｆｅｒｅｎｃｅ ｉｓ ｇａｉｎｅｄ． Ｋｅｙｗｏｒｄｓ：Ｃｏｎｎｅｃｔｅｄ；ｓ—ｖｅｒｔｉｃｅｓ ｃｏｎｎｅｃｔｅｄ ｇｒａｐｈ；Ｆｕｌｌｙ ｃｙｃｌｅ ｅｘｔｅｎｓｉｂｉｌｉｔｙ （责任编辑：季春阳）