李 鑫

?

基于新的核函數求解凸二次規(guī)劃的內點算法

李 鑫

(廣西民族師范學院數學與計算機科學系，廣西崇左 532200)

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

凸二次規(guī)劃；核函數；大步校正；內點算法；迭代復雜性．

本文考慮如下標準形式的CQP原始問題（P）及其對偶問題（D）：

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

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

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

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

受上述文獻思想的啟發(fā)，本文構造了一類新的核函數，并基于它對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）最優(yōu)解的充要條件為

用參數方程=（為正實數)來替換方程組（2）中的第三個方程（互補條件），則有

若IPC滿足，則對任意的>0，方程組（3）有唯一解(()，()，())，稱()為問題（P）的-中心，(()，())為問題（D）的-中心．-中心組成的集合(()，()，())形成了一個同倫路徑，稱之為問題（P）和（D）的中心路徑．當0時，中心路徑的極限值存在．又因為此極限值滿足互補條件，故此極限點即為問題（P）和（D）的最優(yōu)解.[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()在區(qū)間(0,1]上的反函數，則滿足引理3.2的最大步長為:=(2)-1(()(2))．

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

為了證明第二個不等式，為此先求2-1()在區(qū)間(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-），男，甘肅武威人，廣西民族師范學院教師，主要研究最優(yōu)化理論與應用．

廣西重點培育學科（應用數學）建設項目（NO.SXYB2015001）階段性成果