非線形最適化をざっくり俯瞰してみた

非線形最適化入門

世の中にはたくさんの非線形最適化ソルバーが溢れており簡単にアクセスできる。筆者はそれらをそれぞれの方法がどのような方法なのかをあまり理解せずに利用してきた。非線形アルゴリズムの違いを基本事項から整理することが本文章の目的である。

本文は次のような順番で話を進める。

• 解析学の基本事項
• アルゴリズム設計の基本方針
• 具体的なアルゴリズム

解析学の基本事項

ここでは解析学の基本事項を紹介する。

制約なし非線形最適化

制約なし非線形最適化問題は次のような式で表される。

\begin{align}
\underset{\mathbf{x}}{\inf} &f(\mathbf{x})\\
\end{align}

ただし、

• $f(\mathbf{x})$: 評価関数
• $\mathbf{x}$: 最適化対象のパラメータ

この最適解の必要条件は、$\frac{\partial f}{\partial \mathbf{x}} = \mathbf{0}$である。これを一次収束条件と呼ぶ。

等式制約付き非線形最適化

等式付き非線形最適化問題は次のような式で表される。

\begin{align}
\underset{\mathbf{x}}{\inf}~&f(\mathbf{x})\\
\mathrm{s.t.}~&\mathbf{g}(\mathbf{x})=\mathbf{0}
\end{align}

ただし、

• $f(\mathbf{x})$: 評価関数
• $\mathbf{x}$: 最適化対象のパラメータ
• $\mathbf{g}(\mathbf{x})=\mathbf{0}$: 等式制約
  等式付きの非線形最適化問題の解法としてよく知られているラグランジュの未定乗数法を紹介する。以降、議論を簡単にするために$f,\mathbf{g}$はあらゆる点で微分可能であるとする。

ラグランジュの未定乗数法

制約なしの場合と同様に最適解の必要条件を考えると、$\mathbf{g}(\mathbf{x})=\mathbf{0}$に沿って動かした時に$f(\mathbf{x})$が停留することが一つの条件である。つまり、$\mathrm{d}\mathbf{g} = \frac{\partial \mathbf{g}}{\partial \mathbf{x}}\mathrm{d}\mathbf{x}=\mathbf{0}$となる方向$\mathrm{d}\mathbf{x}$に動かした時に$\mathrm{d}\mathbf{f}=\frac{\partial \mathbf{f}}{\partial \mathbf{x}}\mathrm{d}\mathbf{x}=\mathbf{0}$となっていればいい。よって、$\frac{\partial \mathbf{f}}{\partial \mathbf{x}}$が$\frac{\partial \mathbf{g}}{\partial \mathbf{x}}$の行ベクトルの線型結合で表されていればいいとわかる。係数ベクトル$-\mathbf{\lambda}$を導入して、これをまとめると、

\frac{\partial \mathbf{f}}{\partial \mathbf{x}} = -\mathbf{\lambda}^{\intercal}\frac{\partial \mathbf{g}}{\partial \mathbf{x}}

が成り立っていれば良い。

ラグランジュ関数として次の関数を定義する。

\begin{align}
\mathcal{L}(\mathbf{x}, \mathbf{\lambda}) = f(\mathbf{x}) + \mathbf{\lambda}^{\intercal}\mathbf{g}(\mathbf{x})
\end{align}

この関数の$\mathbf{x}, \mathbf{\lambda}$に関する最適解の必要条件を考えると、

\begin{align}
\frac{\partial \mathcal{L}(\mathbf{x}, \mathbf{\lambda}) }{\partial \mathbf{x}} &= \frac{\partial \mathbf{f}}{\partial \mathbf{x}} + \mathbf{\lambda}^{\intercal}\frac{\partial \mathbf{g}}{\partial \mathbf{x}} = \mathbf{0}\\
\frac{\partial \mathcal{L}(\mathbf{x}, \mathbf{\lambda}) }{\partial \mathbf{\lambda}} &= \mathbf{g}(\mathbf{x}) = \mathbf{0}
\end{align}

となっており、これは等式制約と先ほどの最適解の必要条件に一致する。

これまでの議論より、等式制約付き非線形最適化の必要条件は次のような制約なし非線形最適化の問題に置き換えられる。

\begin{align}
&\underset{\mathbf{x},\mathbf{\lambda}}{\inf} \mathcal{L}(\mathbf{x})\\
\end{align}

直感的には$\mathbf{g}(\mathbf{x})=\mathbf{0}$なる$\mathbf{x}$の部分空間での最適化なのだから決定変数が増えるのは非効率な感覚がある。

不等式制約付き非線形最適化

不等式付き非線形最適化問題は次のような式で表され、主問題と呼ばれる。

\begin{align}
\underset{\mathbf{x}}{\inf}~&f(\mathbf{x})\\
\mathrm{s.t.}~&\mathbf{g}(\mathbf{x})=\mathbf{0}\\
&\mathbf{h}(\mathbf{x})\leq\mathbf{0}
\end{align}

ただし、ベクトルの不等式は各成分それぞれに適用するものとする。（つまり、この不等式条件は各$i$番目成分について$h_{i}(\mathbf{x})\leq0$を示す。）
以降、$\mathbf{g}(\mathbf{x})=\mathbf{0}, \mathbf{h}(\mathbf{x})\leq\mathbf{0}$を満たすような$\mathbf{x}$の領域を$\mathcal{C}$と表す。

Karush-Kuhn-Tucker条件（KKT条件）

ラグランジュの未定乗数法と同じように最適解の必要条件を考えていこう。ラグランジュの未定乗数法の結論から先ほどの問題は次のように書き換えられる。

\begin{align}
\underset{\mathbf{x}, \mathbf{\lambda}}{\inf}~&f(\mathbf{x})+\mathbf{\lambda}^{\intercal}\mathbf{g}(\mathbf{x})\\
\mathrm{s.t.}~&\mathbf{h}(\mathbf{x})\leq\mathbf{0} 
\end{align}

したがって、不等式制約の扱いだけを考えれば良い。不等式条件は最適解が不等式が示す領域の内部にある場合と境界にある場合で扱いが異なる。以降の説明では、

• 最適解を内部にもつ制約を$\mathbf{h}_{\mathrm{I}}(\mathbf{x})$
• 最適解を境界にもつ制約を$\mathbf{h}_{\mathrm{B}}(\mathbf{x})$

とする。

このとき、最小値を取る必要条件は、

\begin{align}
\mathbf{h}_{\mathrm{I}}(\mathbf{x})\lt\mathbf{0} \\
\mathbf{h}_{\mathrm{B}}(\mathbf{x})=\mathbf{0} \\
\frac{\partial \mathcal{l}}{\partial \mathbf{x}}=\frac{\partial f}{\partial \mathbf{x}} + \mathbf{\lambda}^{\intercal}\frac{\partial \mathbf{g}}{\partial \mathbf{x}}=\mathbf{0}\\
\frac{\partial \mathcal{l}}{\partial \mathbf{\lambda}}=\mathbf{g}(\mathbf{x}) = \mathbf{0}\\
\end{align}

である。
ラグランジュの未定乗数法と同じように考えて、係数ベクトル$-\mathbf{\mu}_{\mathrm{B}}$を導入すると

\frac{\partial \mathcal{l}}{\partial \mathbf{x}} = \frac{\partial f}{\partial \mathbf{x}} + \mathbf{\lambda}^{\intercal}\frac{\partial \mathbf{g}}{\partial \mathbf{x}}= -\mathbf{\mu}_{\mathrm{B}}^{\intercal}\frac{\partial \mathbf{h}_{\mathrm{B}}}{\partial \mathbf{x}}

が成り立っていれば良い。ただし、ラグランジュの未定乗数法と異なり、係数ベクトルに条件がある。$\mathbf{\mu}_{\mathrm{B}}\lt\mathbf{0}$である場合、$\mathcal{l}(\mathbf{x})$の勾配が

\mathbf{h}_{\mathrm{B}}(\mathbf{x})

のと一致するため、境界よりも内部の評価値の方が小さいことになり最適解が境界にあるという最初の仮定に矛盾してしまう。よって係数ベクトルには$\mathbf{\mu}_{\mathrm{B}}\geq\mathbf{0}$という条件が課される。
まとめると、

\begin{align}
\frac{\partial \mathcal{l}}{\partial \mathbf{x}} &= \frac{\partial f}{\partial \mathbf{x}} + \mathbf{\lambda}^{\intercal}\frac{\partial \mathbf{g}}{\partial \mathbf{x}}= -\left(\mathbf{\mu}_{\mathrm{I}}^{\intercal}\frac{\partial \mathbf{h}_{\mathrm{I}}}{\partial \mathbf{x}}+\mathbf{\mu}_{\mathrm{B}}^{\intercal}\frac{\partial \mathbf{h}_{\mathrm{B}}}{\partial \mathbf{x}}\right) = -\mathbf{\mu}^{\intercal}\frac{\partial \mathbf{h}}{\partial \mathbf{x}}\\
\frac{\partial \mathcal{l}}{\partial \mathbf{\lambda}}&=\mathbf{g}(\mathbf{x}) = \mathbf{0}\\
\mathbf{h}_{\mathrm{B}}(\mathbf{x})&=\mathbf{0}\\
\mathbf{h}_{\mathrm{I}}(\mathbf{x})&\lt\mathbf{0}\\
\mathbf{\mu}_{\mathrm{B}}&\geq\mathbf{0}\\
\mathbf{\mu}_{\mathrm{I}}&=\mathbf{0}
\end{align}

上記では不等式条件のうち領域の境界上にあるものと領域内部にある条件を区別して書いたが、上の条件式を注意深くみると、$i$番目の成分に関して$\mu_{i}h_{i}(\mathbf{x})=0$という関係が常に成り立っていることがわかる。
したがって、先ほどの式は次のようにまとめられる。

\begin{align}
\frac{\partial f}{\partial \mathbf{x}}+\mathbf{\lambda}^{\intercal}\frac{\partial \mathbf{g}}{\partial \mathbf{x}}+\mathbf{\mu}^{\intercal}\frac{\partial \mathbf{h}}{\partial \mathbf{x}}=\mathbf{0}\\
\mathrm{diag}(\mathbf{\mu})\mathbf{h}(\mathbf{x})=
\begin{bmatrix}
\mathrm{diag}(\mathbf{\mu}_{\mathrm{I}})&\mathbf{0}\\
\mathbf{0}&\mathrm{diag}(\mathbf{\mu}_{\mathrm{B}})
\end{bmatrix}
\begin{bmatrix}
\mathbf{h}_{\mathrm{I}}(\mathbf{x})\\
\mathbf{h}_{\mathrm{B}}(\mathbf{x})
\end{bmatrix}
= \mathbf{0}\\
\mathbf{h}(\mathbf{x})\leq\mathbf{0}, \mathbf{g}(\mathbf{x})=\mathbf{0}\\
\mathbf{\mu}\geq\mathbf{0}=\mathbf{0}\\
\end{align}

2番目の条件は相補性条件と呼ばれ、不等式条件が領域の内部で満たされるか境界上にあるかの場合わけに対応する。

双対問題

この問題に対して次のようなラングランジュ関数を考えよう。

\begin{align}
\mathcal{L}(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu}) &= f(\mathbf{x}) + \mathbf{\lambda}^{\intercal}\mathbf{g}(\mathbf{x}) + \mathbf{\mu}^{\intercal}\mathbf{h}(\mathbf{x}) \\
\end{align}

ただし、$\mathbf{\mu} \geq \mathbf{0}$である。$\mathbf{x}$が制約を満たす場合、$\mathbf{g}(\mathbf{x})=0$, $\mathbf{h}(\mathbf{x})\leq0$であったから、この関数は次のような関係を持つ。

f(\mathbf{x}) \geq \mathcal{L}(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu}) 

$\mathbf{\mu}^{\intercal}\mathbf{h}(\mathbf{x})=0$の時に等式が成り立ち、

f(\mathbf{x}) = \underset{\mathbf{\lambda}, \mathbf{\mu}\geq\mathbf{0}}{\sup} \mathcal{L}(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu}) 

という関係を持つ。また、先ほどの不等式から最適解の評価関数の値は次のような関係を持つことがわかる。

\underset{\mathbf{x}\in \mathcal{C}}{\inf}f(\mathbf{x}) \geq \underset{\mathbf{x}\in \mathcal{C}}{\inf}\mathcal{L}(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu}) \geq \underset{\mathbf{x}}{\inf}\mathcal{L}(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu}) =: f^{*}(\mathbf{\lambda}, \mathbf{\mu})

２つ目の不等式は、制約の内部領域の最小値よりも制約なしの領域全体の最小値の方が小さいということに基づく。
上記のように、$f^{*}(\mathbf{\lambda}, \mathbf{\mu})$は評価関数の下限として考えることができる。
また、双対関数は$\mathbf{\lambda}, \mathbf{\mu}$に関して凸関数になっている。
次の$g(\mathbf{\lambda}, \mathbf{\mu})$の最大化問題はもとの最適化問題を主問題と呼ぶのに対して、双対問題と呼ばれる。

\begin{align}
\underset{\mathbf{\lambda}, \mathbf{\mu}\geq\mathbf{0}}{\sup} ~&f^{*}(\mathbf{\lambda}, \mathbf{\mu})
\end{align}

双対という言葉には何か深い意味があるのではないか？と考えたくなるが、次に説明する双対性という性質をもった主問題の対になる問題という意味しかない。

双対問題の最大化のための必要条件は、

\begin{align}
\frac{\partial \mathcal{L}}{\partial \mathbf{\mu}} = \mathbf{h}(\mathbf{x})=\mathbf{0}\\
\frac{\partial \mathcal{L}}{\partial \mathbf{\lambda}} = \mathbf{g}(\mathbf{x})=\mathbf{0}\\
\mathbf{\mu}\geq\mathbf{0}
\end{align}

である。

双対性

双対性は一言で言うと、「主問題の評価値の下限値問題として双対問題があり、双対問題の評価値の上限値問題として主問題があるという互いの関係」である。

さて、これまで得た関係式を整理すると、次のような関係となっている。

\underset{\mathbf{x}\in \mathcal{C}}{\inf}f(\mathbf{x}) = \underset{\mathbf{x}\in \mathcal{C}}{\inf}\underset{\mathbf{\lambda}, \mathbf{\mu}\geq\mathbf{0}}{\sup} \mathcal{L}(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu}) \geq 
\underset{\mathbf{\lambda}, \mathbf{\mu}\geq\mathbf{0}}{\sup}\underset{\mathbf{x}}{\inf}\mathcal{L}(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu}) = 
\underset{\mathbf{\lambda}, \mathbf{\mu}\geq\mathbf{0}}{\sup} f^{*}(\mathbf{\lambda}, \mathbf{\mu})

これは、双対問題の最大値が主問題の最小値よりも小さいことを示しており、最適化問題の弱双対性と呼ばれる。これはMax-Min不等式に基づいている。

特殊な問題設定（例えば、凸最適化問題で$\mathcal{C}\neq\emptyset$の場合：Slaterの条件）では以下が成り立ち、この性質を最適化問題の強双対性と呼ぶ。

\underset{\mathbf{x}\in \mathcal{C}}{\inf}f(\mathbf{x}) = 
\underset{\mathbf{\lambda}, \mathbf{\mu}\geq\mathbf{0}}{\sup} f^{*}(\mathbf{\lambda}, \mathbf{\mu})

先ほど導いたKKT条件は、主問題

\underset{\mathbf{x}\in \mathcal{C}}{\inf}\underset{\mathbf{\lambda}, \mathbf{\mu}\geq\mathbf{0}}{\sup} \mathcal{L}(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu}) 

を満たす$(\mathbf{x},\mathbf{\lambda},\mathbf{\mu})$の条件となっている。

双対関数は凸関数であったので、強双対性がある場合で双対関数が最大となる$(\mathbf{x},\mathbf{\lambda},\mathbf{\mu})$の組は一つに定まる。

主問題だけを考えていると評価値を上からだけ抑えていくことになるが、双対問題を考えることで下からも評価値を抑えていくことができる。これは反復アルゴリズムの収束性の観点でメリットがある。

まとめ

最適化の解析学として次の事項を説明した。

• 最適性の必要条件
  • 一次収束条件
  • ラグランジュの未定乗数法
  • KKT条件
• 不等式制約付き非線形最適化問題の性質
  • 双対問題
  • 双対性（強双対性・弱双対性）

アルゴリズムの基本方針

アルゴリズムの基本方針は解を反復的に更新することで最適化に近づけていくというものである。ここでは解への近づけ方について幾つかの観点で方針を分類する。

反復アルゴリズム

反復アルゴリズムは、

• 現在の解候補周辺での非線形関数の近似（一次式・二次式）
• 近似モデルに基づく解候補の更新

という手順で進む。

解候補の更新

解候補の更新は主に二つの方法がある。一つは、直線探索法、もう一つが信頼領域法である。これらは更新量と更新方向を決定する順番による分類である。

• 直線探索法：更新方向$\delta\mathbf{x}$を決めてから、更新量$d$を決定
  • e.g. 最急降下法
• 信頼領域法：近似モデルが信頼できる領域（更新量$d$）を決めてから更新方向$\delta\mathbf{x}$を決定
  • e.g. DogLeg法

不等式制約の扱い

主問題のみに注目する方法と主問題と双対問題を同時に解く方法の二つの方法がある。

• 主問題のみを解く方法
  • A. 強引に制約を評価関数に組み込む方法
    • e.g.ペナルティ法、バリア法
  • B. KKT条件を満たすような$(\mathbf{x},\mathbf{\lambda},\mathbf{\mu})$の組を発見する方法
    • 相補性条件を条件分岐として扱い最適解を見つける方法
      • e.g.有効制約法・シンプレックス法
    • 式を満たす組を反復的に見つける方法
      • e.g.主双対内点法
• 主問題と双対問題を同時に解く方法（強双対性のある問題）：
  • C. 主問題と双対問題を同時に更新し反復的に$(\mathbf{x},\mathbf{\lambda},\mathbf{\mu})$を更新する方法
    • e.g. dual ascent法

具体的なアルゴリズム

ここでは具体的なアルゴリズムについて解説する。一般の非線形問題について議論する。

ペナルティ法・バリア法（強引に制約を評価関数に組み込む方法）

次のような不等式制約付きの問題が与えられた場合を考える。

\begin{align}
\underset{\mathbf{x}, \mathbf{\lambda}}{\inf}~&f(\mathbf{x})+\mathbf{\lambda}^{\intercal}\mathbf{g}(\mathbf{x})\\
\mathrm{s.t.}~&\mathbf{h}(\mathbf{x})\leq\mathbf{0} 
\end{align}

この時、次のような不等式制約なし問題を解くことで解を求める方法が考えられる。

\begin{align}
\underset{\mathbf{x}, \mathbf{\lambda}}{\inf}~&f(\mathbf{x})+\mathbf{\lambda}^{\intercal}\mathbf{g}(\mathbf{x})+\Sigma_{i=1}^{\mathrm{dim}\mathbf{h}(\mathbf{x})}p_{i}(h_{i}(\mathbf{x}))\\
\end{align}

ただし、$p_{i}()$は不等式を満たさないことによる罰則を表す関数である。$p_{i}()$の設計によってこの手法は呼び方が変わる。

• $p_{i}$の定義域が不等式内部のみの場合、バリア法（障壁法）と呼ばれる
  • 不等式が満たされない場合に$\infty$の罰則が加えられる
  • 例
    • 対数関数を利用したもの

      p_{i}(h_{i}(\mathbf{x})) = -a\mathrm{log}(-h_{i}(\mathbf{x}))
      

• $p_{i}$の定義域が実数全体の場合、ペナルティ法（罰則法）と呼ばれる
  • 例
    • 二次関数とmax関数を合わせた関数(ただし、$a$は定数)

      p_{i}(h_{i}(\mathbf{x})) = a\max(0, h_{i}(\mathbf{x}))^{2}
      

内点法と外点法

内点法と外点法は初期解が不等式条件を満たすことを仮定するかしないかで区別した呼び方であ理、内点法は文字通り不等式条件が示す領域の内部に初期解があることを仮定した方法である。上記の方法で、バリア法（障壁法）は内点法、ペナルティ法（罰則法）は外点法と呼ばれることがある。

主双対内点法（KKT条件を直接反復解法で解く方法）

KKT条件は次のような式であった。

\begin{align}
\frac{\partial f}{\partial \mathbf{x}}+\mathbf{\lambda}^{\intercal}\frac{\partial \mathbf{g}}{\partial \mathbf{x}}+\mathbf{\mu}^{\intercal}\frac{\partial \mathbf{h}}{\partial \mathbf{x}}=\mathbf{0}\\
\mathrm{diag}(\mathbf{\mu})\mathbf{h}(\mathbf{x})= \mathbf{0}\\
\mathbf{h}(\mathbf{x})\leq\mathbf{0}\\
\mathbf{g}(\mathbf{x})=\mathbf{0}\\
\mathbf{\mu}\geq\mathbf{0}=\mathbf{0}\\
\end{align}

KKT条件に$(\mathbf{x},\mathbf{\lambda},\mathbf{\mu})$に関してニュートン法を適用して解くことを考える。kステップ目の解

(\mathbf{x}_{k},\mathbf{\lambda}_{k},\mathbf{\mu}_{k})

のまわりで一次近似して二次以上の微小項を無視すると、

\begin{align}
\begin{bmatrix}
\frac{\partial^{2} f}{\partial \mathbf{x}^{2}}(\mathbf{x}_{k})+\mathbf{\lambda}_{k}^{\intercal}(\mathbf{x}_{k})\frac{\partial^{2} \mathbf{g}}{\partial \mathbf{x}^{2}}(\mathbf{x}_{k})+\mathbf{\mu}_{k}^{\intercal}(\mathbf{x}_{k})\frac{\partial^{2} \mathbf{h}}{\partial \mathbf{x}^{2}}(\mathbf{x}_{k}) 
& \frac{\partial \mathbf{h}}{\partial \mathbf{x}}(\mathbf{x}_{k})^{\intercal} 
& \frac{\partial \mathbf{g}}{\partial \mathbf{x}}(\mathbf{x}_{k})^{\intercal}\\
\mathrm{diag}(\mathbf{\mu})\frac{\partial \mathbf{h}}{\partial \mathbf{x}}(\mathbf{x}_{k})&\mathrm{diag}(\mathbf{h}(\mathbf{x}_{k}))&\mathbf{0}\\
\frac{\partial \mathbf{g}}{\partial \mathbf{x}}(\mathbf{x}_{k}) &\mathbf{0} &\mathbf{0}
\end{bmatrix}
\begin{bmatrix}
\mathrm{d}\mathbf{x}\\
\mathrm{d}\mathbf{\mu}\\
\mathrm{d}\mathbf{\lambda}
\end{bmatrix}
+
\begin{bmatrix}
\frac{\partial f}{\partial \mathbf{x}}(\mathbf{x}_{k})
+\mathbf{\lambda}_{k}^{\intercal}(\mathbf{x}_{k})\frac{\partial \mathbf{g}}{\partial \mathbf{x}}(\mathbf{x}_{k})
+\mathbf{\mu_{k}}^{\intercal}(\mathbf{x}_{k})\frac{\partial \mathbf{h}}{\partial \mathbf{x}}(\mathbf{x}_{k})\\
\mathrm{diag}(\mathbf{\mu}_{k})\mathbf{h}(\mathbf{x}_{k})\\
\mathbf{g}(\mathbf{x}_{k})
\end{bmatrix}
= \mathbf{0}\\
\mathbf{h}(\mathbf{x}_{k}) + \frac{\partial \mathbf{h}}{\partial \mathbf{x}}(\mathbf{x}_{k})\mathrm{d}\mathbf{x}\geq \mathbf{0}\\
\mathbf{\mu}_{k}+\mathrm{d}\mathbf{\mu}\geq\mathbf{0}
\end{align}

となる。この一次方程式を付属する二つの不等式の制約のもとで解くことで更新量を決定する。

有効制約法（KKT条件の相補性条件を条件分岐として扱う方法）

KKT条件の導出は不等式条件が表す領域の境界にのる条件と領域内部にある条件が事前に分かっている、（つまり、どの不等式を等式条件として考え、どの不等式を考慮しなくてもいいかが分かっている）として、ラグランジュの未定乗数法で問題を解くことで導出したのであった。

この考え方をそのままアルゴリズムにすることを考えてみよう。
ただし、どの不等式が等式制約としてみなしてよい制約かは自明ではないので、制約の組をアルゴリズムを使って試行することで決める必要がある。
以下では便宜的に等式制約としてみなしてよい制約を有効制約、そうでない制約を非有効制約と呼ぶことにする。

アルゴリズムの流れ

基本的な流れは次のようになる。

1. 適当な有効制約（等式条件としてみなす制約）とそれを満たす初期解を設定する
2. 等式制約付き問題を解いて解（解候補）を更新する
3. 解候補が非有効制約を満たすことを確認する
4. 制約を満たさない場合、満たさない制約のうち一つを有効制約に加えて2に戻る（最も解候補に近い制約を選ぶことにする）
5. 等式条件としてみなす必要がないか有効制約がないかを確認する
   1. ある場合、有効制約のうち等式条件としてみなす必要のないものを一つ有効制約から除外して2に戻る（最も大きい乗数に対応する不等式を選ぶことにする）

Dual Ascent（主問題と双対問題を同時に解く方法）

強双対性を仮定すると、$(\mathbf{x}, \mathbf{\mu}, \mathbf{\lambda})$の主問題を解いた時の組と双対問題を解いた時の組が一致する。
これを利用して、主問題と双対問題を交互に解くことで解を求めることを考える。
大きな枠組みは、

• $\mathbf{\mu}, \mathbf{\lambda}$を固定したKKT条件を利用して$\mathbf{x}_{k}$を更新する（主問題の解の更新）
• $\mathbf{x}_{k}$を固定した双対問題を解くことで$\mathbf{\mu}, \mathbf{\lambda}$を更新する（双対問題の解の更新）
  の繰り返しである。

$\mathbf{\mu}, \mathbf{\lambda}$を固定したKKT条件は$\mathbf{x}$に関してニュートン法で解き、双対問題の最大化は$(\mathbf{\mu}, \mathbf{\lambda})$に関して最急降下法で解く。
（厳密には主問題の最適化の方法は何を使ってもDual Ascentと呼ぶようだ。）

主問題の解の更新

KKT条件を$\mathbf{\mu}, \mathbf{\lambda}$を固定して一次近似して二次以上の微小項を無視すると、

\begin{align}
\begin{bmatrix}
\frac{\partial^{2} f}{\partial \mathbf{x}^{2}}(\mathbf{x}_{k})+\mathbf{\lambda}_{k}^{\intercal}(\mathbf{x}_{k})\frac{\partial^{2} \mathbf{g}}{\partial \mathbf{x}^{2}}(\mathbf{x}_{k})+\mathbf{\mu}_{k}^{\intercal}(\mathbf{x}_{k})\frac{\partial^{2} \mathbf{h}}{\partial \mathbf{x}^{2}}(\mathbf{x}_{k}) \\
\mathrm{diag}(\mathbf{\mu})\frac{\partial \mathbf{h}}{\partial \mathbf{x}}(\mathbf{x}_{k})\\
\frac{\partial \mathbf{g}}{\partial \mathbf{x}}(\mathbf{x}_{k}) 
\end{bmatrix}
\begin{bmatrix}
\mathrm{d}\mathbf{x}
\end{bmatrix}
+
\begin{bmatrix}
\frac{\partial f}{\partial \mathbf{x}}(\mathbf{x}_{k})
+\mathbf{\lambda}_{k}^{\intercal}(\mathbf{x}_{k})\frac{\partial \mathbf{g}}{\partial \mathbf{x}}(\mathbf{x}_{k})
+\mathbf{\mu_{k}}^{\intercal}(\mathbf{x}_{k})\frac{\partial \mathbf{h}}{\partial \mathbf{x}}(\mathbf{x}_{k})\\
\mathrm{diag}(\mathbf{\mu}_{k})\mathbf{h}(\mathbf{x}_{k})\\
\mathbf{g}(\mathbf{x}_{k})
\end{bmatrix}
= \mathbf{0}\\
\mathbf{h}(\mathbf{x}_{k}) + \frac{\partial \mathbf{h}}{\partial \mathbf{x}}(\mathbf{x}_{k})\mathrm{d}\mathbf{x}\geq \mathbf{0}
\end{align}

これを解くことで$\mathbf{x}$を更新する。

双対問題の解の更新

一方で、双対問題の勾配は、

\begin{align}
\frac{\partial \mathcal{L}}{\partial \mathbf{\mu}} = \mathbf{h}(\mathbf{x})=\mathbf{0}\\
\frac{\partial \mathcal{L}}{\partial \mathbf{\lambda}} = \mathbf{g}(\mathbf{x})=\mathbf{0}\\
\mathbf{\mu}\geq\mathbf{0}
\end{align}

であったから、最急降下法を使って、

\begin{align}
\mathrm{d}\mathbf{\mu} &= \max(\mathbf{h}(\mathbf{x}_{k})t_{k}, 0)\\
\mathrm{d}\mathbf{\lambda} &= \mathbf{g}(\mathbf{x}_{k})t_{k}
\end{align}

で更新すればよい。ただし、$t_{k}$は更新量を決めるパラメータである。

参考資料

• https://qiita.com/zhidao/items/1b0ac934fb6774e1e84b
  • 有効制約法・KKT条件
• https://www.cs.cmu.edu/~pradeepr/convexopt/Lecture_Slides/dual-ascent.pdf
  • dual ascent
• wikipedia