Convex optimization 3.2 --- 凸优化问题 part2
时间：2022-12-22 04:00:00
7 GP(几何规划)
7.1 概念和定义
- monomials
使用log进行处理，并设 x i = e y i x_i=e^{y_i} xi=eyi,monomials 变成线性函数
- posynomial
f ( x ) = ∑ k = 1 k f i ( x ) d o m ( f ) = R n f i ( x ) = c k x 1 α 1 k x 2 α 2 k . . . x n α n k c k > 0 , α n k ∈ R \begin{aligned} f(x) &=\sum \limits_{k=1}^{k}f_i(x) \quad dom(f) = R_{ }^n \\ f_i(x) & =c_k x_1^{\alpha_{1k}} x_2^{\alpha_{2k}} ... x_n^{\alpha_{nk}} \quad c_k>0, \alpha_{nk} \in R \end{aligned} f(x)fi(x)=k=1∑kfi(x)dom(f)=R++n=ckx1α1kx2α2k...xnαnkck>0,αnk∈R
同样的，使用log进行处理，并设 x i = e y i x_i=e^{y_i} xi=eyi，
- GP problem
GP problem并不是凸优化问题，经过转换，根据对数凸函数之和仍然是对数凸函数，转换后的形式是凸函数。
7.2 典型问题
- 求最大值问题
{ m a x x / y s u b 2 ≤ x ≤ 3 x 2 + 3 y / z ≤ ( y ) x / y = z 2 \left \{ \begin{aligned} & max \quad & x/y \\ & sub \quad & 2\leq x \leq 3 \\ & \quad & x^2+3y/z\leq \sqrt(y) \\ & \quad & x/y=z^2 \end{aligned} \right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧maxsubx/y2≤x≤3x2+3y/z≤(y)x/y=z2
这个问题可以转换成GP问题，设
f 0 ( x ) = − x y − 1 f_0(x)=-xy^{-1} f0(x)=−xy−1
f 1 ( x ) = 2 x − 1 f_1(x)=2x^{-1} f1(x)=2x−1
f 2 ( x ) = 1 3 x f_2(x)=\frac{1}{3}x f2(x)=31x
f 3 ( x ) = x 2 y − 1 2 + 3 y 1 2 z − 1 f_3(x)=x^2y^{-\frac{1}{2}}+3y^{\frac{1}{2}}z^{-1} f3(x)=x2y−21+3y21z−1
h 1 ( x ) = x y − 1 z − 2 h_1(x)=xy^{-1}z^{-2} h1(x)=xy−1z−2
就满足了GP 问题。 - Frobenius norm[2] diagonal scaling
y=Mu, 对u进行坐标系放缩 u ˉ = D u , 有 y ˉ = D y \bar{u}=Du,有\bar{y}=Dy uˉ=Du,有yˉ=Dy,其中D是diagonal matrix,并且 D i j > 0 D_{ij}>0 Dij>0。
容易得到 y ˉ = D M D − 1 u ˉ \bar{y}=DMD^{-1}\bar{u} yˉ=DMD−1uˉ
∣ ∣ D M D − 1 ∣ ∣ 2 2 = t r ( ( D M D − 1 ) T ( D M D − 1 ) ) = ∑ i , j = 1 n ( D M D − 1 ) i j 2 = ∑ i , j = 1 n M i j 2 d i 2 / d j 2 \begin{aligned} ||DMD^{-1}||_2^2 & =tr((DMD^{-1})^T(DMD^{-1})) \\ & = \sum \limits_{i,j=1}^{n}(DMD^{-1})_{ij}^2 \\ & = \sum \limits_{i,j=1}^{n}M_{ij}^2d_i^2/d_j^2 \end{aligned} ∣∣DMD−1∣∣22=tr((DMD−1)T(DMD−1))=i,j=1∑n(DMD−1)ij2=i,j=1∑nMij2di2/dj2
坐标系放缩，可以转换成GP问题
m i n ∑ i , j = 1 n M i j 2 d i 2 / d j 2 min \quad \sum \limits_{i,j=1}^{n}M_{ij}^2d_i^2/d_j^2 mini,j=1∑nMij2di2/dj2
8 generalized polynomial
8.1 定义
根据[4],下面这些特殊的方程都是generalized posynomial.
举例，
定义，如果下式中的<
