Explicit dual formulations of continuous optimization problems and their applications

连续优化问题的显式对偶表述及其应用

基本信息

批准号：
21K11769
负责人：
山下信雄
金额：
$ 2.66万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

本研究では，連続最適化の陽にかける双対問題を利用して，実用化の障壁となる「モデル化の壁」と「アルゴリズムの実装の壁」を解決することを考える．本年度の目的は，双対性を利用して，不確実なデータを含む最適化問題や均衡問題，またそれらの応用問題を効率よく解く手法を開発することである．さらに一般ゲージ双対問題を含めた，新しい最適化モデルの構築の検討を行うことであった．その目的に対して以下の成果を得た．・パラメータに不確実性を有した均衡問題の均衡解の性質を解明することは重要である．本研究では，不確実性を有し，さらいに意思決定機会が2回あるシュタッケルベルグ型ゲームに対して，均衡解が存在する条件を与えた．さらに，双対性を利用して均衡解を求める手法を開発した．・非線形方程式に対するLevenberg-Marquardt法において，正則化項を一般化した手法を提案し，その収束性を解明した．さらに，正則化項にL1ノルムを用いた場合の部分問題に対して双対性を利用した解法を開発した．・データとの適合度を制約条件にもつL1正則化問題(Basic Pursuitなど)に対して，双対問題を導出し，その双対問題の特性を利用した有効制約法を提案した．さらに提案手法が有限回の反復で終了することを示した．・凸関数と凸関数との差で表された関数で構成された問題(DC計画問題)の双対問題は，その凸関数の共役関数の差で表された関数によって構成された問題となることが知られている．これはフェンシェル双対の一般化とみなせる．今年度は，ゲージ関数とゲージ関数の差で表せる問題を考え，その双対性について検討した．DC計画問題とは違い，ゲージ関数とゲージ関数の差で構成された問題では有界とならないことがある．そのため，制約条件を含むモデルの構成が重要となることがわかった．

在本研究中，我们将利用连续优化的显式对偶问题来解决实际应用中的“建模墙”和“算法实现墙”。今年的目的是利用对偶性开发有效解决涉及不确定数据的优化问题和均衡问题的方法及其应用问题。此外，我们研究了包含一般规范对偶问题的新优化模型的构建。为此目的获得了以下结果。・阐明参数不确定的平衡问题的平衡解的性质非常重要。在本研究中，我们为具有不确定性和两个决策机会的 Stackelberg 博弈的均衡解的存在设定了条件。此外，我们开发了一种利用对偶性寻找平衡解的方法。 - 我们提出了一种推广非线性方程 Levenberg-Marquardt 方法中正则化项的方法，并阐明了其收敛性。此外，我们开发了一种当 L1 范数用作正则化项时使用对偶性解决子问题的方法。・针对以数据适应度为约束条件的L1正则化问题（如Basic Pursuit），我们导出了对偶问题，并利用对偶问题的特点提出了一种有效的约束方法。此外，我们表明所提出的方法在有限次数的迭代后完成。・由两个凸函数之间的差表示的函数组成的问题（DC规划问题）的对偶问题是由两个凸函数的共轭函数之间的差表示的函数组成的问题。这可以被视为芬舍尔对偶性的推广。今年，我们考虑了一个可以用规范函数和规范函数之间的差异来表达的问题，并研究了它的对偶性。与 DC 规划问题不同，由规范函数和规范函数之间的差异组成的问题可能没有界限。因此，我们发现包含约束的模型配置很重要。