非線形計画法

数学において、非線形計画法（NLP）、別名非線形最適化^{[ 1 ]}は、制約条件の一部が線形等式でなかったり、目的関数が線形関数でなかったりする最適化問題を解くプロセスです。最適化問題とは、未知の実変数の集合に対する目的関数の極値（最大値、最小値、または停留点）を計算する問題であり、制約条件と呼ばれる一連の等式と不等式の充足が条件となっています。これは、非線形な問題を扱う数学的最適化のサブ分野です。

定義と考察

n 、m、pを正の整数とする。XをR ⁿの部分集合(通常はボックス制約付き) とし、f、g _i、h _{j を}{ 1 , ..., m } の各iと{ 1 , ..., p } の各 j に対してX上の実数値関数とし、f、g i 、_h jの_うち少なくとも 1 つは非線形関数とする。

非線形計画問題は、次の形式の最適化問題である。

{\begin{aligned}{\text{minimize }}&f(x)\\{\text{subject to }}&g_{i}(x)\leq 0{\text{ for each }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ for each }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}

制約条件によっては、いくつかの可能性が考えられます。

実行可能な問題とは、すべての制約を満たす選択変数の値の組み合わせが少なくとも1つ存在する問題のことである。
実行不可能な問題とは、選択変数の値のどの組み合わせもすべての制約を満たさない問題のことです。つまり、制約が互いに矛盾しており、解が存在しないということです。実行可能な集合は空集合です。
非有界問題とは、目的関数を任意の有限値よりも優れた値にすることができる実行可能な問題のことである。したがって、最適解は存在しない。なぜなら、常に任意の提案された解よりも優れた目的関数値を与える実行可能な解が存在するからである。

ほとんどの現実的な応用例では、実行可能な問題が扱われ、実行不可能な問題や境界のない問題は、基礎となるモデルの欠陥とみなされます。場合によっては、実行不可能な問題は、実行可能性違反の合計を最小化することによって対処されます。

非線形計画法の特殊なケースには、専用の解法が存在する。

目的関数が凹関数（最大化問題）または凸関数（最小化問題）であり、制約条件集合が凸関数である場合、そのプログラムは凸問題と呼ばれ、ほとんどの場合、凸最適化の一般的な手法を使用できます。
目的関数が二次関数で制約条件が線形である場合、二次計画法が用いられる。
目的関数が凹関数と凸関数の比であり（最大化の場合）、制約条件が凸である場合、分数計画法の手法を用いて問題を凸最適化問題に変換することができる。

適用範囲

典型的な非凸問題は、さまざまな接続性や容量制約を持つ、規模の経済性を示す輸送手段のセットから選択して輸送コストを最適化する問題である。例えば、パイプライン、鉄道タンカー、道路タンカー、河川バージ、沿岸タンカーのいずれか、またはそれらの組み合わせによる石油製品輸送が挙げられる。経済的なバッチサイズのため、コスト関数には滑らかな変化に加えて不連続性が含まれる場合がある。

実験科学では、単純なデータ解析（例えば、位置と形状は既知だが大きさが未知のピークの和でスペクトルをフィッティングするなど）は線形手法で行うことができますが、一般的にこれらの問題は非線形です。通常、研究対象システムの理論モデル（可変パラメータを含む）と、実験モデル（または複数の実験モデル）があり、後者にも未知のパラメータが存在する場合があります。そして、数値的に最適なフィッティングを見つけようとします。この場合、最適なフィッティング自体だけでなく、結果の精度も測定したい場合が多くあります。

一般的な非線形計画問題を解くための方法

分析方法

微分可能性と制約条件の下では、カルーシュ・クーン・タッカー（KKT）条件は、解が最適となるための必要条件を提供する。一部の関数が微分不可能な場合は、カルーシュ・クーン・タッカー（KKT）条件の劣微分バージョンが利用可能である。^[²^]

凸性の下では、KKT条件はグローバル最適解に対して十分条件となる。凸性がない場合、これらの条件はローカル最適解に対してのみ十分条件となる。場合によっては、ローカル最適解の数が少なく、それらをすべて解析的に見つけて、目的関数値が最小となるものを見つけることができる。^{[ 3 ]}

数値計算法

現実的なケースのほとんどでは、KKT条件を解析的に解くことは非常に困難であるため、数値的手法を用いて問題を解く。これらの手法は反復的であり、初期点から始めて、何らかの更新規則を用いて最適点により近いと考えられる点へと進んでいく。更新規則には3種類ある。^{[ 3 ]}^{： 5.1.2}

ゼロ次ルーチン - 現在の時点における目的関数と制約関数の値のみを使用します。
一次ルーチン -これらの関数の勾配の値も使用します。
二次ルーチンでは、これらの関数のヘッセ行列の値も使用します。

3次ルーチン（およびそれ以上の高次ルーチン）は理論的には可能であるが、計算負荷が高く、理論的な利点も少ないため、実際には使用されていない。

枝と境界

別の方法として、分岐限定法を用いる方法があります。この方法では、プログラムをサブクラスに分割し、各サブクラス内で凸近似（最小化問題）または線形近似を用いて、各サブクラス内の全体コストの下限を求めます。分割を繰り返すと、ある時点で、近似解の下限値に等しいコストを持つ実際の解が得られます。この解は最適解ですが、一意ではない可能性があります。また、最良の解が、見つかった最良の点から許容範囲内にあることを保証することで、アルゴリズムを早期に停止することもできます。このような点はε最適点と呼ばれます。ε最適点への停止は、通常、有限終了を保証するために必要です。これは、大規模で困難な問題や、適切な信頼性推定によって不確実性を推定できる不確実性のコストや値を持つ問題に特に有効です。

実装

オープンソースのものを含め、非線形計画法ソルバーは数多く存在する。

ALGLIB （C++、C#、Java、Python API）は、複数の一次非線形計画法ソルバーと導関数不要非線形計画法ソルバーを実装しています。
NLopt（C/C++実装、Julia、Python、R、MATLAB/Octaveなど多数のインターフェースを備える）には、さまざまな非線形計画ソルバーが含まれています。
SciPy（科学計算用Pythonの事実上の標準）には、scipy.optimizeソルバーがあり、これにはいくつかの非線形計画法アルゴリズム（ゼロ次、一次、二次のもの）が含まれています。
IPOPT (C++ implementation, with numerous interfaces including C, Fortran, Java, AMPL, R, Python, etc.) is an interior point method solver (zero-order, and optionally first order and second order derivatives).

Proprietary solvers include SNOPT (written in Fortran, with interfaces to C, C++, Python and MATLAB).

Numerical Examples

2-dimensional example

A simple problem (shown in the diagram) can be defined by the constraints ${\begin{aligned}x_{1}&\geq 0\\x_{2}&\geq 0\\x_{1}^{2}+x_{2}^{2}&\geq 1\\x_{1}^{2}+x_{2}^{2}&\leq 2\end{aligned}}$ with an objective function to be maximized $f(\mathbf {x} )=x_{1}+x_{2}$ where $x = (x 1, x 2)$ .

3-dimensional example

Another simple problem (see diagram) can be defined by the constraints ${\begin{aligned}x_{1}^{2}-x_{2}^{2}+x_{3}^{2}&\leq 2\\x_{1}^{2}+x_{2}^{2}+x_{3}^{2}&\leq 10\end{aligned}}$ with an objective function to be maximized $f(\mathbf {x} )=x_{1}x_{2}+x_{2}x_{3}$ where $x = (x 1, x 2, x 3)$ .

References

↑Richard W. Cottle, Mukund N. Thapa. Linear and Nonlinear Optimization. Springer New York,2017. https://www.springerprofessional.de/linear-and-nonlinear-optimization/12354648
↑Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0691119151. MR 2199043.
12Nemirovsky and Ben-Tal (2023). "Optimization III: Convex Optimization"(PDF).

外部リンク

数理計画法用語集

[1] Richard W. Cottle, Mukund N. Thapa. Linear and Nonlinear Optimization. Springer New York,2017. https://www.springerprofessional.de/linear-and-nonlinear-optimization/12354648

[2] Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0691119151. MR 2199043.

[:0-3] 12Nemirovsky and Ben-Tal (2023). "Optimization III: Convex Optimization"(PDF).

[ 1 ]

[

非線形計画法

定義と考察

適用範囲

一般的な非線形計画問題を解くための方法

分析方法

数値計算法

枝と境界

実装

Numerical Examples

2-dimensional example

3-dimensional example

See also

References

Further reading

外部リンク

関連するトピック

数学

線形等式

線形関数でなかったりする

最適化問題