凸優化學習：PART3凸優化問題（持續更新）

凸優化問題

凸優化問題的廣義定義：

• 目标函數為凸函數
• 限制集合為凸集

一、優化問題

基本用語

一般優化問題的描述：

minimize ⁡ f 0 ( x )  subject to  f i ( x ) ⩽ 0 , i = 1 , ⋯   , m h i ( x ) = 0 , i = 1 , ⋯   , p (1) \begin{array}{ll} \operatorname{minimize} & f_0(x) \\ \text { subject to } & f_i(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_i(x)=0, \quad i=1, \cdots, p \end{array}\tag{1} minimize subject to ​f0​(x)fi​(x)⩽0,i=1,⋯,mhi​(x)=0,i=1,⋯,p​(1)

相關定義：

x ∈ R n x\in \R^n x∈Rn：優化變量，optimization variable

f 0 : R n → R f_0:\R^n\rightarrow R f0​:Rn→R：目标函數/損失函數，objective function/cost function

若是一個極大化問題，那麼稱為 效用函數 utility function

f i ( x ) ≤ 0 : R n → R f_i(x)\leq 0:\R^n\rightarrow \R fi​(x)≤0:Rn→R：不等式限制，inequality constraint

h i ( x ) = 0 h_i(x)=0 hi​(x)=0：等式限制 equality constraint

m = p = 0 m=p=0 m=p=0：無限制 unconstraited

優化問題的域：domain；所有函數定義域的交集

D = ⋂ i = 0 m dom ⁡ f i ∩ ⋂ i = 1 p dom ⁡ h i \mathcal{D}=\bigcap_{i=0}^m \operatorname{dom} f_i \cap \bigcap_{i=1}^p \operatorname{dom} h_i D=i=0⋂m​domfi​∩i=1⋂p​domhi​

可行解集：feasible set，使得問題限制滿足的解的集合

注意，還需要在目标函數的定義域内

最優點與局部最優點

最優點與局部最優點：若可行解集合不是空集那麼總是能在集合中找到一個X，使得目标函數最優，這個值稱為最優值。

P ∗ = inf ⁡ { f 0 ( x ) ∣ X ∈ X f } P^*=\inf \{f_0(x)|X\in X_f\} P∗=inf{f0​(x)∣X∈Xf​}

若 X f X_f Xf​為空集，那麼 P ∗ = ∞ P^*=\infty P∗=∞

最優解：若 X ∗ X^* X∗可行，且 f 0 ( X ∗ ) = P ∗ f_0(X^*)=P^* f0​(X∗)=P∗

最優解集：最優解的集合

X o p t = { X ∣ X ∈ X f , f 0 ( X ) = P ∗ } X_{opt}=\{X|X\in X_f,f_0(X)=P^*\} Xopt​={X∣X∈Xf​,f0​(X)=P∗}

ϵ − \epsilon- ϵ−次優解集：satisficing solution

限制一般要滿足，目标函數值不一定要達到最優值，可以離最優值小一定的距離 ϵ \epsilon ϵ

X ϵ = { X ∈ X f , f 0 ( X ) ≤ P ∗ + ϵ } X_{\epsilon}=\{X\in X_f,f_0(X)\leq P^*+\epsilon\} Xϵ​={X∈Xf​,f0​(X)≤P∗+ϵ}

局部最優解：

域、可行解集、全局最優解、局部最優解， ϵ \epsilon ϵ解集之間的關系：

若 x ∈ X f , f i ( x ) = 0 x\in X_f,f_i(x)=0 x∈Xf​,fi​(x)=0，則 f i ( x ) ≤ 0 f_i(x)\leq 0 fi​(x)≤0為活動限制； f i ( x ) < 0 f_i(x)<0 fi​(x)<0為不活動限制。

排除臨界點的方法：

可行性優化問題

可行性優化問題一般可以寫成下面的形式：

 find  x  subject to  f i ( x ) ⩽ 0 , i = 1 , ⋯   , m h i ( x ) = 0 , i = 1 , ⋯   , p . \begin{array}{ll} \text { find } & x \\ \text { subject to } & f_i(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_i(x)=0, \quad i=1, \cdots, p . \end{array}  find  subject to ​xfi​(x)⩽0,i=1,⋯,mhi​(x)=0,i=1,⋯,p.​

如何寫成标準的形式？寫成最優化一個常數。

問題的标準表示

框限制 Box Constraints

minimize f 0 ( x ) subject to l 1 ≤ x i ≤ u i , i = 1 , . . . , n \begin{array}{ll} \text{minimize}& f_0(x)\\ \text{subject to}& l_1\leq x_i\leq u_i,i=1,...,n \end{array} minimizesubject to​f0​(x)l1​≤xi​≤ui​,i=1,...,n​

即每個變量都有一個上界和下界，那麼可以轉換為下面的标準形式：

minimize f 0 ( x ) subject to l i − x i ≤ 0 , i = 1 , . . . , n x i − u i ≤ 0 , i = 1 , . . . , n \begin{array}{ll} \text{minimize}& f_0(x)\\ \text{subject to}& l_i-x_i\leq 0,i=1,...,n\\ & x_i-u_i\leq 0,i=1,...,n \end{array} minimizesubject to​f0​(x)li​−xi​≤0,i=1,...,nxi​−ui​≤0,i=1,...,n​

等價問題

如果從一個問題的解，很容易得到另一個問題的解，并且反之亦然，那麼我們稱兩個問題是等價的。作為一個簡單的例子，考慮：

minimize ⁡ f ~ ( x ) = α 0 f 0 ( x )  subject to  f ~ i ( x ) = α i f i ( x ) ⩽ 0 , i = 1 , ⋯   , m h ~ i ( x ) = β i h i ( x ) = 0 , i = 1 , ⋯   , p (2) \begin{array}{ll} \operatorname{minimize} & \tilde{f}(x)=\alpha_0 f_0(x) \\ \text { subject to } & \tilde{f}_i(x)=\alpha_i f_i(x) \leqslant 0, \quad i=1, \cdots, m \\ & \tilde{h}_i(x)=\beta_i h_i(x)=0, \quad i=1, \cdots, p \end{array}\tag{2} minimize subject to ​f~​(x)=α0​f0​(x)f~​i​(x)=αi​fi​(x)⩽0,i=1,⋯,mh~i​(x)=βi​hi​(x)=0,i=1,⋯,p​(2)

很多時候限制的量級不同，量級過大導緻限制的權重變化。通過等價轉換，可以将問題的限制進行标準化。

目标函數和限制函數的變換

設： ψ 0 : R → R \psi_0:\R\rightarrow \R ψ0​:R→R單增； ψ 1 , . . . , ψ m : R → R \psi_1,...,\psi_m:\R\rightarrow \R ψ1​,...,ψm​:R→R滿足：當且僅當 u ≤ 0 u\leq 0 u≤0時 ψ i ( u ) ≤ 0 ; ψ m + 1 , . . . , ψ m + p : R → R \psi_i(u)\leq 0;\psi_{m+1},...,\psi_{m+p}:\R\rightarrow \R ψi​(u)≤0;ψm+1​,...,ψm+p​:R→R滿足：當且僅當 u = 0 u=0 u=0時 ψ i ( u ) = 0 \psi_i(u)=0 ψi​(u)=0。我們定義函數 f ~ i \tilde f_i f~​i​和 h ~ i \tilde h_i h~i​為複合函數：

f ~ i ( x ) = ψ ( f i ( x ) ) , i = 0 , . . . , m h ~ i ( x ) = ψ m + i ( h i ( x ) ) , i = 1 , . . . , p \tilde f_i(x)=\psi(f_i(x)),i=0,...,m\qquad \tilde{h}_i(x)=\psi_{m+i}(h_i(x)),i=1,...,p f~​i​(x)=ψ(fi​(x)),i=0,...,mh~i​(x)=ψm+i​(hi​(x)),i=1,...,p

顯然，問題

與标準形式式1等價且同解。并且式2是 ψ \psi ψ為線性函數的一種特例。

例：最小函數和最小範數平方問題

min ⁡ ∣ ∣ A X − b ∣ ∣ 2 \min ||AX-b||_2 min∣∣AX−b∣∣2​

上述問題是一個無限制的優化問題，等價于最小化二範數的平方。

min ⁡ ∣ ∣ A X − b ∣ ∣ 2 2 \min ||AX-b||_2^2 min∣∣AX−b∣∣22​

原因是原函數在實數域内單調遞增。

松弛變量

f i ( x ) ≤ 0 f_i(x)\leq 0 fi​(x)≤0等價于 ∃ s i ≥ 0 , f i ( x ) + s i ( x ) = 0 \exist s_i\geq 0,f_i(x)+s_i(x)=0 ∃si​≥0,fi​(x)+si​(x)=0，将問題進行轉換，得到：

引入 s i s_i si​後，問題就不僅是關于x的優化問題了。對于問題的凸性，需要對變量x和s同時驗證。

進行松弛後，将變量的維數和限制都增加了。但有些時候，會通過松弛變量，将問題的結構轉換為更加通用的結構。

等式限制的消除

例：等式限制的消除

對于優化問題而言，限制的數目越多，優化越複雜，是以消除等式限制是降低優化問題難度的一個重要方法。

{ h i ( x ) = 0 , i = 1 , . . . , p } (3) \{h_i(x)=0,i=1,...,p\}\tag{3} {hi​(x)=0,i=1,...,p}(3)

是一組方程。假設我們能夠得到這組方程的解，那麼用一組參數 z ∈ R k z\in \R^k z∈Rk來顯式地參數化等式限制。設函數 ϕ : R k → R n \phi:\R^k\rightarrow \R^n ϕ:Rk→Rn是這樣的函數： x x x滿足式（3）等價于存在一些 z ∈ R k z\in\R^k z∈Rk，使得

x = ϕ ( z ) x=\phi(z) x=ϕ(z)

那麼優化問題

與原問題式1等價。求解出 z z z後，可由 x = ϕ ( z ) x=\phi(z) x=ϕ(z)得出最優解 x x x。

相當于用變量z去表示x，然後代入原目标函數和限制中。

等式定義了一組超平面，可以表示為特解+一組基的形式。

例：消除線性等式限制 A X − b = 0 AX-b=0 AX−b=0

A ∈ R p × n A\in \R^{p\times n} A∈Rp×n，是否能找到一組 z z z表示X呢？

分情況讨論：

• A X − b = 0 AX-b=0 AX−b=0無解，那麼原問題無可行解
• 反之，令 x 0 x_0 x0​為等式限制的任意可行解，那麼通解可以表示為 F z + x 0 Fz+x_0 Fz+x0​。即 ϕ ( z ) = F z + x 0 \phi (z)=Fz+x_0 ϕ(z)=Fz+x0​

二、凸優化

标準形式的凸優化問題

凸優化問題是形如：

minimize ⁡ f 0 ( x )  subject to  f i ( x ) ⩽ 0 , i = 1 , ⋯   , m a i x = b i , i = 1 , ⋯   , p (4) \begin{array}{ll} \operatorname{minimize} & f_0(x) \\ \text { subject to } & f_i(x) \leqslant 0, \quad i=1, \cdots, m \\ & a_i^x=b_i, \quad i=1, \cdots, p \end{array}\tag{4} minimize subject to ​f0​(x)fi​(x)⩽0,i=1,⋯,maix​=bi​,i=1,⋯,p​(4)

從廣義上來說，如果目标函數是一個凸函數，限制的集合為凸集，那麼問題就是凸問題。

狹義上的凸問題：

• 目标函數是凸函數
• 不等式限制的函數也是凸函數
• 等式限制函數是仿射函數

在這樣的定義下，凸優化問題的可行域一定是凸的，因為他是問題定義域

D = ⋂ i = 0 m d o m f i \mathcal{D}=\bigcap_{i=0}^m\bold{dom}f_i D=i=0⋂m​domfi​

（凸集），m個下水準集，以及p個超平面的交集。是以，在凸優化問題中，我們是在一個凸集上極小化一個凸的函數。

若目标函數變為拟凸函數，那麼該問題成為拟凸優化問題。但如果目标函數是凹函數，或者其他函數，那麼我們統一稱之為非凸優化問題。

例：

min ⁡ f 0 ( x ) = x 1 2 + x 2 2 s.t. { f 1 ( x ) : x 1 1 + x 2 2 ≤ 0 h 1 ( x ) : ( x 1 + x 2 ) 2 = 0 \min f_0(x)=x_1^2+x_2^2\\ \text{s.t.}\begin{cases}f_1(x):\frac{x_1}{1+x_2^2}\leq 0\\ h_1(x):(x_1+x_2)^2=0\end{cases} minf0​(x)=x12​+x22​s.t.{f1​(x):1+x22​x1​​≤0h1​(x):(x1​+x2​)2=0​

表面上看不是狹義的凸問題，可以轉換為下面的形式：

如果等式限制是一個放射限制，那麼可利用等式限制對問題進行降維：

一般來說，不對問題進行降維，有必要的情況才會進行降維。

凹最大化問題

限制不變，若目标是最大化一個凹函數，那麼等價于最小化一個凸函數，即，該情況下仍是凸優化問題。

max ⁡ f 0 ( x ) ⇔ min ⁡ − f 0 ( x ) \max f_0(x)\Leftrightarrow \min -f_0(x) maxf0​(x)⇔min−f0​(x)

同理，如果 f 0 ( x ) f_0(x) f0​(x)是拟凹的，那麼最大化該問題被稱為拟凹的。

局部最優解與全局最優解

對于凸問題來說，局部最優解一定是全局最優解。

局部最優： ∃ R > 0 , f 0 ( x ) = inf ⁡ { f 0 ( z ) ∣ z 可行 , x 可行 , ∣ ∣ x − z ∣ ∣ ≤ R } \exist R>0,f_0(x)=\inf \{f_0(z)|z可行,x可行,||x-z||\leq R\} ∃R>0,f0​(x)=inf{f0​(z)∣z可行,x可行,∣∣x−z∣∣≤R}

證明：

設 x x x不是全局最優解，即 ∃ y \exists y ∃y可行， f 0 ( y ) < f 0 ( x ) f_0(y)< f_0(x) f0​(y)<f0​(x)。

又因為 x x x是局部最優的，那麼 ∣ ∣ y − x ∣ ∣ 2 > R ||y-x||_2> R ∣∣y−x∣∣2​>R，那麼可以構造出一個新的解： z = ( 1 − θ ) x + θ y , θ = R 2 ∣ ∣ y − x ∣ ∣ 2 ∈ [ 0 , 1 2 ] z=(1-\theta)x+\theta y,\theta=\frac{R}{2||y-x||_2}\in[0,\frac{1}{2}] z=(1−θ)x+θy,θ=2∣∣y−x∣∣2​R​∈[0,21​]，是以z是x和y的凸組合。又因為可行解集一定是個凸集，是以z一定在可行解集内，即 z z z可行。

又因為 f 0 ( x ) f_0(x) f0​(x)是凸函數，故

f 0 ( z ) ≤ θ f 0 ( x ) + ( 1 − θ ) f 0 ( y ) ∣ ∣ z − x ∣ ∣ 2 = θ ∣ ∣ x − y ∣ ∣ 2 = R 2 (2.2) f_0(z)\leq \theta f_0(x)+(1-\theta)f_0(y)\\ ||z-x||_2=\theta ||x-y||_2=\frac{R}{2}\tag{2.2} f0​(z)≤θf0​(x)+(1−θ)f0​(y)∣∣z−x∣∣2​=θ∣∣x−y∣∣2​=2R​(2.2)

即 z z z在x的鄰域内。因為x是局部最優解，故 f 0 ( x ) < f 0 ( z ) f_0(x)<f_0(z) f0​(x)<f0​(z)。

即，綜上所述，需要滿足下面的條件：

f 0 ( y ) < f 0 ( x ) f 0 ( x ) < f 0 ( z ) f_0(y)<f_0(x)\\ f_0(x)<f_0(z) f0​(y)<f0​(x)f0​(x)<f0​(z)

即f

f 0 ( y ) < f 0 ( x ) < f 0 ( z ) f_0(y)<f_0(x)<f_0(z) f0​(y)<f0​(x)<f0​(z)

與式2.2沖突。故x一定是全局最優解。

圖形表示：

可微函數 f 0 f_0 f0​的最優性準則

可微凸問題目标函數的一階條件：

f 0 ( y ) ≥ f 0 ( x ) + ∇ f 0 T ( x ) ⋅ ( y − x ) ∀ x , y ∈ d o m f f_0(y)\geq f_0(x)+\nabla f_0^T(x)\cdot (y-x)\qquad \forall x,y\in \bold{dom}f f0​(y)≥f0​(x)+∇f0T​(x)⋅(y−x)∀x,y∈domf

問題的可行域：

X f = { x ∣ f i ( x ) ≤ 0 , i = 1 , . . . , m ; h i ( x ) = 0 , i = 1 , . . . , p } X_f=\{x|f_i(x)\leq 0,i=1,...,m;h_i(x)=0,i=1,...,p\} Xf​={x∣fi​(x)≤0,i=1,...,m;hi​(x)=0,i=1,...,p}

那麼 X ∗ ∈ X f X^*\in X_f X∗∈Xf​最優等價于

∇ f 0 T ( X ∗ ) ( y − X ∗ ) ≥ 0 (2.3) \nabla f_0^T(X^*)(y-X^*)\geq 0\tag{2.3} ∇f0T​(X∗)(y−X∗)≥0(2.3)

限制僅為等式限制

min ⁡ f 0 ( x ) d o m f 0 = R n s . t . A X = b \min f_0(x)\\ \bold{dom}f_0=\R^n\\ s.t. AX=b minf0​(x)domf0​=Rns.t.AX=b

若 ∃ x , A X = b \exist x,AX=b ∃x,AX=b，那麼X最優等價于 ∀ y , A y = b , ∇ f 0 T ( x ) ( y − x ) ≥ 0 \forall y,Ay=b,\nabla f_0^T(x)(y-x)\geq 0 ∀y,Ay=b,∇f0T​(x)(y−x)≥0成立。

又因為 A X = b ， A y = b AX=b，Ay=b AX=b，Ay=b，那麼 y = X + v , v ∈ N ( A ) y=X+v,v\in \mathcal{N}(A) y=X+v,v∈N(A)，即A的化零空間中的一個向量。

y是方程組的解，等于通解v加上特解X

是以，最優性條件可表示為

∇ f 0 ( x ) v ≥ 0 , ∀ v ∈ N ( A ) \nabla f_0(x)v\geq 0,\forall v\in \mathcal N(A) ∇f0​(x)v≥0,∀v∈N(A)

那麼隻有兩種情況：

• 子空間退化為零點：那麼 y = = X y==X y==X，即方程隻有一個解，矩陣A是可逆的。
• ∇ f 0 ( x ) \nabla f_0(x) ∇f0​(x)正交于子空間：

  

限制僅為非負限制：互補條件

min ⁡ f 0 ( x ) s . t . x ≥ 0 \min f_0(x)\\ s.t.x\geq 0 minf0​(x)s.t.x≥0

若 ∃ x ≥ 0 \exist x\geq 0 ∃x≥0， x x x最優等價于 ∀ y ≥ 0 \forall y\geq 0 ∀y≥0

∇ f 0 T ( x ) ( y − x ) ≥ 0 即 ∇ f 0 T ( x ) y − ∇ f 0 T ( x ) x ≥ 0 \nabla f_0^T(x)(y-x)\geq 0\\ 即\nabla f_0^T(x)y-\nabla f_0^T(x)x\geq 0 ∇f0T​(x)(y−x)≥0即∇f0T​(x)y−∇f0T​(x)x≥0

• ①：若 ∇ f 0 T ( x ) ≤ 0 \nabla f_0^T(x)\leq 0 ∇f0T​(x)≤0，則 ∇ f 0 T ( x ) y \nabla f_0^T(x)y ∇f0T​(x)y必可以取無窮小，則必有 ∇ f 0 ( x ) ≥ 0 \nabla f_0(x)\geq 0 ∇f0​(x)≥0
• ② ∀ y \forall y ∀y均有 ∇ f 0 ( x ) T ( y − x ) ≥ 0 \nabla f_0(x)^T(y-x)\geq 0 ∇f0​(x)T(y−x)≥0，當y=0時， ∇ f 0 T ( x ) x ≤ 0 \nabla f_0^T(x)x\leq 0 ∇f0T​(x)x≤0
• ③ ∇ f 0 T ( x ) ≥ 0 , x ≥ 0 ， \nabla f_0^T(x)\geq 0,x\geq 0， ∇f0T​(x)≥0,x≥0，則 ∇ f 0 T ( x ) x ≥ 0 \nabla f_0^T(x)x\geq 0 ∇f0T​(x)x≥0

由②和③可知， f 0 T ( x ) x = 0 f_0^T(x)x=0 f0T​(x)x=0

結論：如果x是最優解，那麼一定滿足下面的條件

{ x ≥ 0 ∇ f 0 ( x ) ≥ 0 ( ∇ f 0 ( x ) ) i x i = 0 \begin{cases}x\geq 0\\ \nabla f_0(x)\geq 0\\ (\nabla f_0(x))_ix_i=0\end{cases} ⎩ ⎨ ⎧​x≥0∇f0​(x)≥0(∇f0​(x))i​xi​=0​

該條件稱為互補條件。

幾何解釋：