平成１２年度６月　最適化とアルゴリズム研究部会

• 日時：6月10日（土） 14:00 〜 17:30
• 場所：上智大学7号館12階第1215号室

• 発表１：久保 幹雄 氏 (東京商船大 流通情報工学課程)

  『組合せ最適化--理論と実務をつなぐには--』

  組合せ最適化問題に対するアルゴリズム開発を例として， 理論から応用，応用から実務への橋渡しをするための 方法論について述べる．また，実務的なアルゴリズム評価のための 実験的解析をどのように遂行すべきかについても述べる．

• 発表２：伊藤 聡 氏 (統計数理研究所)

  『無限計画と最適制御 (Infinite programming and optimal control)』

  古典的変分法および最適制御の理論は無限計画法として一般化かつ抽象化 され，最適解（最適曲線あるいは最適制御）が満たすべき必要条件や十分条件が 得られている．しかし，システムが線形で目的関数が2次のいわゆるLQ問題や低 次元の簡単な場合を除いて，最適解をその必要条件あるいは十分条件から解析的 に求めることは困難であり，一般の非線形の場合には数値計算に頼らざるを得な い．最適制御の数値解法としてこれまで多数の手法が提案されてきたが，最も汎 用的でかつ効率的といえるのは非線形計画法に基づく解法であろう．種々の最適 制御問題のうち，ここでは特に連続時間の最適制御問題を取り上げる．連続時間 最適制御問題は制御入力を決定変数とし，常微分方程式や偏微分方程式を介して 終端状態や過渡状態を評価する目的関数，また同様に終端状態や過渡状態に関す る等式あるいは不等式制約条件を持つ無限計画問題であり，関数空間上の非線形 計画問題として定式化される．制約条件がない場合や終端状態に関する等式条件 あるいは不等式条件のように有限個の汎関数制約条件のみが存在する場合には， 関数空間における準ニュートン法，双対逐次2次計画法がそれぞれ有効である． 過渡状態に関する不等式条件のように無限次元の制約条件が存在する場合は数値 解を求めるのがより困難になる．このような問題を解く一つの有力な方法は，時 間関数である制御入力を何らかの方法でパラメトライズすることにより離散化し， 有限個の決定変数と無限個の制約条件を持つ問題，いわゆる半無限計画問題に変 換して解くことである．半無限計画問題は決定変数が有限次元であるため，一般 的な仮定のもとで双対変数が離散的になる，すなわち無限個の制約条件のうち有 限個（たかだか決定変数の次元）だけを考慮すればよい，という性質があり，こ れに基づいて等価な有限次元の非線形計画問題に書き直すことができる．その他， 切除平面法および双対逐次2次計画法に基づく解法を紹介する． キーワード：無限計画 (infinite programming)，最適制御 (optimal control)，変分法 (calculus of variations)，非線形計画 (nonlinear programming)，半無限計画 (semi-infinite programming)