基于新的核函数求解凸二次规划的内点算法

李 鑫



基于新的核函数求解凸二次规划的内点算法

李 鑫

(广西民族师范学院数学与计算机科学系，广西崇左 532200)

基于一类新的核函数对凸二次规划(CQP)设计了一种大步校正内点算法．通过应用新的技术性结果和这类核函数良好的性质，证明了算法的迭代复杂性为(1/2loglog/)，这与目前凸二次规划的大步校正原始-对偶内点算法最好的迭代复杂性一致．

凸二次规划；核函数；大步校正；内点算法；迭代复杂性．

本文考虑如下标准形式的CQP原始问题（P）及其对偶问题（D）：

（P） min{cx+2-1xQx:=,≥0}，

（D） max{by-2-1xQx:Ay-Qx+=,≥0}，

其中，,,∈R，,∈R，∈，∈R且()=．

CQP是线性规划的推广，它在非线性规划中占有重要的地位．虽然CQP可被转化为单调线性互补问题，但一般会扩大其规模，给实际计算带来困难．近些年来关于CQP内点算法的研究，已取得了一些重要的成果[1-3]．最近，X．Z．Cai等[4]对CQP提出了一种基于有限核函数的大步校正原始-对偶内点算法，证明了算法的复杂性阶为(1/2loglog/)．然而，他们所用的这类核函数与通常的核函数不同，即它们的障碍项在可行域的边界上取有限值．

受上述文献思想的启发，本文构造了一类新的核函数，并基于它对CQP提出了一种大步校正原始-对偶内点算法．通过应用新的技术性结果和这类核函数良好的性质，证明了算法的迭代复杂性为(1/2(1+-1log)2log/)．特别地，当=(log)时，算法得到的迭代复杂性与目前CQP的大步校正原始-对偶内点算法最好的迭代复杂性一致，即(1/2loglog/)．

1 预备知识

1.1 中心路径

假设问题（P）和问题（D）满足内点条件（IPC），即存在(0,0,0)满足

0=,0>0,Ay00+0=c,0>0． （1）

若(,,)是问题（P）和（D）的可行解，则由对偶……