多目的関数の最適化アルゴリズム
多目的最適化の定義
Optimization Toolbox™ には多目的関数を扱う 2 つのソルバー fgoalattain
と fminimax
があります。
fgoalattain
は、F*i の最適解集合の下で、非線形関数 Fi(x) の集合を減らす問題を扱います。いくつかの関数 Fi(x) があるため、問題を解くのに適しているかどうかが明確でない場合があります。特に、同時にすべての最適解に到達することができない場合がそうです。そのため、この問題は常に well-defined な式に定式化し直されます。"スケール化されていないゴール到達問題" は Fi(x) – F*i の最大値を最小化することです。
スケール化されていない問題に対しては有用な一般化があります。正の重み集合 wi を与えて、"ゴール到達問題" は以下の最大値を最小化する x を見つけます。
(1) この最小化は、c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u などの制約を満たす場合が仮定されています。
すべての重みを 1 (または他の正の定数) に等しくした場合、ゴール到達問題はスケール化されていないゴール到達問題と同じになります。F*i が正であり、wi = F*i としてすべての重みを設定した場合、ゴール到達問題は関数 Fi(x) と最適解 F*i の間の相対差を最小化します。
すなわち、ゴール到達問題は 式 1 式の i を変化させて得られる最大値として定義されたスラック変数 γ を最小化することです。ゴール到達問題を形式的に表すと次のようになります。
F(x) – w·γ ≤ F*, c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u が条件になります。
fminimax
は、以下の制約に従う非線形関数の最大値を最小化する問題を扱います。c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u が条件になります。
明らかにこの問題は、F*i = 0 および wi = 1 としたスケール化されていないゴール到達問題の特殊な場合です。
アルゴリズム
ゴール到達法
このセクションでは Gembicki [3] のゴール到達法について説明します。この手法は目的関数の集合 F(x) = {F1(x),F2(x),...,Fm(x)} に関連した設計ゴールの集合 を使用します。問題の定式化で目的関数は under- または overachieved になるので、初期設計ゴールに対して比較的精度の悪いものになります。ゴールの under-achievement または over-achievement の相対的な度合いは、重み係数のベクトル w = {w1,w2,...,wm} によりコントロールされ、標準の最適化問題として次の式を使って表現されます。
(2) |
よって となります。
wiγ の項はスラック (slackness) を問題に導入するもので、これを設定しないとゴールは厳密な意味で満足させなければならなくなります。設計者は、重みベクトル w を目的関数間で相対的なトレードオフの尺度として使うことができます。たとえば、重みベクトル w を初期ゴール値に設定することは、同じ割合の underachievement または overachievement をもつゴール F* が達成されることを意味します。厳密な制約は特別な重み要素をゼロに設定することで可能になります (たとえば、wi = 0)。ゴール到達法は、設計問題の便利で直感的な解釈を表し、標準の最適化手法を使って解くことができます。制御システム設計分野でのゴール到達法の使用例は Fleming ([10] および [11]) の論文で説明されています。
2 次元の問題に対するゴール到達法が、以下の図のゴール到達法の幾何学的表示に示されています。
図 7-1、ゴール到達法の幾何学的表示
ゴール の指定により、ゴール点 P が定義されます。重みベクトルは P から実行可能関数空間 Λ(γ) までの探索方向を定義します。最適化の間、γ は変化し、これにより実行可能領域のサイズが変化します。制約境界はユニークな解の点 F1s, F2s に収束します。
ゴール到達法のアルゴリズムの実行
ゴール到達法は、非線形計画問題として考えられる利点をもっています。問題の特性は、非線形計画アルゴリズムの中で利用されています。逐次二次計画法 (SQP) において直線探索に対するメリット関数の選択は容易なことではありません。これは目的関数を改良することと制約違反を少なくすることの間での相対的な重要性を定義することが難しいからです。このことからメリット関数を作成するさまざまな方法が存在する結果になります (例は、Schittkowski [36] を参照)。ゴール到達計画法において、より適切なメリット関数が存在します。これはミニマックス問題として 式 2 で利用されたものです。
(3) |
ここで、
SQP 法を使ったミニマックス最適化についての Brayton 等 [1] の議論に基づき、式 3のゴール到達問題に式 30のメリット関数を使用すると、次のように表せます。
(4) |
式 4のメリット関数が直線探索手法の基底として使われているとき、ψ(x,γ) は与えられた探索方向の 1 ステップに対して減少しますが、関数 max
Λi は逆に増大します。これが、最悪のケースの目的関数になります。最悪の場合の目的関数は目的関数の値 γ に対して影響するので、最小化されるべき目的関数を最終的に増加することになります。逆に言えば、最悪の目的を改良するステップを拒否して max
Λi が減少するとき ψ(x,γ) は増加します。
Brayton 等 [1] の方法に従って、解は最悪な場合の目的関数に等しい ψ(x) になります。すなわち、次のようになります。
(5) |
ゴール到達法に含まれる問題は厳密な制約に関連させるために重み係数をゼロにすることから生じます。式 5 のメリット関数は制約の中で任意の要素が満足されていないとき、無限大になります。
式 5 の条件を満たしたままこの問題に対処するには、メリット関数を 式 31 と合わせて次のように設定します。
(6) |
SQP の中で利用できる他の特性は目的関数 γ です。KKT 方程式からラグランジュ関数のヘッシアン H の近似が変数 γ と関連した行、列でゼロになることが示されます。しかし、H が単位行列として初期化されると、この性質は現れなくなります。そのため、γ と関連した行と列がゼロとなるように H を初期化して維持します。
これらの変更はヘッシアン H を不定にします。そのため H は対角要素を除いて γ に関連した行と列にゼロを設定します。対角要素には小さな正の数 (たとえば、1e
-10) を設定します。これにより、二次計画法での解法 で説明している高速収束正定値 QP 法を使うことができます。
以上の変更は関数 fgoalattain
で行うことができ、よりロバストな方法として使われます。しかし、SQP 法の収束が速いためにメリット関数が厳密に減少するには 式 30 のメリット関数を使う SQP よりも多くの関数評価を必要とします。
目的関数の最大の最小化
fminimax
はゴール到達法を使用します。このゴールは 0 であり、重みは 1 です。これを定式化すると、ゴール到達問題は以下になります。
これはミニマックス問題です。
多目的関数を単一の目的関数にして、fminimax
を使う場合があります。関数
f(x) = max(F1(x),...Fj(x))
参照
[1] Brayton, R. K., S. W. Director, G. D. Hachtel, and L. Vidigal, “A New Algorithm for Statistical Circuit Design Based on Quasi-Newton Methods and Function Splitting,” IEEE Transactions on Circuits and Systems, Vol. CAS-26, pp 784-794, Sept. 1979.
[2] Fleming, P.J. and A.P. Pashkevich, Computer Aided Control System Design Using a Multi-Objective Optimisation Approach, Control 1985 Conference, Cambridge, UK, pp. 174-179.
[3] Gembicki, F.W., “Vector Optimization for Control with Performance and Parameter Sensitivity Indices,” Ph.D. Dissertation, Case Western Reserve Univ., Cleveland, OH, 1974.
[4] Grace, A.C.W., “Computer-Aided Control System Design Using Optimization Techniques,” Ph.D. Thesis, University of Wales, Bangor, Gwynedd, UK, 1989.
[5] Han, S.P., “A Globally Convergent Method For Nonlinear Programming,” Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.
[6] Madsen, K. and H. Schjaer-Jacobsen, “Algorithms for Worst Case Tolerance Optimization,” IEEE Trans. of Circuits and Systems, Vol. CAS-26, Sept. 1979.
[7] Powell, M.J.D., “A Fast Algorithm for Nonlinear Constrained Optimization Calculations,” Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Vol. 630, Springer Verlag, 1978.