ラグランジュ緩和について、具体的な例を見たうえで、一般の定式化についてまとめる。
※『最適輸送の理論とアルゴリズム』（佐藤竜馬, 2023）の2章の解説記事となっています
具体的な問題から出発する
最小化問題として次の問題 [問題1] を定義する。
$$
\begin{align}
\underset{[x,y] \in \mathbb{R}^2}{\text{minimize}} &\quad x+y \\
(f(x,y) &= x+y とおく) \\
-x-3y+1 &≤ 0 \\
-2x-y+1 &≤0 \\
x, y &≥0 \tag{1}
\end{align}
$$
$x+y=a$と置いたときに、aをどこまで小さくできるかがこの問題の解になる。
幾何的には、数の赤い領域の中で、緑の線をどこまで下に下げられるかという問題になる。
$a=0.6$の時に、直線$y=-x+a$ が領域の縁に来るのでこれが最小値になる。
$λ_1, λ_2 ≥ 0$ を制約条件2つそれぞれにかけて、$x+y$と一緒に和を取ったラグランジュ関数を次のようにとる。
$$
\begin{align}
L(x,y,λ_1,λ_2) &= (x+y) + λ_1 (-x-3y+1) + λ_2 (-2x-y+1) \tag{2-1行目}\\
&= x (1 - λ_1 - 2λ_2)
+y (1 + 3λ_1 + λ_2)
+λ_1+λ_2 \tag{2-2行目}
\end{align}
$$
式(2)の1行目から、$λ_1, λ_2$ は0以上で、制約条件の2つの式は0以下なので、$λ$と制約条件の積は0以下。この$L$は、もとの問題の $f(x,y) = x+y$ 以下になる。
- 元の[問題1]：$\underset{x,y}{\text{minimize}} \quad f(x,y)$
- Lについての問題：$\underset{x,y}{\text{minimize}} \quad L(x,y,λ_1,λ_2) \quad (最小値を~ g(λ_1, λ_2) ~とおく)$
Lについての問題は、[問題1]とは一致しない。Lについての問題の最小値 $g(λ_1, λ_2)$ は、必ず[問題1]の最小値以下になる。
「以下」ということは、元の[問題1]と一致させるためには、$g(λ_1, λ_2)$ が最も大きくなるような$λ_1,λ_2$を見つけてくる必要がある。
雑な言い方をすると、
「$L$の$x,y$についての最小値 $g$ を、最も最大化させる$λ_1$,$λ_2$を見つける」
という問いになる。
よって問題はこのように定式化される。
$$\underset{λ_1,λ_2 ≥ 0}{\text{maximize}} \quad g(λ_1,λ_2)$$
具体的に考えてみる。
(式(2)再掲)
$$
\begin{align}
L(x,y,λ_1,λ_2) &= x (1 - λ_1 - 2λ_2)
+y (1 + 3λ_1 + λ_2)
+λ_1+λ_2 \tag{2-2行目}
\end{align}
$$
式(2)の2行目から、$x,y$についての$L$が最小値を持つためには、
$x,y$の係数が非負でなくてはならない。
もし$x,y$の係数が負の場合、$x,y$を無限に大きくすることで、$L$の値を無限に小さくできてしまうから、$L$の最小値が存在しなくなってしまう（有界でなくなってしまう）。
したがって、係数が非負という条件
- $\begin{equation} 1 - λ_1 - 2λ_2 ≥0 \tag{3} \end{equation}$
- $\begin{equation} 1 + 3λ_1 + λ_2≥0 \tag{4} \end{equation}$
のもとで、最小値は式(2)の2行目の第1,2項が$0$になるときであり、
最小値 $g(λ_1,λ_2) = λ_1 + λ_2$
を得る。
この$g$の最大値を求めればいい。
$$
\begin{align}
&\underset{λ_1,λ_2 ≥ 0}{\text{maximize}} \quad g(λ_1,λ_2) \\
&=\underset{λ_1,λ_2 ≥ 0}{\text{maximize}} \quad λ_1 + λ_2 \tag{5}
\end{align}
$$
式(3),(4),(5)をまとめた最大化問題[問題2]の最大値は、元の[問題1]と一致する。
（↑ 一致することは「強双対定理」によって示されるが、証明略。）
$λ_1+λ_2=b$の最大値は、幾何的には、直線$λ_2=-λ_1+b$を上に上げていったときにこの領域の縁に来るときの$b$の値である。
$b=0.6$の時に最大値となる。確かに[問題1]の最適値 $a=0.6$ と一致する。
このようにして導出した問題は、元の問題「主問題」に対する「双対問題」と呼ばれる。
[問題2]は[問題1]の双対問題になっている。
一般の場合
下記の最適化問題を考える。
今度は、等式が制約条件にも入っていていいことにする。
不等式で書かれている制約条件を、$i=1,...,n$番目とし、
等式で書かれている制約条件を、$i=n+1,...,n+m$番目とする。
$$
\begin{align}
\underset{λ_1,λ_2 ≥ 0}{\text{minimize}} \quad
&f(\boldsymbol{x}) \\
\text{subject to} \quad
&h_i(\boldsymbol{x})≤0 (∀i∈ \lbrace 1,...,n \rbrace ) \\
&h_i(\boldsymbol{x})=0 (∀i∈ \lbrace n+1,...,n+m \rbrace)
\end{align}
$$
全部に$λ_i$という係数を付けたラグランジュ関数を定義する。
$$
L(\boldsymbol{x},λ_1,...,λ_{n+m})=
f(x)+\sum_{i=1}^{n} λ_i h_i(\boldsymbol{x}) +
\sum_{i=n+1}^{n+m} λ_i h_i(\boldsymbol{x})
$$
$λ$ の条件は、
$λ_1,...,λ_n ≥ 0, ~ λ_{n+1,...λ_{n+m}∈\mathbb{R}}$
となる。
このように定義することによって、
$L$の$\boldsymbol{x}$についての最小値は、必ず元の問題の最小値「以下」になる。
具体例の場合に見たのと同じ方法をたどる。
まずこの$L$の$\boldsymbol{x}$についての最小値$g(λ_1,...,λ_{n+m})$を考えたうえで、
その$g$が最大値を取るような$λ_1,...,λ_{n+m}$を求めればよい。
問題はこのように書き換えられる。
$$
\begin{align}
\underset{λ_1,...,λ_n ≥ 0, ~ λ_{n+1,...λ_{n+m}∈\mathbb{R}}}{\text{maximize}} \quad
\min_{x∈\mathbb{R}^d} \quad L(\boldsymbol{x},λ_1,...,λ_{n+m})
\end{align}
$$
実際には、$L$ が最小値を持つ（有界である）ための条件が入ってくる。
$L$の式を$\boldsymbol{x}$の各成分$x_1, x_2,...$について整理した時に、
係数が負であった場合、$\boldsymbol{x}$の各値を限りなく大きくすることで、無限に$L$を小さくすることができてしまう。
そのため、係数が非負であることが必要になる。
最適輸送問題に関する双対問題
最適輸送問題の定式化から変形する。
本節では、式番号を引用文献と一致させる。
$$
\begin{align}
\underset{ \boldsymbol{P} ∈\mathbb{R}^{n×m}}{\text{minimize}} \quad
& \sum_{i=1}^{n} \sum_{j=1}^{m} C(x_i,y_j) \boldsymbol{P}_{ij}
\end{align}
$$
制約条件は次の3つ。
$$
\begin{align}
-P_{ij} \leq 0 \tag{2.66} \\
a_i - \sum_{j} P_{ij} = 0 \tag{2.67} \\
b_j - \sum_{i} P_{ij} = 0 \tag{2.68} \\
\end{align}
$$
制約条件に係数をかけて、目的関数と一緒に和を取る。この時に1つ目の制約条件は緩和せず、2,3つ目の条件を緩和する。
$$
\begin{align}
\underset{ \boldsymbol{P} ∈\mathbb{R}^{n×m}}{\text{minimize}} \quad
& \sum_{ij} C_{ij} P_{ij} + \sum_{i} f_i \left( a_i - \sum_{j} P_{ij} \right) + \sum_{j} g_j \left( b_j - \sum_{i} P_{ij} \right) \tag{2.69} \\
\text{subject to} \quad & P_{ij} \geq 0 \quad (\forall i \in [n], \forall j \in [m])
\end{align}
$$
minimizeの後に書かれているのがラグランジュ関数 $L$。
具体例のときと同じように、項を$a_i$と$b_j$で整理する。
$$
\begin{align}
L(P, f, g) &= \sum_{ij} C_{ij} P_{ij} + \sum_{i} f_i \left( a_i - \sum_{j} P_{ij} \right) + \sum_{j} g_j \left( b_j - \sum_{i} P_{ij} \right) \\
&= \sum_{ij} P_{ij} (C_{ij} - f_i - g_j) + \sum_{i} a_i f_i + \sum_{j} b_j g_j \tag{2.70}
\end{align}
$$
この式の$a_i, b_j$についての最小値$G(f,g)$を考えた時に、$P_{ij}$の係数が負だと、$P_{ij}$に無限に大きい値を入れることで、無限に小さい値を取ることが可能になってしまう。
（※$g$を使うと文字が被るので、一般の場合で$g$と置いていたものを$G$に変えた）
そのため、
$$C_{ij} - f_i - g_j ≥ 0$$
となる場合のもとで、最小値 $G(f,g)$は、
$$
G(f,g)
= \sum_{i} a_i f_i + \sum_{j} b_j g_j
$$
となる。
よって、双対問題は、
$$
\begin{align}
\underset{f \in \mathbb{R}^n, g \in \mathbb{R}^m}{\text{maximize}} \quad
& \sum_{i=1}^{n} a_i f_i + \sum_{j=1}^{m} b_j g_j \tag{2.72} \\
\text{subject to} \quad
& f_i + g_j \leq C_{ij} \quad (\forall i \in [n], \forall j \in [m])
\end{align}
$$
Reference
佐藤 竜馬 (2023) 最適輸送の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)
https://www.amazon.co.jp/dp/4065305144