パターン探索のための非線形制約ソルバーアルゴリズム

このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

パターン検索アルゴリズムは、拡張ラグランジュパターン検索 (ALPS) アルゴリズムを使用して非線形制約問題を解決します。ALPSアルゴリズムによって解決される最適化問題は

$\min_{x} f (x)$

条件

$\begin{matrix} c_{i} (x) \leq 0, i = 1 \dots m \\ c e q_{i} (x) = 0, i = m + 1 \dots m t \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b, \end{matrix}$

ここで、c(x) は非線形不等式制約を表し、ceq(x) は等式制約を表し、m は非線形不等式制約の数、mt は非線形制約の合計数を表します。

ALPS アルゴリズムは、非線形制約、線形制約、および境界を使用して非線形最適化問題を解決しようとします。このアプローチでは、境界と線形制約は非線形制約とは別に処理されます。ラグランジアンおよびペナルティパラメータを使用して、目的関数と非線形制約関数を組み合わせることによってサブ問題が定式化されます。このような一連の最適化問題は、線形制約と境界が満たされるようにパターン検索アルゴリズムを使用して近似的に最小化されます。

各サブ問題の解決は 1 回の反復を表します。したがって、非線形制約を使用する場合、反復ごとの関数評価の回数は、そうでない場合よりもはるかに多くなります。

部分問題の定式化は次のように定義される。

$Θ (x, λ, s, ρ) = f (x) - \sum_{i = 1}^{m} λ_{i} s_{i} \log (s_{i} - c_{i} (x)) + \sum_{i = m + 1}^{m t} λ_{i} c e q_{i} (x) + \frac{ρ}{2} \sum_{i = m + 1}^{m t} c e q_{i} {(x)}^{2},$

ここで、

ベクトルλの成分λ_iは非負であり、ラグランジュ乗数推定値として知られている。
ベクトルsの要素s_iは非負のシフトである
ρ は正のペナルティパラメータです。

アルゴリズムは、ペナルティパラメータ (InitialPenalty) の初期値を使用することから始まります。

パターン検索は、それぞれが元の問題の近似値であるサブ問題のシーケンスを最小化します。各サブ問題には、λ、s、ρ の固定値があります。サブ問題が必要な精度まで最小化され、実現可能性条件を満たすと、ラグランジアン推定値が更新されます。それ以外の場合、ペナルティパラメータはペナルティ係数 (PenaltyFactor) によって増加されます。これにより、新しいサブ問題の定式化と最小化問題が生じます。これらの手順は、停止基準が満たされるまで繰り返されます。

アルゴリズムの詳細な説明については、次の参考文献を参照してください。

参照

[1] Kolda, Tamara G., Robert Michael Lewis, and Virginia Torczon. “A generating set direct search augmented Lagrangian algorithm for optimization with a combination of general and linear constraints.” Technical Report SAND2006-5315, Sandia National Laboratories, August 2006.

[2] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. “A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds,” SIAM Journal on Numerical Analysis, Volume 28, Number 2, pages 545–572, 1991.

[3] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. “A Globally Convergent Augmented Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds,” Mathematics of Computation, Volume 66, Number 217, pages 261–288, 1997.

パターン探索のための非線形制約ソルバーアルゴリズム

参照

関連するトピック