二次計画問題の狭小な半正定値緩和に基づく多項式最適化の大域的解法の展開

基于二次规划问题的窄正半定松弛的多项式优化全局求解方法的开发

基本信息

批准号：
22KJ1307
负责人：
東悟大
金额：
$ 1.09万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2023
资助国家：
日本
起止时间：
2023-03-08 至 2024-03-31
项目状态：
已结题

项目摘要

本研究は多項式最適化問題の正確な最適解を計算できる条件の解析を通じて、多項式最適化問題の計算方法の構築を目指している。本年度は研究計画に従い、多項式最適化問題の正確な最適解を計算できる条件の解明について取り組んだ。まず、多項式最適化問題に関して、対応する二次制約付き二次計画問題を正確に解くことができるかを比較しながら予備的な計算機実験を行った。多項式最適化問題を二次制約付き二次計画問題へ変換する際にその手順は一つに定まらず、対応する二次制約付き二次計画問題は複数存在することから、この実験はそれらの問題の計算可能性と性質を比較することが目的である。変数や制約の数が少ない問題であっても、最適解を計算できる問題へ定式化するための規則性が観測されなかったことから、全ての多項式最適化問題を一括で扱える理論的条件の不適当さが示された。また、2次の多項式最適化問題として定式化可能なランク1行列補完問題に対しては、前処理後の2階のLasserre階層の双対問題を考えたとき、常に退化次数が1である最適解を構成できることを示した。近年提案されたランク1行列補完問題を正確に解くための条件では、鎖構造が連結していることを用いて、双対解の退化次数が1になることを示すことが鍵となっている。本研究の結果は鎖構造を必要としておらず、既存研究の条件を更に緩和するために活用できる。実際に、斉次の等式制約を二乗することで不等式制約に置きかえることによって、鎖構造という条件を無視できることが予備実験で確認できた。

这项研究旨在通过分析条件来构建一种计算多项式优化问题的方法，该条件允许为多项式优化问题提供准确的最佳解决方案。今年，根据研究计划，我们致力于阐明可以计算出准确的多项式优化问题的最佳解决方案的条件。首先，进行了初步的计算机实验，以比较是否可以准确地解决相应的二次约束二次编程问题与多项式优化问题。当将多项式优化问题转换为二次约束二次编程问题时，该过程尚未固定，并且存在多个相应的二次约束二次编程问题，因此该实验旨在比较这些问题的计算可能性和属性。即使问题具有少量的变量和约束，也没有观察到可以将最佳解决方案制定为可以计算最佳解决方案的问题的规律性，这表明理论条件的不足可能会在一个GO中处理所有多项式优化问题。此外，对于可以作为二阶多项式优化问题提出的排名衡量矩阵完成问题，在考虑预处理后二阶套件层次结构的双重问题时，可以证明，可以构建具有1个变性顺序的最佳解决方案。为了准确解决近年来提出的等级-1矩阵完成问题的条件，关键是使用链结构的链接表明双重解决方案的退化顺序为1。这项研究的结果不需要链结构，可以用来进一步缓解现有研究的条件。实际上，初步实验证实，通过平方限制并用不平等约束代替它，可以忽略链结构的状况。