翻訳と辞書
Words near each other
・ 内灘町
・ 内灘町消防本部
・ 内灘砂丘
・ 内灘自転車競技場
・ 内灘闘争
・ 内灘駅
・ 内灘高校
・ 内灘高等学校
・ 内火艇
・ 内点
内点法
・ 内無双
・ 内燃力発電
・ 内燃動車
・ 内燃機
・ 内燃機関
・ 内燃機関組立て技能士
・ 内燃機関車
・ 内片輝
・ 内牧中学校


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

内点法 : ウィキペディア日本語版
内点法[ないてんほう]
内点法(ないてんほう、)とは、連続最適化問題アルゴリズムであり、カーマーカー法に触発されて生まれた多くの手法の総称である。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法よりも優れているといえる。内点法は、点列を生成する方法によって、アフィン変換法ポテンシャル減少法パス追跡法などに分類される。また、扱う問題によっては、与えられた問題を直接扱う方法(主内点法、)、その双対問題を扱う方法(双対内点法、)、主問題と双対問題を同時に解く方法(主双対内点法、)に分けられる。
== 主双対内点法による非線型最適化 ==
主双対内点法のアイディアは単純で、制約付き非線型最適化問題にも応用が可能である。ここでは単純のために制約式が全て不等式で与えられる非線型最適化問題について考える。
:最小化: f(x)
:条件: c(x) \geq 0, x \in \mathbb^n, c(x) \in \mathbb^m~~~~(1)
この最適化問題の対数値バリア関数は次のようになる。
:B(x,\mu) = f(x) - \mu \sum_^m \ln(c_i(x))~~~~(2)
ここで\muは正のスカラーで、時に「バリア・パラメータ」とも呼ばれる。この\muが0に収束していくと、B(x, \mu)が最適解に収束していく。
前述のバリア関数の勾配は
:g_b = g - \mu \sum_^m \frac \nabla c_i (x)~~~~(3)
となる。ただし、gは元の関数f(x)の勾配であり、\nabla c_ic_iの勾配を表す。
主値xに加えて、双対値\lambda \in \mathbb^mをラグランジュ乗数として導入する。
:\forall i=1, \ldots, m, c_i(x) \lambda_i = \mu~~~~(4)
この条件は時に摂動相補性条件とも呼ばれる。式(4)を式(3)に適用することにより以下を得る。
:g - A^T \lambda = 0 ~~~~ (5)
ただし、行列Aは制約c(x)ヤコビ行列である。
式(5)が表しているのは関数f(x)が制約式の勾配により張られる部分空間の中に存在するということである。このとき小さな\muによる摂動相補性条件は、最適解がc_i(x)=0の境界付近に存在するか、もしくは制約c_i(x)の勾配gがほとんど0であるということを表している。
式(4)および式(5)に対してニュートン法を用いて(x, \lambda)を更新していくことを考えると、その更新幅(p_x, p_\lambda)は次の線型方程式の解として与えられる。
: \begin W & -A^T \\ \Lambda A & C \end
\beginp_x \\ p_y \end =
\begin -g + A^T \lambda \\ \mu 1 - C \lambda \end
ただし行列Wは関数f(x)ヘッセ行列であり、対角行列\Lambda\lambdaを対角成分に持つ。
したがって、式(1), (4)から
: \lambda \geq 0
がそれぞれのステップに課される。適切なステップ更新幅\alphaを選び、
:(x, \lambda) \rightarrow (x + \alpha p_x, \lambda + \alpha p_\lambda)
とすることで、最適解に向かって収束していく。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「内点法」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.