ラグランジュ緩和と双対問題

ラグランジュ緩和について、具体的な例を見たうえで、一般の定式化についてまとめる。

※『最適輸送の理論とアルゴリズム』（佐藤竜馬, 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$ が領域の縁に来るのでこれが最小値になる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/280275/df283e3b-e062-d36f-502d-9311ab32c9b7.png)


$λ_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$を見つけてくる必要がある。

雑な言い方をすると、

:::note info
「$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$ と一致する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/280275/3e51da8b-8c44-4002-9b23-42f354d61300.png)


このようにして導出した問題は、元の問題「主問題」に対する「双対問題」と呼ばれる。
[問題2]は[問題1]の双対問題になっている。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/280275/9e3e9e58-f5a4-47bb-c766-cef06af8056f.png)




# 一般の場合
下記の最適化問題を考える。
今度は、等式が制約条件にも入っていていいことにする。
不等式で書かれている制約条件を、$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}}$
となる。
このように定義することによって、

:::note info
$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