京都⼤学数理解析研究所 共同研究（公開型）
数理最適化: 理論と実践
2023年8⽉28⽇(⽉)，29⽇(⽕)
ハイブリッド開催（RIMS 420号での対⾯とZOOM）

プログラム

発表時間1件あたり30分(質疑5分を含む)

ショートトークは20分(質疑5分を含む)
8⽉28⽇(⽉)
13:00-13:05 開会の挨拶
13:05-14:55 セッション１（配置問題とゲーム）
カクタスグラフ上の連続被覆⽴地問題（ショートトーク）
講演者：繁野 ⿇⾐⼦（筑波⼤学）
本研究では，与えられたグラフに施設を配置し，グラフ全体が，配置した施設のどれか⼀つとある定数値以下であるような被覆⽴地問題，及び，施設館の距離がある定数値以上である分割
⽴地問題を扱う．⽊グラフに対しては，Tamir (1991), Chandrasecaran-Daughty (1981)が線形時間のアルゴリズムを提案していて，これを中川(2021)がunicycleグラフ上に拡張した．
本研究では，これをカクタスグラフ上に拡張する．
3状態以下有限オートマトンを⽤いた私的観測繰り返しゲームにおける進化的安定戦略分析（ショートトーク）
講演者：森 勇太（筑波⼤学）共著者：澤 亮治（筑波⼤学）
私的観測繰り返し囚⼈のジレンマゲームにおける進化的安定戦略の分析を⾏った．私的観測とは，相⼿の⾏動を⾒ることができない代わりに相⼿の⾏動に依存する不確実なシグナルを受け取り，それを他⼈は⾒ることができない状況を指す．マシンの複雑さに対する明⽰的なコストを仮定したCooper(1996, Journal of Economic Theory)の定義を私的観測に拡張し，3状態以下の有限オートマトンで表される戦略について，数値解析により進化的安定な有限オートマトン戦略を判定した．その結果，2期相互処罰（2-MP）戦略が⾼い利得を達成しながら進化的安定になることが判明した．さらに，相互処罰の期間をkとしたk-MP戦略について，進化的安定の追加検証を⾏ったところ，3-MPが最も広いエラー率の範囲で進化的安定になり，複雑さのコストに関する頑健性は2-MPが最も⾼いことが判明した．
光通信ネットワークにおける波⻑分割法を取り⼊れた資源割当モデルの提案（ショートトーク）
講演者：半⾕ 圭汰朗（筑波⼤学）共著者：王 家⿍（筑波⼤学）呉謙（法政⼤学）繁野 ⿇⾐⼦

近年，IoTやビックデータの活⽤が進み著しく増加するインターネットトラフィックを柔軟に収容するため，エラスティック光ネットワーク(EON)が研究されている．これらの通信ネットワークでは，リクエストの混雑，ブロッキングが発⽣しないよう使⽤する経路と使⽤帯域を適切に決定することが重要である．光通信ネットワーク上の資源割当問題はリクエストの経路と使⽤帯域を決定する問題（RSA問題）であり，数理最適化問題として扱えることが知られている．EONの課題の1つとして，通信を繰り返し⾏う中で使⽤可能な周波数スロットがリンク上に点在するスペクトル断⽚化という現象がある．このスペクトル断⽚化に対処する⼀つの⽅法が，リクエストを分割して送信する波⻑分割法である．本研究では，波⻑分割法を取り⼊れることでスペクトル断⽚化に対応しながらも，より割り当て後のスペクトル断⽚化を起こしにくい資源割当モデルを提案する．数理最適化に基づき資源割り当てモデルを構築，リクエストの割り当てと解放が⾏われる動的なケースを想定したシミュレーションを⾏いモデルの⽐較を⾏った．提案モデルは先⾏研究のモデルと⽐較し特定のシナリオにおいてブロッキング回数，処理時間などの観点で優れることが分かった．
深層学習の最適化⼿法を⽤いたp-メディアン問題の新解法の提案（ショートトーク）
講演者：寺岡 舜⽃（東京海洋⼤学）共著者：久保幹雄（東京海洋⼤学）
施設配置問題のひとつである p-メディアン問題は、各地点が持つ需要量を最寄りの施設に配送す る際の総コストを最⼩化する施設を選択する問題である。p-メディアン問題は、与えられる地点数 が⼤きくない場合、数理最適化ソルバーなどを使⽤することで、厳密解を⾼速に求めることが可能 である。しかし、与えられる地点数が 1000 を超えるような⽐較的⼤規模な問題になると、厳密解 を実⽤的な時間内に求めることは困難になる。この場合、厳密解ではなく近似解法による近似解を 求めることが有効な⼿段となる。p-メディアン問題の近似解法としてはラグランジュ緩和問題が挙 げられる。p-メディアン問題の制約式をラグランジュ緩和することで得られるこの問題の⽬的関数 は区分線形関数となるため、微分不可能である場合がある。微分不可能な関数の最⼩化問題を解く 際には劣勾配法が⽤いられる。しかし、この劣勾配法は挙動が安定しないことがあるため、実務で 使⽤するには注意が必要である。本論⽂では、劣勾配法に近年ブームになっているディープラーニ ングの中で⽤いられる最適化⼿法を導⼊した新たな解法を提案し、その効果を確かめる。
⽊グラフにおける重み付き centdian 問題と故障確率を考慮したbackup centdian問題のアルゴリズムの構築
講演者：中川 祥吾（筑波⼤学）

本研究のテーマである施設配置問題は、社会の利便性や企業の⽴地戦略を考える上で、その理論と応⽤が重要である。施設配置問題では様々な問題が定義されていて、グラフの形状や配置する施設数、評価⽅法によって問題の複雑さは異なる。本研究では、グラフ上で、需要点との距離の最⼤値を最⼩化するように p個の施設を配置するp-center問題と、需要点との距離の合計値を最⼩化するように p 個の施設を配置する p-median 問題のそれぞれの⽬的関数を凸結合したものを⽬的関数としてもつp-centdian問題について扱う。p = 2とした時、過去の研究
ではグラフ上の頂点の重みを考慮していなかった。そこで本研究では、⽊グラフ上でそれぞれの頂点に重みを付けた場合について、すべてのインスタンスに対する最適解を必ず含む有限⽀配集合を特定し、多項式時間アルゴリズムを構築した。また、2-centdian 問題に関して、各施設が故障確率を持っていて、⼀定の確率で⽚⽅の施設が機能しなくなることを考慮した場合の問題についても同様に、有限⽀配集合を求め、多項式時間アルゴリズムを構築した。

15:20-16:50 セッション２（アルゴリズム）
⽇本の⼈⼯林におけるドローンLiDARと地上型LiDAR点群データのレジストレーション
講演者：譚 翌柳（筑波⼤学）

共著者：張 宇攀（筑波⼤学）

我々は, ドローン搭載ライダーシステム（Drone LiDAR System: DLS）と地上据え置き型レーザースキャナ（Terrestrial Laser Scanner: TLS）から得られた⽇本の⼈⼯林の点群データを融合する新しいアプローチを提案する. DLSはキャノピー上部の情報を提供するが, キャノピー中下部や下層の詳細な情報が不⾜している. ⼀⽅, TLSはこれらの要素をより詳細に描写できるが, 森林の全体をカバーできない可能性がある. そこで, 我々は森林環境における最も安定した樹幹をローカライズし, 幾何学的なグラフ特性を基にして概略位置合わせを⾏う. 詳細位置合わ
せは, 点群全体に対する反復ボクセル化プロセスによって, 点群分布の類似度が⾼い部分を抽出することでレジストレーション⼿法を開発する. また, 既存のレジストレーション⼿法と⽐較し, 提案⼿法の有効性を⽰す.
Existence and Estimation of Critical Batch Size for Training GANs with Two Time-Scale
Update Rule
講演者：佐藤 尚樹（明治⼤学）

共著者：飯塚 秀明（明治⼤学理⼯学部情報科学科）

Previous results have shown that a two time-scale update rule (TTUR) is useful fortraining generative adversarial networks (GANs) in theory and in practice. In this talk,we give a theoretical analysis of TTUR using constant learning rates and show that, forTTUR using constant learning rates, the number of steps needed to train GANs
decreases as the batch size increases, and that there exists a critical batch size
minimizing the stochastic first-order oracle (SFO) complexity. Moreover, we show thatmeasured critical batch sizes are close to the sizes estimated from our theoreticalresults.
電波⼲渉計の⾃⼰校正と画像化に対するハイブリッド Bregman 近接 DC アルゴリズム
講演者：⾼橋 翔⼤（東京⼤学）
理研究所）

共著者：⽥中 未来（統計数理研究所），池⽥ 思朗（統計数本発表では天⽂学における電波⼲渉計の観測データから天体画像を復元するために，⾃⼰校正および画像化を交互に⾏うアルゴリズムを提案する．⾃⼰校正では観測データと復元した天体画像から電波⼲渉計の各アンテナの利得を推定し，画像化では観測データと推定した利得から天体画像を復元する．従来の⼿法では，⾃⼰校正において各アンテナの利得を独⽴に推定する．しかし，⾃⼰校正における損失関数は⾮凸・⾮平滑関数であるため，独⽴に利得を推定した場合，収束点への理論的な保証がない．そこで，損失関数の difference of convexfunctions (DC) 構造を⾒つけ，DC 構造と Bregman 距離を利⽤した⼦問題を各反復で解くことで，各アンテナの利得を同時に推定する．これによって，提案アルゴリズムの⽣成する点列は停留点に⼤域的収束することを理論的に証明した．なお，この問題は複素変数実数値関数を⽬的関数とした制約なし最⼩化問題となる．そのため，実関数の極限劣微分の定義を複素変数実数値関数に⾃然に拡張することで，停留点を定義した．本発表では，提案アルゴリズムとその理論的な結果，複素⾮凸最適化理論，天⽂データへの適⽤結果を中⼼に議論する．

8⽉29⽇(⽕)
09:10-10:40 セッション３（連続最適化）
Nonlinear conjugate gradient method for vector optimization on Riemannian manifolds
講演者：Kangming Chen（Kyoto University）共著者：Ellen Hidemi Fukuda （KyotoUniversity）, Hiroyuki Sato （Kyoto University）
In this research, we propose a conjugate gradient descent algorithm for vector
optimization on Riemannian manifolds. We extend the concepts of Wolfe conditions
and Zoutendjik conditions to Riemannian manifolds. The convergence of the proposed
method is proved for different choices of the parameter beta, including the Riemannian
extension of Fletcher-Reeves, Conjugate Descent, and Dai-Yuan. Numericalexperiments are conducted to validate the proposed method.
構造化Broyden公式族に基づいたニュートン型近接勾配法の⼤域的収束性
講演者：⽮部 博（東京理科⼤学）

共著者：中⼭ 舜⺠（電気通信⼤学）、成島 康史（慶應義塾⼤学）
⽬的関数が f(x) = g(x) + h(x) で表される無制約最適化問題の数値解法について考える．ここで，g(x)は平滑なn変数実数値関数とし，h(x)は⾮平滑かつ真凸なn変数実数値関数とする．この問題に対して，近年，ニュートン型近接勾配法がいくつか研究されている．ニュートン型近接勾配法において，g(x)のヘッセ⾏列の近似⾏列をどのように選ぶかが計算効率の観点から重要な課題になっている．本研究では，関数 g(x) のヘッセ⾏列が C(x)+A(x) という特別な構造を持っている問題に注⽬する．ここで，C(x)は容易に計算できる項を表し，A(x)は計算が困難な項を表すものとする．こうした特別な構造を持つ問題として例えば⾮線形最⼩⼆乗問題が代表的である．本研究では，このような最適化問題に対して g(x) のヘッセ⾏列に構造化準ニュートン法を適⽤して，構造化Broyden公式族に基づいたニュートン型近接勾配法を提案し，その⼤域的収束性を⽰す．さらに，具体的な問題としてg(x)が⾮線形最⼩⼆乗問題で表される最適化問題の場合に，実⽤的な更新公式を提案するとともに，数値実験を通して提案アルゴリズムの有効性について検証する．

複素⾏列の階数とその応⽤
講演者：⼩崎 敏寛（ステラリンク株式会社）
複素数は電気の流れ、四元数は制御やCGのモデリングにあらわれる。これらの問題が、多変数の最適化問題または線形計画問題として定式化できれば、内点法などの最適化アルゴリズムを適⽤できる。そこで、最初の段階として、複素数の線形⽅程式を考え、複素数の⾏列の階数を定義する。

11:00-13:00 セッション４（離散最適化）
Round-robin tournament scheduling considering fairness in breaks and travel distance
講演者：Fei Xue（University of Tsukuba）

共著者：Haijunfu MA（University ofTsukuba）， Maiko Shigeno（University of Tsukuba）
In round robin tournament scheduling, it is desirable to minimize the difference in thenumber of home games and away games for each team to ensure fairness. Many sports
leagues impose restrictions on the consecutive number of home games or away games
for the sake of player workload and spectator attendance. On the other hand, some
sports leagues prefer to reduce total travel distance by favoring breaks. In this study,
we aim to create a schedule that considers fairness and maximizes the number ofbreaks provided that at most two consecutive home/away games are allowed. The
scheduling process is conducted in two stages, resulting in optimal home-away tables
under 36 teams. In addition, the travel distance of the game schedule with the least
break and the largest break is compared.
⼯事⽴会者⼿配業務に対する数理モデルと実践的解法
講演者：⾼須賀 将秀（⻄⽇本電信電話株式会社）
近年，通信技術や情報技術の発展により，今まで⼈⼿で⾏ってきた業務が計算機等で⾏う業務に代わりつつあり，デジタル化が進んでいる．それに伴い，⼈⼿で⾏っ てきた意思決定も，デジタル情報を⽤いた計算機等と⼈⼿によるハイブリッドな⽅法に年々変化している．計算機を⽤いて意思決定の⽀援を⾏うためには，意思決定の過程を数理モデルとして表現し，その数理モデルを解くための実践的解法が必要となる．しかしながら，この過程を数理モデルとして表現したり，実践的解法を実装することは容易ではない．その理由の1 つとして，実社会の要件は多様であり， 少し要件が異なるだけで異なる数理モデルになり，それを解くための実践的解法も異なる場合が多いため，解決したい問題が現れるたびにモデル化と解法開発が必要になって，その都度⼤きな労⼒が必要になってしまうことが挙げられる．また，数理モデルや実践的解法の研究を⾏う⽴場の⼈と，実社会で⽇々それらの課題に直⾯している現場の⼈はの間の交流が少ないため，実社会への活⽤に向けた検討に⾄りづらい．そのため，2 つの⽴場に関わり，数理モデルや実践的解法の活⽤事例を増やしていくことが求められている．本稿では，実社会に存在する課題を解決する試みの⼀環として，⽇本電信電話株式会社で⽇々⾏っている意
思決定の業務の⼀事例を取り上げ，数理モデルとそれに対する実践的解法を検証した結果について述べる．
⽣活圏と世代を意識した選挙区割
講演者：鮏川 矩義（法政⼤学）
波⼤学）

共著者：松原 千波（株式会社NTTデータ）、⼤澤 義明（筑現在、衆議院議員465議席のうち、289議席が⼩選挙区制で選出されている。これら289議席は、茨城県に7議席、北海道に12議席、東京に30議席といった具合に、⼈⼝に応じて各都道府県に配分され、各都道府県には議席数分の選挙区が定められている。選挙区の区割（選挙区割）は、各選挙区を構成する市区町村を定めるもので、⺠意と⾏政をつなぐ重要な役割を果たしている。既存研究は、⼀票の格差の是正を主な⽬的として、選挙区割の数理最適化モデルを確⽴し、勧告案の改善⽅法を⽰している。本研究では、選挙区割が関係する２つの別の問題、①⾏政圏と⽣活圏の不調和と②少⼦⾼齢化に伴うシルバー⺠主主義に焦点を当て、それらの理解や解決のための選挙区割の数理最適化モデルを導⼊する。①に対しては、モバイル空間統計
データと呼ばれる携帯電話の位置情報を利⽤した⼈流の推定値を利⽤して⽣活圏を捉え、選挙区割との調和度を定量的に評価する枠組みを提案する。②に対しては、市区群分割と呼ばれる、やむを得ず実施される、市区町村の分割の代替案として、世代の観点で市区町村を分割する枠組みを提案する。
準M♮凸関数の最⼩化に関する諸性質
講演者：塩浦 昭義（東京⼯業⼤学）

共著者：室⽥ ⼀雄（統計数理研究所，東京都⽴⼤学）

本発表では，離散準凸関数のクラスである半狭義準M♮凸関数を扱う．離散凸解析において，M凸性の変種として(普通の) M♮凸性が提案されており，M♮凸関数の準凸版として半狭義準M♮凸関数の概念が提案されている．この概念に対し，数理経済学やOR分野への応⽤が知られている．(普通の) M♮凸関数はM凸関数の（⼀次元低い空間への）射影として定義されており，ある種の交換公理により特徴付けできるが，その交換公理を弱めた性質により，半狭義準M♮凸関数は定義される．本発表の⽬的は，半狭義準M♮凸関数の最⼩化に関する諸性質を調べることである．（普通の）M♮凸関数に対して，局所最適性を⽤いた最適性条件，最⼩解カット性，測地線性，近接性といった性質が成り⽴つことが知られている．これらの性質のうち，局所最適性を⽤いた最適性条件，および弱い形の最⼩解カット性を半狭義準M♮凸関数が満たすことを⽰す．⼀⽅，測地線性および近接性が半狭義準M♮凸関数に対して成り⽴たないことを，反例を使って⽰す

13:00 閉会の挨拶