Lagrange Multiplier - 02

這裡我們再多討論一點 Lagrangian function.

我們先看最簡單的一維問題, 求一個有限制式的函數最小值問題: $$ \min_{x} f(x), \quad \text{subject to } \quad g(x)=0. $$

我們引進 Lagrangian function $$ L(x, \lambda) = f(x) + \lambda g(x) $$ 並且知道原問題的解發生在 $\nabla L=0$ 的地方.

Question: 從微積分我們知道 $\nabla L=0$ 是 $L(x, \lambda)$ 這個函數 critical point發生的地方, 那這個 critical point 究竟是 local max/min 還是 saddle 呢?

要回答這問題其實很簡單, 我們看這個二維函數的判別式就知道. 這函數的變數有兩個分別是 $x$ 以及 $\lambda$, 所以判別式是 $$ L_{xx}L_{\lambda\lambda} - L_{x\lambda}^2 = -(g_x)^2 \le 0 $$ 所以我們知道原最佳化問題的解其實是這個 Lagragian function 的 saddle point (至少不是 local max/min)!

Constraint optimization problem

我們事實上可以考慮更一般的問題 $$ \min_{x} f(x), \quad \text{subject to } \quad g(x) \le 0. $$ 這樣的問題我們可以定義一樣的 Lagrangian function $$ L(x, \lambda) = f(x) + \lambda g(x). $$

我們有以下這個定理:

Theorem - Saddle point (Sufficient condition)

Let $P$ be a constraint optimization problem. If $(x^+, \lambda^+)$ is a saddle point, that is, $$\forall x\in\mathbb{R}, \forall\lambda\ge 0, \quad L(x^+, \lambda)\le L(x^+, \lambda^+)\le L(x, \lambda^+),$$ then it is a solution of $P$.

這個證明很簡單.

根據不等式第一個部分 $$\forall\lambda\ge 0, \quad L(x^+, \lambda)\le L(x^+, \lambda^+)$$ 帶入 $L$ 我們得到 $\lambda g(x^+) \le \lambda^+ g(x^+)$.

由於對所有 $\lambda\ge 0$ 都對, 我們讓 $\lambda\to\infty$ 得到 $g(x^+)\le 0$. 接著讓 $\lambda\to 0$ 我們得到 $0\le \lambda^+ g(x^+)\le 0$, 因此 $\lambda^+ g(x^+)=0$.

有這件事後我們再看不等式第二部分, $L(x^+, \lambda^+)\le L(x, \lambda^+)$. 代入 $L$ 以及以上結果我們有 $f(x^+)\le f(x) + \lambda^+ g(x)$.

因此, 若 $g(x)\le 0$, 我們必定有 $f(x^+)\le f(x)$.

QED.

可以看到在上面有個隱藏的假設是 $\lambda\ge 0$. 可以被很輕易地看出來所以這裡就不記下了.

更進一步, 我們可以引進這個 Lagrange dual function: $$ F(\lambda) = \inf_{x} L(x, \lambda) $$ 也就是固定一個 $\lambda$ 我去找 $L$ 這函數的最大下界(有點像最小值不過不一定要碰到). 據此我們可以引進以下的 dual problem.

Dual optimization problem

$$ \max_{\lambda} F(\lambda), \quad \lambda \ge 0. $$

舉個例子

我們考慮這個特別的 constraint optimization 問題 $$ \min_{\pmb{x}\in\mathbb{R}^n}f(\pmb{x}), \quad \text{subject to } \quad A\pmb{x}-\pmb{b}=\pmb{0}, $$ 其中 $A$ 是個矩陣而 $\pmb{b}$ 是個向量. 也就是說限制式為 $g(\pmb{x}) = A\pmb{x}-\pmb{b}$.

把 Lagrangian function 寫下來就是 $$ L(\pmb{x}, \pmb{\lambda}) = f(\pmb{x}) + \pmb{\lambda}^T(A\pmb{x}-\pmb{b}). $$ 對於 dual problem 我們可以構造一個迭代法來解這問題.

由 Dual optimization problem 我們知道對於 $F$ 這個函數我們要求其最大值. 所以我們試著朝 gradient 方向走來往上走, 意即 $$ \lambda^{k+1} = \lambda_k + \alpha^k\nabla_{\lambda} F(\lambda^k), $$ 其中 $\alpha^k$ 是步長. 而且我們知道 $\nabla_{\lambda} F(\lambda^k) = A\pmb{\tilde{x}}-\pmb{b},$ 其中 $\pmb{\tilde{x}} = argmin \ L(\pmb{x}, \pmb{\lambda}^k)$. 因此我們有以下這方法:

Dual ascent iteration method:

• 第一步: 固定一個 $\pmb{\lambda}$ 我們解一個 optimization 問題 $$ \pmb{x}^{k+1} = argmin \ L(\pmb{x}, \pmb{\lambda}^k) $$ Remark: 這是一個沒有 constraint 的最小值問題, 可以用 gradient descent 或各式方法來解.

• 第二步: 接著我們用 gradient ascent 來更新 $\pmb{\lambda}$ $$ \lambda^{k+1} = \lambda^k + \alpha^k(A\pmb{x}^{k+1}-\pmb{b}) $$

迭代下去我們可以得到原問題的解!

Augmented Lagrangian

一個很有趣的更進一步推廣是將 Lagrangian 引入一個新的 penalty term: $$ L_{\rho}(\pmb{x}, \pmb{\lambda}) = f(\pmb{x}) + \pmb{\lambda}^T(A\pmb{x}-\pmb{b}) + \frac{\rho}{2}\|A\pmb{x}-\pmb{b}\|^2_2, $$ 其中 $\rho$ 是個常數.

我們可以反過來將這個 Lagrangian 所對應的限制最佳化問題寫下來: $$ \min_{\pmb{x}\in\mathbb{R}^n}f(\pmb{x})+\frac{\rho}{2}\|A\pmb{x}-\pmb{b}\|^2_2, \quad \text{subject to } \quad A\pmb{x}-\pmb{b}=\pmb{0}. $$ 我們可以輕易發現, 加了這新的一項對於這整個問題的最佳解完全沒有影響! 也就是說 $L_{\rho}$ 所得到的解就是原本 $L$ 的解.

接著我們一樣用 dual ascent iteration method 來解這問題（給定 $\pmb{x}^{k}$ 以及 $\pmb{\lambda}^{k}$).

Method of multiplier:

• 第一步: 我們解一個 optimization 問題 $$ \pmb{x}^{k+1} = argmin \ L_{\rho}(\pmb{x}, \pmb{\lambda}^k) $$

• 第二步: 接著我們用 gradient ascent 來更新 $\pmb{\lambda}$ $$ \pmb{\lambda}^{k+1} = \pmb{\lambda}^k + \rho(A\pmb{x}^{k+1}-\pmb{b}) $$

Remark: 這裡有個有趣的事, 原本的方法中步長是不知道的需要自己決定, 不過在這裡我們卻直接設定步常為 $\rho$. 接下來我們就是要解釋這部分.

• 第一步中, 如果 $\pmb{x}^{k+1}$ 是個解那它要滿足 $\nabla_{\pmb{x}} L_{\rho}=0$, 其中整理一下發現 $$ \nabla_{\pmb{x}} L_{\rho}=\nabla_{\pmb{x}} f(\pmb{x}^{k+1}) + A^T\left(\pmb{\lambda}^k + \rho (A\pmb{x}^{k+1}-\pmb{b})\right)=0. $$

• 所以, 如果第二步中的步長我們設定為 $\rho$, 那上式就可以改寫為 $$ \nabla_{\pmb{x}} f(\pmb{x}^{k+1}) + A^T\pmb{\lambda}^{k+1}=0. $$ 有趣的是, 對原本的 Lagrangian 而言我們有 $$ \nabla_{\pmb{x}} L=\nabla_{\pmb{x}} f(\pmb{x}) + A^T\pmb{\lambda}, $$ 所以我們這樣設定步長, 剛好使得我們每次算出的 $\pmb{x}^{k+1}$ 以及 $\pmb{\lambda}^{k+1}$ 滿足 $$ \nabla_{\pmb{x}} L(\pmb{x}^{k+1}, \pmb{\lambda}^{k+1})=0. $$

再把以上兩個方法 summarize 一下

• 原本問題是 $$ \min_{\pmb{x}} f(\pmb{x}), \quad \text{subject to } \quad A\pmb{x}-\pmb{b}=\pmb{0}. $$

• 引進 Lagrangian 後變成我們要解以下方程 $$ \nabla_{\pmb{x}} L =\nabla_{\pmb{x}} f(\pmb{x}) + A^T\pmb{\lambda}=0, \quad \nabla_{\pmb{\lambda}} L=A\pmb{x}-\pmb{b}=0. $$

• 我們使用迭代法來解

  • 若用 dual ascent iteration method, 則有 $$ \nabla_{\pmb{x}} L(\pmb{x}^{k+1}, \pmb{\lambda}^k)=0. $$

  • 若用 method of multiplier, 則有 $$ \nabla_{\pmb{x}} L(\pmb{x}^{k+1}, \pmb{\lambda}^{k+1})=0. $$

  • 對於兩種方法, 原問題的 Constraint 都在 $k\to\infty$ 滿足 $$ \lim_{k\to\infty} A\pmb{x}^k-\pmb{b}=0. $$