WEKO3
アイテム
錐線形計画に対する面削減法の実装の試み
https://uec.repo.nii.ac.jp/records/8468
https://uec.repo.nii.ac.jp/records/84689bbe9d37-be26-4a5f-96c2-fe0018712227
名前 / ファイル | ライセンス | アクション |
---|---|---|
1531039 (522.4 kB)
|
|
Item type | 学位論文 / Thesis or Dissertation(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2017-03-13 | |||||
タイトル | ||||||
タイトル | 錐線形計画に対する面削減法の実装の試み | |||||
言語 | ja | |||||
言語 | ||||||
言語 | jpn | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||
資源タイプ | thesis | |||||
著者 |
香村, 友宏
× 香村, 友宏 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | 近年,半正定値計画問題や二次錐計画問題などの錐線形計画がよく研究されている.錐線形計画においては双対ギャップがある場合,最適値は存在するが最適解が存在しない場合など,通常の線形計画にはありえない状況が起こる場合がある.もし錐線形計画に内点許容解がある場合には,双対ギャップがなく,双対問題には最適解が存在することが知られている. 面削減法とは,内点許容解がない錐線形計画問題が与えられたときに,錐をある面に制限することにより,内点許容解を持つ問題に変換しようとするものである.しかし,面削減法は数値誤差に弱い手法である.これに対し,Lourenco,Muramatsu,Tsuchiyaは削減方向の計算時に,主問題と双対問題の両方に内点許容解が存在するような新しい定式化(LMT)を用いることを提案している.LMTは,従来の計算法よりも数値的に安定して解けることが期待される. 本論文の目的は,LMTにより削減方向を計算することが,どの程度有用なのかを数値計算により確認すること,また,面削減法の実装において数値誤差に対する弱さを克服できないのか検討することである. 結果として,主問題が強実行可能かつ双対問題が弱実行可能な半正定値計画問題について,削減方向の計算に従来の定式化とLMTのどちらを用いても概ね正しい削減方向が計算できることや,面削減法の方がその他の方法よりも安定して解くことができることなどが判明した. また,弱実行不可能な半正定値計画問題について,既存のソルバをそのまま用いるよりも面削減法を用いた方が適していることや,削減方向の計算にはLMTの方が適していることなどが判明した. 加えて,実行可能だが双対ギャップが存在する半正定値計画問題について,面削減法は解くのに適しているとは断言できないことや,削減方向の計算方法は,解くことができる問題数には関係が無いことなどが判明した. |
|||||
学位名 | ||||||
学位名 | 修士 | |||||
学位授与機関 | ||||||
学位授与機関名 | 電気通信大学 | |||||
学位授与年度 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 2016 | |||||
学位授与年月日 | ||||||
学位授与年月日 | 2017-03-24 | |||||
著者版フラグ | ||||||
出版タイプ | AM | |||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
専攻 | ||||||
値 | 情報理工学研究科 | |||||
専攻 | ||||||
値 | 情報・通信工学専攻 |