Effective procedures for speeding up global optimization algorithms for large-scale canonical dc quadratic programming problems

加速大规模典型直流二次规划问题全局优化算法的有效程序

基本信息

批准号：
20K11688
负责人：
山田修司
金额：
$ 2.66万
依托单位：
Niigata University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究は，大規模標準DC2次計画問題に対する大域的最適化アルゴリズムの高速化を目的としている。従来，DC計画問題に対しては，凸多面体近似法や強力な局所的最小解探索法であるDCAを導入した反復解法が提案されている。しかしながら，これらの手法は，変数の数や反復回数に依存してアルゴリズムの実行に必要なデータ量が増加するため, 大規模な問題に対しては計算速度が著しく低下することが知られている。このため，本研究では，KKT点列挙アルゴリズムを応用し，変数の数が1000以上の大規模標準DC2次計画問題に対して高速に大域的最適解の近似解を求めることができるアルゴリズムの開発を目指している。また，パラメトリック最適化法，ラグランジュ乗数に対する分枝限定法，及びKKT点列挙アルゴリズムを組み合わせることで，最適値との差が許容誤差内に収まる目的関数値をもつ近似解を求めることができるように，アルゴリズムの計算精度の向上を目指している。本研究では、対象問題を直接解くことが困難であるため、パラメトリック最適化法を導入し、凸2次最大化問題を逐次的のKKT点を逐次的に列挙することで対象とする問題の大域的最適解の近似解を求めるアルゴリズムの構築を目指している。そこで、これまでに本研究では、逐次的に生成される凸2次計画問題の最適性条件を解析し、KKT点を列挙するアルゴリズムの開発に成功している。また、この研究成果を応用し、分数2次計画問題に対するKKT点列挙アルゴリズムの開発にも成功している。さらに、この研究成果を応用し，分数計画問題に対する新たな大域的最適化手法も開発している。さらに. 本研究で開発した手法を応用し，大規模建設工事のスケジューリング最適化アルゴリズムの構築を進めている。

本研究旨在加速大规模标准直流二次规划问题的全局优化算法。传统上，针对 DC 规划问题提出了迭代求解方法，其中结合了凸多面体逼近方法和 DCA（一种强大的局部最小解搜索方法）。然而，众所周知，这些方法会显着降低大规模问题的计算速度，因为执行算法所需的数据量会随着变量数量和迭代次数的增加而增加。因此，在本研究中，我们应用 KKT 点枚举算法来开发一种算法，可以快速找到具有 1000 个或更多变量的大规模标准 DC 二次规划问题的近似全局最优解。此外，通过将参数优化方法、拉格朗日乘子的分支定界法和KKT点枚举算法相结合，可以获得目标函数值与最优值的差值在以下范围内的近似解：容差，旨在提高算法的计算精度。在本研究中，由于很难直接解决目标问题，因此我们引入了参数优化方法，并通过顺序枚举凸二次最大化问题的KKT点来解决问题，我们的目标是构建一种找到近似解的算法。最优解。因此，在本研究中，我们分析了顺序生成的凸二次规划问题的最优性条件，并成功开发了一种枚举 KKT 点的算法。此外，通过应用本研究成果，我们成功开发了一种用于分数二次规划问题的 KKT 点枚举算法。此外，通过应用这项研究的结果，我们正在开发一种新的分数规划问题的全局优化方法。此外，通过应用本研究中开发的方法，我们正在着手构建大型建筑工程的调度优化算法。