クエリ可能最適化理論の深化

深化可查询优化理论

• 批准号: 19K20219
• 负责人: 前原 貴憲
• 金额: $ 2.75万
• 依托单位: Institute of Physical and Chemical Research
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2021-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K20219/
• 关键词: 離散最適化; クエリ可能最適化; オンライン最適化; 劣モジュラ関数; 組合せ最適化; 確率最適化

確率的なパラメタをもつ組合せ最適化問題において，各パラメタに問合せ（クエリ）することでその実現値が得られる，という設定のもとで高品質な解が得られるクエリの手順を求める問題をクエリ可能最適化とよぶ．クエリ可能最適化はごく最近現れた新しい最適化問題の枠組みであり，オンラインカップリングサービスや臓器移植など様々な実問題に対しての応用が期待されている．本研究では様々な実問題に対してクエリ可能最適化の手法が適用できるよう，理論・アルゴリズムを深化・拡張する．2020年度は代表者が研究を一時中断することと，新型コロナウイルスの影響で密に共同研究を進められなかったことから，これまでに得られた成果をまとめることを中心に研究を進めた．まず，2019年度に得られた「劣モジュラ目的関数に対するクエリ可能最適化理論」の結果を論文にまとめて国際論文誌へ投稿した．また，2019年の研究において副次的効果として得られた「ナップサック問題に対する交換可能性」の議論が預言者秘書問題と呼ばれるオンライン最適化の問題に適用できることがわかったため，そちらでも論文を書いて国際会議に投稿した．

在具有概率参数的组合优化问题中，一个问题找到了一个查询过程，该问题提供了一个高质量解决方案，该设置以查询每个参数以获得实际值的设置，称为可查询优化。可查询优化是最近出现的新优化问题的框架，预计将应用于各种实际问题，例如在线耦合服务和器官移植。在这项研究中，理论和算法得到了加深和扩展，因此可以将可查询的优化技术应用于各种实际问题。在2020年，代表们暂时暂停了这项研究，由于Covid-19大流行的影响，无法进行密切合作，因此该研究的重点是总结迄今为止获得的结果。首先，我们汇编了2019年获得的“符合过时目标功能的合格优化理论”的结果，并提交给国际杂志。此外，发现在2019年研究中作为副作用获得的“交换性交换性交换性”的讨论可以应用于称为先知秘书问题的在线优化问题，因此我在此上写了一篇论文并将其提交给国际会议。