組合同倫法求一般非線性規(guī)劃問題

黃青群

（河池學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 宜州 546300）

組合同倫法求一般非線性規(guī)劃問題

黃青群

（河池學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 宜州 546300）

文章把含有等式約束和不等式約束的一般非線性規(guī)劃問題轉(zhuǎn)化為只有不等式約束的非線性規(guī)劃問題，然后構(gòu)造一個新的同倫方程，與牛頓法結(jié)合得到一個新的同倫算法，在變形錐條件下，證明了算法的全局線性收斂性。

組合同倫；一般凸規(guī)劃；全局收斂性；牛頓法

1 引言

同倫算法是大范圍的收斂算法，它是求解非線性方程組的一種新途徑。由于非線性方程組的復(fù)雜性，導(dǎo)致很難直接求得其相應(yīng)的解，此時可以構(gòu)造一個相對容易求解的方程組，從求解后者的解出發(fā)，通過路徑跟蹤從而求得前者的解。這就是同倫算法的基本思路。同倫算法已經(jīng)應(yīng)用到了不同的非線性規(guī)劃問題，如線性互補問題[1]、多目標(biāo)優(yōu)化問題[2]、均衡規(guī)劃問題[3]等等。本文把含有等式約束和不等式約束的一般非線性規(guī)劃問題轉(zhuǎn)化為只有不等式約束的非線性規(guī)劃問題，然后構(gòu)造一個新的同倫方程，與牛頓法結(jié)合得到一個新的同倫算法，在變形錐條件下，證明了算法的全局線性收斂性。

考慮一般非線性規(guī)劃問題(GNLP)：

充分光滑的凸函數(shù)。由文獻(xiàn)[4]知可將問題(1)轉(zhuǎn)化為問題(2)進(jìn)行求解：

問題(2)的KKT系統(tǒng)為：

目前為止，很多文獻(xiàn)在“法錐條件”、“弱法錐條件”、“擬法錐條件”或“偽法錐條件”下證明了同倫路徑的存在性以及收斂性。本文在變形錐條件下證明同倫路徑的存在性以及收斂性，該條件比“法錐條件”、“弱法錐條件”、“擬法錐條件”及“偽法錐條件”更容易滿足。

為了求解問題(2)，構(gòu)造同倫方程：

作如下的假設(shè)：

(A1)Ω0非空有界；

(A2)? x ∈Ω，矩陣{? g i(x):i∈ B(x);?hi(x):i∈E}列滿秩；

(A3)(變形錐條件【5】) 設(shè) T(x,x0):Rn→ Rn是二次連續(xù)可微的，滿足：

（1）對任意的 x0,T = 0當(dāng)且僅當(dāng) x = x0；

（2） ?y∈ Rm,x ∈?Ω，若 T(x,x0) ≠ 0，則

其中I(x) ={i ∈{m + 1,6 ,m + r}:hi(x ) =0}。

（3）對任意的 x0，矩陣是列滿秩的。

本文結(jié)構(gòu)如下，第2節(jié)給出了β-錐鄰域的定義以及算法的基本框架，第3節(jié)給出了算法的全局線性收斂性證明。

2 算法

同倫方法主要是在 β-錐鄰域內(nèi)通過追蹤同倫路徑從而得到原方程的解，所以首先給出β-錐鄰域的定義：

稱 N (β ,μ)為β-錐鄰域，β＞0稱為為鄰域半徑。下面引理說明β-錐鄰域在可行域內(nèi)部。

引理1[4]設(shè) y＞ 0,z＞o,β ∈ (0,1)則有

下面給出本文算法。

算法:

步0.(初始化)

令

步1.(終止條件)

若μ ＜ε，則算法停止,ωk=(xk,yk,zk)T即為問題(4)的

k解。

步2.(更新參數(shù) ρk)

計算

取

步3.(計算牛頓方向)

固定 μk，求解線性方程組

得

步4.(線性搜索)

取 λk為 1, δ, δ2,6中的最大值，使之滿足

令

返回步1。

引理2 如果 f(x),gi(x),i∈ I,hi(x),i∈ E 是充分光滑的凸函數(shù)，初始點 ω0∈Ω0× R+m

+

× R+

r+，那么對于任意μ∈ (0,1],(ω,μ) ∈ N(β,μ) ,H'(ω,μ)是非奇異矩陣。

ω

證 通過計算整理，有

其中

有

由于 f(x),g(x),i∈ I,hi(x),i∈ E 是充分光滑的凸函數(shù)，所以?2f(x), ?2gi(x), ?2hi(x)是半正定矩陣，又從算法可得yi＞0,i ∈I,zi-ρ＞0,i∈ E ，于是 Q(ω)為半正定矩陣，因為Y,Z,E(x)是正對角矩陣，通過計算知 W (ω)也是半正定矩陣，故對任意 μ∈ (0,1],(ω,μ) ∈ N(β,μ)，有(1-μ)Q( ω)+ E(x)+W(ω)為正定矩陣，G(x),H(x)為非奇異矩陣。所以亦即為非奇異矩陣。

定理1 算法是良定的。

證 由引理2及算法中的(5)知 Hω'(ω,μ)是非奇異的,于是方程組(5)有唯一解，所以算法的步3良定。由文獻(xiàn)[4]知，存在整數(shù)c1,c2,c3，當(dāng)時(6)成立，于是算法的步4良定。綜上可得整個算法是良定的。

3 算法的全局收斂性

為證明算法全局線性收斂性給出以下假設(shè)：

H3.1 由算法產(chǎn)生的序列{ωk}有界，且其聚點滿足嚴(yán)格互補條件。

引理5說明了問題(1)與問題(2)之間的關(guān)系。

引理5[4]設(shè)ρ為給定值，若x是問題(2)的KKT點，則x是問題(1)的KKT點。

引理 6[4]存在正整數(shù) k0，使得對所有 k≥k0，有ρk≡ ρk0≡ ρ,k∈K 。

下面證明算法的全局線性收斂性。

定理2 設(shè)算法產(chǎn)生的無窮序列為{(ωk,μk)}，那么下列結(jié)論成立

（1）對于 k= 0,1,2,···

故{μk}全局收斂于0。

（4）序列{ωk}線性收斂到問題(4)的解，即{xk}線性收斂到問題(2)的解，從而得到問題(1)的解。

證

（1）對k進(jìn)行數(shù)學(xué)歸納法證明。當(dāng)k=0時，由算法的步0可知結(jié)論成立.假設(shè)對任意的k＞0結(jié)論都成立，那么對于k+1，根據(jù)β-錐鄰域的定義及算法的步驟4有而而且

故結(jié)論成立。

（2）根據(jù)定理1中對步驟4良定性的證明過程可知，對任意k≥0，有其中于是

所以{μk}全局收斂于0。

（3）根據(jù)同倫方程(4)可知，存在常數(shù) c4＞ 0，使得因此有

（4）根據(jù)由算法可得

這說明{ωk}是一個Cauchy序列而且收斂到一點ω*，因為(ωk,μk)∈N (β,μk)所以ω*為(4)的一個解，亦即 x*為問題(2)的解，從而也就是問題(1)的解。

[1] 楊丹丹,韓海山,李園.基于不動點迭代法解線性互補問題[J].內(nèi)蒙古民族大學(xué)學(xué)報(自然科學(xué)版),2014,29(4):388-389.

[2] 賀莉,譚佳偉,陳嘉,等.混合約束多目標(biāo)優(yōu)化問題的凝聚同倫內(nèi)點方法[J].吉林大學(xué)學(xué)報(理學(xué)版),2014,52(2):212-218.

[3] 何非,商玉鳳,梁心,等.半內(nèi)點同倫方法解均衡規(guī)劃問題[J].吉林大學(xué)學(xué)報(理學(xué)版),2014,52(3):470-474.

[4] Q. Huang, Zh.Zhu,X.Wang.A predictor-corrector algorithm combined conjugate gradient with homotopy interior point for general nonlinear programming[J].Applied Mathematics and Computation,2013(219):4379-4386.

[5] 張珊.非線性規(guī)劃的同倫內(nèi)點方法[D].長春:吉林大學(xué), 2008.

Combined homotopy method for general nonlinear programming problem

This paper transfers the general nonlinear programming with equality constraints and inequality constraints problem into a nonlinear programming problem with inequality constraints only, and then constructs a new homotopy equation, finally combines with Newton's method to get a new homotopy algorithm. Under the condition of deformation cone, it proves the global linear convergence of the algorithm.

Combined homotopy; general convex programming; global convergence; Newton’s method

O232

A

1008-1151(2016)07-0132-03

2016-06-11

廣西高?？蒲许椖浚?013LX120）；河池學(xué)院教改課題（2014EB019）；河南省高校重點科研項目（17A110032）。

黃青群（1980－），女，廣西梧州人，河池學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院講師，碩士，研究方向為優(yōu)化理論與算法。