定義と考察 n 、 m 、p を正の整数とする。Xを R n の部分集合(通常はボックス制約付き) とし、f 、g i 、h j を { 1 , ..., m } の各 iと { 1 , ..., p } の各 j に対してX 上 の実 数値関数と し 、f 、g i 、 h の うち
非線形計画問題は、次の形式の最適化問題である。
最小限に抑える f （ x ） 対象 g 私 （ x ） ≤ 0 各 私 ∈ { 1 、 … 、 m } h j （ x ） = 0 各 j ∈ { 1 、 … 、 p } x ∈ X 。 {\displaystyle {\begin{aligned}{\text{最小化}}&f(x)\\{\text{制約条件}}&g_{i}(x)\leq 0{\text{各}}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{各}}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}} 制約条件によっては、いくつかの可能性が考えられます。
実行可能な 問題とは、すべての制約を満たす選択変数の値の組み合わせが少なくとも1つ存在する問題のことである。実行不可能な 問題とは、選択変数の値のどの組み合わせもすべての制約を満たさない問題のことです。つまり、制約が互いに矛盾しており、解が存在しないということです。実行可能な集合は空集合 です。非有界 問題とは、目的関数を任意の有限値よりも優れた値にすることができる実行可能な問題のことである。したがって、最適解は存在しない。なぜなら、常に任意の提案された解よりも優れた目的関数値を与える実行可能な解が存在するからである。ほとんどの現実的な応用例では、実行可能な問題が扱われ、実行不可能な問題や境界のない問題は、基礎となるモデルの欠陥とみなされます。場合によっては、実行不可能な問題は、実行可能性違反の合計を最小化することによって対処されます。
非線形計画法の特殊なケースには、専用の解法が存在する。
適用範囲 典型的な非凸問題は、さまざまな接続性や容量制約を持つ、 規模の経済性 を示す輸送手段のセットから選択して輸送コストを最適化する問題である。例えば、パイプライン、鉄道タンカー、道路タンカー、河川バージ、沿岸タンカーのいずれか、またはそれらの組み合わせによる石油製品輸送が挙げられる。経済的なバッチサイズのため、コスト関数には滑らかな変化に加えて不連続性が含まれる場合がある。
実験科学では、単純なデータ解析（例えば、位置と形状は既知だが大きさが未知のピークの和でスペクトルをフィッティングするなど）は線形手法で行うことができますが、一般的にこれらの問題は非線形です。通常、研究対象システムの理論モデル（可変パラメータを含む）と、実験モデル（または複数の実験モデル）があり、後者にも未知のパラメータが存在する場合があります。そして、数値的に最適なフィッティングを見つけようとします。この場合、最適なフィッティング自体だけでなく、結果の精度も測定したい場合が多くあります。
一般的な非線形計画問題を解くための方法
数値計算法 現実的なケースのほとんどでは、KKT条件を解析的に解くことは非常に困難であるため、数値的手法 を用いて問題を解く。これらの手法は反復的であり、初期点から始めて、何らかの更新規則を用いて最適点により近いと考えられる点へと進んでいく。更新規則には3種類ある。[ 3 ] ：
ゼロ次ルーチン - 現在の時点における目的関数と制約関数の値のみを使用します。 一次ルーチン -これらの関数の勾配 二次ルーチンでは、これらの関数のヘッセ行列 3次ルーチン（およびそれ以上の高次ルーチン）は理論的には可能であるが、計算負荷が高く、理論的な利点も少ないため、実際には使用されていない。
枝と境界 別の方法として、分岐限定 法を用いる方法があります。この方法では、プログラムをサブクラスに分割し、各サブクラス内で凸近似（最小化問題）または線形近似を用いて、各サブクラス内の全体コストの下限を求めます。分割を繰り返すと、ある時点で、近似解の下限値に等しいコストを持つ実際の解が得られます。この解は最適解ですが、一意ではない可能性があります。また、最良の解が、見つかった最良の点から許容範囲内にあることを保証することで、アルゴリズムを早期に停止することもできます。このような点はε最適点と呼ばれます。ε最適点への停止は、通常、有限終了を保証するために必要です。これは、大規模で困難な問題や、適切な信頼性推定によって不確実性を推定できる不確実性のコストや値を持つ問題に特に有効です。
実装 オープンソースのものを含め、非線形計画法ソルバーは数多く存在する。
ALGLIB （C++、C#、Java、Python API）は、複数の一次非線形計画法ソルバーと導関数不要非線形計画法ソルバーを実装しています。NLopt（C/C++実装、Julia、Python、R、MATLAB/Octaveなど多数のインターフェースを備える）には、さまざまな非線形計画ソルバーが含まれています。 SciPy （科学計算用Pythonの事実上の標準）には、scipy.optimizeソルバーがあり、これにはいくつかの非線形計画法アルゴリズム（ゼロ次、一次、二次のもの）が含まれています。IPOPT （C++による実装で、C、Fortran、Java、AMPL、R、Pythonなど多数のインターフェースを備えている）は、内点法 ソルバー（ゼロ次、およびオプションで1次および2次導関数）です。独自のソルバーとしては、SNOPT （Fortranで記述され、C、C++、Python、MATLABとのインターフェースを備えている）などがある。
数値例
2次元の例 青色の領域は実行可能領域 です。直線と実行可能領域との接点 が解を表します。この直線は、目的関数の与えられた値に対応する最適な等高線（軌跡）です。 （図に示す）単純な問題は、制約によって定義できる。 x 1 ≥ 0 x 2 ≥ 0 x 1 2 + x 2 2 ≥ 1 x 1 2 + x 2 2 ≤ 2 {\displaystyle {\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}}} f （ x ） = x 1 + x 2 {\displaystyle f(\mathbf {x} )=x_{1}+x_{2}} x = ( x 1 , x 2 )
3次元の例 上面と中央の制約空間との接線が解を表す。 もう一つの単純な問題（図を参照）は、制約によって定義できます。 x 1 2 − x 2 2 + x 3 2 ≤ 2 x 1 2 + x 2 2 + x 3 2 ≤ 10 {\displaystyle {\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}}} f （ x ） = x 1 x 2 + x 2 x 3 {\displaystyle f(\mathbf {x} )=x_{1}x_{2}+x_{2}x_{3}} x = ( x 1 , x 2 , x 3 )
参考文献 ↑ Richard W. Cottle、Mukund N. Thapa。『線形および非線形最適化』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 . 1 2 Nemirovsky and Ben-Tal (2023). "Optimization III: Convex Optimization" (PDF) .
さらに読む アヴリエル、モルデカイ（2003）。非線形計画法：分析と手法。 ドーバー出版。ISBN 0-486-43227-0 。 Bazaraa, Mokhtar S. および Shetty, CM (1979).非線形計画法。理論とアルゴリズム。John Wiley & Sons. ISBN 0-471-78610-1 。 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 3-540-35445-X MR 2265882 . Luenberger, David G. ; Ye, Yinyu (2008).線形計画法と非線形計画法 . International Series in Operations Research & Management Science. Vol. 116 (Third ed.). New York: Springer. pp. xiv+546. ISBN 978-0-387-74502-2 . MR 2423726 . ノセダル、ホルヘ、ライト、スティーブン J. (1999).数値最適化. スプリンガー. ISBN 0-387-98793-2 。 ヤン・ブリンクハイス 、ウラジミール・ティホミロフ著『最適化：洞察と応用』 、2005年、プリンストン大学出版局
