『ラグランジュの未定乗数法、KKT条件、そして双対性 – 直感的に説明する』

『ラグランジュ未定乗数法、KKT条件、双対性を直感的に解説』

あなたがSVM、正則化、PCA、その他の機械学習の概念を理解するための鍵

この記事では、数学的最適化の3つの関連する概念を明確かつ洞察力に富んだ方法で探求します。私が完全に理解するためにはかなりの時間と努力が必要でしたので、すべての読者に直感的な方法で提示することを目指しています。私たちの旅は、制約のない最適化の復習から始まり、ラグランジュ乗数法とKKT条件を利用した制約最適化の考慮で続きます。これらのアイデアの相互作用とそれらの概念との関連性についても深く掘り下げます。

制約のない最適化

制約のない最適化では、多変数関数 f(u) が与えられ、関数 f(u*) の値が最適（最大または最小）となるベクトル u* の値を見つけることを目指します。

一般的に、関数は上記のように複数の最大値および最小値を持つことがあります。この物語では、古典的な機械学習およびこの記事全体を通じて、私たちは主に凸関数（または十分に平滑な関数）に興味を持ちます。凸であることは、関数が最大一つ（関数が損失関数の場合は最小）の最適値を持つことを意味します。

凸関数は扱いやすいため、それ以外の場合は最低値がすべての値の中で最も低い（つまり、グローバル最小値）であるかどうかを判断するのが非常に困難になることがあります。一般に、最小値が存在する場合でも、満足する点が多く存在することがあります（例：平坦な場合）。説明を簡略化するため、このようなケースは起こらないと仮定しますが、この仮定をしても導出される内容には何ら影響を及ぼしません。

• 「DevOpsとDataOpsとの私の経験」
• PySparkにおけるロジスティック回帰の紹介
• 「ジオスペーシャルデータの同時変化を示すためのPythonによる5つの可視化」

与えられた多変数関数 f(u) の制約のない最適化は、∇ᵤf(u) = 0 を解くことで可能です。f(u) が n 変数（u₁, u₂,…,uₙ）の関数である場合、これは n 個の方程式の系です。

これを解くと、最適な解 u*=(u*₁,u*₂,…,u*ₙ) が得られます。この最適解の場所が最適値（最小値など）が発生する場所です。

これがどこから来たのかを確認するために、次のことを思い出してください：

• 任意の点uにおける接平面の法線ベクトルは、(∂f(u)/∂u₁, ∂f(u)/∂u₂, …, ∂f(u)/∂uₙ, f(u))の形を取ります
• 最小値または最大値のいずれの場合も、接平面は水平です（視覚的に明らかです）
• したがって、∇ᵤf(u) = 0が成立する場合、その点で水平な接平面が存在し、私たちが求めている最小値である必要があります。

また、このことを合理化する別の方法は、勾配が最も増加する方向を指し示すこと（および最も減少する方向の反対）です。したがって、∇ᵤf(u) = 0が成立する場合、その点から関数を増加させる（方向を指し示す）ことはできない（つまり、最大である）か、その点から関数を減少させる（つまり、最小である）ことはできません。

制約なし最適化の概要

与えられた： f(u)求める： f(u)が最小になるuアプローチ： ∇ᵤf(u) = 0を解く，それは最小値で成立する

制約最適化

このタイプの最適化では、g(u)=0またはg(u)≤0という等号制約が与えられ（そうでなければ項目を並び替えたり、負の値をかけることでこの形にすることができます）、制約を満たすすべての点に対してのみ最適化を行いたいと思います。

通常、等号制約g(u)=0はアフィン（線形の一般化）であると仮定し、不等号制約g(u)≤0は凸関数を含むようにして、全体として最適化問題が凸であると仮定します（それ以外の場合、f(u)が単独で凸であるだけでは、最適な値を保証するのに十分ではないかもしれません）。

等号制約を伴う制約最適化

ここでは、多変数関数f(u)と制約g(u)=0が与えられ、g(u*)=0およびf(u*)が最小（つまり、制約を満たす最も低い可能な点）である点u*を見つけたいとします。

たとえば、表示されている例では、目的関数はf(u₁,u₂) = u₁+ u₂（3D平面）で、制約はu²₁+ u²₂=1（2D円）です。目標は、u²₁+ u²₂=1が成立する最も低い点（つまり、平面上に射影された円の最も低い点）に対応する点(u₁, u₂)を見つけることです。

このような制約最適化問題を解くための方法の1つは、ラグランジュ乗数法を使用することです。簡単に言えば、ラグランジュ乗数の定理は、次の形式の最適化問題の解u*が次の方程式を満たす必要があると述べています：

最小化 f(u) 制約： g(u)=0

あるλ∈R（および当然、g(u*)=0）に対して∇ᵤL(u*,λ)=0が成り立つとします。ここでLはラグランジアン関数で、L(u,λ)=f(u)+λg(u)です。∇ᵤg(u*)≠0と仮定されます。

これによって、等式制約を持つ制約最適化問題を次のように解くことができます（∇ᵤg(u*)≠0と仮定して）：

1. ラグランジュ関数 L(u,λ)=f(u)+λg(u) を書きます。
2. g(u)=0 のもとで ∇ᵤL(u,λ) = 0（n個の方程式）からなる n+1 個の方程式を解いて、n+1 個の未知数 u*₁,u*₂,…,u*ₙ,λ を求めます。
3. 解は u*=(u*₁,u*₂,…,u*ₙ) です。

λはラグランジュ乗数と呼ばれます。我々は解u*を導くシステムの一部としてそれを見つける必要があるだけです。

上記の図に対応する例の詳細は、こちらで確認できます。この例では、問題は凸ではなく、解を求めると最小値または最大値が出てくる可能性があります。なお、上記のステップ（1）と（2）は、L(u,λ)=f(u)+λg(u)に対する制約のない最適化を行うことと同じです。すなわち、次のように設定します：

∇ L(u,λ) =(∂L(u)/∂u₁, ∂L(u)/∂u₂, …, ∂L(u)/∂uₙ, ∂L(u)/∂λ)= 0

この意味では、このラグランジュ乗数の方法は、制約のある最適化問題を制約のない最適化問題に変換し、単に勾配をゼロに設定することで解くという点で強力です。

理論的根拠

なぜこれが機能するのか、直感的に導くのは難しくありません。実行可能領域は、問題の制約を満たす点の集合です（上の円上の点など）；我々はこのような点の中で目的関数が最適な点を見つけたいと思っています。

∇ f(u)は、最大減少方向（最大増加方向に逆向き）を指すことがわかっています。しかし、今回の場合は、制約領域内（制約を満たす点）でのみ移動が許可されています。したがって、制約の下で関数を最小化するためには、制約曲線に沿った最大減少方向に移動したいと思うはずです（それによって実行可能領域を出ずに最小値に到達します）。

制約曲線上の点uにおける接線の方向をr(u)で表すと、ベクトルの射影の公式を思い出すと、次の方向に逆向きに移動したいと思います（∇ f(u)をr(u)上に射影）：

制約を満たす方向には動けませんので、この値が0になるときに移動できる方向がありません。これが最大値の場合は f(u)をさらに増加させる方向に、最小値の場合は減少させる方向に移動することができないという意味です。

これがゼロになるためには、r(u)≠0（分母がゼロでないため）および∇ f(u) ⋅ r(u)=0となる必要があります。後者については、制約曲線上の法線ベクトル∇ g(u)は接線r(u)に垂直であることを知っています。したがって、我々に必要なのは∇ f(u)が∇ g(u)と平行であることです。

そのため、最適点u*では次の条件が成り立たなければなりません：

1. 制約の法線ベクトルは非零である：∇ g(u*)≠0（つまりr(u*)≠0）
2. 制約が満たされる：g(u*)=0（自明な要件）
3. ∇ f(u*) ∥∇ g(u*)：ある実数βが存在し、∇ f(u*) = β∇ g(u*)

項目を再配置し、-βをリネームすることで、「実数λが存在し、∇ f(u)+λ∇ g(u)=0」という（3）が同等であることに注意してください。言い換えると、∇ᵤL(u,λ) = 0です。したがって、我々は直感的に1つの制約に対するラグランジュ乗数の定理を導出しました（必要に応じて上にスクロールしてください）。

第1の条件は制約条件適格性と呼ばれます。この条件が制約条件で満たされていない場合、（2）と（3）が満たされる点でこの点が最適であることを保証するものではありません。なぜなら、その射影はそこで定義されていないからです。

複数の等式制約

複数の制約g₁(u), g₂(u),…,gₖ(u)が存在する場合、次のようにスムーズに一般化します：

1. ラグランジアンL(u,λ₁,λ₂,…,λₖ) = f(u) + λ₁g₁(u) + λ₂g₂(u) +…+λₖgₖ(u)を記述する
2. ∇ᵤL(u,λ₁,λ₂,…,λₖ) = 0（n個の方程式）とg₁(u)=0, g₂(u)=0, …, gₖ(u)=0を設定して、n+k個の未知数u*₁,u*₂,…,u*ₙ, λ₁,λ₂,…,λₖを求めるためにn+k個の方程式を解く
3. 解はu*=(u*₁,u*₂,…,u*ₙ)です

仮定∇ g(u*)≠0は、∇ g₁(u), ∇ g₂(u),…,∇ gₖ(u)が線形独立であることを一般化したものです。これをLICQ（線形独立制約条件適格性）といいます。

不等式制約による制約最適化

g(u)≤0のような不等式制約に対処している場合、問題は複雑になります。この場合、g(u)≤0を満たすf(u)の最適点を求める必要があります。

上記の問題の場合、許容領域は円上の点だけでなく、その内部の点も含まれます。特定の問題では（一般的ではありませんが）、これが解に変化をもたらさないことは明らかです。

ラグランジュ乗数（2、3）の2つの条件を解く代わりに、ラグランジュ乗数の場合と一般化される、KKT条件と呼ばれる4つの条件のセットを解きます。これらは次のように導出できます：

任意の多様体f(u)と制約条件g(u)≤0に対して、凸な滑らかな関数を仮定すると、最適な解は2つあります。

1. 最適点uᴾは実行可能領域の内側に存在します。

• この場合、最適化問題の解であるu*はuᴾであり、g(u*)<0が成立する必要があります（左の画像）。
• 実行可能領域内でより最適な点を見つけることは不可能です。なぜなら、uᴾがf(u)の範囲全体（ドメイン）で最も最適な点（例えば最小値）であるからです。

2. 最適点uᴾは実行可能領域の外側に存在します。

• この場合、その点が最大値である場合、実行可能領域でf(u)は単調減少する必要があります（他の最適な点が生成されないように再び増加しない）
• その点が最小値である場合、実行可能領域ではf(u)は単調増加する必要があります（他の最適な点が生成されないように再び減少しない）
• したがって、最適点u*は実行可能領域の境界にある必要があります。内部ではさらに良くなることはありません（g(u*) = 0が成立する必要があります）

最初の場合は、最適化問題を解くことは明らかに制約なしのバージョンを解くことと同等です。

∇ᵤf(u) = 0

制約が「非活性」であると言いますが、それは最適化問題に影響を与えないためです。

2番目の場合では、最適化問題を等式制約のバージョン（ラグランジュ乗数法）を解くことと同等であることは明らかです。

ただし、この場合の注意点は、最小化の場合にはλ≥0でなければならず、最大化の場合にはλ≤0である必要があることです。最小化の場合、これは∇ᵤf(u)と∇ᵤg(u)が逆の方向を指すことを意味します（つまり、β∇ᵤf(u) = β∇ ᵤg(u) ≤0が成立する必要があります）。これは、∇ᵤg(u)が制約g(u)≥0の正の側に向かっていることを示しています（基本的な性質）；一方、∇ᵤf(u)はf(u)が増加する場所に向かっているため、制約の負の側を指しています。最大化の場合についても同様の議論が簡単に構築できます。

ただし、どちらの場合が適用されるかは事前にはわかりません。以下のようにこれらの方法を統合することができます（最小化を仮定しています）：

1. ラグランジュ関数L(u,λ)=f(u)+λg(u)を書く
2. ∇ᵤL(u,λ) = 0（n個の方程式）およびg(u)≤0を設定する
3. 解（u*₁,u*₂,…,u*ₙ,λ）を求める。上記のいずれかの場合が適用される：

• λ=0およびg(u*)<0（λ=0は∇ᵤL(u,λ) = ∇ᵤf(u) = 0を意味するため、ステップ1、2は∇ᵤf(u) = 0を解くことと等価です）
• g(u*)=0およびλ≥0（g(u)=0はラグランジュ法の適用が正しいことを意味し、それが行われた内容です）

最適点u*に対してg(u*)≤0およびλ≥0が成立し、λg(u*)=0が成立する必要があるとまとめることができます（λまたはg(u*)のいずれかがゼロでなければなりません）。これにより、次の形式の最適化問題が与えられた場合：

最小化 f(u) 制約 g(u)≤0

最適点u*に対して以下の4つの条件が満たされることが期待されます：

1. 停留：∇ᵤL(u*,λ) = 0
2. 原始的制約条件：g(u*)≤0
3. 双対的制約条件：λ≥0
4. 相補的スラック：λg(u*)=0

これらの条件を一緒に解くことで最適点u*が得られます。実際のところ、凸問題では、これらの条件は最適性のために必要十分ではありません。

• これらの条件を満たす点が存在する場合（それらを一緒に解くことによって見つかった場合）、その点が最適であることが証明されます（凸問題の場合、さらに見る必要はありません）。
• 一方、これらの条件は最適であるために必要ではありません。実際には、これらの条件を解くことで解が得られない場合でも、実際には条件を満たさない最適点が存在する場合があります。例えば、f(x) = x および制約 x² ≤ 0 を考えてください（このドキュメントでは、このKKTの例と別の例が解かれています）

いったん、LICQ（前述のような制約条件）を適用すると、KKT条件が十分かつ必要であることを保証することができます。より簡単に確認できる代替の制約条件は、Slaterの条件で、これによりKKTが凸問題に対して必要かつ十分であることが保証されます。

Slaterの条件は、単に実行可能領域が内部点を持つ必要があるというものです。つまり、制約 g(u)≤0 に対して f(u) の定義域の中で g(u)<0 を満たす点が存在する必要があります。これは現実の問題ではほとんど常に満たされる基本的な条件です（ただし、上記の例外を除く）し、これは KKT が最適解を見逃すことはほとんどないことを意味します。

複数の制約

複数の等式制約 h₁(u), h₂(u),…,hₖ(u) と複数の不等式制約 g₁(u), g₂(u),…,gₚ(u) が存在する場合、この方法は制約とそれらの乗数（αと呼ぶことにしましょう）に関して完全なラグランジアンを書き、KKT条件を不等式制約とそれらの乗数に対してのみチェックすることによって滑らかに一般化します。

0. ラグランジアンを書く

1. ∇ᵤL(u,λ₁,λ₂,…,λₖ, α₁, α₂, …, αₚ) = 0（n式） を設定する

2. h₁(u)=0, h₂(u)=0, …, hₖ(u)=0（k式）および g₁(u)≤0, g₂(u)≤0, …, gₚ(u)≤0（p不等式）を設定する

3. α₁≥0, α₂≥0, …, αₚ≥0（p不等式）を設定する

4. α₁g₁(u) = α₂g₂(u) = αₚgₖ(u) = 0（p式）を設定する

合計して、n+k+pの式と2pの不等式があり、これらを一緒に解いて n+k+p個の変数 (u*₁,u*₂,…,u*ₙ,λ₁,λ₂,…,λₖ,α₁, α₂, …, αₚ ) を求めます。これにより、k+pの制約を満たしつつ関数を最小化する解 u*=(u*₁,u*₂,…,u*ₙ) が得られます。

デュアリティの原理

デュアリティの原理は単純には、どんな最適化問題に対しても、それを解くことで元の問題（原始問題と呼ばれる）について何かを示すか、解くことができますと述べています。

以下のような形式の最適化問題に対して:

デュアル最適化問題は次のようになります:

また、その逆も成り立ちます（最大化の場合も同様です）。

例

たとえば、先に議論した制約最適化問題:

に対応するデュアル問題は次のようになります:

基本的な微積分によれば、最小化を続けるためにまず行うのは

これは次を意味します

したがって、最適化問題は次のようになります

これを微分してゼロに等しくすると、λ = 1/√2 となり、これは (x*, y*) = (−1/√2, −1/√2) を意味し、これは KKT を使用して元の問題を解決したときと同じ解です。

デュアルの導出

元の原始問題は次のようになります

uが制約を満たさない場合には無限大を返し、そうでない場合にはゼロを返す関数を定義するとします：

この場合、原始問題は次のようになります

これは、f(u)+P(u) が実行可能領域の外部を無限大に設定し、実行可能領域をそのまま残します。この合計の最小値は、無限大が最大であるため、必ず実行可能領域で生じます。

次のように主張できることに注目してください：

これにより、次の場合：

• g(u)<0 の場合、λg(u) を最大にするために λ=0 が成立するため、P(u)=0 となります (g(u)<0 なのでそれ以外は負になります)
• g(u)=0 の場合、λg(u) はゼロになるため、P(u)=0 となります (λは任意の値を取ることができます)
• g(u)>0 の場合、λ=∞ が λg(u) を最大化するため、P(u)=∞ となります

したがって、原始問題は次のようになります

これとデュアル問題の違いは、デュアルではMaxとMinが入れ替わっていることです。

したがって、一般的に MinMax(…) ≥ MaxMin(…) となるため、デュアルの解は、原始問題の解の下界となります。これは弱双対性と呼ばれます。

より興味深いのは、MinMax(…) = MaxMin(…) の場合です。デュアルの解は、原始問題の解自体と完全に一致します（この例では）。これは強双対性と呼ばれます。KKTが必要かつ十分な場合、等式が成り立つ（つまり、強双対性）ことを比較的簡単に証明できます。言い換えれば、凸問題の場合、スレーターの条件が成り立つ場合には、強双対性が成り立ちます！

それでは、どうなの？

考えてみると、双対問題を解くことは、KKTの定常性と双対実行可能性条件を主問題にのみ適用することと同じです。元問題では主実行可能性と補余余裕を適用する代わりに、双対変数上の追加の最小化問題を扱う必要があります。多くの場合、これは元問題のKKTを解くよりも簡単です。追加の最小化問題は、線形プログラミングや二次計画法などで解決することができます。

複数の制約条件？

複数の制約条件への拡張では、ラグランジュ乗数が予想どおり変化します（前述のものと似ています）。不等号制約に関連する乗数には、α≥0の条件が追加されるだけです。

この記事が無制約最適化、ラグランジュ乗数、KKT、双対性を理解するのに役立ったことを願っています。次回まで、さようなら！

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!