トップ > 最適化とは > 非線形計画法

非線形計画法

ここでは数理計画法の中の非線形計画法についてご紹介します。 非線形計画法とは非線形計画問題を解く解法・アルゴリズムを総称したものです。 なお Numerical Optimizer の「フルセット」「NLP(V17 まで)」のモジュールが 非線形計画法のアルゴリズムに対応しています。

非線形計画問題とは

線形計画問題では制約式や目的関数が全て線形の式( 1 次式 )で表すことが できる問題とご説明しました。非線形計画問題は制約式や目的関数が線形でない 任意の連続関数として表現される問題ということになります。例えば sin や cos を 用いたり、変数の 2 乗 3 乗、変数同士の積がそれにあたります。また、 離散変数を含む非線形計画問題のアルゴリズムも研究されており、 Numerical Optimizer にも Global というアドオンで対応していますが、ここでは 離散変数を考慮しない連続変数のみで構成されている問題を考えます。右の図が 2 変数の問題のイメージです。最大化問題ですと、赤い○が最適解の候補になります。

非線形計画問題イメージ

整数変数を含む非線形計画問題や、大域的最適解を求める場合のアルゴリズムは Globalをご覧ください。

アルゴリズムイメージ

我々が実は丸い地球を、普段平らだと思って暮しているように、どんなに折れ 曲がった曲面でも大抵のものは近寄ってみると、平面に見えます。非線形最適 化とは遠目で見ると曲面上のどこかの点を探しているのですが、思いきってあ る点のまわりをぐっとクローズアップすると(線形近似すると)平面に見え てきます。平面としての「見たて」に従えば例えば線形計画法の方法を使って、 解の存在する方角を導くことができます。もちろん平面としての見立ては完全ではない ので、導いた方角はちょっとずれてきますが、大丈夫。ずれが深刻にならない 程度まで進んで、またクローズアップを繰り返せばよいのです。そうしていつ かクローズアップした領域の中に解が含まれるところまで来ればこちらのもの。解の まわりを今度は顕微鏡的に拡大することを繰り返せば、平面としての「見立て」 の精度はどんどん正確になり、好きなだけ精度良く真の解を求めることができ るのです。

非線形計画法で取り扱うことのできる応用問題

Numerical Optimizer におけるアルゴリズムの工夫

クローズアップを繰り返して解にのそばに迫る局面では、できるだけ少ないク ローズアップでおおまかに解のありそうな場所を特定することが必要。そのた めに「メリット関数」という、解への肉迫度合を計測する関数を定義して得ら れる大局的な情報を活用しています。Numerical Optimizer に利用されているアルゴリズムは どこから出発しても必ずいずれかの局所解に辿りつくことができるという理論 的な保証(大域的収束性)を備えたものです。

また、クローズアップした領域に解が入ってからの局面では Numerical Optimizer では解を 素早く収束させるために複数のパラメータを同時かつ動的 に調整します。この調整方法も理論的な保証(超一次収束性)があります。探索方 向を導く部分は線形計画法の内点法と同一ですので、線形計画法の実装で培っ た数値的工夫の積み上げによって高速性と安定性が実現されています。