2009-02-27

計算最適化システム 「IOSO」No.2 制約条件

§2 制約条件

[1]最適化の数値解析に困難を生じる主な理由

課題を列挙すれば、

• 目的関数の非線形性
• 許容領域の特異性

です。

課題 a.に伴う困難は当然ですが、設計変数の許容領域を或る程度まで予測できれば、その範囲で目的関数をスムーズな関数にモデル化出来ます。現在でも線形計画法（LP: Linear Programming）は実務では便利なツールとして使用されます。 厳密な意味の最適解(optimal solution)でなく次善の許容解であっても、結果を速く得るツールが好便です。 現状分析の第一課題は b.と認識しています。

課題 b.は具体的には、

• (b-1) 設計変数の余裕幅(マージン)が狭く、探索の余地が少ない
• (b-2) 許容領域が凹関数（concave）の問題
  

  (制約条件から見れば凸関数(convex)の問題)

• (b-3) cuspの先端形状の如く特異点を持つ場合

等が挙げられます。

上記(b-1)に関しては、「IOSO」No.1 概説[5]でRosenbrock問題を採り上げ、IOSOのスキームが頑丈である事を述べました。 文献^[4],p.316には「非凸計画問題」の場合、大域的最適解を求める事の難しさに付いて記述されています。 従いまして、本章§2,[3]で、上記の事項(b-2),(b-3)に関し展望を述べます。

（補足：IOSOの別モジュールの機能にロバスト設計^[1] への対応が有ります（IOSO-RMモジュール）。従いまして、本文では「スキームの頑丈性」を「ロバスト」と呼ぶ事を避けています。後掲（予定）Appendix-[91]：「用語解説」を御参照下さい）

[2] GUIの設定

制約条件を形式で分類し、GUIの対応を述べます。

(2-1) 設計変数がBounding-Box形（不等式型、「側面制約条件」）

基本的な形式であり、困難となる事項を想定していません。設定例は下記の図2-1の第1行目を御覧下さい。

(2-2) 設計変数がMPC型(Multiple Point Constraint、等式型)

一般形

入力の具体例

図2-1 設計変数レベルの制約条件(タイプ(2-1),(2-2) )

(2-3) 独立変数を特定しない型

（多くの場合、不等式型の制約条件）

文献[2]のLP問題（線形計画法）の入力例

設題

図2-2 線形不等式型の制約条件の入力(タイプ(2-3) )

(2-4) 制約条件が非線形の型（一般形）

タイプ(2-1) , (2-2)は設計変数の段階で設定します。 しかし、タイプ(2-3)の如く制約条件g(x)は線形であっても、目的関数と同じレベルのGUIで記述します（図2-2："Synthetic Parameters"の段階）。 「条件付き最適化問題」は、penalty法 [3],[4],[6]の定式化が便利です。この場合、目的関数と同じ処理レベルで定義します。従いまして、タイプ(2-4)はタイプ(2-3)と同様のGUI対応です。

---

（感覚的に分かり易く表現すれば、絶対座標系に於けるBounding-box型とは異なり、関数型制約条件（functional constraints[7] ）はif-statementだけでは処理できないという意味です。

即ち；

の様な単純な処理では目的関数fの最適（最急）勾配はスムーズには求まりません。

Lagrange-multiplierをλとした時、極値の方向は境界で、
∇f+λ∇g
を考慮する必要が有ります）

---

Penalty定数などに伴う手続きはプログラム内部で処理されます。従って、GUIに定数入力の項目は有りません。即ち、「条件付き最適化問題」に対応する場合、ユーザはこのアルゴリズムに関する詳細な知識を必要としません。

なお、本節中の「Bounding-Box型、MPC型」は分類の便宜上、㈱シムサイドが用いた仮称です。

[3]　検証例題-1（cusp）

本節§2 [1] で列挙した、制約条件が原因に依り生じる、数値計算上の幾つかの課題に対してIOSOのスキームが頑丈である事を検証します。

文献^[3] , p-34のcusp領域の問題を採り上げます。

解は、

図3-1 制約条件と許容領域の特異性

検討課題は

• 許容領域が凹形状（concave）、制約条件から見れば凸領域（convex）を含む、
• cusp先端に最適解が在る、

の２項です。

課題 a.の課題に関しては、後掲(予定)のAppendix-[1]「線形化」を御覧下さい。

課題 b.の困難は、理論解に近接するに従って探索領域は極端にアスペクト比の小さい楔状になります。

連続関数の尖点近傍を、有限個数のサンプリングによるRSMで近似する場合、補間に依るRSMでは、数値で表現出来る或る限度の限界が予想されます。

理論解の近傍

の範囲では、

です。従って、実務ではEq.(3-5)の範囲の数値解を得れば良いと考えます。

図3-2 変数x1の収束状況

IOSOは特異領域（cusp）と凹領域（concave）を含む問題を、離散化法（RSM）の範囲で迅速に解を得る事を示しました。

[4]　検証例題-2（crescent(三日月状)領域）

前節§2,[3]ではcuspに関連する特異領域の問題を検証しました。尖端部が常に離散化誤差の問題を生じるとは限りません。有限サイズの許容領域であればIOSOは計算機精度の範囲で正確に解を求めます。 此処では、文献^[4]の問題を追試致します。

図4-1に設問の概念図を掲載いたします。この問題も[3]の検証例題-1と同様

• 尖端を含む
• 凹領域を含む

の数値計算上の課題を含んでいます。しかし、尖端は有限のサイズです。

図4-1 計算概念図

この課題は２番目の「凹領域の存在」が数値計算を非常に難しくしています。
試みに、g1(x)を線形、

又は、凸関数、具体的には、

に置き換えた場合は、簡単に解が得られます。

図4-2 制約条件、目的関数のGUI入力

図4-3 x2の収束状況

図4-1 に対応する入力画面、及び結果は、図4-2、図4-3です。収束に関するパラメータの設定はdefaultです。理論解に迅速に収束しています。

目的関数が、max_f(x)=x1 の場合は、解が特異では有りませんが、凹領域を含む事は同様ですから結果を掲載します。

図4-4 x1の収束状況

[5] 結語

以上からIOSOのスキームが頑丈である事、即ち

• IOSOは確率論的な学習･推論法（ヒューリスティックの手法）を用いている。従って、凹領域を含んでも大域解が得られる。
• 尖端点を含んでも、有限のサイズであれば収束する。cusp状であっても、離散化の精度の範囲で解が得られる。

事を示しました。

[6] 補足：凹領域の解析に関する文献

論文(5-1)では、凹関数に対して大域的最適化を求める場合、「ヒューリスティック」な解法の有効性を述べています。

引用文献

1. 開発元SIGMA社のサイト
   http://www.iosotech.com/robust.htm
2. 静岡理工科大学 総合情報学部 菅沼研究室のサイト
   http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/linear/linear.htm
3. 坂和正敏、「非線形システムの最適化」、森北出版、1987．（Cuspの例題はp.34）
4. 今野･山下、「非線形計画法」、日本科学技術連盟出版社、1978．（凹関数の例題はp.60、(b)の問題）
5. 凹関数とヒューリスティック的手法に関する文献
   (5-1) ルンキーラティクン スワン、趙 偉平、浅野 正一郎 、「既存網を考慮したパケット交換網のリンク容量割り当て設計法 : 凹のリンクコスト関数の場合」の抄録
   書誌情報 http://ci.nii.ac.jp/naid/20001381801/ の中程
6. Orwiki : (社団法人 日本オペレーションズ・リサーチ学会 OR事典編集委員会 によって作成されているページです)
   http://www.orsj.or.jp/~wiki/wiki/index.php/《制約付き最適化》
7. I.Egonv, "Indirect Optimization Method on the Basis of Self-Organization", International Conference on OPTIMIZATION TECHNIQUES AND APPLICATIONS (ICOTA'98), Perth, Australia, July 1...3, 1998 Conference Proceedings, vol.2, pp.683-690,
   ICOTA98.pdf