Construction of theory of polyhedral approximation of the semi-definite cone in conic optimization and its applications

二次曲线优化中半定锥多面体逼近理论的构建及其应用

• 批准号: 19H02373
• 负责人: 吉瀬 章子
• 金额: $ 10.98万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19H02373/
• 关键词: 錐最適化; 半正定値錐; 線形計画問題; 優対角錐; 二重非負値錐; 優対角行列錐; 錐最適化; 半正定値錐; 線形計画問題; 優対角錐; 二重非負値錐; 優対角行列錐

錐最適化モデルは，線形計画問題や半正定値計画問題を含む広範な最適化モデルであり，21世紀を代表する最適化モデルとして世界的規模で活発に研究が行われている．本研究では，2次割当問題など困難な数理最適化問題に対する「錐最適化モデル」の高い問題記述能力に着目し，応募者らが発案した半正定値基とそれらの拡張によって生成される多様な凸多面錐を精査することで，錐最適化手法のさらなる社会実装に役立つ，半正定値錐の凸多面錐近似の理論を構築することを目的としている．理論的性質の導出と計算機実験を繰り返すことにより，計算効率と近似精度の双方から半正定値錐の凸多面錐近似の限界を見極め，半正定値錐の凸多面錐近似に関する独自の理論を構築するとともに，錐最適化の社会実装を意識した，計算効率の議論と検証を重視した理論構築を目指している．2021年度は，特に小さなサイズの主座小行列式が非負である性質をもつ行列錐に着目し，半正定値錐の凸多面錐近似における近似精度の導出を試みるととともに，0-1整数計画問題あるいは混合整数計画問題への応用可能性を検証するため，0-1制約の連続緩和による線形計画問題を子問題とする従来手法と，連続緩和の代わりに半正定値緩和の凸多面錐近似を用いた手法の比較を行った．研究代表者吉瀬は理論の構築，応用可能性の検証など研究全般にわたる役割を担った．研究分担者の繁野氏には組合せ最適化に関する専門知識を，八森氏には組合せ論に関する専門知識を，高野氏には混合整数計画問題や大域的最適化に関する専門知識を，佐野氏には離散数学に関する専門知識を，それぞれご提供頂いた．

锥优化模型是广泛的优化模型，包括线性编程问题和半阳性的确定编程问题，并在全球范围内积极研究，是21世纪最具代表性的优化模型。这项研究着重于在困难的数学优化问题（例如二次分配问题）的“锥优化模型”的高问题描述能力上由其扩展产生的多方面锥体。通过得出理论属性和重复计算机实验，我们可以从计算效率和近似准确性中确定凸的多面锥近似的限制，并建立一个独特的理论，并建立有关CONVEX Multifacted锥形近似的独特理论实施锥优化。在2021年，我们专注于矩阵锥，具有小尺寸的决定因素的特性，并试图得出半阳性决定因素的凸多方面锥近似的近似准确性，并验证使用0-1个整数编程问题或使用常规编制的方法，我们将应用于0-1的限制性问题来验证应用程序的应用，我们比较了一个常规方法，我们将一定的限制性问题比较了，我们比较了一定的限制性问题。儿童和一种使用凸多面锥的方法，代替连续松弛。首席研究者Yoshise在一般的研究中发挥了作用，包括建立理论和验证应用程序的可能性。研究人员Shigeno提供了组合优化的专业知识，Yamori提供了组合理论的专业知识，Takano提供了混合整数编程问题和全球优化方面的专业知识，Sano提供了离散数学方面的专业知识。