Study on algorithms of numerical methods for large scale nonlinear optimization problems and their implementation

大规模非线性优化问题数值方法算法研究及其实现

基本信息

批准号：
20K11698
负责人：
矢部博
金额：
$ 2.25万
依托单位：
Tokyo University of Science
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11698/
关键词：
非線形最適化無制約最小化問題制約条件付き最小化問題２次の最適性条件準ニュートン法近接勾配法主双対内点法非線形半正定値計画問題リーマン多様体最適化無制約最適化制約条件付き最適化数値的最適化機械学習への応用

项目摘要

非線形最適化問題に対する数値解法について以下の通り研究した。研究成果の一部は日本OR学会、応用数理学会、研究集会（統計数理研究所）等で発表した。また、研究成果が学術論文誌等に掲載された。（１）制約条件付き最適化問題に対して、ラグランジュ関数の射影ヘッセ行列の負の曲率方向を利用することによって最適性の２次必要条件を満たす点への収束性を保証する信頼領域逐次２次計画法を提案した。　（２）滑らかな関数と微分不可能な関数の和で表現されるような目的関数を持つ最適化問題に対する準ニュートン型近接勾配法を取り扱った。近似行列として正定値性を保持するようなSR1更新公式を用いることで部分問題を容易に解くことが可能になるので、それを取り入れたアルゴリズムを提案した。さらに同様の最適化問題に対して、対角行列を重みとした近接写像が閉形式で計算ができることに注目して、ヘッセ行列の対角成分だけを取り入れたニュートン型近接勾配法（近接対角ニュートン法）を提案し実用化を図った。　（３）L1型正則化項を持つ無制約最適化問題に対するニュートン型近接勾配法を考え、部分問題の目的関数の上界近似を用いることで部分問題の近似解を閉形式で表現できるような手法を提案し、それを組み込んだアルゴリズムを開発した。　（４）各目的関数が滑らかな関数とD.C.関数の和で表されるような多目的最適化問題に対する準ニュートン型近接勾配法を提案し、直線探索を組み込んだアルゴリズムを開発した。さらに、提案アルゴリズムの大域的な収束性を証明するとともに、数値実験によってその有効性を検証した。　（５）応用上、変数の属性ごとに独立した性質を持つ上下限制約付き最適化問題がしばしば現れるような問題に対して、変数をブロックで分け、属性ごとに異なるスケーリングを施す有効制約ブロックBarzilai-Borwein法を提案した。

对非线性优化问题的数值求解方法进行了如下研究。部分研究成果在日本OR学会、应用数学学会、研究会议（统计数学研究所）上发表。此外，研究成果发表在学术期刊等上。 (1) 对于有约束的优化问题，置信域序列2利用拉格朗日函数的投影Hessian矩阵的负曲率方向保证收敛到满足二次要求的点，提出了以下规划方法。 (2) 我们处理了拟牛顿型邻近梯度法，用于解决目标函数表示为平滑函数和不可微函数之和的优化问题。由于使用保持正定性的 SR1 更新公式作为近似矩阵可以轻松解决子问题，因此我们提出了一种结合此的算法。此外，对于类似的优化问题，我们着眼于以对角矩阵为权重的邻近映射可以以封闭形式计算，并使用牛顿邻近梯度法（近对角线牛顿法）并尝试将其投入实际应用。 (3)考虑到带有L1型正则化项的无约束优化问题的牛顿邻近梯度法，我们可以利用子问题目标函数的上界近似来表达子问题的近似解。方法并开发了一种包含该方法的算法。 (4)我们提出了一种用于多目标优化问题的拟牛顿型邻近梯度法，其中每个目标函数由平滑函数和D.C.函数之和表示，并开发了一种结合线搜索的算法。此外，我们通过数值实验证明了该算法的全局收敛性并验证了其有效性。 (5) 有效的约束块 Barzilai，将变量划分为块并对每个属性应用不同的缩放，用于通常涉及具有上限和下限约束的优化问题，其中变量的每个属性都具有独立的属性 - 建议使用 Borwein 方法。