京都⼤学数理解析研究所 共同研究（公開型）
数理最適化の進展とその周辺
2024年8⽉26⽇(⽉)，27⽇(⽕)
ハイブリッド開催（RIMS 110号での対⾯とZOOM）

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

プログラム
8⽉26⽇(⽉)
10:00

開会の挨拶

10:00-12:00 セッション１（ゲーム・スケジューリング）
３チームで対戦するセーリングリーグ問題
講演者：繁野 ⿇⾐⼦（筑波⼤学）共著者：⾺ 海俊夫（筑波⼤学）
スポーツスケジューリングは，様々な試合形式での対戦表作成を対象としている．本研究では，１試合で複数チームが同時に対戦する問題を扱う．複数チームが同時に対戦するときに，試合を⾏うラウンド数が与えられていて各チームは１ラインドでちょうど１試合⾏うときに，チーム対ごとの対戦数の差を最⼩化する．この問題は，セーリングの試合形式に基づいていて，Schuler-Schurmann(2024)はセーリングリーグ問題と呼んでいる．この問題は，balanced incomplete block designと関連しており，3チームで対戦するときは，カークマンの⼥学⽣問題の拡張とみなせる．本報告では，3チームで対戦するときを対象とし，チーム数とラウンド数の条件を整理して，最適値がわかるケースを⽰す．
動的最短経路阻⽌モデルの拡張と観察
講演者：和⽥ 信太郎（筑波⼤学）共著者：繁野 ⿇⾐⼦（筑波⼤学）
動的最短経路阻⽌(Dynamic Shortest-Path Interdiction, DSPI)は, 攻撃者とユーザーによる動的なネットワークゲームである. ユーザーは有向ネットワーク内の最短経路を⾒つけようとし, 攻撃者はユーザーの最短経路のコストを最⼤化するためにアークを阻⽌する. 攻撃者は決められた本数だけアークを阻⽌することができ, 阻⽌されたアークはコストが増加する. 攻撃者はユーザーがネットワーク内を移動する度にアークを阻⽌することができ, ユーザーは阻⽌に対して次に進むノードを選択することができる. Sefair & Smith(2016)は, DSPIモデルに対して動的計画法による指数時間アルゴリズムを提案している. 本研究では, DSPIモデルを拡張し, 阻⽌に関する制約を設けた場合の観察を⾏う. 具体的には, 阻⽌本数があるときは必ず阻⽌しなければいけない場合や, 1度に阻⽌できるアークの本数に条件を与えた場合などを観察する.

特許ライセンスゲームにおける安定集合の存在性対する⼗分条件
講演者：⼤林 渓（電気通信⼤学）共著者：⾼橋 ⾥司（電気通信⼤学）

本研究では，コアが空である可能性のある提携型ゲームにおける安定集合の存在性に対する⼗分条件を与える．具体的に，特許ライセンスの売り⼿である特許権者と，買い⼿である企業のライセンス交渉を提携型ゲームとして定式化した特許ライセンスゲームを考える．⼀般にコアが空である提携型ゲームにおいて，安定集合を構成することは困難であるとされており，先⾏研究では，特許ライセンスゲームにおいて，縮⼩ゲームのコアを⽰し，そこから安定集合を構成し，存在性の⼗分条件を与えている．本研究では，企業数3のゲームに対して，提携企業数2の場合について，先⾏研究で与えられた安定集合とは別の安定集合が存在するための⼗分条件を⽰す．また，先⾏研究で⽰されている具体例で述べられている差別的安定集合の唯⼀性も⽰す．
Ex ante and ex post envy-freeness on polytope resources
講演者：Zhan Ping（江⼾川⼤学）共著者：佐野 良夫（筑波⼤学）
Allocating goods among agents under ordinal preferences is a well-studied problem. In
this study, each type of good may have multi-copies with quotas varying in a polytope.
When goods are indivisible, it is difficult to achieve exact fairness, but various
approximations have been suggested. An exact ex ante envy-freeness (before therandomization or decomposition is realized) can be obtained based on past research.
This study achieves the envy-freeness for up to two copies of goods based on a``nearest" structure. The fairness is called ``Best-of-Both-Worlds (BoBW),'' meaning it
achieves the best possible fairness notions in both the ex ante and ex post senses, orbefore and after randomization. What differentiates this work is that we deal with themulti-copies of goods and integer demands, i.e., each entry of a discrete allocation canbe an {arbitrary positive integer} instead of a binary number. Although ourapproximation is for {two} copies of goods, instead of {one} indivisible good, this maylead to a much better approximation when the number of copies is larger. Additionally,
these allocations are also efficient in stochastic dominance (a Pareto optimality). We
give a solution to this problem by constructing box-integer networks. Moreover, therandomized allocations can be obtained in polynomial time when the resource
polytope is a polymatroid through computing so-called independent flows.

13:00-15:00 セッション２（離散アルゴリズム）
区間グラフ上の最⼤重み付き独⽴集合問題に対する省領域アルゴリズム
講演者：松本 直仁（成蹊⼤学）共著者：清⾒ 礼(成蹊⼤学)
与えられた重み付きグラフに対して，互いに隣接しない頂点の集合を独⽴集合という．最⼤重
み付き独⽴集合問題は，最も重み和の⼤きい独⽴集合を求める問題であり，組み合わせ最適化問題の中でも重要なものである．特に，区間グラフ上の独⽴集合問題は重み付き区間スケジューリング問題としても有名であり，動的計画法を⽤いて解くことができる．また，Savitchによれば指数時間をかけることにより，O(log^2 n) bitsの領域で解くことができる．
本研究では，Savitchのアルゴリズムを改良することにより，省領域かつ多項式時間の解法を与える．この⼿法は分割統治法を利⽤したものであり，多くの多項式時間アルゴリズムが改良されると期待できる．

深層学習の⼿法を⽤いた容量制約付きk-メディアン問題
講演者：寺岡 舜⽃（東京海洋⼤学）共著者：久保 幹雄（東京海洋⼤学）
施設配置問題のひとつである k-メディアン問題は、各地点が持つ需要量を最寄りの施設に配送する際の総コストを最⼩化する施設を選択する問題である。地点数が 1000 を超えるような⽐較的⼤規模な問題になると、厳密解を実⽤的な時間内に求めることは数理最適化ソルバーを⽤いても困難になる。この場合、厳密解ではなく近似解法による近似解を求めることが有効な⼿段となる。k-メディアン問題の近似解法としてはラグランジュ緩和と劣勾配法を⽤いた⼿法が挙げられる。しかし劣勾配法は挙動が安定しないことがあるため、深層学習で⽤いられる⼿法を導⼊した解法で代替を検討した。ここでは、容量制約付きk-メディアン問題に対して、既存の解法と⽐較して性能を確認する。

An approximation algorithm for K-best enumeration of minimal connected edge
dominating sets with cardinality constraints
講演者：和佐 州洋（法政⼤学）共著者：栗⽥ 和宏（名古屋⼤学）
K-best enumeration is a helpful tool in data analysis for many fields. However, k-best
enumeration tends to be intractable since, in many cases, finding one optimum
solution is NP-hard. To overcome this difficulty, we combine k-best enumeration with aconcept of enumeration algorithms called approximation enumeration algorithms. As amain result, we propose a 4-approximation and k-best enumeraion algorithm forminimal connected edge dominating sets with polynomial delay.
有向グラフの平⽅根計算問題に対する整数計画法
講演者：鮏川 矩義（法政⼤学）共著者：平⽥ 祥⼈（筑波⼤学）与えられた正⽅⾏列Ｙに対し，⼆乗するとＹに⼀致するような正⽅⾏列Ｘを求める問題を⾏列の平⽅根計算問題と呼ばれる．本発表ではブール⾏列に対する平⽅根計算問題を扱う．同問題に対しては，ブール⾏列をグラフ理論における接続⾏列とみなすことで，グラフ理論の技法に基づくアルゴリズムが開発されてきた．たとえば，与えられた正⽅⾏列が⽊グラフなどの特徴的な単純無向グラフの接続⾏列となる場合には多項式時間アルゴリズムが知られている．⼀⽅，⼀般の場合にはNP-完全であることが⽰されている．本発表では，この⽂脈において，⾮線形時系列への応⽤に動機づけられて，ブール⾏列Ｙとブール⾏列Ｘのどちらの対⾓成分もすべて１の場合（グラフ理論における隣接⾏列を⽤いた⾒⽅では，各頂点が⾃⼰ループを持つ場合）について議論する．ブール⾏列に対する平⽅根計算問題は（⽬的関数の無い）整数計画問
題として定式化できるが，対⾓成分がすべて１であるという設定を活かした前処理と定式化の改善⽅法を提案し，その有効性を検証するための数値実験の結果を報告する．

15:20-16:50 セッション3（不確実性）
インフルエンサーマーケティングにおける影響⼒最⼤化問題に対するBenders分解
講演者：江頭 唯（電気通信⼤学）共著者：村松 正和(電気通信⼤学)

SNSを利⽤したマーケティング⼿法の⼀つにインフルエンサーマーケティングがある。これはSNS内の影響⼒のある⼈物（インフルエンサー）に商品を紹介してもらうことで、顧客の購買意欲を⾼めるものである。本研究では、ライバル企業がいる場合に、⾃社の商品をなるべく多くの⼈に知ってもらうインフルエンサーマーケティングを数理モデル化し、期待値を最⼤化する問題（影響最⼤化問題）を考える。この問題においては、ある⼈が別の⼈に影響を与えるか否かが確率によって与えられている。確率空間が巨⼤なため、影響最⼤化問題を正確に解くことは難しい。そのため、確率空間を限定し、Benders分解を⽤いて影響最⼤化問題を解く。
Benders分解では主問題に対して、主問題における変数を固定した問題の双対問題を何回も解くことが重要であるが、本研究では双対問題を⾼速に解くことができることを⾒出した。 実験の結果、我々のBenders分解を⽤いた⽅法は、⼀般的なMIPソルバーを⽤いるよりも⾼速に解を求めることができた。今後は、得られた解でシミュレーションを⾏い、最適値との⽐較やサンプルサイズの適切性を検証する予定である。
最⼤リグレット最⼩化0-1整数計画問題に対するコア選択法
講演者：⻑⾕川 和樹（静岡⼤学）共著者：呉 偉（静岡⼤学），柳浦 睦憲（名古屋⼤学）
ナップサック問題や集合被覆問題をはじめとして，古典的な0-1整数計画問題（binary integerprogramming problem, BIP）では各決定変数に対する⼊⼒は確定していた．しかしながら，現実世界の問題を考えると多くの⼊⼒データには不確定さが内在している．本研究で扱う最⼤リグレット最⼩化BIP（min-max regret BIP, MMR-BIP）では，⽬的関数に関わる⼊⼒に対して不確定さを考慮する．MMR-BIPの特殊ケースである最⼤リグレット最⼩化巡回セールスマン問題（min-max regret traveling salesman problem, MMR-TSP）に対してコア選択（core selection, CS）法という発⾒的解法を提案し，MMR-TSPに対しては既存の解法を上回る結果を確認することができた．本研究ではCS法を⼀般化されたMMR-BIPにも適⽤できるように改善する．最⼤リグレット最⼩化基準の下でのナップサック問題，多次元ナップサック問題，⼀般化割当問題，集合被覆問題のベンチマーク問題例に対して計算実験を⾏い，既存の解法と⽐較して性能を確認する．
確率密度モデルに基づいた2種類のレーザースキャナの森林点群レジストレーション
講演者：譚 翌柳（筑波⼤学）共著者：繁野 ⿇⾐⼦（筑波⼤学）
LiDARは，森林調査に広く利⽤されるリモートセンシング技術である．その中で，地上型レーザースキャナ（TLS）と無⼈航空機搭載レーザースキャナ（UAV-LS）は，代表的な森林観測プラットフォームとして知られている．本研究では，TLSとUAV-LSで収集した点群のレジストレーションを⾏う新しいアルゴリズムを提案する．
提案⼿法では，まずセグメンテーションによって樹⽊点のクラスターを作成し，各クラスターから幾何的特徴を抽出する．具体的には，離散モース理論を⽤いてクラスターの点群から3次元の単体で構成される複体を⽣成し，スカラー関数の極⼩点をキーポイントとして検出する．キーポイントの特徴分布を評価することで，クラスター間の類似度を計算する．
次に，ガウス混合モデルを⽤いて点群の類似度を考慮したレジストレーションパラメータを最尤法で推定する．得られたレジストレーションパラメータは，疎⾏列を使⽤して解の精度を向上させるために調整される．

8⽉27⽇(⽕)
9:30-11:00

セッション4（連続最適化とアルゴリズム１）

On sequential optimality conditions for second-order cone optimization
講演者：福⽥ エレン 秀美（京都⼤学）共著者：岡部 公亮（京都⼤学）
We begin the presentation with an overview of sequential optimality conditions fornonlinear programming and nonlinear second-order cone programming (NSOCP)
problems. Subsequently, we introduce the proposed second-order optimality
conditions for NSOCP, called approximate Karush-Kuhn-Tucker 2 conditions (AKKT2),
which do not require any constraint qualification. We demonstrate the validity of
AKKT2 and discuss how some well-known methods can be adapted to generate AKKT2points.
On Second-Order Sequential Optimality Conditions for Nonlinear ProgrammingProblems
講演者：李 慧⺠（京都⼤学）共著者：⼭川 雄也(京都⼤学)

福⽥ エレン 秀美(京都⼤学)

Algorithms for finding second-order stationary points are desirable, but dealing withthe whole critical cone is computationally difficult. One initial step towards such
implementable algorithms was given by the Strong Second-Order Approximate KKT(henceforth SAKKT2) condition for Nonlinear Programming (NLP) problems. We show
SAKKT2 is a necessary condition of local minimizer for NLP without requiring anyassumptions.

Computing local minimizers in polynomial optimization under genericity conditions
講演者：Vu Trung Hieu（RIKEN）共著者：Akiko Takeda （University of Tokyo）
This talk focuses on computing local minimizers of a multivariate polynomial
optimization problem under certain genericity conditions. By using a technique incomputer algebra and the second-order optimality condition, we provide a univariate
representation for the set of local minimizers.
In particular, for the unconstrained problem, i.e. the constraint set is $R^n$, thecoordinates of all local minimizers can be represented by the values of $n$ univariate
polynomials at real roots of a system including a univariate polynomial equation and a
univariate polynomial matrix inequality.
We also develop the technique for constrained problems having equality/inequality
constraints. Based on the above technique, we design symbolic algorithms toenumerate the local minimizers and provide experimental examples based on hybrid
symbolic-numerical computations. For the case that the genericity conditions fail, we
propose a perturbation technique to compute approximately a global minimizer
provided that the constraint set is compact.

11:10-12:10 セッション5（集合）集合最適化問題における⾮線形スカラー化⼿法：20年余の研究史と最新の動向（オンライン）
講演者：荒⾕ 洋輔（秋⽥県⽴⼤学）
最適化問題のカテゴリーの⼀つである多⽬的（ベクトル）最適化問題とは、関数の値域空間にベクトル順序を導⼊することによりベクトルの⽐較を⾏い、その順序における最⼩（Pareto最適解）などを議論する分野である。
集合最適化問題とは最適化問題の１つのカテゴリーで、多⽬的最適化問題・区間解析の⾃然な拡張である。研究発⾜から20年余の新興分野である。ベクトル順序の⾃然な拡張である「集合順序関係」は、社会的選択理論でのある種の選好になっている。2014年にIde et al.の研究から、多⽬的ロバスト最適化問題は集合最適化問題の応⽤として変換できることが判明した。
また、同じく2014年にHamel et al.の研究で、特別なクラスの集合最適化問題は束(lattice)の構造を持つことが判明した。
Tammerが提唱したベクトルの⾮線形スカラー化関数（効⽤関数）は、Pareto最適解を⼗分に特徴づけ出来るという利点がある。本発表では、Tammerの⾮線形スカラー化関数を⾃然に拡張する研究について、20年余の研究史を概説する。さらには、発表者の最新の研究成果について紹介する予定である。

Borsukの対⼼定理の応⽤：集合の評価付け定理
講演者：川崎 英⽂（九州⼤学）
Borsukの対⼼定理は「n次元球⾯S^nからn次元ユークリッド空間R^nへの連続写像 f にはf(u)=f(-u)を満たす点 u∈S^nが存在する．」と主張する．n個のコンパクト集合A_1,…A_n⊂
R^nに対し，u=(u,u_(n+1) )∈S^nとして，n個の連続関数 δ^* (u∣A_i )+δ_* (u∣A_i )u_(n+1) にBorsukの対⼼定理を適⽤することにより，A_1,…A_nの集合幅を同時等分割する超平⾯の存在を⽰した．これはHam-Sandwich定理に類似する結果であるが，本研究はHamSandwich定理にないタイプの結果を含む．それは集合（グループ）A_1,…A_nに所望の評価を与える重みu∈S^nが存在するというものである．本研究では，それを集合の評価付け定理と呼ぶ．

13:30-15:00 セッション6（連続最適化とアルゴリズム２）
Randomized submanifold method for optimization on the Stiefel manifold
講演者：POIRION Pierre-Louis（理研）共著者：Han Andi (RIKEN), Takeda Akiko (TokyoU. / RIKEN))
In this talk, we consider an optimization problem over the Stiefel manifold. We willpropose an iterative algorithm that consider, at each iteration, a function restricted toa small random sub-manifold on which retractions can be performed at a small cost.
We will prove convergence of our method and illustrate the results numerically.
微分不可能な正則化項を含む多⽬的最適化問題に対する準ニュートン型近接勾配法について
講演者：桑原 寛⼤（慶應義塾⼤学）共著者：成島 康史（慶應義塾⼤学）

本研究では、各⽬的関数が平滑な関数と⾮平滑な関数（正則化項）の和で表される多⽬的無制約最適化問題に対する準ニュートン型近接勾配法を提案する。近年、正則化項付き単⽬的最適化問題を解く⼿法について、多くの研究が⾏われており、その⼀つとして近接勾配法が注⽬されている。さらに近接勾配法の拡張として、ニュートン法や準ニュートン法の概念を取り⼊れた（準）ニュートン型近接勾配法が提案されている。⼀⽅で正則化項付き多⽬的最適化問題においては、ニュートン型近接勾配法が提案されてはいるものの、準ニュートン型近接勾配法については提案されていない。そこで本研究では、⽬的関数の平滑な部分のヘッセ⾏列の近似を使⽤し、探索⽅向を決定する準ニュートン型近接勾配法の考え⽅を多⽬的最適化問題に拡張する新たな⼿法を提案し、その⼿法の収束性について議論する。さらに、L1正則化項を含む多⽬的最適化問題に対して、数値実験を⾏い、提案⼿法の有効性を検証する。

L1正則化項を含んだ無制約最適化問題に対するニュートン型近接勾配法の上界近似を⽤いた加速について
講演者：成島 康史（慶應義塾⼤学）共著者：辺 浩（慶應義塾⼤学）
本講演ではL1正則化項を含んだ無制約最適化問題に対するニュートン型近接勾配法を考える．
通常の近接勾配法では，（例えばL1正則化などといった）典型的な正則化項の場合には探索⽅向を容易に計算できるという利点がある．⼀⽅，ニュートン型近接勾配法では，探索⽅向の計算に部分問題を解く必要があり，その計算が全体の計算量の⼤部分を占めてしまう．そこで，今回は部分問題の⽬的関数を２次関数で上界近似することにより，探索⽅向の計算の容易化を図る．さらに，近似⾏列としてメモリーレス準ニュートン法を⽤いることにより，探索⽅向が陽に表せることを⽰す．
他⽅，提案した⽅法では部分問題において近似を⽤いているため，⼤域的な収束性の保証がない．そこで，提案した⽅法を既存のニュートン型近接勾配法の加速ととらえ，加速を⽤いる基準を提案し，その基準の下での⼤域的収束性を議論する．最後に数値実験により加速の効果を検証する．

15:20-16:50 セッション7（回帰モデルと最適化）
ポアソン回帰のスパース推定に対する問題規模縮⼩法
講演者：栗原 昂汰（九州⼤学）共著者：伊⾖永 洋⼀（九州⼤学）
あるイベントの発⽣回数のような⾮負整数値をとるカウント変数を，与えられたデータから予測する⽅法の⼀つにポアソン回帰があり，交通事故や⾃然災害の発⽣予測など多くの応⽤を有する．⼀般に，回帰モデルに含まれる特徴量の数が多いほど予測精度の向上が期待できるが，⼀⽅でモデルが複雑になり，過学習が発⽣する可能性がある．したがって，適切な特徴量を選択し，スパースなモデルを推定することが重要である．
しかし，適切な特徴量選択のために，ポアソン回帰モデルの推定に対して基数制約を課した問題は，基数制約が⾮線形・不連続な関数で表現される制約であることから，⼤規模なデータに対しては実⽤的な時間で解くことができない．
本研究では釘付けテストと呼ばれる，元問題の実⾏可能解と，その緩和問題の最適解の情報から元問題の最適解の⼀部を特定する⽅法を⽤いて，解くべき問題の規模を縮⼩する⽅法を提案する．また，計算機実験により，提案⼿法の有効性を⽰す．

Damped semismooth Newton method for LASSO problems
講演者：中⼭ 舜⺠（電気通信⼤学）
変数選択を⾏う線形回帰の⼀つとしてLASSO回帰があり，線形最⼩⼆乗問題にL1正則化を加えた最⼩化問題である．このような平滑な関数と⾮平滑な関数の和で表せる問題は，近接勾配法を⽤いて解くことができる．また，この問題の最適性条件は近接勾配法の反復ステップが不動点になっていることである．近年，この不動点問題を半平滑な⾮線形⽅程式として定式化し，semismooth法を⽤いて解く研究が注⽬を集めている．適当な仮定のもとでsemismoothは超⼀次や2次収束という速い収束率を誇るが，強凸関数などの仮定がなければ⼤域的収束の保証がない．本研究では，Damped semismooth Newton法と近接勾配法を組み合わせた⽅法を提案し，提案アルゴリズムの⼤域的収束性を⽰す．また，数値実験を通じて提案アルゴリズムの有効性について検証する．
双複素線形計画問題の弱双対定理
講演者：⼩崎 敏寛（ステラリンク株式会社）
双複素線形計画問題を考える。
はじめに、複素数の拡張である双複素数(bicomplex number)を導⼊する。双複素数は複素数の実数に制限されている成分を複素数にしたものである。
次に、双複素数に対する共役を利⽤し、実数の線形計画問題の拡張である双複素線形計画問題を導⼊する。ここで⽬的関数は実数値、変数は双複素変数のベクトルである。そして双対問題を導⼊する。
最後に、主双対内点法で解を求めるには重要な役割を果たす弱双対定理を証明する。
16:50

閉会の挨拶