平成4（1992）年度　共同研究実施報告書

課題番号	4−共研−22			専門分類		2
研究課題名	工学上の諸問題の数値的最適化
フリガナ 代表者氏名	ミズノ　シンジ 水野　眞治			ローマ字
所属機関	統計数理研究所
所属部局	予測制御研究系
職　　名	助教授
所在地
TEL				FAX
E-mail
URL
配分経費	研究費	0千円	旅　費		0千円		研究参加者数	9　人

研究目的と成果（経過）の概要

本研究の目的は、工学上あらわれる諸問題、例えば施設配置問題、輸送問題、資源配分問題、スケジューリング問題等を最適化問題としてモデル化し、個々の問題の特徴をとらえた数値的計算方法の研究を行い、実際問題を効率よく解くアルゴリズムを開発することである。


本年度は、工学上の最適化問題を解くための数値的アルゴリズムの基礎研究をおもに行った。工学上の最適化問題の多くは、線形計画問題としてモデル化できる。また、線形計画問題は、その他の多くの最適化問題のモデル（例えば整数線形計画問題）の基礎として重要な問題である。この線形計画問題を解く数値的アルゴリズムにはシンプレックス法と内点法があるが、大規模な問題を解く場合には、その計算効率等において内点法が優れている。
内点法には、与えられた線形計画問題を直接解く主内点法と、双対定理を利用する主双対内点法がある。主双対内点法は、任意の初期点からアルゴリズムを開始できるという利点を持つ。既存の内点法の研究において、この初期点が実行可能な場合についてのみ、アルゴリズムの収束性が明らかにされていた。
しかし、この場合には、初期点として実行可能解を必要とするために、人工問題を作成するなどの付加的な計算を伴い、非効率的なアルゴリズムとなる。そこで、初期点が一般に実行不可能な場合について、アルゴリズムの収束性の解析を行った。
その結果、ステップサイズなどを巧みに操作することにより、入力データの多項式時間で収束する主双対内点法を開発することができた。そして、その解法の計算時間がΟ（ｎ4Ｌ）となることも明らかにした。ここで、ｎは線形計画問題の変数の数を表し、Ｌは入力データのサイズを表す。さらに、ポテンシャル関数を使った主双対内点法の解析、近似解と真の最適解の関係に関する解析等を行った。

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

Shinji Mizuno, A New Polynomial Time method for a Linear Complementarity Method,Mathematical Programming,56,1992.
M.Kojima,S.Mizuno and A.Yoshise, A Convex Property of Monotone Complementarity Problems, Research Report B-267, Tokyo Institute of Technology,1993 March.

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

一ヶ月または二ヶ月に１回程度、統計数理研究所に集まり共同研究を行う。毎回講演者を決め具体的な問題の説明、モデル化について説明した後、全員によりディスカッションを行う。新しい問題、知見、アイディア等を得たときには、適宜計算機ネットワークを通して共同研究者相互に情報交換を行う。また、数値計算プログラムの開発、あるいは数値実験を行う場合には、統計数理研究所の計算機を使用する。したがって、本研究は統計数理研究所との共同研究として実施する必要がある。

研究参加者一覧
氏名	所属機関
伊藤 聡	統計数理研究所
久野　章子	筑波大学
小島　政和	東京工業大学
田辺　國士	統計数理研究所
田村　明久	電気通信大学
土谷　隆	統計数理研究所
松井　知巳	東京大学
山本　芳嗣	筑波大学