凸二次規劃基于新的核函數的大步校正原始－對偶內點算法

汪 燕 張明望

（三峽大學理學院，湖北宜昌 443002）

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

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

1 預備知識

1.1 中心路徑

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

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

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

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

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

1.2 迭代方向

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

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

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

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

本文考慮的障礙函數Ψ（v）是開區間（0，＋∞）上光滑的嚴格凸函數，且當v＝e時取得最小值0，因此

現在用－▽Ψ（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 是半正定對稱矩陣，所以有

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

1.3 凸二次規劃的大步校正原始－對偶內點算法

現在具體描述凸二次規劃的原始－對偶內點算法：

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

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

Step3：Ψ（v）≤τ，返回Step2，否則進入Step4.

2 核函數的性質

本文引用文獻［1］中的核函數

以下關于核函數的性質證明均類似于文獻［1］.

3 凸二次規劃的算法分析

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

設在內迭代過程中，當前點（x，s）經過一次內迭代之后，得到新的迭代點（x＋，s＋），其中

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

對f1（α）關于α求導可得

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

于是

對f1（α）關于α求二階導數可得

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

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

由于φ″（t）在（0，＋∞）上單調遞減，可得

所以

同理

根據式（15），可得

證畢.

引理3.1.2 如果α滿足不等式

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

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

所以

注意到0≤s≤1，則有

于是，有

從引理3.1.6，可得

由于式（20）的右邊不等式關于δ是單調遞減的，利用引理2.3，可得

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

3.2 迭代復雜性分析

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

引理3.2.1（文獻［3］中的引理14） 設t0，t1，…，tk是一列正實數，滿足

引理3.2.2 設K 表示在一次外迭代之后內迭代的總數目，則有

證明 根據式（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.