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

李 鑫



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

李 鑫

(广西民族师范学院数学与计算机科学系，广西崇左 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）的可行解，则由对偶理论知，(,,)是问题（P）和（D）最优解的充要条件为

用参数方程=（为正实数)来替换方程组（2）中的第三个方程（互补条件），则有

若IPC满足，则对任意的>0，方程组（3）有唯一解(()，()，())，称()为问题（P）的-中心，(()，())为问题（D）的-中心．-中心组成的集合(()，()，())形成了一个同伦路径，称之为问题（P）和（D）的中心路径．当0时，中心路径的极限值存在．又因为此极限值满足互补条件，故此极限点即为问题（P）和（D）的最优解.[3]

1.2 迭代方向

对方程组（3）运用牛顿法，得到如下方程组

方程组（4）的唯一解(,,)用作算法的迭代方向．为了便于算法分析，对任意>0，>0，定义

于是，方程组（4）等价于方程组

注意到，方程组（6）中第三个方程的右边是下面对数障碍函数的负梯度方向

因为是半正定对称矩阵，所以有

△x△s=△x(Q△x-A△y)=△xQ△x≥0． （9）

1.3 CQP的大步校正原始-对偶内点算法

算法的基本框架如下图所示

Input：阈值参数τ≥0；精度参数ε>0；障碍校正参数θ，0<θ<1；严格初始可行点(x0,y0,s0)，μ0=1，使得Ψ(x0,y0,μ0)≤τ；beginx:=x0；y:=y0；s:=s0；μ:=μ0；Whilenμ≥εdobegin （外迭代）μ-校正：μ:=(1-θ)μ；v:=(xs/μ)1/2；whileΨ(v)≥τdo；Begin （内迭代）求解方程组(8)，通过(5)得到新的迭代方向(△x,△y,△s)，选取适当的步长α；更新(s,y,s):=(x,y,s)+α(△x,△y,△s)；endendend

2 核函数和障碍函数的性质

首先，给出()的前三阶导数

容易验证()满足核函数的定义[5].

引理2.1核函数()满足下列不等式：

（a）()>1，任意>0．

（b）()+()>0，任意>0．

（c）()()>0，任意>0．

（d）()<0，任意>0．

在算法的分析中，利用障碍函数()给出的一个邻近度量()，其定义为

基于这个度量，我们直接给出如下结论，其证明类似于文献[6]中引理3.2-3.3以及推论3.4．

引理2.4 核函数()和障碍函数()有如下性质：

（a）若>0，则2-1(1)2≤()≤2-1()2，

（b）()≤2()2，

（c）||||≤1/2+(2())1/2≤1/2+2()．

推论 2.5 如果()1，那么()21．

引理 2.6 假设0≤≤1，+:=/(1)1/2，则(+)≤()+2(1-)·(2()+2((2())1/2)+)．

在-校正之前，有()≤，则(+)≤+2(1)·(2+2(2)1/2)+)．

定义L(n,,):=+2(1)·(2+2(2)1/2)+)．

由于本文考虑大步校正算法，因此()，(1)，于是有L:=L(n,,)=()．

3 CQP的算法分析

3.1 障碍函数()的下降量和步长的取值

迭代点(,,)经过一次内迭代之后，得到新的迭代点+:=+(+αd)·/；+:=+；+:=+(+αd)·/．因此．

定义():=(+)()=((+αd)(+αd))1/2()．

由引理2.2，得()≤1()，其中1():=2-1((+αd)+(+αd)())．显然，(0)=1(0)=0．再对1()求一阶导数和二阶导数，得

为了证明的方便，记1:=min()；:=()．

引理3.1（引理4.1文献[5]）1()≤22(12)．

引理3.2（引理4.2文献[5]）若步长满足(12)+(1)≤2，则不等式1()≤0成立．

引理3.3（引理4.3 文献[5]）设:[0,]→(0,1]是2-1()在区间(0,1]上的反函数，则满足引理3.2的最大步长为:=(2)-1(()(2))．

引理 3.5（引理4.5文献[5]）若步长满足，则()≤2．

为了证明第二个不等式，为此先求2-1()在区间(0,1]上的反函数=()，它由方程

两边取对数可得，1≤1+-1log(4+1)，于是

≥(1+2(4)(1+-1log(4+1))+(4)(1+-1log(4+1))2)-1

≥(1+2(4)(1+-1log(4+1))2+(4)(1+-1log(4+1))2)-1

≥(1+12(1+-1log(4+1))2+3(1+-1log(4+1))2)-1=(1+(12+3)(1+-1log(4+1))2)-1．

应用推论2.5，有

≥(212+6)(1+-1log(4+1))2)-1

≥(218)(1+-1log(4+1))2)-1．

因此

由于不等式(15)的右端关于单调递减，所以由引理2.4(b)，得

3.2 算法的复杂性

为了得到大步校正原始-对偶内点算法的总迭代复杂性，需要计算经过一次-校正之后需多少次内迭代可使()≤．记0为()在-校正之后的初值，在同一次外迭代中内迭代其值依次记为Ψ,=1,2,…，这里表示一次外迭代中内迭代的总次数．

引理 3.7 （引理4.7 文献[6]）设0,1,…,t是一列正实数，且满足=0,1,…-1，其中0，0<γ≤1，则．

引理 3.8 设表示一次外迭代中内迭代的总次数，则．

由定理3.9的结果可以看出，本文提出新算法的迭代复杂性与参数的选取有关．特别地，当=(log)时，算法的迭代复杂性与目前CQP大步校正原始-对偶内点算法最好的迭代复杂性一致，即(1/2loglog/)．

[1] Monterior R D C，Alder L．Interior-path Following Primal-dual Algorithms．Part II：Convex Quadratic Programming [J].Mathematical Programming，1989(1)：43-66．

[2] Den Hertog D. Interior Point Approach to Linear，Quadratic，and Convex Programming： Algorithms and Complexity [M].Dordrecht；Kluwer Academic Publishers，1994．

[3] Wang G Q，Bai Y Q．A New Primal-dual Interior-point Algorithm for Convex Quadratic Programming [J]．Shanghai Univ (Engl Ed)，2008(3)：189-196．

[4] Cai X Z，Wang G Q，Zhang Z H．Complexity Analysis and Numerical Implementation of Primal-dual Interior-point Methods for Convex Quadratic Programming Based on a Finite Barrier [J]. Numerical Algorithms，2013(62)：289-306．

[5] Bai Y Q，Roos C，Gham MEI． A Comparative Study of Kernel Functions for Primal-dual Interior-point Algorithms in Linear Programming[J]. SIAM Journal on Optimization，2004(1)： 101-128．

[6] Zhang M W．A Large-update Interior-point Algorithm for Convex Quadratic Semi-definite Optimization Based on A New Kernel Function [J]. Acta Mathematica Sinica，English Series，2012(11)：2313-2328．

（责任编辑：涂正文）

Interior-point Algorithm for Convex Quadratic Programming Based on A New Class of Kernel Functions

LI Xin

Based on a new class of kernel functions，a large-update primal-dual interior-point algorithm for convex quadratic programming is presented．By using new technical results and favorable properties of the kernel function, the study proves that the iteration complexity for the algorithm is1/2loglog/, which is identical with the currently best iteration bound for large-update primal-dual interior-point algorithms of convex quadratic programming．

convex quadratic programming; kernel function; large-update; interior-point algorithms; iteration complexity

O221.2

A

1009-8135（2016）03-0016-05

2016-01-28

李 鑫（1989-），男，甘肃武威人，广西民族师范学院教师，主要研究最优化理论与应用．

广西重点培育学科（应用数学）建设项目（NO.SXYB2015001）阶段性成果