内点法

内点法（バリア法またはIPMとも呼ばれる）は、線形および非線形凸最適化問題を解くためのアルゴリズムです。IPMは、従来知られているアルゴリズムの2つの利点を組み合わせています。

理論的には、これらの手法の実行時間は多項式時間である。これに対し、シンプレックス法では最悪の場合、実行時間は指数関数的になる。
実際には、それらは単体法と同じくらい高速に動作します。これに対し、楕円体法は理論上は多項式時間で実行できますが、実際には非常に遅いです。

実行可能領域の境界をたどるアクティブセット法（単体法など）や、実行可能領域を外側から境界付ける楕円体法とは対照的に、IPMは実行可能領域の内部をたどることで最適解に到達します。これがIPMという名前の由来です。

歴史

内点法は、1967 年にソ連の数学者 II ディキンによって発見されました。^{[ 1 ]}この方法は、1980 年代半ばに米国で再発明されました。1984 年に、ナレンドラ・カルマルカーは、カルマルカーのアルゴリズムと呼ばれる線形計画法を開発しました。^[²^]これは、多項式時間 ( $O(n^{3.5}L)$ Lビット数に対する演算( nは変数と定数の数) であり、実用上も非常に効率的です。カルマルカーの論文は、内点法への関心の高まりを引き起こしました。2 年後、ジェームズ・レネガーは、実行時間で最初のパス追跡内点法を発明しました。 $O(n^{3}L)$ この方法は後に、凸集合を符号化するために使用される自己一致バリア関数に基づいて、線形最適化問題から凸最適化問題に拡張されました。^[³^]

任意の凸最適化問題は、エピグラフ形式に変換することにより、凸集合上の線形関数の最小化（または最大化）に変換できます。^[⁴^]^：¹⁴³実行可能集合をバリアを使用してエンコードし、バリア法を設計するというアイデアは、1960 年代初頭に Anthony V. Fiacco、Garth P. McCormick らによって研究されました。これらのアイデアは主に一般的な非線形計画法のために開発されましたが、この種の問題に対するより競争力のある方法 (例えば、逐次二次計画法)の存在により、後に放棄されました。

ユーリ・ネステロフとアルカディ・ネミロフスキーは、任意の凸集合を符号化するために使用できる特殊なクラスのバリアを考案しました。彼らは、アルゴリズムの反復回数が次元の多項式と解の精度によって制限されることを保証します。^{[ 5 ]}^{[ 3 ]}

主双対経路追跡内点法のクラスは最も成功したクラスと考えられています。メロトラの予測子・修正子アルゴリズムは、このクラスのメソッドのほとんどの実装の基礎となっています。^{[ 6 ]}

定義

次のような凸プログラムが与えられます。 ${\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{最小化}}}\quad &f(x)\\{\text{制約条件}}\quad &x\in G.\end{aligned}}$ ここで、f は凸関数であり、G は凸集合です。一般性を失うことなく、目的関数fは線形関数であると仮定できます。通常、凸集合Gは凸不等式と線形等式の集合で表されます。線形等式は線形代数を使用して消去できるため、簡単のために凸不等式のみが存在すると仮定し、プログラムは次のように記述できます。ここで、g _iは凸関数です。 ${\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{最小化}}}\quad &f(x)\\{\text{制約条件}}\quad &g_{i}(x)\leq 0{\text{ for }}i=1,\dots ,m.\\\end{aligned}}$ 制約関数は何らかのファミリー（例えば二次関数）に属すると仮定し、プログラムを有限個の係数ベクトル（例えば二次関数の係数）で表現できるものとします。この係数ベクトルの次元をプログラムのサイズと呼びます。与えられたプログラムファミリーに対する数値ソルバーとは、係数ベクトルが与えられたときに、有限個の算術演算を用いて、 t = 1, 2, ...に対する近似解x _tのシーケンスを生成するアルゴリズムです。数値ソルバーは、ファミリー内の任意のプログラムと任意の正のε > 0 に対して、任意の t > Tに対して近似解x _t がε 近似となるようなT（これはプログラムとεに依存する可能性があります）が存在する場合に収束すると言います。つまり、次のようになります。 ${\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad {\text{for}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}$ どこ $f^{*}$ が最適解です。ソルバーは、最初のTステップにおける算術演算の総数が最大での場合、多項式であると呼ばれます。

poly(問題のサイズ) * log( V / ε ) 、

ここで、V はデータに依存する定数であり、例えば、実行可能集合における最大値と最小値の差などです。言い換えれば、V / εは解の「相対精度」、つまり最大係数に対する精度です。log( V / ε ) は「精度の桁数」を表します。したがって、精度の桁数が1つ増えるごとに、問題のサイズに対して多項式となる演算回数が必要になる場合、ソルバーは「多項式的」であると言えます。

種類

内点法には以下のような種類があります。

ポテンシャル削減方法：カルマルカーのアルゴリズムが最初のものであった。
経路追跡法：ジェームズ・レネガー^{[ 7 ]}とクロビス・ゴンザガ^{[ 8 ]}のアルゴリズムが最初のものであった。
原始双対法。

経路追跡法

アイデア

制約付き凸最適化プログラム (P) が与えられた場合、バリア関数を追加することで、制約なしプログラムに変換できます。具体的には、実行可能領域Gの内部で定義された滑らかな凸関数b を、任意のシーケンスに対して、となるようにします。 $\{x_{j}\in {\textbf {G}}\}$ その限界がGの境界上にあるもの： $\lim _{j\to \infty }b(x_{j})=\infty$ また、bは非退化であると仮定します。すなわち、次のようになります。 $b''(x)$ は、interior(G) のすべての x に対して正定値である。次に、次のプログラム群を考えてみよう。 $P_{t}=t\cdot f(x)+b(x)$

技術的には、 bはGの内部でのみ定義されているため、このプログラムは制約付きです。しかし実際には、関数を最小化しようとするソルバーはb が無限大に近づく境界に近づかないため、制約なしプログラムとして解くことができます。したがって、( P _t ) は一意の解を持ち、それをx *( t ) とします。関数x * はtの連続関数であり、中心パスと呼ばれます。tが無限大に近づくときのx *のすべての極限点は、元のプログラム (P ) の最適解です。

パス追跡法とは、関数x * をある増加数列 t ₁ ,t ₂ ,... に沿って追跡する方法であり、すなわち、点x *( t _i ) に対する十分な近似値x _iを計算し、 i が無限大に近づくにつれて差分x _i - x *( t _i ) が 0 に近づくようにすることで、数列x _{i が}(P) の最適解に近づくようにする。これには次の 3 つの事項を指定する必要があります。

障壁関数 b(x)。
ペナルティパラメータt _iを決定するためのポリシー。
( P _i ) を解いてx _{i を}求めるために使用される制約なし最適化ソルバー（ニュートン法など）。各x _{i を}次の問題 ( P _i+1 )を解くための開始点として使用できることに注意してください。

この手法が多項式時間であることを証明する際の主な課題は、ペナルティパラメータが大きくなるにつれて解が境界に近づき、関数の傾きが急になることです。ニュートン法などのソルバーの実行時間が長くなり、全体の実行時間が多項式時間であることを証明するのが難しくなります。

Renegar ^{[ 7 ]}と Gonzaga ^{[ 8 ]}は、パス追跡法の特定のインスタンスが多項式時間であることを証明した。

制約条件（および目的関数）は線形関数である。
障壁関数は対数関数である。 $b(x)=-\sum _{j=1}^{m}\log({-g_{j}(x)})$
ペナルティパラメータtは幾何級数的に更新されます。つまり、 $\displaystyle t_{i+1}:=\mu \cdot t_{i}}$ ここでμは定数（彼らは $\mu =1+0.001\cdot {\sqrt {m}}$ （ここでmは不等式制約の数である）。
ソルバーはニュートン法であり、tの各ステップごとにニュートン法の1ステップが実行されます。

彼らは、この場合、差x _i - x *( t _i ) は最大で 0.01 であり、f( x _i ) - f* は最大で ${\frac {2m}{t_{j}}}$ したがって、解の精度は ${\frac {1}{t_{j}}}$ したがって、精度を1桁追加するには、t _iに 2 (またはその他の定数係数) を掛ければ十分であり、 $O({\sqrt {m}})$ ニュートンステップ。各ニュートンステップはO( mn2 )回^の演算を必要とするため、精度桁に対する全体の複雑さはO( m3 ^/ 2n2 )回^の演算となります。

ユーリ・ネステロフは、このアイデアを線形計画問題から非線形計画問題へと拡張した。彼は、上記の証明で使用されている対数バリアの主な特性は、有限のバリアパラメータと自己整合的であることだと指摘した。したがって、実行可能領域に適した自己整合的なバリア関数を見つけることができれば、他の多くの凸計画問題もパス追跡法を用いて多項式時間で解くことができる。^{[ 3 ]}^：第1節

詳細

凸最適化問題（P）が「標準形式」で与えられます。

Gにおいてc ^Tx st xを最小化する、

ここで、Gは凸かつ閉集合である。また、 Gは有界であると仮定することもできる（十分大きなRに対して| x |≤Rという制約を追加することで容易に有界にすることができる）。^[³^]^：^第4節

内点法を用いるには、Gの自己一致バリアが必要です。bをGのM自己一致バリアとします。ここで、M ≥ 1 は自己一致パラメータです。Gの内部のすべての点 x に対して、 bの値、その勾配、およびそのヘッセ行列を効率的に計算できると仮定します。

t > 0 の任意の値に対して、ペナルティ付き目的関数f _t (x) := t c ^Tx + b( x )を定義します。最小化パスは、x*(t) := arg min f _t (x)で定義されます。このパスは、増加数列t _iに沿って近似されます。数列は、ある非自明な 2 段階初期化手順によって初期化されます。その後、次の規則に従って更新されます。 $\displaystyle t_{i+1}:=\mu \cdot t_{i}}$ 。

各t _iに対して、 f _tiの近似最小値x _iを求めます。近似最小値は、次の「近接条件」を満たすように選択されます（ここでLはパス許容値です）。

${\sqrt {[\nabla _{x}f_{t}(x_{i})]^{T}[\nabla _{x}^{2}f_{t}(x_{i})]^{-1}[\nabla _{x}f_{t}(x_{i})]}}\leq L$ 。

x _i₊₁を求めるには、 x _iから始めて減衰ニュートン法を適用します。上記の「近接関係」が満たされるまで、この方法を数回繰り返します。この関係を満たす最初の点をx _i₊₁とします。^{[ 3 ]}^：第4節

収束と複雑性

この方法の収束率は、すべてのiに対して次の式で与えられる。^{[ 3 ]}^{:命題 4.4.1}

$c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}$

取 $\mu =\left(1+r/{\sqrt {M}}\right)$ x _iからx _i₊₁へ進むのに必要なニュートンステップ数は、 rとLのみに依存する固定数である。特に、ε近似解 (すなわち、c ^Tx - c* ≤ εとなるようなG内のx を見つける) を見つけるのに必要なニュートンステップの総数は、最大で次の通りである。^[³^]^:^{定理 4.4.1}

$O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1\right)$

ここで定数係数 O(1) はrとLのみに依存します。2 段階初期化手順に必要なニュートンステップ数は最大で次のようになります。^{[ 3 ]}^{:定理 4.5.1}

$O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1\right)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{\text{Var}}_{G}(c)}{\epsilon }}+1\right)$

ここで定数係数O(1)はrとLのみに依存し、 ${\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x$ 、そして ${\bar {x}}$ はGの内部のどこかの点である。全体として、 ε近似解を見つけるための全体的なニュートン複雑度は最大で

$O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)$ ここで、Vは問題に依存する定数である。 $V={\frac {{\text{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}$ 。

ニュートン法の各ステップは、O( n³ )^回の算術演算を必要とする。

初期化：フェーズIの方法

パス追跡法を初期化するには、実行可能領域Gの相対内部にある点が必要です。言い換えれば、Gが不等式g _i ( x ) ≤ 0 で定義されている場合、 1,..., mのすべてのiに対してg _i ( x ) < 0 となるようなxが必要です。そのような点がない場合は、いわゆるフェーズ I 法を使用して見つける必要があります。^[⁴^]^:^11.4 単純なフェーズ I 法は、次の凸計画問題を解くことです。 ${\begin{aligned}{\text{最小化}}\quad &s\\{\text{制約条件}}\quad &g_{i}(x)\leq s{\text{ for }}i=1,\dots ,m\end{aligned}}$ 最適解を x*、s * と表記する。

s *<0の場合、x* は元の問題の内部点であることがわかります。そして、「フェーズ II」、つまり元の問題を解く段階に進むことができます。
s *>0の場合、元のプログラムは実行不可能であることがわかります。つまり、実行可能領域は空です。
s *=0 であり、それが何らかの解 x* によって達成される場合、問題は実行可能であるが内部点は存在しない。達成されない場合は、問題は実行不可能である。

このプログラムでは、内点を見つけるのは簡単です。x = 0 を任意に設定し、 s を max( f 1 (0),..., f m (0)) より大きい任意の数に設定すればよい_のです。_{したがって}、内点法を用いて解くことができます。ただし、実行時間は log(1/ s *) に比例します。s* が 0 に近づくにつれて、フェーズ I の問題の正確な解を見つけることがますます難しくなり、したがって、元の問題が実行可能かどうかを判断することも難しくなります。

実務上の考慮事項

理論的な保証では、ペナルティパラメータが次の割合で増加すると仮定しています。 $\mu =\left(1+r/{\sqrt {M}}\right)$ 最悪の場合の必要なニュートンステップ数は $O({\sqrt {M}})$ 理論的には、μが大きい場合（例えば2以上）、必要なニュートンステップの最悪ケースの数は $O(M)$ しかし実際には、μが大きいほど収束ははるかに速くなります。これらの方法は長ステップ法と呼ばれます。^{[ 3 ]}^：第4.6節実際には、μが3から100の間であれば、制約の数に関係なく、プログラムは20～40ニュートンステップ以内に収束します（ただし、各ニュートンステップの実行時間は制約の数とともに増加します）。この範囲内でのμの正確な値は、パフォーマンスにほとんど影響を与えません。^{[ 4 ]}^：第11章

電位低減方法

ポテンシャル低減法の場合、問題は円錐形で表されます: ^{[ 3 ]}^{: Sec.5}

{b+L} ∩ Kにおいてc ^Tx st x を最小化する、

ここで、bは R ⁿのベクトル、L はR ⁿの線形部分空間（したがって、b + Lはアフィン平面）、Kは内部が空でない閉じた尖った凸錐である。すべての凸プログラムは円錐形式に変換できる。ポテンシャル縮小法（具体的には、カルマルカーのアルゴリズムを凸プログラミングに拡張したもの）を使用するには、次の仮定が必要である。^[³^]^：^第6節

A. 実行可能集合{b+L} ∩ Kは有界であり、円錐Kの内部と交差する。
B. 我々は、厳密に実行可能な解x ^、すなわちKの内部の実行可能な解を事前に与えられている。
C. 問題の最適目的値 c* は事前にわかっている。
D.円錐Kに対して、 M対数的に均質な自己一致バリアFが与えられます。

仮定A、B、Dは、ほとんどの内点法で必要となる。仮定Cはカルマルカーの手法に特有のものであり、「スライディング目的値」を用いることで緩和できる。さらに、プログラムをカルマルカー形式に簡略化することも可能である。

M ∩ Kにおいてs ^Tx st xを最小化し、e ^Tx = 1 とする。

ここで、MはR ⁿにおけるの線形部分空間であり、最適目的値は0である。この方法は、以下のスカラーポテンシャル関数に基づいている。

v ( x ) = F ( x ) + M ln( s ^Tx )

ここで、Fは実行可能コーンのM自己一致バリアです。xが厳密に実行可能で、v ( x ) が非常に小さい (-非常に負) 場合、xは近似的に最適であることが証明できます。ポテンシャル低減法の考え方は、各反復でポテンシャルが少なくとも固定定数X (具体的には、X = 1/3 - ln(4/3))だけ低下するようにx を修正することです。これは、 i回の反復後、目的値と最適目的値の差が最大で V * exp(- i X / M ) であることを意味します。ここで、Vはデータ依存定数です。したがって、 ε近似解に必要なニュートンステップ数は最大で $O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1$ 。

パス追跡メソッドでは、式は次のようになります。 $\displaystyle {\sqrt {M}}}$ 理論的にはMの方が優れているが、実際にはカルマルカーの方法の方が目標に向かってより大きなステップを踏むことができるため、理論上の保証よりもはるかに速く収束する可能性がある。

原始双対法

主双対法の考え方は、制約付き非線形最適化に対して容易に実証できる。^{[ 9 ]}^{[ 10 ]}簡単にするために、不等式制約付きの次の非線形最適化問題を考えてみよう。

${\begin{aligned}\operatorname {minimize} \quad &f(x)\\{\text{subject to}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{\text{ for }}i=1,\ldots ,m,\\{\text{where}}\quad &f:\mathbb {R} ^{n}\to \mathbb {R} ,\ c_{i}:\mathbb {R} ^{n}\to \mathbb {R} .\end{aligned}}\quad (1)$

この不等式制約付き最適化問題は、最小値を効率的に求めることができる制約なし目的関数に変換することで解決されます。具体的には、(1)に関連付けられた対数バリア関数は次のようになります。 $B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)$

ここ $\mu$ は小さな正のスカラーで、「バリアパラメータ」と呼ばれることもあります。 $\mu$ 最小値はゼロに収束します $B(x,\mu )$ （１）の解に収束するはずである。

微分可能な関数の勾配 $h:\mathbb {R} ^{n}\to \mathbb {R}$ と表記される $\nabla h$ 障壁関数の勾配は $\nabla B(x,\mu )=\nabla f(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x).\quad (3)$

元の（「プライマル」）変数に加えて $x$ ラグランジュ乗数に着想を得た双対変数を導入する $\displaystyle \lambda \in \mathbb {R} ^{m}}$ $c_{i}(x)\lambda _{i}=\mu ,\quad \forall i=1,\ldots ,m.\quad (4)$

式（4）は、 KKT条件における「相補的緩み」に似ていることから、「摂動相補性」条件と呼ばれることもある。

私たちはそれらを見つけようとします $(x_{\mu },\lambda _{\mu })$ 障壁関数の勾配がゼロとなる場合。

代入 $1/c_{i}(x)=\lambda _{i}/\mu$ （4）を（3）に代入すると、勾配の式が得られる。 $\nabla B(x_{\mu },\lambda _{\mu })=\nabla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)$ 行列 $J$ は制約条件のヤコビアンです。 $c(x)$ 。

（５）の背後にある直観は、 $f(x)$ 制約の勾配によって張られる部分空間内に存在するはずです。小さな「摂動された相補性」 $\mu$ （４）は、解が境界付近にあるべきであるという条件と理解できる。 $c_{i}(x)=0$ あるいは、勾配の投影 $\nabla f$ 制約コンポーネントについて $c_{i}(x)$ 正常値はほぼゼロであるべきだ。

させて $(p_{x},p_{\lambda })$ 反復更新のための探索方向とする $(x,\lambda )$ （4）と（5）にニュートン法を適用すると、次の式が得られます。 $(p_{x},p_{\lambda })$ : ${\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-\nabla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}},$

どこ $H$ はヘッセ行列です $B(x,\mu )$ 、 $\operatorname {diag} (\lambda )$ は対角行列である $\lambda$ 、そして $\operatorname {diag} (c(x))$ は対角行列です $c(x)$ 。

（１）と（４）の条件により

\lambda \geq 0

各段階で実施する必要があります。これは適切な選択を行うことで実現できます。 $\alpha$ :

(x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).

内点法を用いたxの反復軌跡。

内点法で解ける凸計画問題の種類

以下に、内点法によって効率的に解ける凸計画問題の特殊なケースをいくつか示す。^{[ 3 ]}^：第10節

線形計画法

次の形式の線形計画問題を考えてみましょう。 ${\begin{aligned}\operatorname {minimize} \quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b.\end{aligned}}.$ バリアを使用してパス追跡法を適用できます $b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x).$ 機能 $b$ これは、パラメータM = m (制約の数)と自己整合的です。したがって、パス追跡法に必要なニュートンステップ数は O( mn ² ) であり、全体の実行時間複雑度は O( m ^3/2n ² ) です。

二次制約付き二次計画問題

次のような形式の二次制約付き二次計画問題が与えられた場合： ${\begin{aligned}\operatorname {minimize} \quad &d^{\top }x\\{\text{subject to}}\quad &f_{j}(x):=x^{\top }A_{j}x+b_{j}^{\top }x+c_{j}\leq 0\quad {\text{ for all }}j=1,\dots ,m,\end{aligned}}$ ここで、すべての行列A _jは正定値半行列です。バリアを使用してパス追跡法を適用できます。 $b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).$ 機能 $b$ は、パラメータM = mを持つ自己整合バリアです。ニュートン複雑度は O( (m+n)n ² ) であり、総実行時間複雑度は O( m ^1/2 (m+n) n ² ) です。

L _pノルム近似

次のような問題を考えてみましょう。 ${\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{\top }x|_{p}\end{aligned}},$ それぞれ $u_{j}$ はベクトルで、各 $v_{j}$ はスカラーであり、 $|\cdot |_{p}$ はL _pノルムで、 $1<p<\infty .$ 標準形式に変換した後、パラメータM = 4 mの自己一致バリアを使用したパス追跡法を適用できます。ニュートン複雑度は O( (m+n)n ² ) であり、総実行時間複雑度は O( m ^1/2 (m+n) n ² ) です。

幾何プログラム

問題を考察する

${\begin{aligned}\operatorname {minimize} \quad &f_{0}(x):=\sum _{i=1}^{k}c_{i0}\exp(a_{i}^{\top }x)\\{\text{subject to}}\quad &f_{j}(x):=\sum _{i=1}^{k}c_{ij}\exp(a_{i}^{\top }x)\leq d_{j}\quad {\text{ for all }}j=1,\dots ,m.\end{aligned}}$

パラメータ 2 k + mを持つ自己整合バリアが存在する。パス追跡法のニュートン複雑度は O( mk ² + k ³ + n ³ ) であり、全体の複雑度は O(( k+m ) ^1/2 [ mk ² + k ³ + n ³ ]) である。

半確定プログラム

内点法は半正定値計画問題を解くために使用できる。^{[ 3 ]}^：第11節

参考文献

↑ Dikin, II (1967). "線形計画問題と二次計画問題の反復解法" . Dokl. Akad. Nauk SSSR . 174 (1): 747– 748. Zbl 0189.19504 .
↑ Karmarkar, N. (1984). "線形計画法のための新しい多項式時間アルゴリズム" (PDF) .第16回ACM理論計算シンポジウム（STOC '84）論文集. p. 302. doi : 10.1145/800057.808695 . ISBN 0-89791-133-42013年12月28日にオリジナル（PDF）からアーカイブされました。
1 2 3 4 5 6 7 8 9 10 11 12 13 Arkadi Nemirovsky (2004).凸計画法における内点多項式時間法。
1 2 3 Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization . Cambridge: Cambridge University Press . ISBN 978-0-521-83378-3MR 2061575 .
↑ Wright, Margaret H. (2004). "最適化における内点法の革命：歴史、最近の発展、そして永続的な影響" . Bulletin of the American Mathematical Society . 42 : 39– 57. doi : 10.1090/S0273-0979-04-01040-7 . MR 2115066 .
↑ポトラ、フロリアン A.、スティーブン J. ライト (2000)。「内点法」。Journal of Computational and Applied Mathematics。124 ( 1–2 ): 281–302。Bibcode : 2000JCoAM.124..281P。doi : 10.1016/S0377-0427(00)00433-7。
1 2 Renegar, James (1988 年 1 月 1 日). 「ニュートン法に基づく線形計画法のための多項式時間アルゴリズム」 . Mathematical Programming . 40 (1): 59–93 . doi : 10.1007/BF01580724 . ISSN 1436-4646 .
1 2 Gonzaga, Clovis C. (1989), "線形計画問題をO(n3L)演算で解くアルゴリズム" , Megiddo, Nimrod (編), Progress in Mathematical Programming: Interior-Point and Related Methods , New York, NY: Springer, pp. 1–28 , doi : 10.1007/978-1-4613-9617-8_1 , ISBN 978-1-4613-9617-82023年11月22日取得
↑ Mehrotra, Sanjay (1992). "On the Implementation of a Primal-Dual Interior Point Method". SIAM Journal on Optimization . 2 (4): 575–601 . doi : 10.1137/0802028 .
↑ライト、スティーブン (1997).原始双対内点法. フィラデルフィア、ペンシルベニア州: SIAM. ISBN 978-0-89871-382-4。

Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects . Universitext (1997年フランス語版の翻訳版、第2版改訂版 ). Berlin: Springer-Verlag. pp. xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 978-3-540-35445-1MR 2265882 .
ノセダル、ホルヘ；スティーブン・ライト（1999）。数値最適化。ニューヨーク、NY：スプリンガー。ISBN 978-0-387-98793-4。
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「第 10.11 節線形計画法: 内点法」 . Numerical Recipes: The Art of Scientific Computing (第 3 版). ニューヨーク: Cambridge University Press. ISBN 978-0-521-88068-8. Archived from the original on 11 August 2011. Retrieved 12 August 2011.

[1] Dikin, II (1967). "線形計画問題と二次計画問題の反復解法" . Dokl. Akad. Nauk SSSR . 174 (1): 747– 748. Zbl 0189.19504 .

[2] Karmarkar, N. (1984). "線形計画法のための新しい多項式時間アルゴリズム" (PDF) .第16回ACM理論計算シンポジウム（STOC '84）論文集. p. 302. doi : 10.1145/800057.808695 . ISBN 0-89791-133-42013年12月28日にオリジナル（PDF）からアーカイブされました。

[:0-3] 1 2 3 4 5 6 7 8 9 10 11 12 13 Arkadi Nemirovsky (2004).凸計画法における内点多項式時間法。

[:3-4] 1 2 3 Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization . Cambridge: Cambridge University Press . ISBN 978-0-521-83378-3MR 2061575 .

[5] Wright, Margaret H. (2004). "最適化における内点法の革命：歴史、最近の発展、そして永続的な影響" . Bulletin of the American Mathematical Society . 42 : 39– 57. doi : 10.1090/S0273-0979-04-01040-7 . MR 2115066 .

[6] ポトラ、フロリアン A.、スティーブン J. ライト (2000)。「内点法」。Journal of Computational and Applied Mathematics。124 ( 1–2 ): 281–302。Bibcode : 2000JCoAM.124..281P。doi : 10.1016/S0377-0427(00)00433-7。

[:1-7] 1 2 Renegar, James (1988 年 1 月 1 日). 「ニュートン法に基づく線形計画法のための多項式時間アルゴリズム」 . Mathematical Programming . 40 (1): 59–93 . doi : 10.1007/BF01580724 . ISSN 1436-4646 .

[:2-8] 1 2 Gonzaga, Clovis C. (1989), "線形計画問題をO(n3L)演算で解くアルゴリズム" , Megiddo, Nimrod (編), Progress in Mathematical Programming: Interior-Point and Related Methods , New York, NY: Springer, pp. 1–28 , doi : 10.1007/978-1-4613-9617-8_1 , ISBN 978-1-4613-9617-82023年11月22日取得

[9] Mehrotra, Sanjay (1992). "On the Implementation of a Primal-Dual Interior Point Method". SIAM Journal on Optimization . 2 (4): 575–601 . doi : 10.1137/0802028 .

[10] ライト、スティーブン (1997).原始双対内点法. フィラデルフィア、ペンシルベニア州: SIAM. ISBN 978-0-89871-382-4。

[ 1 ]

[

[ 5 ]

[ 6 ]

[ 9 ]

[ 10 ]

内点法

歴史

定義

種類

経路追跡法

アイデア