43.1 Introduction to cobyla

fmin_cobylaは Powell[1][2][3]による Fortran制約最適化ルーチンCOBYLAの(f2clによる)Common Lisp翻訳です。

COBYLAは X上の形式g(X) >= 0のM個の不等式制約を条件として目的函数F(X)を最小化します。 ここで、XはN個の成分を持つ変数のベクトルです。

等式制約g(X)=0は、 よく、不等式制約の組g(X)>=0と-g(X)>= 0で実装することができます。 MaximaのCOBYLAインターフェースは等式制約を受け入れ、 内部的に等式制約を不等式制約の組に変換します。

アルゴリズムは目的函数や制約函数の線形近似を用います。 変数空間内のN+1点での線形補間で形成された近似です。 補間点は単体の頂点としてみなされます。 パラメータRHOは単体のサイズを制御し、 RHOBEGからEHOENDに自動的に減らされます。 それぞれのRHOで、 サブルーチンは 現在のサイズにとって変数の良いベクトルを達成しようとし、 そして、RHOは値RHOENDに達するまで減らされます。 それゆえに、RHOBEGとRHOENDはそれぞれ、変数への合理的な初期変化と 変数に要求される精度に設定されるべきですが、 この精度は、保証はないので、実験の対象として見るべきです。 ルーチンは、 変数の変化を計算する時、 制約を単一のペナルティ函数にひとまとめにせずに、 制約それぞれを個別に扱います。 サブルーチン名は the phrase Constrained Optimization BY Linear Approximations(線形近似による位相制約下最適化)に由来します。

参考文献:

[1] Fortran Codeはhttp://plato.asu.edu/sub/nlores.html#generalから

[2] M. J. D. Powell, "A direct search optimization method that models the objective and constraint functions by linear interpolation," in Advances in Optimization and Numerical Analysis, eds. S. Gomez and J.-P. Hennart (Kluwer Academic: Dordrecht, 1994), p. 51-67.

[3] M. J. D. Powell, "Direct search algorithms for optimization calculations," Acta Numerica 7, 287-336 (1998). Also available as University of Cambridge, Department of Applied Mathematics and Theoretical Physics, Numerical Analysis Group, Report NA1998/04 from http://www.damtp.cam.ac.uk/user/na/reports.html