内点法

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

• 理論的には、その実行時間は多項式です。これは、最悪の場合に指数関数的な実行時間を持つ単体法とは対照的です。
• 実際には、これらの方法は単体法と同じくらい速く実行されます。これは、理論上は多項式実行時間であるものの、実際には非常に遅い楕円体法とは対照的です。

実行可能領域の境界を横断する単体法や、実行可能領域の外側を囲む楕円体法とは対照的に、IPM は実行可能領域の内部を横断することで最適な解に到達します(これが名前の由来です)。

内点法は、1967 年にソ連の数学者 II Dikin によって発見されました。 ^[1]この方法は、1980 年代半ばに米国で再発明されました。1984 年に、Narendra Karmarkar は、Karmarkar アルゴリズムと呼ばれる線形計画法を開発しました。 ^[2]これは、証明可能な多項式時間 ( Lビット数の演算、nは変数と定数の数) で実行され、実際に非常に効率的でもあります。Karmarkar の論文は、内点法への関心の高まりを生み出しました。2 年後、James Renegar は、実行時間 の最初のパス追跡内点法を発明しました。この方法は、凸集合をエンコードするために使用される自己一致バリア関数に基づいて、線形最適化問題から凸最適化問題に拡張されました。^[3]${\displaystyle O(n^{3.5}L)}$${\displaystyle O(n^{3}L)}$

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

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

主双対経路追従内点法のクラスは最も成功していると考えられています。Mehrotraの予測子修正子アルゴリズムは、このクラスの方法のほとんどの実装の基礎を提供します。^[6]

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

ポリ(問題サイズ) * log( V / ε )、

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

内点法の種類は次のとおりです。

• 潜在的な削減方法: Karmarkar のアルゴリズムが最初のものでした。
• 経路追跡法： James Renegar ^[7]とClovis Gonzaga ^[8]のアルゴリズムが最初のものでした。
• プライマル-デュアル法。

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

( P _t ) t * 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 )を解くための開始点として使用できることに注意してください。

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

レネガー^[7]とゴンザガ^[8]は、経路追跡法の特定のインスタンスが多時間であることを証明した。

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

彼らは、この場合、差x _i - x *( t _i ) は最大でも 0.01 のままであり、 f( x _i ) - f* は最大でも 2* m / t _iであることを証明しました。したがって、解の精度は 1/ t _iに比例するため、精度桁を 1 つ追加するには、t _{i を}2 (またはその他の定数係数) 倍にするだけで十分であり、これには O(sqrt( m )) ニュートン ステップが必要です。各ニュートン ステップには O( mn ² ) 回の演算が必要なので、精度桁の合計複雑度は O( m ^3/2 n ² ) 回の演算です。

ユーリ・ネステロフは、この考え方を線形計画から非線形計画にまで拡張した。彼は、上記の証明で使用した対数障壁の主な特性は、有限の障壁パラメータと自己一致していることだと指摘した。したがって、実行可能領域に適した自己一致障壁関数を見つけることができれば、他の多くのクラスの凸計画もパス追跡法を使用して多時間で解くことができる。^{[3] : Sec.1}

「標準形式」の凸最適化問題 (P) が与えられます。

Gのc ^T x st x を最小化する、

ここで、Gは凸かつ閉じている。また、Gは有界であると仮定することもできる（十分に大きいRに対して制約| x |≤ Rを追加することで簡単に有界にすることができる）。^{[3] ：Sec.4}

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

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

各t _iについて、 x _iで表されるf _tiのおおよその最小値を見つけます。おおよその最小値は、次の「近似条件」を満たすように選択されます (ここで、Lはパス許容値です)。

${\displaystyle {\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 +1}を見つけるには、まずx _iから始めて減衰ニュートン法を適用します。この方法をいくつかのステップで適用し、上記の「近似関係」を満たします。この関係を満たす最初の点はx _{i +1}で示されます。^{[3] : Sec.4}

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

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

をとると 、 x _iからx _{i +1}まで進むのに必要なニュートンステップの数は最大で固定数であり、これはrとLのみに依存します。特に、 ε近似解（つまり、c ^T x - c* ≤ εとなるG内のx を見つける）を見つけるために必要なニュートンステップの総数は最大で次のようになります。^{[3] : Thm.4.4.1}${\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}$

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

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

${\displaystyle 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のみに依存し、 はGの内部にある点である。全体として、 ε近似解を求めるニュートン複雑度 は最大で${\displaystyle {\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x}$${\displaystyle {\bar {x}}}$

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

各ニュートンステップではO( n3 )^回の算術演算が必要です。

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

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

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

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

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

{b + L } ∩KにおいてcTxstx^を最小化する、

ここで、bは R ⁿのベクトル、L はR ⁿの線型部分空間（したがってb + Lはアフィン平面）、K は内部が空でない閉じた凸錐である。すべての凸計画法は円錐形式に変換できる。ポテンシャル削減法（具体的には、Karmarkar のアルゴリズムの凸計画法への拡張）を使用するには、次の仮定が必要である：^{[3] ：Sec.6}

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

仮定 A、B、D は、ほとんどの内点法で必要です。仮定 C は Karmarkar のアプローチに特有のもので、「スライディング目的値」を使用することで緩和できます。プログラムをさらにKarmarkar 形式に縮小することも可能です。

M ∩ Kでs ^T x st x を最小化し、e ^T x = 1とする

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

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

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

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

プライマルデュアル法の考え方は、制約付き非線形最適化に対して簡単に実証できます。^{[9] [10]}簡単にするために、不等式制約付きの次の非線形最適化問題を考えてみましょう。

$${\displaystyle {\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)に関連する 対数バリア関数は$${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}$$

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

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

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

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

バリア関数の勾配がゼロになる ものを見つけようとします。${\displaystyle (x_{\mu },\lambda _{\mu })}$

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

(5) の背後にある直感は、 の勾配が制約の勾配によって張られる部分空間内にあるはずであるということです。 が小さい (4) の「摂動相補性」は、解が境界 の近くにあるか、制約成分の法線上の勾配の投影がほぼゼロになるという条件として理解できます。 ${\displaystyle f(x)}$${\displaystyle \mu }$${\displaystyle c_{i}(x)=0}$${\displaystyle \nabla f}$${\displaystyle c_{i}(x)}$

を反復更新するための探索方向とします。ニュートン法を(4)と(5)に適用すると、 の式が得られます。 ${\displaystyle (p_{x},p_{\lambda })}$${\displaystyle (x,\lambda )}$${\displaystyle (p_{x},p_{\lambda })}$$${\displaystyle {\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}},}$$

ここで、は のヘッセ行列、はの対角行列、は の対角行列です。 ${\displaystyle H}$${\displaystyle B(x,\mu )}$${\displaystyle \operatorname {diag} (\lambda )}$${\displaystyle \lambda }$${\displaystyle \operatorname {diag} (c(x))}$${\displaystyle c(x)}$

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

${\displaystyle \lambda \geq 0}$

各ステップで強制する必要があります。これは適切なものを選択することで実行できます。 ${\displaystyle \alpha }$

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

ここでは、内点法によって効率的に解くことができる凸計画の特殊なケースをいくつか挙げる。^{[3] : Sec.10}

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

次のような形式の二次制約二次計画法があるとします。 ここで、すべての行列A _jは半正定値行列です。バリアを持つパス追跡法を適用できます 。関数は、パラメーターM = mを持つ自己一致バリアです。ニュートン複雑度は O( (m+n)n ² ) で、実行時複雑度の合計は O( m ^1/2 (m+n) n ² ) です。 $${\displaystyle {\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}}}$$$${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).}$$${\displaystyle b}$

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

問題を考えてみましょう

$${\displaystyle {\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] : Sec.11}

• アフィンスケーリング
• 拡張ラグランジアン法
• シャンボール・ポックアルゴリズム
• カルーシュ・クーン・タッカー条件
• ペナルティ方式

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). 数値最適化: 理論と実践の側面。Universitext (1997 年フランス語版の翻訳の第 2 版)。ベルリン: Springer -Verlag。pp. xiv+490。doi :10.1007 / 978-3-540-35447-5。ISBN 978-3-540-35445-1. MR  2265882。
• Nocedal, Jorge; Stephen Wright (1999)。数値最適化。ニューヨーク、NY: Springer。ISBN 978-0-387-98793-4。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)。「セクション 10.11. 線形計画法: 内点法」。数値レシピ: 科学計算の技法(第 3 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8. 2011年8月11日時点のオリジナルよりアーカイブ。2011年8月12日閲覧。