田文娟

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西西安 710126)

自從Karmarkar's algorithm［1］被證明具有多項(xiàng)式的有效性后，多項(xiàng)式就被作為衡量算法有效性的重要指標(biāo)。所以，眾多的內(nèi)點(diǎn)算法被形成，尤其是半定規(guī)劃的內(nèi)點(diǎn)算法。由于其在眾多領(lǐng)域均有著廣泛和重要的應(yīng)用，如經(jīng)濟(jì)、管理、工程設(shè)計(jì)、控制、交通等部門［2－5］。故受到了更多重視。而文中在求解半定規(guī)劃的優(yōu)化問題時，也需考慮其的多項(xiàng)式有效性，而多項(xiàng)式有效性與中心參數(shù)及步長有一定的關(guān)系。但長久以來，中心參數(shù)始終是固定的，且與步長獨(dú)立。本文提出了半定規(guī)劃中基于寬鄰域的可行內(nèi)點(diǎn)算法，且中心參數(shù)與步長有多項(xiàng)式的關(guān)系，在每一次迭代中，中心參數(shù)和步長均是使對偶間隙降到最小的一組最優(yōu)解，收斂性也較好。

1 問題背景

考慮半定規(guī)劃問題(P)及其對偶問題(D)

定義寬鄰域N－∞(1－θ):={(X，y，S)∈F0∶λmin(XS)≥θμ}。半定規(guī)劃(P)和(D)等價于求解最優(yōu)性條件(KKT條件)

考慮式(3)的擾動方程

由于X，S∈Sn，乘積 XS未必屬于Sn。所以，提出相似對稱化算子Hp

對等式系統(tǒng)應(yīng)用牛頓法，可得方程組

定義新的迭代為

其中，α∈［0，1］，σ∈［0，1］。

若 P 滿足 P XS P－1∈Sn，則對于(X，y，S)∈Sn++××Sn++，系統(tǒng)式(6)有唯一解。

本文限制尺度矩陣P滿足

而令式(8)中第三方程的右端項(xiàng)為μI，系統(tǒng)方程組為

則

引理1鄰域N－∞(1－θ)是縮放不變的，即(X，y，S)∈N－∞(1－θ)當(dāng)且僅當(dāng)，(X^(α，σ)，y(α，σ)，S^(α，σ))包含于相應(yīng)的變尺度鄰域。證明與文獻(xiàn)［9］中命題4.1相似。

引理2 設(shè)(ΔX(σ)，Δy(σ)，ΔS(σ))被定義在式(5)中，以下成立

定理1 從式(9)可知，以下關(guān)系成立

令

由式(10)表明，f(α，σ)對于α是一個單調(diào)遞增的函數(shù)。因此，對于任何固定的σ∈［0，1］，若對于最大的，有 f(α，σ)≤0成立，則對于任何 α∈(0，α］有 f(α，σ)≤0 成立。從而，λmin(X(α，σ)S(α，σ))≥θμ(α)＞0 成立，由文獻(xiàn)［9］中引理可知，X(α，σ)≥0，S(α，σ)≥0成立。

設(shè)(X0，y0，S0)∈F0，在每次迭代中，若要對偶間隙μ(α，σ)最小，且滿足(X(α，σ)，y(α，σ)，S(α，σ))∈F，則有以下最優(yōu)問題

優(yōu)化問題式(11)的解法類似于文獻(xiàn)［10］中(18)的解法。

情況1 α =1，f(1，σ)=0，如 f(1，σ)=0 有解，則其最小解可能是式(11)的最優(yōu)解。

情況2 α≠1時，可知 f(α，σ)=0，h(σ):=(a2+a1)σ2+2a0σ －a0=0。

綜上所述，在情況 1，2 中，對于(α，σ)∈(0，1］× (0，1)，將用以上方法求出的可能最優(yōu)解對(α，σ)代入式(11)的目標(biāo)函數(shù)中，使得μ(1－α(1－α))最小，便是要找的最優(yōu)解對(α，σ)。

2 算法及其復(fù)雜性

輸入?yún)?shù) Ai，θ∈(0，1)，ε ＞ 0，初始點(diǎn)(X0，y0，S0)，且其滿足(X0，y0，S0)∈N－∞(1－θ)。計(jì)算，令k:=0。

步驟1 若〈Xk，Sk〉≤ε，則停止。

步驟 3 根據(jù)定理 1，2 計(jì)算 px，qx，ps，qs，p1，q1，r1，p2，q2，r2，a0，a1，a2。

步驟4 下面選擇α，σ。

(1)若 a0=0，令 σ =0，α =1。

(2)若 a0＞0。

1)解方程 f(1，σ)=0，若 f(1，σ)在 σ∈(0，1)有解，則解對(α，σ)=(1，σ)可能是式(11)的最優(yōu)解。

2)解方程組 h(σ)=0，f(α，σ)=0，從而，求的解對(α，σ)∈(0，1)×(0，1)可能是式(11)的最優(yōu)解。

3)將1)，2)中的可能最優(yōu)解對(α，σ)代入式(11)的目標(biāo)函數(shù)中，使得μ(1－α(1－σ))最小，即是所要找的最優(yōu)解對(α，σ)。

步驟 5 令(Xk+1，yk+1，Sk+1)=(X(α，σ)，y(α，σ)，S(α，σ))令 k:=k+1，轉(zhuǎn)步驟1。

證明 由μ(α)=μ(1－α(1－α))得(1－α(1－

而log(1－α(1－σ))≤ －α(1－σ)＜0，所以，只需滿足成立即可。因此，k≥時，迭代終止。

推論1 在算法多項(xiàng)式的證明中，為使寬領(lǐng)域N∞－(1－θ):={(X，y，S)∈F0∶λmin(XS)≥θμ}成立。取 α=1，σ=1－，文獻(xiàn)［11］滿足。此時，其復(fù)雜性為O()與步驟4中1)的效果一致，且明顯不如本文算法。若取α＜1，由于每次迭代的步長變小，對偶間隙趨于零的速度變慢，其的復(fù)雜性將不及O)。因此，與本文每次迭代均取(α，σ)的最優(yōu)解相比，其需要更多的時間，故驗(yàn)證了所提算法更優(yōu)。

［1］Karmarkar N.A new polynomial－ time algorithm for linear programming［J］.Combinatorica，1984(4):373 －395.

［2］Kojima M，Mizuno S，Yoshise A.A polynomial－ time algorithm for a class of linear complementarity problem ［J］.Math Program，1989，44(1 －3):1 －26.

［3］Mizuno S，Todd M Y.On adaptive step primal－ dual interior－ point algorithms for linear programming［J］.Math Operation Result，1993，18(4):964 －981.

［4］Salahi M，Mahdavi－ Amiri N.Polynomial time second order Mehrotra－ type predictor－ corrector algorithms［J］.Application Mathation Comput，2006，183(1):646 －658.

［5］Feng Z，F(xiàn)ang L.A wide neighborhood interior point method with iteration complexity bound for semidefinite programming［J］.Optimation，2010，59(8):1235 －1246.

［6］Nesterov Y，Todd M J.Self－ scaled barriers and interiorpoint methods for convex programming［J］.Math Operation Result，1997，22(1):1 －42.

［7］Nesterov Yu，Todd M J.Primal－ dual interior－ point methods for self－ scaled cones［J］.SIAM Journal Optimization，1998，8(2):324 －364.

［8］Monteiro R D C，Zhang Y.A unified analysis for a class of long－step primal－dual pathfollowing interior－point algorithms for semidenite programming ［J］.Manuscript，1996(11):670－681.

［9］劉長河.錐規(guī)劃中若干內(nèi)點(diǎn)算法的復(fù)雜性分析研究［D］.西安:西安電子科技大學(xué)，2012.

［10］Yang Y.An interior－point algorithm for linear optimization based on a new barrier function ［J］.Applied Mathematics and Computation，2011，25(3):1110 －1127.

［11］Wright S J.Primal－ dual interior－ point method［M］.NZ USA:Siam Press，1997.