【研究分野】社会システム工学

【研究領域課題番号】12680433 (KAKENデータベースで見る）

【研究キーワード】

最適化 / アルゴリズム / 内点法 / 線形計画問題 / 最適化問題

【研究成果の概要】

本研究は、大規模な数理計画問題を効率よく解くアルゴリズムを開発し、その理論的な性質と実用性を明らかにすることを目的としている。平成12年度には、そのための基礎的な研究を行った。大規模な数理計画問題では、問題に含まれる変数に自由変数、非負変数、上下限制約付きの変数の3種類がある。これらの変数を同時に、そのまま処理することが、問題を効率よく解く上で重要である。そこで、このような問題を直接解く内点法によるアルゴリズムについて研究を行った。平成13年度には、係数行列に特殊な構造を持つ大規模な最適化問題に対するアルゴリズムの研究を行った。特に、多期間の確率計画問題から派生する線形計画問題を効率よく解くアルゴリズムについて研究した。この問題は、期間の数あるいはシナリオの数が増えると、変数の数が非常に大きくなるが、係数行列の右上部分がゼロ行列という特徴を持つ。この特徴を利用し、大規模な多期間の確率計画問題を効率的に解くアルゴリズムを開発することができた。平成14年度は、大規模な線形計画問題あるいは非線形計画問題を解く新しい内点法について研究した。この方法は、問題に現れる一部の変数について対数変換を施した後に、ニュートン法を適用する点において従来のアルゴリズムと大きく異なる。変数に対数変換を施すことにより、問題の実行可能領域に横たわる複雑なセンターパスが滑らかになり、内点法により効率よくパスを追跡することが可能となることが期待される。実際、数値実験により、現実の線形計画問題において、提案したアルゴリズムにより対数変換を使わない場合に比べ反復回数を減少させることができることを確認した。

【研究種目】基盤研究(C)

【研究期間】2000 - 2002

【配分額】3,400千円 (直接経費: 3,400千円)

【研究分野】社会システム工学

【研究領域課題番号】08680478 (KAKENデータベースで見る）

【研究キーワード】

最適化 / 社会システム / 内点法 / 線形計画問題 / 半正定値計画問題 / 相補性問題

【研究成果の概要】

社会システムにおける最適化問題を解く内点法についての基礎的な研究を平成8年度より引き続き行った。今年度は、社会システムによく現れる線形計画問題と半正定値計画問題を解く内点法の開発とその大域的収束性と局所的収束性について重点的に研究した。
社会システムにおける最適化問題の多くは、数理計画問題としてモデル化することができる。最も基本的な数理計画問題は、線形計画問題である。線形計画問題を解く内点法について、主だった研究を二つ行った。ひとつは、内点法の局所的な収束性を高めるために、問題の実行可能領域内を通り最適解まで導くセンターパスを高次元に近似するアルゴリズムを研究した。この研究の結果、局所的に高次に収束する内点アルゴリズムを開発することができた。もうひとつは、内点アルゴリズムを実行する上で、初期点を簡単に得るための研究を行った。そのために、与えられた問題に対して自己双対線形計画問題を使うことが有効であることを調べ、そのような内点法について詳しく研究した。
さらに、線形計画問題だけでなく、凸計画問題、半正定値計画問題、半無限計画問題などを解く内点法を研究した。半正定値計画問題に対する内点法では、数多くの探索方向が存在する。そのような方向族の中で、自己双対なものの特徴を詳しく調べあげた。また、線形および2次の半無限計画問題に対する内点法に基づくアルゴリズムの研究と、凸半無限計画問題に対する双対パラメトライゼイションを使ったアルゴリズムの開発を行った。

【研究種目】基盤研究(C)

【研究期間】1996 - 1998

【配分額】2,700千円 (直接経費: 2,700千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】07640343 (KAKENデータベースで見る）

【研究キーワード】

最適化 / 数理計算法 / 線形計画問題 / 内点法 / 線形方程式

【研究成果の概要】

最適化問題を解く内点法についての基礎的な研究を行った。とくに、アルゴリズムの理論的な収束性について研究した。
線形計画問題を解く内点法には、多項式オーダーで収束するアルゴリズムが数多く提案されているが、その中でも係数行列のみに依存した数で反復回数がおさえられる新しいタイプのアルゴリズムが、VavasisとYeにより最近発表された。このアルゴリズムは、優れた収束性を備えているが、理論的に定義されている未知の定数を使う必要があり、実際的なアルゴリズムではなかった。本研究では、このタイプに属するが、そのような未知数を必要としない新しいアルゴリズムを提案し、その収束性を明らかにした。このアルゴリズムは、変数の大きさによる層分割を利用して探索方向を求めることにより、既知のアルゴリズムの高速化に成功している。また、内点法を研究する上で重要なセンターパスの解析を行い、アルゴリズムの計算複雑度に関する新しい解析を行った。
内点法のアルゴリズムでは、大規模な線形方程式を解く必要がある。線形方程式を正確に解くことは理論的に可能であるが、問題が大規模な場合などには、実際には近似的な解を求めるだけの場合も数多くある。今までの内点法の収束性の解析では、この線形方程式の解が正確に求められるということを仮定していた。本研究では、線形方程式の解法に近似計算を使うアルゴリズムについて、理論的な解析を行った。そして、大域的に収束するアルゴリズムを開発し、さらに多項式オーダーの反復回数で収束するための条件を求めた。

【研究種目】一般研究(C)

【研究期間】1995

【配分額】1,000千円 (直接経費: 1,000千円)

【研究分野】社会システム工学

【研究領域課題番号】06680395 (KAKENデータベースで見る）

【研究キーワード】

線形計画問題 / 内点法 / カ-マーカー法 / 数理計画問題 / 組み合せ最適化 / 半正定値計画問題

【研究成果の概要】

本研究の目的「より一般的で広範な数理計画問題を解く計算手法を開発する」に沿って、以下の研究を行った。
1.研究代表者の小島等のグループが開発した大規模な線形計画問題の高速解法である主双対内点法を半正定値計画問題(Semidefinite Program)に拡張し、その理論的基礎を築いた。半正定値計画問題はシステムと制御、組み合わせ最適化、統計等に広い応用がある。
2.線形計画問題、半正定値計画問題、線形相補性問題、凸2次計画問題等を統一的に扱える枠組みである対称行列の空間での線形相補性問題を提案し、この問題への主双対内点法の拡張を行なった。
3.上述の数値計算手法をプログラム言語Mathematicaを使って、購入したPower Macintosh上に実装し、数値実験を行っている。

【研究種目】一般研究(C)

【研究期間】1994

【配分額】2,000千円 (直接経費: 2,000千円)

【研究分野】社会システム工学

【研究領域課題番号】03832017 (KAKENデータベースで見る）

【研究キーワード】

線形計画問題 / 内点法 / カーマーカー法 / 数理計画問題 / 組み合せ最適化 / カ-マ-カ-法

【研究成果の概要】

平成3年度および4年度に計画した研究目標は以下通りであった。
1.主双対内点法の計算効率の向上および評価に関する基礎研究。
2.非凸型2次計画問題および組合せ最適化問題への内点法の適用に関する基礎研究。
3.内点法を中心とする線形計画法のソフトウェアに関する基礎研究。
4.内点法の一般化に関する基礎研究。
研究目標1に関しては,
(1)内点法の各反復でのステップ長をコントロールする新手法の提案,
(2)内点法の初期点に関する研究
を行い理論的な成果を得るとともに,研究目標3と関連して,これらの成果を主双対内点法のソフトウェアに組み込んだ計算実験を行いその有効性を検証した。研究目的2に関しては、非凸型2次計画問題および組合せ最適化問題そのものについての研究成果はあげたが、内点法を適用出来るまでには研究は進んでいない。これはこれらの問題がもともと非常に難しい問題であることが主な原因であり、今後もこの方向で研究を続ける必要がある。研究目標の4に関しては、上述の線形計画問題に関する結果を一般の凸型計画問題に拡張することが出来、充分な成果をあげたと言える。

【研究種目】一般研究(C)

【研究期間】1991 - 1992

【配分額】2,000千円 (直接経費: 2,000千円)