内点法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/05/19 14:06 UTC 版)
内点法(ないてんほう、英: interior point method, internal point method)とは、連続最適化問題のアルゴリズムであり、カーマーカー法に触発されて生まれた多くの手法の総称である[1]。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法よりも優れているといえる。内点法は、点列を生成する方法によって、アフィン変換法、ポテンシャル減少法、解析的中心追跡法、パス追跡法などに分類される[2]。また、扱う問題によっては、与えられた問題を直接扱う方法(主内点法、英: primal interior point method)、その双対問題を扱う方法(双対内点法、英: dual interior point method)、主問題と双対問題を同時に解く方法(主双対内点法、英: primal-dual interior point method)に分けられる[3]。
主双対内点法による非線型最適化
主双対内点法のアイディアは単純で、制約付き非線型最適化問題にも応用が可能である。ここでは単純のために制約式が全て不等式で与えられる非線型最適化問題について考える。
-
最小化:
Optimization computes maxima and minima.
一般 | |
---|---|
微分可能 |
凸最小化 | |||||||
---|---|---|---|---|---|---|---|
線形 および 二次 |
|
系列範例 (Paradigms) |
|||||
---|---|---|---|---|---|
グラフ理論 |
|
||||
ネットワークフロー (最大流問題) |
内点法と同じ種類の言葉
Weblioに収録されているすべての辞書から内点法を検索する場合は、下記のリンクをクリックしてください。

- 内点法のページへのリンク