写像minとmaxとAffine写像の合成写像による区分線形写像の特徴付け

導入

この記事は数理最適化 Advent Calendar 2024 9日目の記事です．

区分線形写像(piecewise linear map, PL写像)は，最適化問題，機械学習，統計学，制御理論，位相幾何学などで出てくる，基本的な関数である．
今回は，区分線形写像の特徴付として，minとmaxとAffine写像の合成写像で与えられることを紹介する．

定理 1. (c.f [Kit2024])
写像$h : \mathrm{dom} h (\subset \mathrm{R}^d)\to \mathbb{R}^{d'}$を$\mathrm{dom} h$が凸多面体であるものとする．このとき，以下同値である．
(1) 写像$h$は区分線形写像である，つまり，ある凸多面体の有限の属$\mathcal{Q}$が存在して，$\mathrm{dom} h = \bigcup_{Q \in \mathcal{Q}}Q$かつ$h |_{Q}$はAffine写像．
(2) 写像$h$は$\min$と $\max$とAfiine写像の合成で書ける，つまり，各成分$h_k (k=1, \ldots, d)$に対して，$I_k$, $J_{ik}$, $A_{ijk} \in \mathbb{R}^{d \times d'}$，$b_{ijk} \in \mathbb{R}$が存在して，

$$h_k (x) = \min_{i \in I_k} \max_{j \in J_{ik}} (A_{ijk}^{\top} x + b_{ijk}).$$

(2)’ 写像$h$は$\min$と$\max$とAfiine写像の複数回合成で書ける.
(3) 写像$h$は多面体的，つまり$h$のグラフ$\{ (x , h(x)) | x \in \mathrm{dom} h \}$は多面体である．

ただし，凸多面体を，有限個の点の凸包で得られる集合とし，
多面体を凸多面体の有限をとして定義する．

定理 1の各条件の由来

• (1) 区分線形写像の直感的な定義として用いられる(c.f. wikipedia)．

• (2) 数理最適化で出てくる．特に，混合整数線形計画で定式化しようとするときに出てくる(c.f. [kel2020])．

• (3) 数理科学の位相幾何学の分野の一つである，PLトポロジーで出てくる(c.f [yam2018])．PLトポロジーの理論を展開する際に，(3)の性質を湯水のように使う．

定理 1の応用例

• 解が与えられたときに，解が混合整数線形計画の最適解になるような目的関数の重みを決定する問題(逆最適化問題)を高速で解くためのアルゴリズムに関する理論保証で使われる[Kit2024]．

定理1の強みは，たとえば混合整数線形計画の最適解となり得る集合は，実質，有限点群で表されることが証明できる点である．

誰が証明したか

(3)ならば(1)はStallings-Swarupの定理 2.2.4で証明されている．

(1)ならば(2)はOvchinnikovの2節で証明されている．

(2)ならば(2)'は定義から従う．

(2)'ならば(3)は著者が証明した．

参考文献

[kel2020] kelicht, 整数計画法による定式化テクニックをまとめたい, 2020, avaiable at 締め切り駆動開発.

[Kit2024] A. Kitaoka, A fast algorithm to minimize prediction loss of the optimal solution in inverse optimization problem of MILP, 2024, Available at arXiv:2405.14273

[Ovc2002] S. Ovchinnikov, Max-min representation of piecewise linear functions, Contributions
to Algebra and Geometry 43 (2002), no. 1, 297–302.

[SS1967] J. R. Stallings and G. A. Swarup, Lectures on polyhedral topology, Vol. 43, Tata
Institute of Fundamental Research Bombay, 1967.

[yam2018] yamyamtopo, PLトポロジーの基礎, 2018, Available at トポロジーいろいろ.