数式表現によらない関数の 制約付き最適化
(株)数理システム
発表内容
最適化手法の概要
制約付き問題への適用の際の注意点
数値実験
最適化手法の概要
数式表現によらない関数の最適化手法
直接探索法
信頼領域法の概念を用いる解法
直線探索法の概念を用いる解法
有限差分と準ニュートン法を組み合わせた 解法
→これらの手法を総称して “DFO” と呼ぶ
5
信頼領域法の概念を用いる解法
個の点からなる集合 を用意
モデル 2 次関数の構築
部分問題を解き，点の集合 等を更新する
モデル 2 次関数
2 次の補間多項式
( を満たすものとする) を用い次式により構築する：
( は関数値の情報「のみ」
7
部分問題（制約なし問題の場合）
ただし，
：暫定解
：信頼領域半径
アルゴリズム
Step0: 初期設定
Step1: モデル 2 次関数の構築
Step2: モデル 2 次関数の最小化
Step3: 集合 の更新
Step4: 信頼領域半径の更新
Step5: 暫定解の更新
制約付き問題への適用の際の
注意点
制約付き最小化問題
次の制約付き最小化問題を扱う：
ただし， は関数値の情報「のみ」利用可
は微係数値も利用可
11
点の集合のとり方
「全ての制約条件を満たす点のみで構成す る」のでは問題がある
「非負制約を満たす点のみで構成し，等式 制約は違反量をペナルティとして扱う」ことで 対応
部分問題（制約付き問題の場合）
制約ごとにペナルティを設定
13
は に 対応する双対変数に相当
部分問題の KKT 条件を考えることにより 次が言える：
（つまり ）の解を得るには である必要がある．
ペナルティパラメータの値について
点の集合の更新
部分問題の解 の良さを次式により計算
: ペナルティ関数
: モデルペナルティ関数
本物の関数での変化 モデル関数での変化
15
点の集合の更新（ケース１）
点 それぞれについて を計算する．
を最大にする点 を集合か ら除き，部分問題の解 を集合に加える
この範囲で最大に
点の集合の更新（ケース２）
点の集合 が次の条件を満たしていない 場合，満たすように調整を行なう．
各 について
次を満たす点 が存在しない ・
・ある に対し
17
Lagrange 関数の扱い
制約付き最小化問題の Lagrange 関数：
： に対応する双対変数 ： に対応する双対変数
Lagrange 関数の扱い
モデル 2 次関数を利用する：
19
信頼領域半径の更新
次の場合に更新を行なう：
の値が大きく が一定値以上であっ
た場合
の値が小さく
点の集合 が所定の条件を満たして いた場合
拡大する
縮小する
終了判定条件
以下のいずれかを満たした場合に終了する：
(ア)信頼領域半径が十分に小さい
(イ) の値が大きく，さらに
の値が十分小さい (ウ) の値および制約違反量の値
が十分小さい
数値実験
数値実験： Hock and Schittkowski
問題数
終了状態の内訳 信頼領域
半径(ア) Lagrange
関数(イ) モデル 2 次関数(ウ) 文献にある解
に収束 ９６ 問 １ 問 ２７ 問 ６８ 問 文献とは異なる
解に収束 １５ 問 ０ 問 ０ 問 １５ 問 探索に失敗 ４ 問
23
数値実験：構造最適化
多質点せん断型構造物に対する地震時
弾塑性応答制約条件下のコスト最小化問題
問題設定・資料提供：
京都大学大学院工学研究科建築学専攻 山川誠 先生
数値実験：構造最適化
変数：建物各層の履歴特性
目的関数：建物コスト
制約条件：
・建物各層の履歴特性の上下限
・所与の地震動下における最大層間変形角制約
25
数値実験：構造最適化
実験時の定式化：
：ペナルティ係数（実験では ）
実験環境：
・マシン： Pentium D 2.8GHz，メモリ 1 GB，Windows XP SP2 ・アルゴリズム： Python を用いて実装
・部分問題： NUOPT （信頼領域法）を使用して求解
数値実験：構造最適化
実験により 得られた解
27
数値実験：構造最適化
暫定解における目的関数値の変化
信頼領域半径が 十分小さくなったこと
により終了
謝辞
数値実験を行うにあたり，京都大学の山川 誠先生に，問題やデータの提供および得ら れた解の評価をして頂きました。心より感謝 の意を申し上げます。
[参考文献]
山川誠, 辻聖晃, 上谷宏二, 中川佳久, ”応答補正モデルを用
