凸二次規(guī)劃基于新的核函數(shù)的大步校正原始－對偶內(nèi)點算法

汪 燕 張明望

（三峽大學(xué)理學(xué)院，湖北宜昌 443002）

本文根據(jù)原始－對偶內(nèi)點算法的思想，基于Zhang M W 提出的一個新核函數(shù)［1］，對凸二次規(guī)劃設(shè)計了新的大步校正原始－對偶內(nèi)點算法.考慮下面的凸二次規(guī)劃及其對偶問題：

其中，x，c，s∈Rn，b，y∈Rm，Q∈Sn＋，A∈Rm×n且rank（A）＝m.

1 預(yù)備知識

1.1 中心路徑

如果（x，y，s）是（P）和（D）的可行解，由對偶理論知，（x，y，s）是（P）和（D）的最優(yōu)解的充要條件是

其中，xs＝（x1s1，x2s2，…，xnsn）T，第3 個方程稱為（P）和（D）的互補(bǔ)性條件.

根據(jù)原始－對偶內(nèi)點算法的基本思想，用參數(shù)方程xs＝μe（μ＞0）代替方程組（1）中的第3個方程，即得如下方程組：

不失一般性，假設(shè)問題（P）和（D）滿足內(nèi)點條件（IPC），即存在內(nèi)點（x0，y0，s0），滿足

這時，對任意的μ＞0，方程組（2）都有唯一解，記為（x（μ），y（μ），s（μ））.集合｛（x（μ），y（μ），s（μ））｝形成了一個同倫路徑，稱之為（P）和（D）的中心路徑.若μ→0，則中心路徑的極限值存在，且滿足互補(bǔ)性條件，故此極限值即為（P）和（D）的最優(yōu)解.

1.2 迭代方向

將牛頓法運用到方程組（2），得方程組

則方程組（4）的解（Δx，Δy，Δz）取作算法的迭代方向.

為了便于算法的分析，對任意的（x，s）＞0，μ＞0，定義：

因此，方程組（4）等價于方程組

本文考慮的障礙函數(shù)Ψ（v）是開區(qū)間（0，＋∞）上光滑的嚴(yán)格凸函數(shù)，且當(dāng)v＝e時取得最小值0，因此

現(xiàn)在用－▽Ψ（v）替換（6）中的第3個方程的右半部分，得方程組

由于A 的秩為m 且滿足（IPC），所以對任意μ＞0，方程組（10）都有唯一解（dx，Δy，ds）.再由（5），從而得到算法新的迭代方向（Δx，Δy，Δs）.

若（x，y，s）≠（x（μ），y（μ），s（μ）），則（Δx，Δy，Δs）≠（0，0，0）.迭代點（x，y，s）沿牛頓方向取步長α，有

又因為Q 是半正定對稱矩陣，所以有

這與線性規(guī)劃中（dx）Tds＝（ds）Tdx＝0不同，這正是本文新算法與線性規(guī)劃相應(yīng)算法及其分析的主要不同之處.

1.3 凸二次規(guī)劃的大步校正原始－對偶內(nèi)點算法

現(xiàn)在具體描述凸二次規(guī)劃的原始－對偶內(nèi)點算法：

Step1：輸入?yún)?shù)τ＞0，精度參數(shù)ε＞0，以及一個固定的障礙校正參數(shù)θ（0＜θ＜1），選一組嚴(yán)格初始可行解（x0，y0，s0），使得Ψ（x0，s0，μ0）≤τ（這里μ0＝（x）0Ts0／n），令x：＝x0，y：＝y(tǒng)0，s：＝s0，μ：＝μ0.

Step2：如果nμ＜ε，停止.此時的（x，y，s）便是ε－最優(yōu)解，否則修改μ＝（1－θ）μ，轉(zhuǎn)Step3.

Step3：Ψ（v）≤τ，返回Step2，否則進(jìn)入Step4.

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

本文引用文獻(xiàn)［1］中的核函數(shù)

以下關(guān)于核函數(shù)的性質(zhì)證明均類似于文獻(xiàn)［1］.

3 凸二次規(guī)劃的算法分析

3.1 步長α的選擇和障礙函數(shù)Ψ（v）的下降

設(shè)在內(nèi)迭代過程中，當(dāng)前點（x，s）經(jīng)過一次內(nèi)迭代之后，得到新的迭代點（x＋，s＋），其中

根據(jù)引理2.1，顯然有f（α）≤f1（α），f（0）＝f1（0）＝0.

對f1（α）關(guān)于α求導(dǎo)可得

定義f（α）：＝Ψ（v＋）－Ψ（v）和

于是

對f1（α）關(guān)于α求二階導(dǎo)數(shù)可得

為方便討論，記δ：＝δ（v），vmin：＝min｛vi｝，i＝1，…，n.

證明 根據(jù)δ（v）的定義，可得‖dx＋ds‖＝2δ，所以有‖dx‖≤2δ和‖ds‖≤2δ，由此可得

由于φ″（t）在（0，＋∞）上單調(diào)遞減，可得

所以

同理

根據(jù)式（15），可得

證畢.

引理3.1.2 如果α滿足不等式

引理3.1.5（文獻(xiàn)［3］中引理12） 若h（t）是一個二階可微函數(shù)且滿足h（0）＝0，h′（0）＜0，如果h（t）在t＊＞0處取得最小值，且h″（t）在［0，t＊］上單調(diào)遞增，則h″（t）≤h′（0）t／2，t∈［0，t＊］.

為討論方便，記s＝ρ（2δ），由ρ的定義，則有－φ′（s）＝4δ.由核函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)可得

所以

注意到0≤s≤1，則有

于是，有

從引理3.1.6，可得

由于式（20）的右邊不等式關(guān)于δ是單調(diào)遞減的，利用引理2.3，可得

其中，這里的第二個不等式用到Ψ0≥Ψ≥τ≥1.

3.2 迭代復(fù)雜性分析

為了估計大步校正內(nèi)點算法總的迭代復(fù)雜性，需要定量計算出算法在μ 修正以后，需要迭代多少步滿足Ψ（v）≤τ.記μ 修正后Ψ（v）的值為Ψ0，此后的序列值記為Ψk，k＝1，2，…，K.K 表示在一次外迭代中內(nèi)迭代的總數(shù)目，則有

引理3.2.1（文獻(xiàn)［3］中的引理14） 設(shè)t0，t1，…，tk是一列正實數(shù)，滿足

引理3.2.2 設(shè)K 表示在一次外迭代之后內(nèi)迭代的總數(shù)目，則有

證明 根據(jù)式（21），可得

證畢.

［1］ 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，28（11）：2313－2328.

［2］ Bai Y Q，El Ghami M，Roos C.A Comparative Study of Kernel Functions for Primal－dual Interior－point Algorithms in Linear Optimization［J］.SIAM Journal on Optimization，2004，15（1）：101－128.

［3］ Peng J，Roos C，Terlaky T.Self－regular Functions and New Search Directions for Linear and Semidefinite Optimization［J］.Mathematical Programming，2002，93：129－171.