Convex Optimization

Convex Function

「凸函數」。任意割面,都是凸的。任意截面,都是凸函數。

凸函數的運算性質:

凸函數的非負倍率,仍是凸函數。
多個凸函數相加,仍是凸函數。
多個凸函數的最小上界,仍是凸函數,但是通常變得不可微。
非負的凸函數的平方,仍是凸函數,而且有時候變得可微。

Convex Optimization

「凸最佳化」。凸函數求極值。

演算法設計:大家沿用一般函數的演算法,例如梯度下降法。雖然凸函數有專門演算法,但是不實用,例如橢球法。

演算法分析:一般函數,實施演算法,不保證趨近極值位置(收斂),無法推導時間複雜度。但是凸函數可以!

請見專著《Convex Optimization》

Online Convex Optimization

「在線凸最佳化」。時時變動的凸函數求極值。

請見專著《Introduction to Online Convex Optimization》

Disciplined Convex Optimization

凸最佳化是P問題。然而,判斷凸函數是NP-complete問題。

於是有人改弦易轍,排列組合常見運算符號、常見函數,藉由已知的數學性質,以判斷凸函數,甚至判斷要使用哪個演算法。

照理來說,這是在判斷凸函數,不應該取名為最佳化。

請見專論《Disciplined Convex Programming》

Ellipsoid Method(橢球法)

https://stanford.edu/class/ee364b/lectures/ellipsoid_method_notes.pdf

製造一個橢球,涵蓋極值位置。依照當前梯度,移動橢球球心、調整橢球形狀、縮小橢球體積,球心逐步收斂至極值位置。

僅有理論上的價值,沒有實務上的價值。

Convergence Analysis

Convex Optimization

https://www.cs.ubc.ca/~schmidtm/Courses/540-W19/L5.pdf

誤差error:當前位置與極值位置的差距。

殘差residual:當前函數值與極值的差距。

收斂速率rate of convergence:走一步,前後兩處的誤差比率。或者是殘差比率。

error: |x - x*|
residual: |f(x) - f(x*)|
rate of convergence: |f(xnext) - f(x*)| / |f(x) - f(x*)|

各種演算法、各種特殊函數,收斂速率皆不同。利用收斂速率,判斷時間複雜度:達到預定的數值精確度,需要走多少步。

例如梯度下降法用於凸函數,時間複雜度O(log 1/ε)。

run algorithm until residual is small enough: |f(x) - f(x*)| ≤ ε

f is Lipschitz: |f(a) - f(b)| ≤ λ |a - b|
O(1/ε²) iterations

∇f is Lipschitz: |∇f(a) - ∇f(b)| ≤ λ |a - b|
O(1/ε) iterations

f is strongly convex: (∇f(a) - ∇f(b)) ∙ (a - b) ≥ λ (a - b) ∙ (a - b)
O(log 1/ε) iterations

Online Convex Optimization

http://www.cs.cmu.edu/~15850/notes/lec18.pdf

在線最佳化,殘差改成遺憾。事與願違、悔不當初的意思。

超級極值位置【尚無正式名稱】:極值隨時改變,無高下之分。方便起見,所有極值位置概括成一個超級極值位置。

遺憾regret:以往殘差總和(窮舉超級極值位置,取殘差總和最大者)。照理來說應該要取絕對值,我不知道為何不取。

換句話說,以往位置們的函數值的總和、超級極值位置的函數值的總和(窮舉超級極值位置,取函數值的總和最小者),兩者差距。

regret: max sum {ft(xt) - ft(x*)} = sum ft(xt) - min sum ft(x*)
         x*  t                       t            x*  t

Duality

Lagrange Duality

可微函數的對偶。製造新維度,窮舉斜率λ,求最高截距。

http://www.eng.newcastle.edu.au/eecs/cdsc/books/cce/Slides/Duality.pdf
http://www.onmyphd.com/?p=duality.theory
http://www.cnblogs.com/90zeng/p/Lagrange_duality.html

Fenchel Duality(Convex Conjugate)

凸函數的對偶。畫個切線求截距。

動態規劃有一個技巧是:最佳解位於直線們的包絡線,經過點線對偶,最佳解位於凸包切線的截距。正是此對偶。

https://mdav.ece.gatech.edu/ece-8823-spring2019/notes/06-fenchel-dual.pdf
https://people.ok.ubc.ca/bauschke/Research/68.pdf
maximum: largest value
minimum: smallest value
supremum: least upperbound function
infimum: most lowerbound function
epigraph: upper area (of convex function)
hypograph: below area (of concave function)
let f is convex, g is concave
convex conjugate:  f*(y) = sup { x∙y - f(x) }
concave conjugate: g⁎(y) = inf { x∙y - g(x) }
Fenchel duality theorem: inf { f(x) - g(x) } = sup { g⁎(y) - f*(y) }
Fenchel duality: f** = f , g⁎⁎ = g
when y = ∇f(x)
thus x = ∇f*(y)
thus ∇f = (∇f*)⁻¹   --> orthonormal matrix Aᵀ = A⁻¹
Fenchel inequality: f(x) + f*(y) ≥ x∙y
Moreau decomposition: x = proxf(x) + proxf*(x)
infimal convolution: (f ◇ g)(x) = inf { f(x-y) + g(y) }
Fenchel dual operation: (f ◇ g)* = f* + g* , (f + g)* = f* ◇ g*

Linear Programming Duality(Complementary Slackness)

一次規劃的對偶。

原始問題稱作primal,對偶問題稱作dual,兩個問題等價。根據單形法作者的回憶錄,primal是他爹創造的名稱。

primal: max cᵀx   subject to Ax ≤ b, x ≥ 0
dual:   min bᵀy   subject to Aᵀy ≥ c, y ≥ 0
primal:                       dual:
-------------------------     |   ∑     ∑     ∑   |  ∑
∑ a₁₁x₁ a₁₂x₂ a₁₃x₃ ≤ b₁      | a₁₁y₁ a₁₂y₁ a₁₃y₁ | b₁y₁
∑ a₂₁x₁ a₂₂x₂ a₂₃x₃ ≤ b₂      | a₂₁y₂ a₂₂y₂ a₂₃y₂ | b₂y₂
∑ a₃₁x₁ a₃₂x₂ a₃₃x₃ ≤ b₃      | a₃₁y₃ a₃₂y₃ a₃₃y₃ | b₃y₃
∑ a₄₁x₁ a₄₂x₂ a₄₃x₃ ≤ b₄      | a₄₁y₄ a₄₂y₄ a₄₃y₄ | b₄y₄
-------------------------     |   |V    |V    |V  |  ||
∑  c₁x₁  c₂x₂  c₃x₃ = max     |   c₁    c₂    c₃  |  min

一次規劃的對偶,源自窮舉法。

一、以約束條件夾擠最大值,得到對偶問題的目標函數。

約束條件的加權總和,不影響正解。窮舉權重,約束條件的加權總和與目標函數,取其一致者;常數項,取其最小者。

二、最大值不超過約束條件,得到對偶問題的不等式。

約束條件的加權總和,重新整理成變數們的加權總和。窮舉權重,並讓第一個變數以外的權重是零,得到第一道不等式。

"min bᵀy"
row₁ k₁ + row₂ k₂ + ...       ≤ b₁k₁ + b₂k₂ + ...   row sum, kᵢ ≥ 0
∑ kᵢaᵢ₁ x₁ + ∑ kᵢaᵢ₂ x₂ + ... ≤ b₁k₁ + b₂k₂ + ...   column sum
c₁x₁ + c₂x₂ + ...             ≤ b₁k₁ + b₂k₂ + ...   ∑ kᵢaᵢ₁ = c₁ for some k
objective                     = min bᵀy             k is y
"subject to Aᵀy ≥ c"
cᵀx               ≤ row₁ k₁ + row₂ k₂ + ...         row sum
c₁x₁ + c₂x₂ + ... ≤ ∑ kᵢaᵢ₁ x₁ + ∑ kᵢaᵢ₂ x₂ + ...   column sum
c₁x₁              ≤ ∑ kᵢaᵢ₁ x₁                      ∑ kᵢaᵢ₂ = c₂ for some k
c₁                ≤ ∑ kᵢaᵢ₁                         divide x₁ when x₁ ≠ 0
c                 ≤ Aᵀy                             k is y

一次規劃的對偶,本質是拉格朗日對偶。

max cᵀx   subject to Ax ≤ b, x ≥ 0
L(x,y) = cᵀx - yᵀ(Ax - b)
L(x,y) = cᵀx - yᵀAx + yᵀb
L(x,y) = bᵀy - xᵀAᵀy + xᵀc
L(x,y) = bᵀy - xᵀ(Aᵀy - c)
min bᵀy   subject to Aᵀy ≥ c, y ≥ 0

原始問題的最佳解等於對偶問題的最佳解。

Ax ≤ b  ---> yᵀAx ≤ yᵀb     (y ≥ 0)
Aᵀy ≥ c ---> xᵀAᵀy ≥ xᵀc    (x ≥ 0)
cᵀx = xᵀc ≤ xᵀAᵀy = yᵀAx ≤ yᵀb = bᵀy

一次規劃是特例,一次不等式是通例。

原始問題的約束條件、對偶問題的約束條件、兩個問題的目標函數相等,三者聯立得到一次不等式。

linear programming          linear inequality
maximize   cᵀx              { Ax ≤ b    (primal constraint)
subject to Ax ≤ b    --->   { Aᵀy ≥ c   (dual constraint)
           x ≥ 0            { cᵀx = bᵀy (two objectives equality)

Proximal Method

Proximal Function

「近側函數」。追加目標函數f(x),稍微喬一下位置x。

位置x被喬到位置z,距離不要離太遠。自訂權重α,以調整遠近。1/2只是為了方便抵銷微分係數。

proxα,f(x) = argmin { 1/2 ‖z - x‖² + α f(z) }
               z

近側函數是一種操作,而不是一種性質。

Proximal Method

「近側法」。運用近側函數進行最佳化。一種最佳化技巧。

演算法設計:近側函數不易計算,實務上派不上用場。

演算法分析:近側函數是平緩函數!不動點遞推法用於近側函數,保證遭遇不動點!因而可以分析時間複雜度!

例如ADMM用於凸函數,可以視作近側法,分析時間複雜度。

請見課程講義、學習筆記:

http://niaohe.ise.illinois.edu/IE598_2016/pdf/IE598-lecture20-splitting algorithms.pdf
https://glooow1024.github.io/2020/05/24/optimization/ch25-PDHG/
https://glooow1024.github.io/2020/04/16/optimization/ch18-proximal-mapping/

Proximal Point Iteration(近側點遞推法)

類似於不動點遞推法、梯度下降法。用同一個函數不斷喬位置。

minimize f(x)
xnext = proxα,f(x)

近側函數當中,極值位於斜率等於零的地方。微分等於零,嘗試求得z。但是只能求得z的關係式,無法求得z的確切數值。

argmin { 1/2 ‖z - x‖² + α f(z) }
   z
∂
—— { 1/2 ‖z - x‖² + α f(z) } = 0
∂z

(z - x) + α ∇f(z) = 0

z = x - α ∇f(z)

如果z = x則是不動點。但是z往旁邊偏,因而取名為近側點。

Accelerated Proximal Point Method(加速近側點遞推法)

類似於非線性共軛梯度法。待喬位置是「本次的位置」與「上次的前進方向」的加權平均。

xnext = proxα,f(x + step ⋅ (x - xprev)))

Proximal Gradient Method(近側梯度法)

類似於投影梯度法。朝著原始函數的梯度方向走一步,再用追加函數稍微喬一下位置。

minimize f(x) + α g(x)
p = x + step ⋅ ∇f(x)
xnext = proxα,g(p) = argmin { 1/2 ‖x - p‖² + α g(x) }

計算近側函數,是另一個最佳化問題。兩層最佳化。

如果追加函數很單純,則推導近側函數的公式解,一步到位。如果追加函數很複雜,則以梯度下降法慢慢走往近側函數的極值:梯度是追加函數的梯度、乘上α、再加上x。

Accelerated Proximal Gradient Method(加速近側梯度法)

p = x + step ⋅ ∇f(x)
xnext = proxα,g(p + step ⋅ (p - pprev))

Proximal Splitting Method(近側分裂法)

類似於算子分裂法。喬來喬去、密室協商。

xnext = prox1,f(y)
ynext = y + ρ [proxα,g(2xnext - y) - xnext]

ρ = 1是Douglas-Rachford Splitting Method,ρ = 2是Peaceman-Rachford Splitting Method。

Bandit Optimization

Bandit Optimization

https://sites.google.com/site/yenhuanli/teaching

thompson sampling
multi-armed bandit
https://www.zhihu.com/question/429071633/answer/1565691971
https://lihongli.github.io/
http://www.columbia.edu/~sa3305/