活性制約を考慮した線形計画法の内点法とその数値実験

本年度においては次のような研究をおこなった.1.高性能パソコンを導入し,この研究のための基本的なソフトを作成中である.2.活性制約に関する論文を学会誌に発表し,理論的な面の確立を行った.3.活性制約法については目下,例題につき数値実験中である.これまでの実験からは次のようなことが指摘できる.(a)係数行列がほぼ密で非退化の場合には,活性制約の検出が早期に行われ,極めて少ない反復回数で,最適基底を得て終了する.即ち,上記の理論は正しく作動し,有効である.(b)係数行列が疎で,退化した問題の場合には,活性制約の検出において困難が発生し,一種のzigzag運動が観測される.これは内点法が本質的にfacetのcenterに収束していくということに由来するものと思われる.4.上記の後半部分について更に研究を進めている.Ye等が行ったようなネットワークの問題ではこのような現象が見られないという発表もあるので,問題の種類をより限定することも考えている.5.その他,制約を緩和したり,摂動させて退化を避ける方法についても研究中である.

本年度においては次のような研究をおこなった.1.高性能パソコンを導入し,この研究のための基本的なソフトを作成中である.2.活性制約に関する論文を学会誌に発表し,理論的な面の確立を行った.3.活性制約法については目下,例題につき数値実験中である.これまでの実験からは次のようなことが指摘できる.(a)係数行列がほぼ密で非退化の場合には,活性制約の検出が早期に行われ,極めて少ない反復回数で,最適基底を得て終了する.即ち,上記の理論は正しく作動し,有効である.(b)係数行列が疎で,退化した問題の場合には,活性制約の検出において困難が発生し,一種のzigzag運動が観測される.これは内点法が本質的にfacetのcenterに収束していくということに由来するものと思われる.4.上記の後半部分について更に研究を進めている.Ye等が行ったようなネットワークの問題ではこのような現象が見られないという発表もあるので,問題の種類をより限定することも考えている.5.その他,制約を緩和したり,摂動させて退化を避ける方法についても研究中である.