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

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

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

minxf(x)

条件

ci(x)≤0,  i=1…mceqi(x)=0,  ​i=m+1…mtA⋅x≤bAeq⋅x=beqlb≤x≤ub,

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

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

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

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

Θ(x,λ,s,ρ)=f(x)−∑i=1mλisilog(si−ci(x))+∑i=m+1mtλiceqi(x)+ρ2∑i=m+1mtceqi(x)2,

ここで、

  • ベクトルλの成分λiは非負であり、ラグランジュ乗数推定値として知られている。

  • ベクトルsの要素siは非負のシフトである

  • ρ は正のペナルティパラメーターです。

アルゴリズムは、ペナルティパラメーター(InitialPenalty) の初期値を使用して開始されます。

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

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

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

参照

[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.

参考

トピック