正定式約束下廣義幾何規(guī)劃的一種線性化方法

韓學(xué)鋒， 楊本朝

(1.河南理工大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河南 焦作 454000；2.信息工程大學(xué) 數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室 河南 鄭州 450000)

?

正定式約束下廣義幾何規(guī)劃的一種線性化方法

韓學(xué)鋒1， 楊本朝2

(1.河南理工大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河南 焦作 454000；2.信息工程大學(xué) 數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室 河南 鄭州 450000)

幾何規(guī)劃是一類具有特殊形式的非線性規(guī)劃問題，正定式幾何規(guī)劃問題借助于凸規(guī)劃問題的求解已基本得到解決. 但廣義幾何規(guī)劃問題作為一種特殊的(DC)規(guī)劃，至今沒有好的求解方法. 利用線性化技術(shù)，將正定式約束下的一類廣義幾何規(guī)劃問題轉(zhuǎn)化為一列凸規(guī)劃問題進(jìn)行求解，構(gòu)造了正定式約束下廣義幾何規(guī)劃的一種新算法，并證明了該算法的全局收斂性.

廣義幾何規(guī)劃； 正定式； 凸規(guī)劃； 最優(yōu)解

0 引言

幾何規(guī)劃是一種特殊的非線性規(guī)劃，在許多實際問題如經(jīng)濟(jì)分析[1]、電路設(shè)計[2]、工程分析與工程設(shè)計、化學(xué)平衡等問題中都可以或近似可以表示為幾何規(guī)劃模型，因此研究幾何規(guī)劃問題有重要意義. 一般情況下，正定式幾何規(guī)劃可以通過對偶轉(zhuǎn)化為凸規(guī)劃進(jìn)行求解，但對于廣義幾何規(guī)劃至今沒有好的求解方法[3]. 本文在文[4-7]基礎(chǔ)上，利用多元函數(shù)泰勒展開式的線性技術(shù)，通過將正定式約束下的一類廣義幾何規(guī)劃問題轉(zhuǎn)化為凸規(guī)劃問題進(jìn)行求解，并用此凸規(guī)劃問題的解來逼近(GGP)的解，構(gòu)造了正定式約束下廣義幾何規(guī)劃的一種新算法，最后證明了該算法具有全局收斂性.

1 問題的提出

本文主要考慮問題

(1)

令ti=exi,i=1,2,…,n,則問題(1)轉(zhuǎn)化為

(2)

2 線性化過程

g1(x)=f1(x)=ATdiag(C)eAx;G1(x)=2f1(x)=ATdiag(C)diag(eAx)A，

(3)

g2(x)=，

(4)

構(gòu)造線性函數(shù)

(5)

對于y∈Rn，引入規(guī)劃問題：

(6)

性質(zhì)1(DCGGP)為凸約束下的(DC)規(guī)劃.

證明因為G1(x),G2(x)均為半正定矩陣，

f1(x),f2(x)為凸函數(shù)，同理hλ(x)也為凸函數(shù),即(DCGGP)為凸約束下的(DC)規(guī)劃.

性質(zhì)2對于任意的y∈Rn，(Py)為凸規(guī)劃.

證明只需證明目標(biāo)函數(shù)和約束函數(shù)為凸函數(shù)即可. 由性質(zhì)1可知，(Py)的約束函數(shù)為凸函數(shù)，而(Py)的目標(biāo)函數(shù)為一凸函數(shù)和一線性函數(shù)之差，即目標(biāo)函數(shù)也為一凸函數(shù).

2) 由(1)式可知，對x,y∈Z，均有f(x)≤h(x)，即有

假設(shè)1(GGP)有最優(yōu)解.

性質(zhì)5若(DCGGP)有最優(yōu)解x*，則x*也一定是(Px*)的最優(yōu)解.

而(Px*)的形式為

顯然(Px*)的KK-T條件與(DCGGP)的KK-T條件相同，即x*一定為(Px*)的KK-T點，又因為(Px*)為凸規(guī)劃，故x*為(Px*)的最優(yōu)解.

3 算法及其全局收斂性分析

算法描述為：

step 1任取x0∈Rn，給定正數(shù)ε，置k=0；

step 3若‖gk‖≤ε，則停止；

step 4求解凸規(guī)劃(Px*),得到它的最優(yōu)解，記為xk+1；

step 5若xk+1=xk， 停止；

step 6置k=k+1，轉(zhuǎn)step 2.

定理1設(shè)xk是由算法得到的迭代點列,若存在某一個k，滿足xk+1=xk，則xk為(DCGGP)的KK-T點.

所以，xk為(DCGGP)的KK-T點.

定理2設(shè){xk}是由算法產(chǎn)生的迭代點列，則{xk}的任一聚點均為(DCGGP)的KK-T點.

又因為hλ(x)為無限次可微函數(shù)，對上式兩邊取極限得：

[1] 呂會茹，王永茂，管巍，等. 基于效用最大化理論關(guān)于保險人監(jiān)管成本的分析[J]. 鄭州大學(xué)學(xué)報：理學(xué)版,2013,45(1)：42-45.

[2] 王杰，周賀松. 增一型分層模糊系統(tǒng)結(jié)構(gòu)的PCA優(yōu)化方法[J]. 鄭州大學(xué)學(xué)報：理學(xué)版,2013,45(2)：59-63.

[3] Stephen B, Seung-Jean K, Lieven V, et al. A tutorial on geometric programming [J]. Optimization and Engineering, 2007, 8(1):67-127.

[4] Qu Shaojian, Zhang Kecun, Wang Fusheng. A global optimization using linear relaxation for generalized geometric programming[J].European Journal of Operational Research, 2008, 190(2): 345-356.

[5] Qu Shaojian, Zhang Kecun, Ji Ying. A new global optimization algorithm for signomial geometric programming via lagrangian relaxation[J]. Applied Mathematics and Computation，2007,184(2):886-894.

[6] Wang Yanjun, Liang Zhian. A deterministic global optimization algorithm for generalized geometric programming[J]. Applied Mathematics and Computation，2005,168(1):722-737.

[7] 黨亞崢，景書杰，張可村. 幾何規(guī)劃的廣義梯度投影內(nèi)點算法[J]. 工程數(shù)學(xué)學(xué)報,2009,26(3)：461-465.

A New Linearization Method for Posynomial Constrained Generalized Geometric Programming

HAN Xue-feng1, YANG Ben-chao2

(1.InstituteofMathematicsandInformationScience,HenanPolytechnicUniversity,Jiaozuo454000，China;2.StateKeyLaboratoryofMathematicEngineeringandAdvancedComputing,InformationEngineeringUniversity,Zhengzhou450002,China)

Geometric programming was a type of nonlinear programming problem in special form. A posynomial geometric programming could be converted to convex programming problem. Therefore, the problem of posynomial geometric programming could be solved just like that of convex program. But generalized geometric programming was a special DC programming, and its problem was very difficult to solve. And so far, there were not any good methods for this problem. By using linearization technique, posynomial constrained generalized geometric programming was converted to a sequence of convex programming, and a new algorithm was proposed the problem of posynomial constrained generalized geometric programming. The proof of global convergence of the proposed algorithm was also given.

generalized geometric programming; posynomial; convex programming; optimization solution

2014-08-25

國家自然科學(xué)基金資助項目，編號11305048.

韓學(xué)鋒(1981-)，男，河南濮陽人，講師，碩士，主要從事優(yōu)化理論研究，E-mail：108242720@qq.com.

O221.2

A

1671-6841(2015)01-0024-04

10.3969/j.issn.1671-6841.2015.01.005