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

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

The DM (difference of monotonic) relation is the target relation and the minimization of a large domain on a convex polyhedron is designed to be implemented on a computer. Report of Joint Utilization Research Conference of Institute of Mathematical Analysis, Kyoto University. Design and implementation of the method of branching limit, convex polyhedron, rectangle, subdivision, etc. The calculation of the feasible solution to the problem of linear planning in a straight body, the optimal solution to the problem of linear planning in a straight body, the subdivision of a straight body, the subdivision of a straight body, the operation of a new case in a straight body, and the calculation of the feasible solution to the problem of linear planning in a straight body. The method of dividing a square into two parts is to compare the method of dividing a square into two parts, and to calculate the method of dividing a square into two parts. The results show that the optimal solution of the problem is to optimize the problem by dividing the problem into two parts, and to determine the problem by dividing the problem into two parts. The two-division method is used to calculate the optimal solution of the linear planning problem. The optimal solution of the linear planning problem is to construct the longest part of the hyperplane. The two-division method is usually installed on the computer. Subdivision operation is a necessary part of the subdivision method of the network, and the purpose of the proof is to establish the subdivision method.