申培萍,班鳳麗

(河南師范大學數(shù)學與信息科學學院,河南新鄉(xiāng)453007)

1 引言

考慮如下一類帶有多項式約束的廣義分式規(guī)劃問題

廣義分式規(guī)劃問題是一類非凸優(yōu)化模型, 它包含比式和問題、多乘積問題、幾何規(guī)劃問題等. 近年來這類問題的特殊形式已經(jīng)引起許多學者的關注. 一方面, (GFP) 問題通常存在多個非全局的局部最優(yōu)解, 在計算方面有很大的挑戰(zhàn). 另一方面, (GFP) 能廣泛應用于實際問題中, 如運輸行業(yè)、政府合同、經(jīng)濟投資等[1–7]. 關于問題(GFP) 的特殊形式, 文獻[8–11]中已給出不同的求解算法, 如分支定界算法、魯棒算法等. 本文針對一般形式的(GFP) 問題提出一種迭代算法, 利用等價轉化技巧與特殊不等式的有關性質將原問題壓縮為幾何規(guī)劃問題, 通過求解一系列幾何規(guī)劃問題得到原問題的解, 并對算法進行理論分析, 通過數(shù)值算例表明提出的算法是可行有效的.

2 預備知識

為求解問題(GFP), 引入變量ηjt, ξjt, 記

其中T = T1+T2+···+Tp. 并令aj> 0, j = 1,··· ,p1; aj< 0, j = p1+1,··· ,p. 問題(GFP) 有如下等價形式

問題(GFP) 和問題(EGFP) 在如下意義下是等價的.

定理2.1如果(x?,η?,ξ?)是問題(EGFP)的最優(yōu)解,則x?是問題(GFP)的最優(yōu)解. 反之,如果x?是問題(GFP)的最優(yōu)解,那么(x?,η?,ξ?)是問題(EGFP)的最優(yōu)解,其中j =1,2,··· ,p; t=1,2,··· ,Tj.

證由問題(GFP) 和問題(EGFP) 的結構易得結論成立.

基于以上討論, 為了獲得問題(GFP) 的最優(yōu)解, 可以轉而求解其等價問題(EGFP). 令z =(x,η,ξ)∈RN(N =n+2T). 通過改變記號, 問題(EGFP) 可被重新寫為如下形式

為了求解問題(EP), 下面將提出一種迭代算法, 該算法通過求解一系列的幾何規(guī)劃來獲得問題(EP) 的最優(yōu)解. 為此, 需要對問題(EP) 中的約束進行處理與變形, 當k ∈K 時, 根據(jù)的值將不等式約束分成如下兩類

于是問題(EP) 可以寫為如下形式

其中

下面為了求解問題(P1), 我們需要對問題(P1) 中k =0,k ∈Tk2所對應約束的右端項用近似單項式替換. 為此, 考慮如下函數(shù)

其中

接下來, 類似式(2.1)–(2.5) 的結果, 對于給定的點若k =0, 記

則有

若k ∈Tk2, 記

則有

因此問題(P1) 可被壓縮為以下問題

3 算法及其收斂性

根據(jù)上述討論, 問題(GFP) 等價于問題(P1). 給定點ˉz, 利用算術– 幾何平均不等式, 將問題(P1) 壓縮為(P2(ˉz)). 為了獲得原問題(GFP) 的最優(yōu)解, 這里提出一種迭代算法. 給定初始參數(shù)z0和誤差ε. 令ˉz =z0, 計算式(2.6), (2.8) 中的參數(shù)α0i,β0λki,σk, 可構造幾何規(guī)劃問題(P2(ˉz)), 求解(P2(ˉz)) 可獲得新的點z1. 若≤ε 成立, 算法終止, z?=z1即為問題(GFP) 的近似最優(yōu)解. 否則, 令ˉz =z1, 重復上述過程直到滿足終止條件為止. 算法的具體步驟如下

步0給定容許誤差ε>0, 選擇初始點z0, 令迭代次數(shù)r =1.

步1令, 計算式(2.6), (2.8) 中的參數(shù)α0i,β0, λki,σk.

步2求解問題得最優(yōu)解zr.

步3若≤ε, 算法終止. 令z?= zr, 且z?是問題(P1) 的最優(yōu)解. 否則, 令r =r+1, 返回到步1.

算法的實際操作中, 若初始點為非可行點, 那么算法經(jīng)過很少的迭代次數(shù)后就會產(chǎn)生問題(P2的可行點[12]. 因此, 當初始可行點未知時, 可以用非可行點代替.

下面為了討論算法的收斂性, 先給出引理3.1.

引理3.1對于算法中產(chǎn)生的每一點zr(r ≥1) 均有

證由函數(shù)H(z),的定義以及代數(shù)平均不等式易得

進而由Gk(z),的表達式, 容易得出Gk(zr)=k =0,1,··· ,m1+2T.

當k =0 時, 對任意q =1,2,··· ,N +1, 有

當k ∈Tk1,k ∈Tk2時,可類似證明. 從而

定理3.2對于算法中產(chǎn)生的點zr(r ≥1), 假設問題(P2(zr)) 滿足Slater’s 約束規(guī)范.如果算法有限步迭代, 則算法終止于問題(P1) 的KKT 點. 否則, 如果算法產(chǎn)生無窮序列{zr}, 則無窮序列{zr} 的聚點是問題(P1) 的KKT 點.

證若算法迭代r 步后終止. 由于問題(P2(zr)) 滿足Slater’s 約束規(guī)范, 則問題(P2(zr?1)) 的最優(yōu)解zr是它的KKT 點, 即有

其中λk,μk,νi是拉格朗日乘子, C = (?ν0,?ν1,··· ,?νN+1+1)T∈RN+1. 另外, 由算法中的第3 步, 有zr=zr?1. 因此

這意味著zr是問題(P1) 的KKT 點.

若算法是無限步迭代的, 易證序列{zr} 是有界的. 那么序列{zr} 存在一個收斂的子列.不失一般性, 仍記為序列{zr}, 并假設由和的連續(xù)可微性, 對式(3.1)–(3.4) 兩邊取極限, 可得

再結合引理3.1 和式(3.5)–(3.8), 有

因此z?是問題(P1) 的KKT 點. 定理得證.

4 數(shù)值實驗

為驗證算法的有效性, 在酷睿雙核CPU (主頻2.4 GHz), 2GB 內(nèi)存的微機上用Matlab進行數(shù)值計算. 表1 的數(shù)值結果表明本文算法是可行有效的.

例1

例2

例3

表1: 例1–4 的數(shù)值計算結果

例4

由表1 可知, 本文算法的運行時間及迭代次數(shù)較文獻[11, 13] 都有明顯改善, 結果表明提出的算法是可行有效的.

5 結論

本文針對一類帶有多項式約束的廣義分式規(guī)劃問題提出相應的迭代算法, 利用等價轉化技巧與特殊不等式的有關性質將原問題的求解過程轉為一系列幾何規(guī)劃問題的求解, 數(shù)值結果表明提出的算法是可行有效的. 另外, 本文考慮的問題模型中要求fjt(x),gjt(x) 為正的仿射函數(shù), 但是本文算法針對更一般的模型也可以進行求解.