平成11年度9月 最適化とアルゴリズム研究部会
- 日時:9月18日(土) 14:00 〜 17:30
- 場所:上智大学7号館12階第1215号室
- 参加者:45名
- 発表1: 田辺隆人氏((株)数理システム)
『『非線形最適化のアルゴリズムとソフトウエア』
-
-
非線形最適化問題とは非線形な制約条件の下で非線形な目的関数を最小/最大
化する問題です.すなわち線形計画問題の一般化として考えられますが,線形
関数を含めたより広い範囲の関数を相手にするため,アルゴリズムとその実装
も複雑になり,ソフトウエア的にも扱える問題の規模に制限があったり,問題
の入力が面倒だったりと,線形計画問題に比べて格段に難しいという印象を与
えてきました.
しかし,近年のアルゴリズム,ソフトウエアの進歩とコンピュータパワーの増
大により,実際に解くことのできる問題の種類や規模が飛躍的に増大し,非線
形最適化は手軽に様々な問題に応用可能なツールとなりつつあります.
本講演では,非線形最適化のアルゴリズムとソフトウエアの現状について,回
路設計,金融工学,生産計画などへの応用事例の話題を交えながら解説します.
- 発表2:藤重 悟 氏(大阪大学 基礎工学研究科)
- ``A Strongly Polynomial-Time Algorithm for Minimizing Submodular
Functions''
-
劣モジュラ関数の最小化は, 離散最適化における基本的な問題である.
Gr\"otschel--Lov\'asz--Schrijver (1981) は, 楕円体法を用いて,
この問題が多項式時間で解けることを示した. しかし, 楕円体法が実際には
極めて非効率的であるため, 組合せ的な多項式時間アルゴリズムの開発が
長い間望まれてきた.
本論文では, 劣モジュラ関数を最小化する最初の組合せ的な多項式時間
アルゴリズムを提示する. このアルゴリズムは, 各枝の容量が一様な完全
有向グラフを用いた新たなスケーリング技法を利用しており, 計算量が台集合
の大きさと関数値の最大ビット長の多項式で押えられる. さらに, 計算量
が台集合の大きさの多項式で押えられる強多項式時間アルゴリズムも
提示する.
(岩田 覚 氏(大阪大学), Lisa Fleischer 氏(コロンビア大学)との共著論文)
SOA Home Page へ.