線形計画問題に対する新しい非内点法型逐次反復解法の開発

この課題において行なわれた研究発表中の各論文について,研究を行なった時期の順にその内容を述べる.Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow functions for nonlinear complementarity problems:相補性問題に対するCHKS平滑法と内点法の類似性の発見を原点として,CHKS型平滑法が追跡しているパスを明示し,その解への収束性と大域的収束性をもつ解法を示した.線形計画問題に直接平滑法が適用可能であることを示した最初の論文である.A non-interior continuation method for complementarity problems and its numerical experiences:上記の論文を基に計算機実験を行ない,例題群に対して内点法と同様の高速性が得られることを示した.On the complexity of non-interior-point methods for monotone linear complementarity problems:CHKS型平滑法を線形計画問題に適用した場合の計算量に関するいくつかの補題を示した.A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems:上記の論文を発展させて,解法が必要とする計算量を初めて導出した.ただしここでの解法はパス追跡型ではなく,実用性に関しては未知である.より実用性の高いパス追跡法とその計算量を導出するという課題は残ったが,本研究の当初の目的は十分満足できたと考える.最近,内点法と,CHKS平滑法の類似点に加え,2つの解法がn次元空間を互いに補完する領域に点列を生成させていることが判明し,2つの解法の特性を生かした解法が存在する可能性が高いことがわかった.また,半正定値問題に対するCHKS平滑法の応用など,今後もこの解法についてより多くの研究を行なう予定である.

この課題において行なわれた研究発表中の各論文について,研究を行なった時期の順にその内容を述べる.Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow functions for nonlinear complementarity problems:相補性問題に対するCHKS平滑法と内点法の類似性の発見を原点として,CHKS型平滑法が追跡しているパスを明示し,その解への収束性と大域的収束性をもつ解法を示した.線形計画問題に直接平滑法が適用可能であることを示した最初の論文である.A non-interior continuation method for complementarity problems and its numerical experiences:上記の論文を基に計算機実験を行ない,例題群に対して内点法と同様の高速性が得られることを示した.On the complexity of non-interior-point methods for monotone linear complementarity problems:CHKS型平滑法を線形計画問題に適用した場合の計算量に関するいくつかの補題を示した.A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems:上記の論文を発展させて,解法が必要とする計算量を初めて導出した.ただしここでの解法はパス追跡型ではなく,実用性に関しては未知である.より実用性の高いパス追跡法とその計算量を導出するという課題は残ったが,本研究の当初の目的は十分満足できたと考える.最近,内点法と,CHKS平滑法の類似点に加え,2つの解法がn次元空間を互いに補完する領域に点列を生成させていることが判明し,2つの解法の特性を生かした解法が存在する可能性が高いことがわかった.また,半正定値問題に対するCHKS平滑法の応用など,今後もこの解法についてより多くの研究を行なう予定である.