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

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

• 批准号: 22KJ1307
• 负责人: 東 悟大
• 金额: $ 1.09万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2023
• 资助国家: 日本
• 起止时间: 2023-03-08 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22KJ1307/
• 关键词: 多項式最適化; 二次制約付き二次計画問題; 狭小性; ランク1; ランク1行列補完問題

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

本研究旨在通过分析能够计算出准确最优解的条件，构建多项式优化问题的计算方法。今年，我们按照研究计划，致力于阐明多项式优化问题的准确最优解的计算条件。首先，我们对多项式优化问题进行了初步的计算机实验，比较了是否能够准确求解相应的带有二次约束的二次规划问题。当将多项式优化问题转换为具有二次约束的二次规划问题时，不存在单一的过程，并且存在多个相应的具有二次约束的二次规划问题，因此本实验的目的是比较 的可计算性和性质。即使对于具有少量变量和约束的问题，也没有观察到将问题表述为可以计算最优解的问题的规律性。另外，对于可以表述为二阶多项式优化问题的rank-1矩阵补全问题，在考虑预处理后的二阶Lasserre层次的对偶问题时，总是求解简并度为1的最优解我们证明了构建的可能性。准确解决近年来提出的Rank-1矩阵补全问题的关键条件是利​​用链式结构相连的事实来证明对偶解的简并阶为1。本研究结果不需要链式结构，可用于进一步放宽现有研究的条件。事实上，初步实验证实，通过将齐次等式约束替换为平方不等式约束，可以忽略链结构条件。

项目成果

Exactly Solving a class of QCQPs via Semidefinite Relaxation with Bipartite Sparsity Patterns

通过二部稀疏模式的半定松弛精确求解一类 QCQP

• 发表时间: 2022
• 作者: Godai Azuma; Mituhiro Fukuda; Sunyoung Kim;Makoto Yamashita
• 通讯作者: Makoto Yamashita

Ewha Womans University(韓国)

梨花女子大学（韩国）

Exact SDP relaxations for quadratic programs with bipartite graph structures

具有二部图结构的二次规划的精确 SDP 松弛

• DOI: 10.1007/s10898-022-01268-3
• 发表时间: 2022
• 影响因子: 1.8
• 作者: Godai Azuma; Mituhiro Fukuda; Sunyoung Kim; Makoto Yamashita
• 通讯作者: Makoto Yamashita

Exactness conditions for SDP relaxation of bipartite-structured and sign-indefinite QCQPs

二分结构和符号不定 QCQP 的 SDP 松弛的精确条件

• 发表时间: 2022
• 作者: Godai Azuma