基于新的核函數(shù)求解凸二次規(guī)劃的內(nèi)點(diǎn)算法

李 鑫

?

基于新的核函數(shù)求解凸二次規(guī)劃的內(nèi)點(diǎn)算法

李 鑫

(廣西民族師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，廣西崇左 532200)

基于一類新的核函數(shù)對凸二次規(guī)劃(CQP)設(shè)計(jì)了一種大步校正內(nèi)點(diǎn)算法．通過應(yīng)用新的技術(shù)性結(jié)果和這類核函數(shù)良好的性質(zhì)，證明了算法的迭代復(fù)雜性為(1/2loglog/)，這與目前凸二次規(guī)劃的大步校正原始-對偶內(nèi)點(diǎn)算法最好的迭代復(fù)雜性一致．

凸二次規(guī)劃；核函數(shù)；大步校正；內(nèi)點(diǎn)算法；迭代復(fù)雜性．

本文考慮如下標(biāo)準(zhǔn)形式的CQP原始問題（P）及其對偶問題（D）：

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

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

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

CQP是線性規(guī)劃的推廣，它在非線性規(guī)劃中占有重要的地位．雖然CQP可被轉(zhuǎn)化為單調(diào)線性互補(bǔ)問題，但一般會擴(kuò)大其規(guī)模，給實(shí)際計(jì)算帶來困難．近些年來關(guān)于CQP內(nèi)點(diǎn)算法的研究，已取得了一些重要的成果[1-3]．最近，X．Z．Cai等[4]對CQP提出了一種基于有限核函數(shù)的大步校正原始-對偶內(nèi)點(diǎn)算法，證明了算法的復(fù)雜性階為(1/2loglog/)．然而，他們所用的這類核函數(shù)與通常的核函數(shù)不同，即它們的障礙項(xiàng)在可行域的邊界上取有限值．

受上述文獻(xiàn)思想的啟發(fā)，本文構(gòu)造了一類新的核函數(shù)，并基于它對CQP提出了一種大步校正原始-對偶內(nèi)點(diǎn)算法．通過應(yīng)用新的技術(shù)性結(jié)果和這類核函數(shù)良好的性質(zhì)，證明了算法的迭代復(fù)雜性為(1/2(1+-1log)2log/)．特別地，當(dāng)=(log)時(shí)，算法得到的迭代復(fù)雜性與目前CQP的大步校正原始-對偶內(nèi)點(diǎn)算法最好的迭代復(fù)雜性一致，即(1/2loglog/)．

1 預(yù)備知識

1.1 中心路徑

假設(shè)問題（P）和問題（D）滿足內(nèi)點(diǎn)條件（IPC），即存在(0,0,0)滿足

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

若(,,)是問題（P）和（D）的可行解，則由對偶理論知，(,,)是問題（P）和（D）最優(yōu)解的充要條件為

用參數(shù)方程=（為正實(shí)數(shù))來替換方程組（2）中的第三個(gè)方程（互補(bǔ)條件），則有

若IPC滿足，則對任意的>0，方程組（3）有唯一解(()，()，())，稱()為問題（P）的-中心，(()，())為問題（D）的-中心．-中心組成的集合(()，()，())形成了一個(gè)同倫路徑，稱之為問題（P）和（D）的中心路徑．當(dāng)0時(shí)，中心路徑的極限值存在．又因?yàn)榇藰O限值滿足互補(bǔ)條件，故此極限點(diǎn)即為問題（P）和（D）的最優(yōu)解.[3]

1.2 迭代方向

對方程組（3）運(yùn)用牛頓法，得到如下方程組

方程組（4）的唯一解(,,)用作算法的迭代方向．為了便于算法分析，對任意>0，>0，定義

于是，方程組（4）等價(jià)于方程組

注意到，方程組（6）中第三個(gè)方程的右邊是下面對數(shù)障礙函數(shù)的負(fù)梯度方向

因?yàn)槭前胝▽ΨQ矩陣，所以有

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

1.3 CQP的大步校正原始-對偶內(nèi)點(diǎn)算法

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

Input：閾值參數(shù)τ≥0；精度參數(shù)ε>0；障礙校正參數(shù)θ，0<θ<1；嚴(yán)格初始可行點(diǎn)(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 （內(nèi)迭代）求解方程組(8)，通過(5)得到新的迭代方向(△x,△y,△s)，選取適當(dāng)?shù)牟介Lα；更新(s,y,s):=(x,y,s)+α(△x,△y,△s)；endendend

2 核函數(shù)和障礙函數(shù)的性質(zhì)

首先，給出()的前三階導(dǎo)數(shù)

容易驗(yàn)證()滿足核函數(shù)的定義[5].

引理2.1核函數(shù)()滿足下列不等式：

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

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

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

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

在算法的分析中，利用障礙函數(shù)()給出的一個(gè)鄰近度量()，其定義為

基于這個(gè)度量，我們直接給出如下結(jié)論，其證明類似于文獻(xiàn)[6]中引理3.2-3.3以及推論3.4．

引理2.4 核函數(shù)()和障礙函數(shù)()有如下性質(zhì)：

（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 假設(shè)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 障礙函數(shù)()的下降量和步長的取值

迭代點(diǎn)(,,)經(jīng)過一次內(nèi)迭代之后，得到新的迭代點(diǎn)+:=+(+αd)·/；+:=+；+:=+(+αd)·/．因此．

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

由引理2.2，得()≤1()，其中1():=2-1((+αd)+(+αd)())．顯然，(0)=1(0)=0．再對1()求一階導(dǎo)數(shù)和二階導(dǎo)數(shù)，得

為了證明的方便，記1:=min()；:=()．

引理3.1（引理4.1文獻(xiàn)[5]）1()≤22(12)．

引理3.2（引理4.2文獻(xiàn)[5]）若步長滿足(12)+(1)≤2，則不等式1()≤0成立．

引理3.3（引理4.3 文獻(xiàn)[5]）設(shè):[0,]→(0,1]是2-1()在區(qū)間(0,1]上的反函數(shù)，則滿足引理3.2的最大步長為:=(2)-1(()(2))．

引理 3.5（引理4.5文獻(xiàn)[5]）若步長滿足，則()≤2．

為了證明第二個(gè)不等式，為此先求2-1()在區(qū)間(0,1]上的反函數(shù)=()，它由方程

兩邊取對數(shù)可得，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．

應(yīng)用推論2.5，有

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

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

因此

由于不等式(15)的右端關(guān)于單調(diào)遞減，所以由引理2.4(b)，得

3.2 算法的復(fù)雜性

為了得到大步校正原始-對偶內(nèi)點(diǎn)算法的總迭代復(fù)雜性，需要計(jì)算經(jīng)過一次-校正之后需多少次內(nèi)迭代可使()≤．記0為()在-校正之后的初值，在同一次外迭代中內(nèi)迭代其值依次記為Ψ,=1,2,…，這里表示一次外迭代中內(nèi)迭代的總次數(shù)．

引理 3.7 （引理4.7 文獻(xiàn)[6]）設(shè)0,1,…,t是一列正實(shí)數(shù)，且滿足=0,1,…-1，其中0，0<γ≤1，則．

引理 3.8 設(shè)表示一次外迭代中內(nèi)迭代的總次數(shù)，則．

由定理3.9的結(jié)果可以看出，本文提出新算法的迭代復(fù)雜性與參數(shù)的選取有關(guān)．特別地，當(dāng)=(log)時(shí)，算法的迭代復(fù)雜性與目前CQP大步校正原始-對偶內(nèi)點(diǎn)算法最好的迭代復(fù)雜性一致，即(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．

（責(zé)任編輯：涂正文）

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-），男，甘肅武威人，廣西民族師范學(xué)院教師，主要研究最優(yōu)化理論與應(yīng)用．

廣西重點(diǎn)培育學(xué)科（應(yīng)用數(shù)學(xué)）建設(shè)項(xiàng)目（NO.SXYB2015001）階段性成果