Algorithms and Analysis of M-convex Function Minimization and Related Problems

2021年8月15日 08:32

邦訳：M凸関数最小化および関連問題に対するアルゴリズムと解析

南川智都

（東京都立大学　助教）

------------------ keyword ------------------
離散最適化
離散凸解析
最急降下法
----------------------------------------------

【背景】離散凸解析におけるアルゴリズムの発展
【問題】M凸関数最小化およびその関連問題
【貢献】アルゴリズムの解析とM凸関数最小化として定式可能な問題の提案

　与えられた条件を満たしつつ，ある基準に沿って最も良い選択を行う問題を，離散最適化問題とよびます．たとえば，カーナビのように現在地点から目標地点までの最短経路を見つける問題は，典型的な離散最適化問題です．離散最適化問題は，すべての選択肢を比較することで最適な解を見つけることができます．しかし，大規模な問題において全選択肢を調べつくすのは現実的ではありません．そのため，解を調べる回数をできる限り抑えつつ，最適な解を見つけられることが理想です．

　離散最適化問題では，比較的少ない解の調査により最適解を見つけられることが保証された「解きやすい」問題が存在します．このような解きやすい問題を統一的に扱うための枠組みとして提唱されたのが「離散凸解析」です．離散凸解析の目を持って離散最適化問題を眺めると，未知の問題が効率的に解くことが可能かどうか，理論的に判定できることがあります．最近では，離散凸解析の理論を利用し，難しい問題を可能な限り高速に解こうとする研究も進められています．離散凸解析の理論を発展させることは，世の中に潜むさまざまな離散最適化問題を解くことに繋がります．

　離散凸解析における重要な研究テーマの1つが，離散凸性を持った関数の最小解を求めるアルゴリズムの改良です．本研究では，離散凸解析において中心的な役割を担う関数の1つであるM凸関数の最小化について，以下の2つの観点から研究を行いました．

（1）基本的なアルゴリズムの計算回数の解析
　M凸関数最小化は，さまざまな離散最適化問題を表現できる問題の枠組みです．M凸性をもつ離散最適化問題は，M凸関数最小化アルゴリズムによって解くことができます．M凸関数最小化に対する最も基本的なアルゴルズムとして知られるのが，現在の解に近い解の中で最も良い解に移動することを繰り返す，という最急降下法です．最急降下法は離散凸解析が提唱された1990年代後半に提案されたアルゴリズムですが，近年まで厳密な計算回数が明らかになっていませんでした．本研究ではM凸関数最小化と，その一般化として知られるジャンプM凸関数最小化について，最急降下法の厳密な計算回数を示しました．さらに，最急降下法によって生成される解が，最短距離で最も近い最小解に接近していく，という新たな性質を示しました．

（2）M凸関数最小化として定式化可能な新たな問題の提案
　数理経済学において，いくつかの離散的な資源を複数の活動に割り当てる問題を，資源配分問題とよびます．資源配分問題の一種である分離凸資源配分問題は，凸関数で与えられた経費・損失が最小になるように，資源を配分することを目的とします．本研究では，資源がすでに配分されている状況で，配分の変更量に関する制約を満たす新たな最適配分を求めたい，という新しい分離凸資源配分問題を提案しました．そして，この制約付き分離凸資源配分問題がM凸関数最小化として定式化できることを示すとともに，この問題に特化したアルゴリズムを構築しました．

（2021年5月31日受付）
（2021年8月15日note公開）

ーーーーーーーーーーーーーーーーーー
　取得年月日：2021年3月
　学位種別：博士（工学）
　大学：東京工業大学
ーーーーーーーーーーーーーーーーーー

推薦文：（アルゴリズム研究会）
本論文では，「Ｍ凸関数」の反復回数に関する理論的な解析を行っている．また，Ｍ凸関数を利用することで，自転車シェアリング等に応用がある資源配分問題を，ある条件の下で効率的に解くことができることも示している．Ｍ凸関数は組合せ最適化の分野で重要なツールの1つであり，大きな実用性を持つ論文として推薦する．　

南川智都（正会員）

研究生活：博士課程では離散最適化に関する理論研究を行ってきました．理論研究では「よく分からないが何か難しそうな研究をやっているな」と思われてしまいがちなので，自分の研究成果・貢献をうまく説明するのが重要です．最初は研究成果・貢献を人に説明することに苦手意識があり，自分の研究の立ち位置が分からなくなることが多々ありました．研究の方向性を見失ってしまい，どうすればよいか何度も悩んできましたが，なんとか博士の学位をとれたことにほっとしています．

博士課程では，指導教員である塩浦昭義教授をはじめとした世界トップレベルの専門家の指導の下で，自分の突き詰めたい研究ができるという，人生で二度とないであろう貴重な時間を過ごすことができました．充実した研究生活を支えていただいた塩浦研究室の皆様，および家族に心より感謝を申し上げます．今後は新たな環境で研究に邁進し，離散最適化の研究の発展と，その面白さを伝えることに貢献していきたいと思います．