内点法 （ないてんほう、英 : internal point method ）とは、連続最適化問題 のアルゴリズム であり、カーマーカー法 に触発されて生まれた多くの手法の総称である。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法 よりも優れているといえる。内点法は、点列を生成する方法によって、アフィン変換法 、ポテンシャル減少法 、パス追跡法 などに分類される。また、扱う問題によっては、与えられた問題を直接扱う方法(主内点法 、英 : primal interior point method )、その双対問題を扱う方法(双対内点法 、英 : dual interior point method )、主問題と双対問題を同時に解く方法(主双対内点法 、英 : primal-dual interior point method )に分けられる。
主双対内点法による非線型最適化
編集
主双対内点法のアイディアは単純で、制約付き非線型最適化問題にも応用が可能である。ここでは単純のために制約式が全て不等式で与えられる非線型最適化問題について考える。
最小化:
f
(
x
)
{\displaystyle f(x)}
条件:
c
(
x
)
≥
0
,
x
∈
R
n
,
c
(
x
)
∈
R
m
(
1
)
{\displaystyle c(x)\geq 0,x\in \mathbb {R} ^{n},c(x)\in \mathbb {R} ^{m}~~~~(1)}
この最適化問題の対数バリア関数 は次のようになる。
B
(
x
,
μ
)
=
f
(
x
)
−
μ
∑
i
=
1
m
ln
(
c
i
(
x
)
)
(
2
)
{\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\ln(c_{i}(x))~~~~(2)}
ここで
μ
{\displaystyle \mu }
μ
{\displaystyle \mu }
B
(
x
,
μ
)
{\displaystyle B(x,\mu )}
前述のバリア関数の勾配は
g
b
=
g
−
μ
∑
i
=
1
m
1
c
i
(
x
)
∇
c
i
(
x
)
(
3
)
{\displaystyle g_{b}=g-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x)~~~~(3)}
となる。ただし、
g
{\displaystyle g}
f
(
x
)
{\displaystyle f(x)}
∇
c
i
{\displaystyle \nabla c_{i}}
c
i
{\displaystyle c_{i}}
主値
x
{\displaystyle x}
λ
∈
R
m
{\displaystyle \lambda \in \mathbb {R} ^{m}}
∀
i
=
1
,
…
,
m
,
c
i
(
x
)
λ
i
=
μ
(
4
)
{\displaystyle \forall i=1,\ldots ,m,c_{i}(x)\lambda _{i}=\mu ~~~~(4)}
この条件は時に摂動相補性条件とも呼ばれる。式(4)を式(3)に適用することにより以下を得る。
g
−
A
T
λ
=
0
(
5
)
{\displaystyle g-A^{T}\lambda =0~~~~(5)}
ただし、行列
A
{\displaystyle A}
c
(
x
)
{\displaystyle c(x)}
ヤコビ行列 である。
式(5)が表しているのは関数
f
(
x
)
{\displaystyle f(x)}
μ
{\displaystyle \mu }
c
i
(
x
)
=
0
{\displaystyle c_{i}(x)=0}
c
i
(
x
)
{\displaystyle c_{i}(x)}
g
{\displaystyle g}
式(4)および式(5)に対してニュートン法 を用いて
(
x
,
λ
)
{\displaystyle (x,\lambda )}
(
p
x
,
p
λ
)
{\displaystyle (p_{x},p_{\lambda })}
(
W
−
A
T
Λ
A
C
)
(
p
x
p
λ
)
=
(
−
g
+
A
T
λ
μ
1
−
C
λ
)
{\displaystyle {\begin{pmatrix}W&-A^{T}\\\Lambda A&C\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-g+A^{T}\lambda \\\mu 1-C\lambda \end{pmatrix}}}
ただし行列
W
{\displaystyle W}
B
(
x
,
μ
)
{\displaystyle B(x,\mu )}
ヘッセ行列 であり、対角行列
Λ
{\displaystyle \Lambda }
λ
{\displaystyle \lambda }
C
{\displaystyle C}
C
i
i
=
c
i
(
x
)
{\displaystyle C_{ii}=c_{i}(x)}
式(1), (4), および
μ
>
0
{\displaystyle \mu >0}
λ
≥
0
{\displaystyle \lambda \geq 0}
がそれぞれのステップに課される。この条件を保つために、適切なステップ更新幅
α
{\displaystyle \alpha }
(
x
,
λ
)
→
(
x
+
α
p
x
,
λ
+
α
p
λ
)
{\displaystyle (x,\lambda )\rightarrow (x+\alpha p_{x},\lambda +\alpha p_{\lambda })}
とすることで、最適解に向かって収束していく。
参考文献
編集
