Ctrl+K

射影と抽出

7. 射影と抽出#

7.1. 導入#

射影は多次元集合の各成分をそれぞれ高々 \(1\) つ選び出して，より小さい次元へと落とす写像のことである． 一方で我々が以下で述べるところの抽出はその限りではなく，必要な成分を望む順序で必要な数だけ選び出すことを許容する写像である． 数理最適化では抽出が基本的な演算になっており，これに慣れることで自由度の高い定式化にも慣れ親しむことができる．

7.2. 射影とは#

多次元集合 \(M\) の要素を \((a_1,\ldots,a_m)\) とするとき， 第 \(i_1\) 成分から第 \(i_n\) 成分についての次の写像を射影とよぶ． 但し \(i_1<\cdots<i_n\) とする．

(1)#\[\pi_{i_1,\ldots,i_n}\colon M\to M^{\prime}; \to (a_1,\ldots,a_m) \mapsto (a_{i_1},\ldots,a_{i_n})\]

例えば \(M=\{(1,2,3),(4,5,6),(7,8,9)\}\) である場合に，次の写像は何れも射影である．

(2)#\[\begin{split}\pi_{1}(M) &= \{1,4,7\}, \\ \pi_{3}(M) &= \{3,6,9\}, \\ \pi_{2,3}(M) &= \{(2,3),(5,6),(8,9)\}\end{split}\]

上記は PySIMPLE では次のように対応している．

1from pysimple import Set
2
3M = Set(value=[(1, 2, 3), (4, 5, 6), (7, 8, 9)])
4print(M(0))    # M(0)=Set(value=[1, 4, 7])
5print(M(2))    # M(2)=Set(value=[3, 6, 9])
6print(M(1,2))  # M(1,2)=Set(value=[(2, 3), (5, 6), (8, 9)])

Tip

定義に従えば，\(\pi_{1}(M) = \{(1),(4),(7)\}\) と成分数が \(1\) の組に本来は射影される． このとき，\({1,4,7}\) と等しいことは必ずしも自明ではなく，等しくはないが， 本稿では集合論を背景に持つモデリング言語の実装系との対応を考える場合には，同一視して扱うことにする．

7.3. 抽出とは#

射影は幾何学的な事柄を背景に持っており， 高次の図形を低次の空間へと影を落としたように得られる図形に対応させる写像としての意味合いが強い． このため例えば \(M=\{(1,2,3),(4,5,6),(7,8,9)\}\) から \(M^{\prime}=\{(3,2),(6,5),(9,8)\}\) という集合を得る操作は， 射影 \(\pi_{2,3}\) と二つの成分を互換する写像 \(\tau\) の合成になっている 1互換 (transposition) と関係代数での選択の標準的な記号はともに \(\sigma\) であり，異なる概念についての記号が被ってしまう．本稿では互換よりも選択が重要なため，選択に \(\sigma\) を割り当てることにしている．． というように，射影だけでない他の写像も必要になってくる．

しかし数理最適化の文脈では，幾何学的な背景を考慮してもあまり実りあるものではなく， どちらかと言えば，そのようなことを気にするあまり，正確を期すほどより煩雑な記述になってしまう．

我々はこのような徒労を避けるために，抽出 とよぶ操作を定め，より複雑な定式化を柔軟に行うために用いている．

抽出とは多次元集合の要素の組み合わせを維持しながら，各成分を任意の順序で，任意の数だけ取得する操作として定める．

(3)#\[\epsilon_{s_1,\ldots,s_k}\colon M\to M^{\prime}; (a_1,\ldots,a_m) \mapsto (a_{s_1},\ldots,a_{s_k})\]

ここで \(s_1<\ldots<s_k\) や \(k\leq m\) といった制約はなく，自由度の高い操作になっている．

例えば \(M=\{(1,2,3),(4,5,6),(7,8,9)\}\) である場合に，次の写像は何れも抽出である．

(4)#\[\begin{split}\epsilon_{1,1}(M) &= \{(1,1),(4,4),(7,7)\}, \\ \epsilon_{3,2}(M) &= \{(3,2),(6,5),(9,8)\}, \\ \epsilon_{1,3,2,1}(M) &= \{(1,3,2,1),(4,6,5,4),(7,9,8,7)\}\end{split}\]

上記は PySIMPLE では次のように対応しており，そもそも抽出を基礎とした記述になっている．

1from pysimple import Set
2
3M = Set(value=[(1, 2, 3), (4, 5, 6), (7, 8, 9)])
4print(M(0,0))      # M(0,0)=Set(value=[(1, 1), (4, 4), (7, 7)])
5print(M(2,1))      # M(2,1)=Set(value=[(3, 2), (6, 5), (9, 8)])
6print(M(0,2,1,0))  # M(0,2,1,0)=Set(value=[(1, 3, 2, 1), (4, 6, 5, 4), (7, 9, 8, 7)])

Tip

射影を記述する共通に普及した専用の記号は (数学の中で緩やかな合意として)， \(p\), \(\pi\) や \(\Pi\) 果ては \(\varpi\) など projection の p を意図した写像を書くことで表現されることが標準的である． 特に関係代数では \(\pi\) や \(\Pi\) が意識して記号選定される．

一方で抽出に至っては何かあるわけではない． 数理最適化の定式化では，抽出は頻出するため，できれば専用の記号が欲しいところであるが，残念ながらない． extract の e から \(\epsilon\) を選定することにした．

注釈

関係代数では個々の演算を拡張したものを必要に応じて導入されることがある． その中でも，通常の射影 \(\pi\) について，次の二つの操作を許すよう拡張した演算 \(\Pi\) を一般化射影 (generalized projection) という．

  1. 各成分を任意の順序で，任意の数だけ取得して射影してよい．つまり，抽出である．

  2. 各成分について算術演算した結果を射影してよい．

7.4. 要素からの参照#

射影や抽出は集合から新たな集合を導くものであったが， 多成分の要素から，射影や抽出と同様の意味で新たな要素 (の集まり) を対応させる操作も数理最適化の定式化では重要である．

この操作は \((a_1,\ldots,a_m)\in M\) に対して，次のように書かれるものである．

(5)#\[\epsilon_{s_1,\ldots,s_k}\colon (a_1,\ldots,a_m) \mapsto (a_{s_1},\ldots,a_{s_k})\]

この操作によって，例えば次の数式を記述できるようになる．

(6)#\[\sum_{m\in M}WT_{\epsilon_1(m)}\cdot x_m\]

これは \(x\) については多成分の要素 \(m\) そのものを添字としている一方で， \(WT\) については \(m\) の第 \(1\) 成分のみを参照する添字についての和であることを意図した数式である．

集合への抽出操作と同様に，要素についても PySIMPLE では次のように対応した言語になっている．

1from pysimple import Set, Element
2
3M = Set(value=[(1, 2, 3), (4, 5, 6), (7, 8, 9)])
4m = Element(set=M)
5print(m(0,0).set)      # m.set(0,0)=Set(value=[(1, 1), (4, 4), (7, 7)])
6print(m(2,1).set)      # m.set(2,1)=Set(value=[(3, 2), (6, 5), (9, 8)])
7print(m(0,2,1,0).set)  # m.set(0,2,1,0)=Set(value=[(1, 3, 2, 1), (4, 6, 5, 4), (7, 9, 8, 7)])

7.5. SIMPLE での抽出の記述#

PySIMPLE に限らずモデリング言語 SIMPLE では抽出の記述が提供されている． SIMPLE の実装言語ごとの記述方法は次の表のとおりである．

種別

集合 \(M\) の抽出

要素 \(m\) の抽出

関数表記

\(\epsilon_{1,3,2,1}(M)\)

\(\epsilon_{1,3,2,1}(m)\)

PySIMPLE

M(0,2,1,0)

m(0,2,1,0)

C++SIMPLE

M.slice(1,3,2,1)

m.at(1),m.at(3),m.at(2),m.at(1)

C++SIMPLE では slice や at があてがわれ，at については一度に at(1,3,2,1) とすることはできない． つまり at に関しては抽出よりも限定的な概念である．

プログラミング言語としてスライスは Python や JavaScript などの登場と普及から，一定の範囲を取り出す操作として定着している． 一方で英単語としての slice は部分としての意味合いがあり，同様の操作を part とよぶ言語もある． また薄く切り取るという意味もあり，C++SIMPLE では指定した成分を切り取っていることからも，この意味に近い．

7.6. 頻出する総和条件#

疎な記述 では，次に記述する総和が頻出する．

(7)#\[\sum_{j;(i,j)\in IJ} x[(i,j)]\]

この総和は次の集合に属する \(j\) についての和を意味している．

(8)#\[\{j \mid (i,j)\in IJ\}\]

\(IJ=\{(1,1),(2,1),(2,2)\}\) の場合を考えたとき，この集合は次のように記述できる．

(9)#\[\{j \mid (i,j)\in IJ\} = \pi_J(\sigma_{I=i}(IJ))\]

ここで，\(\sigma_{I=i}\) は \(IJ\) の要素の第一成分が \(i\) である要素のみを選択せよ，という選択演算子である． よって，次のようにも総和を書き下せるとわかる．

(10)#\[\sum_{j\in\pi_J(\sigma_{I=i}(IJ))} x[(i,j)]\]

上記の \(IJ\) の場合についての総和は，C++SIMPLE と PySIMPLE では次のように書き下せる．

1Set I = "1 2";
2Set J = "1 2";
3Set IJ(dim=2) = "1,1 2,1 2,2";
4Element i(set=I), j(set=J);
5Variable x(index=(i,j));
6sum(x[i, j], (j, (i, j) < IJ)) >= 0;
7showSystem();
8// newModel.smp:6:info: (1-1) x[1,1] >= 0
9// newModel.smp:6:info: (1-2) x[2,1]+x[2,2] >= 0

ここで，C++SIMPLE は集合の内包的表記を強く意識した記述である一方で， PySIMPLE は記述が簡便ではあるものの，Sum 関数が非自明であることに注意する． というのも，ij(1) が第二成分の射影であることを踏まえると， i=1 について，x[1,2] という項も総和に含まれるような記述に見える． しかし，Sum 関数では適切に選択演算がなされていて，x[1,1] のみを足し上げている．

Tip

\(\pi_J(\sigma_{I=i}(IJ))\) は関係代数における商として，次のように簡潔に記述することもできる．

(11)#\[\pi_J(\sigma_{I=i}(IJ)) = IJ \div \{(i)\}\]

商構造が頻出することから，更なる経済的な短縮表記として，次の表記法を採用してもよいだろう．

(12)#\[I(i) := IJ \div \{(i)\}\]

商の構造は添字が複数になっても同様で，\(\sum_{(j,l);(i,j,k,l)\in IJKL}\) のような場合でも，やはり成り立っている．

(13)#\[\pi_{J,L}(\sigma_{I=i\land K=k}(IJKL)) = IJKL \div \{(i,k)\} =: JL(i,k)\]

関連

引用書式

BibTeX

目次