幾何規(guī)劃內(nèi)點算法的復雜性研究.pdf

1、幾何規(guī)劃是一類在工程設計中應用廣泛的數(shù)學問題。通常一個幾何規(guī)劃問題可以表述為： (GP)minf0(x)s.t.fi(x)≤1i=1,…，mx＞0其中x∈Rn，f0(x)=(∑k∈K0)Tk，fi(x)=(∑k∈Ki)Tki=1,…，mTk=ck(nΠj=1)xjakj是posynomial函數(shù)，Ki∩Kj=φ(i≠j)，(m∪i=0)Ki={1,…，M}。 幾何規(guī)劃問題本身不是凸規(guī)劃，但是我們可以把它轉(zhuǎn)化成凸規(guī)劃來研究

2、。 本文的主要工作是受凸規(guī)劃問題的錐自對偶嵌入算法[1]的啟發(fā)給出了求解幾何規(guī)劃問題一種內(nèi)點算法，并證明了該算法是多項式時間的。 我們先給出了幾何規(guī)劃問題的凸規(guī)劃形式的對偶問題，并把對偶問題轉(zhuǎn)化成了混合凸規(guī)劃形式，這一形式是在標準凸規(guī)劃的基礎(chǔ)上增加了一個決策變量的凸錐的限制。然后給出幾何規(guī)劃問題混合凸規(guī)劃的自對偶嵌入模型。最后我們證明了自對偶嵌入模型的障礙函數(shù)是自協(xié)調(diào)的，從而由Nesterov和Neminrovski自協(xié)