Convex Optimization
Convex Function
「凸函數」。任意割面，都是凸的。任意截面，都是凸函數。
凸函數的運算性質：
凸函數的非負倍率，仍是凸函數。 多個凸函數相加，仍是凸函數。 多個凸函數的最小上界，仍是凸函數，但是通常變得不可微。 非負的凸函數的平方，仍是凸函數，而且有時候變得可微。
Convex Optimization
「凸最佳化」。凸函數求極值。
演算法設計：大家沿用一般函數的演算法，例如梯度下降法。雖然凸函數有專門演算法，但是不實用，例如橢球法。
演算法分析：一般函數，實施演算法，不保證趨近極值位置（收斂），無法推導時間複雜度。但是凸函數可以！
Online Convex Optimization
「在線凸最佳化」。時時變動的凸函數求極值。
請見專著《Introduction to Online Convex Optimization》。
Disciplined Convex Optimization
凸最佳化是P問題。然而，判斷凸函數是NP-hard問題。
於是有人改弦易轍，排列組合常見運算符號、常見函數，藉由已知的數學性質，以判斷凸函數，甚至判斷要使用哪個演算法。
照理來說，這是在判斷凸函數，不應該取名為最佳化。
請見專論《Disciplined Convex Programming》。
Ellipsoid Method（橢球法）
製造一個橢球，涵蓋極值位置。依照當前梯度，移動橢球球心、調整橢球形狀、縮小橢球體積，球心逐步收斂至極值位置。
僅有理論上的價值，沒有實務上的價值。
Convergence Analysis
Convex Optimization
誤差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
在線最佳化，殘差改成遺憾。事與願違、悔不當初的意思。
超級極值位置【尚無正式名稱】：極值隨時改變，無高下之分。方便起見，所有極值位置概括成一個超級極值位置。
遺憾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。