A study on practical algorithms for solving DM optimization problems

解决DM优化问题的实用算法研究

基本信息

批准号：
22K11917
负责人：
久野誉人
金额：
$ 2.41万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2025-03-31
项目状态：
未结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K11917/
关键词：
数理最適化非線形最適化大域的最適化 DM関数単調最適化

项目摘要

実用上重要な関数のほとんどは２つの単調関数の差として表記できることが知られているが，このDM(difference of monotonic)関数を目的関数として凸多面体上で大域的に最小化するアルゴリズムをいくつか設計し，計算機上に実装した．計算実験の途中経過を京都大学数理解析研究所の共同利用研究集会で報告した．設計・実装したのはいずれも分枝限定法をベースとするアルゴリズムであり，凸多面体を直方体によって細分する矩形アルゴリズムの亜種である．直方体上における問題の実行可能解の算出には線形計画問題を用い，その最適解ωを使って直方体の細分を行うω細分操作を新たに考案して用いていた．直方体の細分操作に従来からよく使われているのは最長辺を二分割する網羅的方法であるが，これと考案した方法とを比較するため，ランダムに生成したテスト問題を解かせる計算実験を繰り返した．その結果，最適解への手掛かりが極めて少ないこの種の最適化では，実直に二分割を繰り返す方法が意外にも効率のよいことが判明した．この二分割法を凌駕するために様々な工夫を試み，下界値計算に用いる線形計画問題の最適解ωを通る超平面で直方体の最長辺を二分するタイプのω細分操作を構築し，アルゴリズムを計算機上に実装したところ，通常の二分割法と比較しても良好な実験結果を得ることができた．ω細分操作は網羅的な細分法ではないため，アルゴリズムの収束を保障する必要があるが，その証明の目処はすでに立っている．

众所周知，最重要的实际函数可以表示为两个单调函数之间的差，并且已经开发了几种算法来全局最小化凸多面体上的DM（单调差）函数作为目标函数。它在计算机上。在京都大学数学科学研究所举行的联合研究会议上报告了计算实验的进展。我们设计和实现的算法都是基于分支定界法，它是矩形算法的一种变体，将凸多面体细分为长方体。使用线性规划问题来计算长方体上问题的可行解，并设计了一种新的 ω 细分运算，并使用最优解 ω 来细分长方体。传统上，最常用的细分长方体的方法是将最长边一分为二的穷举法，但为了将该方法与所设计的方法进行比较，我们进行了计算实验，其中解决了随机生成的测试问题。重复。结果发现，在这种类型的优化中，最优解的线索很少，而重复两部分划分的方法却出奇地高效。为了超越这种平分方法，我们尝试了各种方法，开发了一种 ω 细分运算，用一个超平面平分长方体的最长边，该超平面穿过用于下界计算的线性规划问题的最优解 ω。当在计算机上实现时，与通常的两部分方法相比，我们能够获得良好的实验结果。由于 ω 细分操作不是穷举细分方法，因此有必要确保算法的收敛性，但我们已经在证明这一点。