幾何規劃（Geometric Program）問題其實是最佳化問題中很常見的問題，如果直接解決該問題的標準形式，是比較困難的，因為幾何規劃一般不是凸最佳化問題，比較難解決。那麼如何把GP問題轉化成凸最佳化問題然後對其進行求解？

目錄：

1。 GP 問題定義

2。 GP問題求解

3。一般問題轉化為GP問題

4。例項

一。 GP問題定義

我們先回顧一下最佳化問題的標準形：

min f_0(x)

s.t. f_i(x) \leq0 , i \in \{1,2,...,k\}

g_j(x)=0, j \in \{1,2,...,l\}

也就是說，最小化某個函式，這個函式的定義域滿足上面的

k+l

個條件。

那麼

GP的標準型

是這樣的：

min f_0(x)

s.t. f_i(x) \leq 1 , i \in \{1,2,...,m\}

g_j(x)=1, j \in \{1,2,...,p\}

其中：

目標函式

f_0

及約束條件

f_1,f_2,...,f_k

為

正項式函式(posynomial function)

， 約束條件

g_1,g_2,...,g_l

為

單項式函式(monomial function)

。

A。 單項式函式（monomial function）的形式：（

R^n \rightarrow R

）

g(x):= a x_1^{a_{1}} x_2^{a_{2}}... x_n^{a_{n}}

其中，

a >0, a_1,a_2,...,a_n \in R

。 也就是說常數倍為正數；冪可正可負，為實數即可。

monomial舉例：

2xy

、

x_1^3x_2^{\frac{1}{3}}

、

x^{-1}y^2

、

1

等，常數也是monomial。 但是，

-xy

不是monomial。因為

a >0

。

因此 monomial 在

乘除運算中閉包

。

B。 正項式函式（posynomial function）的形式 ：

f(x): = \sum_{k=1}^K c_{0,k} x_1^{c_{1,k}} x_2^{c_{2,k}}... x_n^{c_{n,k}}

同樣，

c_{0,k} >0

且

c_{1,k},c_{2,k},...,c_{n,k} \in R

， 這個posynomial就是monomial的加和形式，一共有

K

項單項式函式

相加

。

注意monomial

相減

不是 posynomial

c(x+xyz)^a

是不是posynomial呢？ 也就是說

monomial加和的a次冪

是不是posynomial？當a是

整數

的時候，括號次冪可以展開，因此是posynomial；反之，如果是非整數，那麼這就不是posynomial。

這個

K

等於1時，那麼posynomial等於monomial，也就是說monomial是posynomial的真子集。

這個形式看起來有點兒複雜，為什麼有這個問題的存在呢？ 其實現實場景中GP問題非常常見，舉個簡單的例子：用一塊紙板設計一個長方體，要求長方體的體積最大，但是對面積和長寬高以及其比例有所約束。這個時候就是一個GP問題了。（很多時候在多維空間中，加上一定的約束條件，最大化面積、體積等，大多都是幾何規劃問題）

二、GP問題求解

已知了標準的幾何規劃問題的形式，那麼如何將它轉化為凸最佳化問題，但是不影響結果？

目標函式轉化：

f(x)=\sum_{k=1}^K c_{0,k} x_1^{c_{1,k}} x_2^{c_{2,k}}... x_n^{c_{n,k}}

=\sum_{k=1}^K e^{\log c_{0,k} } e^{{c_{1,k}} \log x_1} e^{{c_{2,k}} \log x_2}...e^{{c_{n,k}} \log x_n} = \sum_{k=1}^{K} \exp\{c_k^T y+h_k \}

其中，

c_k = (c_{1,k},...,c_{n,k} )^T

，

y=(\log x_1,\log x_2,...,\log x_n)^T

，

h_k ={\log c_{0,k} }

。

同樣，約束條件

g_1,g_2,...,g_l

轉化為：

g(x)= a x_1^{a_{1}} x_2^{a_{2}}... x_n^{a_{n}}

=

\exp\{a^T y+h \}

其中，

a= (a_{1},a_{2}...,a_{k} )^T

，

y=(\log x_1,\log x_2,...,\log x_n)^T

，

h ={\log a }

。

因此，

GP問題可以轉化為

：

min f_0(x)= \sum_{k=1}^{K} \exp\{c_k^T y+h_k \}

s.t. f_i(x) = \sum_{k=1}^{K} \exp\{b_k^T y+d_k \} \leq 1 , i \in \{1,2,...,m\}

g_j(x)=\exp\{a^T y+g \}=1, j \in \{1,2,...,p\}

這時候對我們想到

log\sum_{k=1}^{K} \exp\{c_k^T y+h_k \}

是凸函式，且對上面問題取對數不會影響結果，因此

GP最佳化問題變成

：

min \log f_0(x)=\log\sum_{k=1}^{K} \exp\{c_k^T y+h_k \}

s.t. \log f_i(x) = \log\sum_{k=1}^{K} \exp\{b_k^T y+d_k \} \leq 0 , i \in \{1,2,...,m\}

\log g_j(x)=a^T y+g =0, j \in \{1,2,...,p\}

上述式子則變成一個凸最佳化問題，其中

y=(\log x_1,\log x_2,...,\log x_n)^T

是未知的向量變數，透過最最佳化

y =y^*

則可以反推出原問題的最優解

x^*

：

x^*=(e^{y_1^*},e^{y_2^*},...,e^{y_n^*})

證明

f(y)=log\sum_{k=1}^{K} \exp\{c_k^T y+h_k \}

是凸函式。

c_k^T y+h_k

是線性變換，是凸函式，那麼如果我們證明了

log\sum_{k=1}^{K} \exp x_k

也是凸函式，根據保凸運算規則，就可以得證。

證明

f(x)=log\sum_{k=1}^{K} \exp x_k

為凸函式，即證

\forall x,y \in R, \theta f(x)+ (1-\theta) f(y)\geq f(\theta x +(1- \theta)y)

即可。

三、一般問題轉化為GP問題

有很多時候，根據場景描述寫的最佳化問題並不是標準的GP問題，這個時候如何將這些形式轉化為GP問題呢？

取相反數將大於號變成小於號，用乘除法將右邊化成1。

例子略

2. 變數替換，並且將替換方式加入約束條件。

例子：

\min \sqrt{1+x^2} +(1+\frac{y}{z})^{3.1}

，

s.t. \frac{1}{x}+\frac{z}{y}\leq1

，

(\frac{x}{y}+\frac{y}{z})^{2.2}+x+y\leq1

令

t_1 = 1+x^2

；

t_2=1+\frac{y}{z}

；

t_3=\frac{x}{y}+\frac{y}{z}

；則，問題轉化為：

\min t_1^\frac{1}{2} +t_2^{3.1} ; s.t.

\frac{1}{x}+\frac{z}{y}\leq1

，

t_3^{2.2}+x+y\leq1

；

t_1 = 1+x^2; t_2=1+\frac{y}{z};t_3=\frac{x}{y}+\frac{y}{z}

。

但是他們是等號的正項式，問題改寫成：

\min t_1^\frac{1}{2} +t_2^{3.1} ; s.t.

\frac{1}{x}+\frac{z}{y}\leq1；t_3^{2.2}+x+y\leq1；t_1 \geq 1+x^2; t_2 \geq1+\frac{y}{z};t_3 \geq\frac{x}{y}+\frac{y}{z}

取大於等於和取等於是等價的，相當於把該值放大了，但是由於其他的約束條件，這個值只能取邊界值，也就是取等於。簡單的證明下面兩約束條件等價：

A。

f(x)=x^2+1;g(x)=x+1;f(x)^2+g(x)^2\leq1

B。

f(x)\geq x^2+1;g(x)\geq x+1;f(x)^2+g(x)^2\leq1

顯然

A\Rightarrow B，

A是B的充分條件；

(x^2+1)^2 +(x+1)^2\leq f(x)^2+g(x)^2 \leq 1

則：

(x^2+1)^2 +(x+1)^2 \leq 1 \Leftrightarrow A

則：

B\Rightarrow A

；則

A\Leftrightarrow B

3. max函式則進行變數替換，並且修改成大於等於max內每個元素，形成新的約束條件。

\min max\{ x+y,1+(y+z)^\frac{1}{2} \}; s.t. max\{y,x^2\}+max\{yz,0.3\}\leq1;\frac{3xy}{z}\leq 1

令

t_1= max\{ x+y,1+(y+z)^\frac{1}{2} \}; t_2=max\{y,x^2\};t_3=max\{yz,0.3\}

問題轉化為：

\min t_1; s.t. t_2 +t_3\leq1;\frac{3xy}{z}=1;t_1 \geq x+y;t_1 \geq 1+(y+z)^\frac{1}{2};t_2 \geq y; t_2 \geq z^2;t_3 \geq yz; t_3 \geq 0.3

令

t_4 = (y+z)

再轉化為：

t_1 \geq1+t_4^\frac{1}{2};t_4\geq y+z

四、例項

最優功率分配問題

考慮最大最小功率分配問題

\begin{array}{r} \min _{p_{i}, i=1, \ldots, K} \max _{i=1, \ldots, K} \frac{\sum_{j=1, j \neq i}^{K} G_{i j} p_{j}+\sigma_{i}^{2}}{G_{i i} p_{i}} \\ \text { s.t. } 0<p_{i} \leq P_{i}, i=1, \ldots, K \end{array}

這是一個擬凸最佳化問題，定義域為：

D ⊆ R_{++}^K

，該問題可以採用迭代二分法求解。現在考慮採用GP得到最優解。該問題重構為：

\begin{array}{rl} \min _{t, p_{i}, i=1, \ldots, K} & t \\ \text { s.t. } & \frac{\sum_{j=1, j \neq i}^{K} G_{i j} p_{j}+\sigma_{i}^{2}}{G_{i i} p_{i}} \leq t, i=1, \ldots, K \\ & 0<p_{i} \leq P_{i}, i=1, \ldots, K . \end{array}

其中目標函式

t

是一個單項式函式，對於任意約束條件是正項不等式和單項不等式。因此該問題是一個定義域為

D ⊆ R_{++}^K

的GP問題，因此，該非凸幾何規劃可以轉化為凸最佳化問題。

參考文獻

1。

2。最佳化問題-GP（幾何規劃，Geometric Program）

以上就是我的學習或回顧記錄，有部分參考其他的部落格；能力有限如有錯誤歡迎指出。

好記性不如爛筆頭，希望自己多寫多記錄，無論是簡單知識的還是複雜未解決的問題，都記錄一下總是好的。