制約付き最適化の 3 手法を統一的に導出する ラグランジュ関数の視点から

今回は,数理最適化の中でも,連続最適化のお話です.競技プログラミング的には,マラソン(ヒューリスティック)のコンテストで役立つことがあるかもしれません.

制約付き最適化問題に対する有名な手法のうち,

  • ペナルティ関数法
  • 拡張ラグランジュ関数法
  • 交互方向乗数法(ADMM)

の 3 つを紹介します.これらの手法は「ラグランジュ関数」を用いると自然に導出できる,というのがメインテーマです.等式制約の場合を詳しく扱い,記事の最後で不等式制約の場合にも軽く触れます.

厳密な話はあまりせず,お気持ち重視で説明します.「どういう仮定の下で,どれくらい良い解が,どれくらいの計算量で得られるか?」というような理論保証が気になる方は,教科書や論文を参照してください.

扱う最適化問題

この記事では,2 つの関数 $f: \R^n \to \R,$ $g: \R^n \to \R^m$ により定まる最適化問題

等式制約付き最適化問題

\begin{equation}\label{problem} \min_{x \in \R^n} f(x) \quad \text{subject to}\ \ g(x) = \0 \end{equation}

を考えます.これは「$g(x) = \0$ という制約を満たす $x \in \R^n$ のうち,$f(x)$ を最小化するものを求めよ」という問題です.

関数 $f, g$ の凸性や線形性は仮定しません.ただしそのような仮定が無いと,問題 \eqref{problem} の最適解を求めるのは大変難しくなります.この記事で紹介する手法でも,一般に最適解は求まりませんが,弱い仮定の下で「ある程度良い解」が得られることは知られています1

ラグランジュ関数の導入

制約付き問題を解くための典型的な戦略に,「制約無し問題に変形する」というものがあります.問題 \eqref{problem} を制約無し問題に変形するため,ラグランジュ関数を導入します.「ラグランジュの未定乗数法」でも使うアレです.

問題 \eqref{problem} のラグランジュ関数 $L : \R^n \times \R^m \to \R$ は,\[ L(x, \lambda) := f(x) + \inner{\lambda}{g(x)} \] で定義されます.$\inner{a}{b}$ はベクトル $a, b$ の内積を表します.つまり,$\lambda = [\lambda_1, \dots, \lambda_m]^\top,$ $g(x) = [g_1(x), \dots, g_m(x)]^\top$ とすると,$\displaystyle \inner{\lambda}{g(x)} = \sum_{i=1}^m \lambda_i g_i(x)$ です.この $\lambda \in \R^m$ はラグランジュ乗数と呼ばれます.

実はラグランジュ関数を使うと,問題 \eqref{problem} を制約無しの問題

\begin{equation} \label{problem-lagrange} \min_{x \in \R^n} \max_{\lambda \in \R^m} L(x, \lambda) \end{equation}

に書き換えることができます2.$\displaystyle \min_{x \in \R^n} \max_{\lambda \in \R^m}$ の順なので,$\lambda$ は $x$ に依存してもいいですが,$x$ は $\lambda$ に依存してはいけないことに注意してください.

問題 \eqref{problem} と問題 \eqref{problem-lagrange} が等価であることを確認しましょう.問題 \eqref{problem-lagrange} の $\displaystyle \max_{\lambda \in \R^m} L(x, \lambda)$ の部分について考えると,\[ \max_{\lambda \in \R^m} L(x, \lambda) = \begin{cases} f(x) & \text{if $g(x) = \0$,} \\ +\infty &\text{otherwise} \end{cases} \] であることが分かります.$g(x) = \0$ ならば $L(x, \lambda) = f(x)$ ですし,$g(x) \neq \0$ ならば $\lambda$ を「$g(x)$ と同じ方向の大きいベクトル」にとることで $L(x, \lambda)$ の値をどれだけでも大きくできるためです.よって,$\displaystyle \max_{\lambda \in \R^m} L(x, \lambda)$ を小さくするためには $x$ を $g(x) = \0$ を満たすようにとるしかなく,結局問題 \eqref{problem-lagrange} は問題 \eqref{problem} に一致します.

手法 1: ペナルティ関数法

まず,3 手法の中で最も基本的なペナルティ関数法を導出しましょう.

前節で,問題 \eqref{problem} を解くためには問題 \eqref{problem-lagrange} を解けばよいことが分かりました.しかし,$g(x) \neq \0$ なる $x \in \R^n$ を固定したとき,$L(x, \lambda)$ を最大にする $\lambda$ は「大きさ無限大のベクトル」となってしまうため,問題 \eqref{problem-lagrange} はまだ扱いにくそうです.

この難しさを避けるために,問題 \eqref{problem-lagrange} そのものを解くのは諦め,代わりに余分な項を追加した問題\begin{equation} \label{problem-regularized} \min_{x \in \R^n} \max_{\lambda \in \R^m} \Big\{ L(x, \lambda) \under{{}- \frac{1}{2\mu} \|\lambda\|^2 } \Big\} \end{equation} を解くことを考えます.ここで,$\|a\| = \sqrt{\inner{a}{a}}$ で,$\mu \in \R$ は正のパラメータです.

$\frac{1}{2\mu} \|\lambda\|^2$ は正則化項などと呼ばれます.この項は,$\lambda$ がなるべく原点から離れてほしくないという気持ちを反映しています.この項のおかげで,式 \eqref{problem-regularized} の $\max$ を達成する $\lambda$ は「大きさ無限大のベクトル」ではなく,大きさが有限な普通のベクトルになるわけです.

さらに,その $\max$ を達成する $\lambda$ は $\lambda = \mu g(x)$ と明示的に書けます.これは $L(x, \lambda) - \frac{1}{2\mu} \|\lambda\|^2 = f(x) + \inner{\lambda}{g(x)} - \frac{1}{2\mu} \|\lambda\|^2$ を $\lambda$ について平方完成 or 微分することで分かります. この $\lambda$ を代入すると,問題 \eqref{problem-regularized} は

\begin{equation} \label{problem-penalty} \min_{x \in \R^n} \Big\{ f(x) + \frac{\mu}{2}\|g(x)\|^2 \Big\} \end{equation}

と等価だと分かります.

もともと解きたかった問題 \eqref{problem} の代わりに制約無し問題 \eqref{problem-penalty} を解くのがペナルティ関数法です! $\frac{\mu}{2}\|g(x)\|^2$ の項が,制約 $g(x) = \0$ を破ることに対するペナルティと見なせるので,このように呼ばれています.

ペナルティ関数法
  1. $\mu > 0$ を適切に選ぶ.
  2. 制約無し問題 \eqref{problem-penalty} を最急降下法などで解く.

ペナルティ関数法の導出では,正則化項 $\frac{1}{2\mu} \|\lambda\|^2$ を勝手に付け加えました.この項の影響を小さくするためには,$\mu$ を大きくとる必要があります.特に,影響をゼロにするには $\mu \to +\infty$ とする必要があります.しかし,$\mu$ をあまり大きくとると,問題 \eqref{problem-penalty} は数値的な意味で解きにくくなってしまいます.このように,ペナルティ関数法には $\mu$ の調節が難しいという欠点があります.

上では $\max$ を達成する $\lambda$ を有界にするために,$2$-ノルムによる正則化項を追加しました.もちろん,$\lambda$ を有界にする方法はこれ以外にもあります.有名なものでは,$\infty$-ノルムによる制約 $\displaystyle \max_{i=1,\dots,m}|\lambda_i| \leq \mu$ を追加する方法があります.

手法 2: 拡張ラグランジュ関数法

拡張ラグランジュ関数法はペナルティ関数法の進化系のような手法です.これまでの議論を前提にすると,以下のように割と自然に導出できます.

ペナルティ関数法により,問題 \eqref{problem-penalty} の最適解 $\hat x \in \R^m$ が得られたと仮定します3$\hat \lambda := \mu g(\hat x)$ と定めると,$(x, \lambda) = (\hat x, \hat \lambda)$ は問題 \eqref{problem-regularized} の最適解なので,問題 \eqref{problem-lagrange} の「そこそこ良い」解でもあることが期待されます.

ペナルティ関数法では,$\lambda$ が原点から離れすぎないようにするため,正則化項 $\frac{1}{2\mu} \|\lambda\|^2$ を追加し,問題 \eqref{problem-regularized} を得ました.今はそこそこ良い解 $\hat \lambda$ が得られているため,$\lambda$ が原点ではなく $\hat \lambda$ から離れないようにする,つまり\begin{equation} \label{problem-proximal} \min_{x \in \R^n} \max_{\lambda \in \R^m} \Big\{ L(x, \lambda) \under{{}- \frac{1}{2\mu} \|\lambda - \hat \lambda \|^2 } \Big\} \end{equation}とするのが自然です4.こうすることで,より問題 \eqref{problem-lagrange} に「近い」問題になることが期待されます.

ペナルティ関数法のときと同様に,問題 \eqref{problem-proximal} の $\max$ は $\lambda = \hat \lambda + \mu g(x)$ で達成されることが分かります.$\lambda$ を消去すれば,問題

\begin{equation} \label{problem-alm} \min_{x \in \R^n} \Big\{ f(x) + \inner{\hat \lambda}{g(x)} + \frac{\mu}{2}\|g(x)\|^2 \Big\} \end{equation}

を得ます.

この問題の最適解を新たに $\hat x \in \R^n$ とおき,$\hat \lambda + \mu g(\hat x)$ を $\hat \lambda$ におきなおし,上と同様のことを繰り返す,というのが拡張ラグランジュ関数法です! 問題 \eqref{problem-alm} の目的関数(で $\hat \lambda$ も変数と見なした関数)は拡張ラグランジュ関数と呼ばれています(個人的には「ペナルティラグランジュ関数」とかの方がしっくりくる気がします).

拡張ラグランジュ関数法
  1. $\mu > 0$ を適切に選び,$\hat \lambda \gets \0$ と初期化する.
  2. 以下を交互に繰り返す:
    • 問題 \eqref{problem-alm} を最急降下法などで解き,得られた解を新たに $\hat x \in \R^n$ とする.
    • $\hat \lambda \gets \hat \lambda + \mu g(\hat x)$ と更新する.

導出過程から当然ですが,ステップ 2 を一度だけ実行する拡張ラグランジュ関数法は,ペナルティ関数法に一致します.この意味で,拡張ラグランジュ関数法はペナルティ関数法の進化系というわけです.

多くの場合,ペナルティ関数法では $\mu \to +\infty$ としないと最適解(もしくは停留点)が得られませんが,拡張ラグランジュ関数法は有限の $\mu$ を使っても最適解(もしくは停留点)に収束することが知られています5.これは,拡張ラグランジュ関数法の反復を進めると $\hat \lambda$ が徐々に「最適な $\lambda$」に近づき,問題 \eqref{problem-proximal} の $\frac{1}{2\mu} \|\lambda - \hat \lambda \|^2$ の項の影響が($\mu \to +\infty$ としなくても)ゼロに近づきそうだ,ということからなんとなく納得できると思います.このことから,拡張ラグランジュ関数法の方が $\mu$ の調節が簡単で,より扱いやすい手法だと言えます.

手法 3: 交互方向乗数法(ADMM)

交互方向乗数法は,「特別な拡張ラグランジュ関数法で計算を少しサボったもの」だと言えます.英語では Alternating Direction Method of Multipliers と呼ばれ,ADMM と略されることが多いです.

拡張ラグランジュ関数法では問題 \eqref{problem-alm} を繰り返し解きますが,そのときに使うアルゴリズムはなんでもよいです.そこで,問題 \eqref{problem-alm} を交互最小化法という手法で解くことを考えます.交互最小化法は,変数 $x \in \R^n$ を $x = (x_1, x_2)$ と 2 つのブロックに分け,「$x_2$ を固定した下での $x_1$ についての最小化」と「$x_1$ を固定した下での $x_2$ についての最小化」を交互に繰り返す手法です.

交互最小化法を用いた拡張ラグランジュ関数法において,交互最小化部分を少しサボったのが ADMM です.具体的には,$x_1$ についての最小化と $x_2$ についての最小化をそれぞれ一回ずつのみ行います.

交互方向乗数法(ADMM)
  1. 変数 $x \in \R^n$ を $x = (x_1, x_2)$ と 2 つのブロックに分ける.
  2. $\mu > 0$ を適切に選び,$\hat x_2 \gets \0, $ $\hat \lambda \gets \0$ と初期化する.
  3. 以下を順に繰り返す:
    • $\displaystyle \min_{\red{x_1}} \Big\{ f(\red{x_1}, \hat x_2) + \inner{\hat \lambda}{g(\red{x_1}, \hat x_2)} + \frac{\mu}{2}\|g(\red{x_1}, \hat x_2)\|^2 \Big\}$ の解を新たに $\hat x_1$ とする.
    • $\displaystyle \min_{\red{x_2}} \Big\{ f(\hat x_1, \red{x_2}) + \inner{\hat \lambda}{g(\hat x_1, \red{x_2})} + \frac{\mu}{2}\|g(\hat x_1, \red{x_2})\|^2 \Big\}$ の解を新たに $\hat x_2$ とする.
    • $\hat \lambda \gets \hat \lambda + \mu g(\hat x_1, \hat x_2)$ と更新する.

ADMM は,「$x_1$ と $x_2$ を同時に動かして最適化するのは難しいが,一方を固定しもう一方を動かして最適化するのは簡単」という状況で特に有効な方法です.そのような状況は,画像処理,信号処理や,分散コンピューティングの文脈でよく現れるようで,ADMM が応用されているのをしばしば目にします.

ADMM も,拡張ラグランジュ関数法と同様に,$\mu \to +\infty$ とする必要はないことが知られています.嬉しいですね.

おまけ: 不等式制約の場合

これまで,等式制約付きの問題を考えてきましたが,上の 3 手法は,不等式制約付きの問題

不等式制約付き最適化問題

\begin{equation}\label{problem-ineq} \min_{x \in \R^n} f(x) \quad \text{subject to}\ \ g(x) \red{{}\leq{}} \0 \end{equation}

にも適用できます.これを簡単に説明します.

等式制約の問題が問題 \eqref{problem-lagrange} に書き換えられたのと同様に,問題 \eqref{problem-ineq} は\[ \min_{x \in \R^n} \max_{\lambda \in \R^m,\ \red{\lambda \geq \0}} L(x, \lambda) \] と書き換えられることが分かります.

不等式制約版のペナルティ関数法では,問題 \eqref{problem-regularized} の代わりに \[ \min_{x \in \R^n} \max_{\lambda \in \R^m,\ \red{\lambda \geq \0}} \Big\{ L(x, \lambda) - \frac{1}{2\mu} \|\lambda\|^2 \Big\} \]を解くことになります.この $\max$ を達成する $\lambda$ も $\lambda = \max \{ \mu g(x), \0 \}$ と明示的に書けるので($\max$ はベクトルの要素ごとにとります),問題 \eqref{problem-penalty} の対応物として \[ \min_{x \in \R^n} \Big\{ f(x) + \frac{\mu}{2}\| \max \{ \mu g(x), \0 \} \|^2 \Big\} \] が得られます.これを解くのが,問題 \eqref{problem-ineq} に対するペナルティ関数法です.

同様に,拡張ラグランジュ関数法や ADMM でも,$\max$ を達成する $\lambda$ は $\lambda = \max \{ \hat \lambda + \mu g(x), \0 \}$ だと分かり,問題 \eqref{problem-alm} の不等式制約版が得られます.ただし,実際に計算すると分かるのですが,等式制約の場合に比べて少々複雑な式になってしまいます.

  1. $f$ が凸かつ $g$ が線形の場合は問題 \eqref{problem} が凸になるので,(追加の弱い仮定の下で)最適解に十分近い解が求まります.
  2. $\max$ が存在するとは限らないため,本当は $\max$ ではなく $\sup$ と書くべきですが,この記事では気にしないことにします.
  3. 実際には凸性などの仮定が無いと最適解を得るのは難しいですが,ここでは気にしないことにします.
  4. この $\frac{1}{2\mu} \|\lambda - \hat \lambda \|^2$ も正則化項と呼びたくなるかもしれませんが,近接項と呼ばれることが多いです.
  5. 凸性などの仮定の下では最適解に収束します.凸性が無い場合でも,比較的弱い仮定の下で停留点に収束することが知られています.停留点の定義はしませんが,「ある程度良い解」と思ってください.
タイトルとURLをコピーしました