权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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点列挙アルゴリズムの開発にも成功している。さらに、この研究成果を応用し，分数計画問題に対する新たな大域的最適化手法も開発している。さらに. 本研究で開発した手法を応用し，大規模建設工事のスケジューリング最適化アルゴリズムの構築を進めている。

This study aims to optimize the optimization of large-scale standard DC2 projects. In recent years, the convex polyhedron approximation method and the minimal solution search method of the strong local problem have been introduced into the proposal. The number of iterations depends on the number of iterations required to implement the algorithm. For large-scale problems, the speed of computation is low. In this paper, we propose an approximate solution for the optimal solution of a large-scale standard DC2-order project with a number of KKT points over 1000. In this paper, we introduce the optimization method, the branch-limit method, and the KKT point array method. The difference between the optimal value and the allowable error is the approximate solution of the target value. In this paper, we study the direct solution of the inverse problem, the optimization method, the convex quadratic maximization problem, the sequential KKT point, the sequential sequence of the inverse problem, and the approximate solution of the large domain of the inverse problem. In this paper, the optimal conditions of convex quadratic programming problem are analyzed and KKT points are listed. The results of this study were successfully applied to the development of the KKT point array for fractional second order planning problems. In this paper, the results of this research are applied to develop new optimization methods for fractional planning problems.さらに. This study is aimed at developing methods for optimizing the construction of large-scale construction projects.