数理解析研究所講究録
第 1829 巻 2013 年 102-112102

凹費用関数をもつ輸送問題に対する 2 乗和多項式緩和
神奈川大学水谷友彦 1
Tomohiko Mizutani
Kanagawa University

東京工業大学山下真 2
Tokyo Institue of Technology Makoto Yamashita

概要
本稿は [9] の概説である。 [9] では凹費用関数を持つ輸送問題 (CCTP) に対して 2 乗和多項式に基づく半正定値計画緩和 (SDP 緩和) を提案した。 その特徴は以下の通りである。 は生産地の数、 は需要地の数、 は緩和強度を表すとする。 (1) SDP 緩和問題の行列変数となる。 (2) 緩和強度 を大きくすると、 SDP 緩和の大きさは $O(( \min\{p, q\})^{\omega-1}),$問題の最適値は CCTP の大域的な最適値に収束する。 (3) どんな に対しても、 SDP 緩$P$$\omega$$q$$\omega\geq 2$$\omega$$\omega$和問題とその双対問題の間に双対ギャップは存在しない。本稿ではこのような特徴を持つ
SDP 緩和の構築の仕方について解説する。

1

はじめに

凹費用関数を持つ輸送問題 (CCTP) とは以下のような問題である。 生産地 $i\in I:=$$\{1, \ldots, p\}$ から需要地 $j\in J:=\{1, \ldots, q\}$ に製品を送るとき、 輸送量に対して費用はで定まるとする。 このとき、 CCTP は生産、 需要に関する制約の下で凹関数ん :$X_{i}j$$\mathbb{R}arrow \mathbb{R}$

総費用が最小となるような輸送量を求める問題であり、次のように定式化される。

(Q) :Minimize

EE

subject to$\sum_{j\in J}^{i\in I}x_{ij}=j\in ja_{i},$$f_{ij}(x_{ij})$$i\in I$, and$\sum_{i\in I}x_{ij}=b_{j},$$j\in J,$

$x_{ij}\geq 0, i\in I, j\in J$

本稿では特にんが 2 次の凹多項式関数である場合を考える。
この問題の特徴はんが凹関数であることにある。実社会では、いわゆる規模の経済性によって、 輸送量が増加するにつれて費用が減少するということが起こる。 このような状況を反映させるためにんを凹関数としている。実際、 CCTP は輸送システム、工場建設
計画、 生産計画などの実問題を定式化するために用いられている [2, 4, 6]。んが凹関数で
$1E$

$2E$

-mail: mizutani@kanagawa-u.ac.jp-mail: Makoto. Yamashita@is.titech.ac.jp

103
あることがこの問題を解くことを難しくさせている。実際、 CCTP は $NP$ 困難な問題であることが知られており $[4]$ 大域的な最適解を求めることは難しい。
CCTP を解くための手法として、 Lasserre[7] によって提案された多項式最適化問題 (POP)に対する半正定値計画緩和 (SDP 緩和) の枠組みを利用する。 この緩和手法は非負多項式
を 2 乗和多項式で置き換えることで得られるので、 2 乗和多項式緩和 (SOS 緩和) とも呼ばれる。 この手法では、 緩和強度を高めると、 SDP 緩和問題の最適値は POP の大域的な最適値に収束するということが理論的に保証されている。 一方で、 緩和強度を高めるとSDP 緩和問題の規模が非常に大きくなり、 実際には解くことが困難になるという課題がある。 この課題に対して、 Waki ら [11] は POP がある種の疎構造を有している場合、 その構造を利用することで規模が小さい SDP 緩和問題を構築する手法を提案した。 Lasserreの SDP 緩和手法に対して、 この手法は疎な SDP 緩和手法と呼ばれる。
本稿では CCTP を POP とみなし、 Waki らによって提案された疎な SDP 緩和手法を適用する。 一般的には CCTP は望ましい疎構造を有していない。 本稿では CCTP に対して
変数変換を施すと疎構造を持つ問題に変換できることを示す。 そして、 その構造を観察す
ることで以下のような特徴を持つ SDP 緩和問題を構築できることを説明する。 正整数を緩和強度とする。
、$\omega$(1) SDP 緩和問題の行列変数の大きさは $O(( \min\{p, q\})^{\omega-1}),$(2) 緩和強度$\omega$$\omega\geq 2$となる。

を大きくすると、 SDP 緩和問題の最適値は CCTP の大域的な最適値に収束する。

(3) どんなない。

$\omega$に対しても、 SDP 緩和問題とその双対問題の間に双対ギャップは存在し(Q) におけるんが凹平方関数である場合も、 上記と同じ特徴を持った SDP 緩和問題が構築できる [9]。

本稿は 4 節からなる。 まず、 第 2 節において疎な SDP 緩和とその収束定理について説明する。 第 3 節ではボックス制約をもつ 2 次計画問題に対する疎な SDP 緩和問題の性質をまとめる。 第 4 節では CCTP に対してどのように変数変換を施すか説明した後、 上記のような特徴を持つ SDP 緩和問題が構築できることを説明する。

1.1

記号や用語の定義

本稿では実数の係数と$n$個の変数で構成される次のような多項式$f= \sum_{\alpha\in \mathcal{F}}f_{\alpha}x^{\alpha},$を考え、 このような $f$ の集合をと書く。 $x=(x_{1}, \ldots, x_{n})$ とは単項式
を 次元の非負整数の集合とする。
を表している。

$\alpha=(\alpha_{1}, \ldots, \alpha_{n})$$\mathbb{R}[x]$$x^{\alpha}$$x_{1}^{\alpha_{1}}\ldots x_{n}^{\alpha_{n}}$$\mathbb{Z}_{+}^{n}$$n$$\mathcal{F}$はとし、$\mathbb{Z}_{+}^{n}$の104部分集合で、 のサポートと呼ばれる。 のサポートは $supp(f)$ と表すことがある。 の次数ははベクトルの要素の和で、 これを $\deg(f)$ と書く。 ここで、
を表す。
に対して、
とする。 また、 $C\subseteq\{1, \ldots, n\}$$i\in C$ で構成されに対して、とする。 これは変数をると表す際に使われる。
$C\subseteq\{1, \ldots, n\}$ と正整数
に対して
if
and
を
とする。 これは次数が 以下のと表す際に使われる。
$\phi=f_{1}^{2}+\cdots+f_{r}^{2}$
$fi,$
が
を用いて
と書けるとき、 は SOS 多項\’ix]で表す。 SOS 多項式式と呼ばれる。 このような SOS 多項式 の集合をで、特に $fi,$を用いて $\phi=f_{1}^{2}+\cdots+f_{r}^{2}$ と書けるものを
で表す。
次
に対して、
SOS 多項式は半正定値対称行列を用いて表すことができる。
元ベクトル
$:=$
と定義し、 また、対称行列
対称行列の集合をで表し、特に半正定値対称と定義する。
行列であるものをで表す。 このとき、
$f$

$f$

$f$

$\max\{|\alpha|:\alpha\in \mathcal{F}\}$$\mathbb{R}[x, \mathcal{G}]:=\{f\in \mathbb{R}[x] :$\mathcal{G}\subseteq \mathbb{Z}_{+}^{n}$$\mathcal{A}(C)$$f$$|\cdot|$supp(f)\subseteq \mathcal{G}\}$$:=\{\alpha\in \mathbb{Z}_{+}^{n}:\alpha_{i}=0 if i\not\in C\}$$x_{i},$$f\in \mathbb{R}[x, \mathcal{A}(C)]$$\mathcal{A}^{\omega}(C)$$\omega$$\phi\in \mathbb{R}$$\ldots,$$|\alpha|\leq\omega\}$$f\in \mathbb{R}[x, \mathcal{A}^{\omega}(C)]$$f_{r}\in \mathbb{R}[x]$$\phi$$\phi\in \mathbb{R}[x]$$\Sigma[x]$$\phi$$\ldots,$$i\not\in C$$:=\{\alpha\in \mathbb{Z}_{+}^{n}:\alpha_{i}=0$$f\in \mathbb{R}[x, \mathcal{A}(C)]$$\omega$$f_{r}\in \mathbb{R}[x, \mathcal{G}]$$\Sigma[x, \mathcal{G}]$$|\mathcal{G}|$$\mathcal{G}\subseteq \mathbb{Z}_{+}^{n}$$u(x, \mathcal{G})$$:=(x_{\alpha}:\alpha\in \mathcal{G})$$u(x, \mathcal{G})u^{T}(x, \mathcal{G})$$M(x, \mathcal{G})$$|\mathcal{G}|\cross|\mathcal{G}|$$|\mathcal{G}|\cross|\mathcal{G}|$$\mathbb{S}(\mathcal{G})$$\mathbb{S}_{+}(\mathcal{G})$$\phi\in\Sigma[x, \mathcal{G}]\Leftrightarrow\exists Y\in \mathbb{S}_{+}(\mathcal{G}), \phi=\langle M(x, \mathcal{G}), Y\rangle$.

(1)が成立する [10, 5]。ここで、はフロベニウスノルムを表す。 例えば、 対称行列 $X$ と$Y$ に対して、$Y\rangle=tr(XY)$ となる。
$\langle\cdot,$$\cdot\rangle$$\langle X,$

2

疎な SDP 緩和の収束定理

Waki ら [11] によって提案された POP に対する疎な SDP 緩和とその収束定理について説明する。 次のような POP (P) を考える。
(P) :ここで $f,$$g_{1},$$\{C_{1}, \ldots, C_{\ell}\}$条件 1$C_{1},$

1-1. $j=2,$$\ldots,$$|$

Minimize$g_{m}\in \mathbb{R}[x]$subject to$f(x)$$g_{k}(x)\geq 0,$$k=1,$

1-3.

$f$

は

$\ldots,$$C_{\ell}\subseteq\{1, \ldots, n\}$とする。

$\ell$$\ldots,$$f_{i}\in \mathbb{R}[x, \mathcal{A}(C_{i})]$$k\in$$\triangle=$を用意する。

瓦は
いに疎な集合で、$g_{k},$$m$である。 この (P) に対して、 以下の条件を満たす集合族に対して、 $Ci\supseteq C_{j}\cap(C_{1}\cup C_{2}\cup\cdots\cup C_{j-1})$ のようなが存在する。

1-2.

$\ldots,$を用いて、$g_{k}\in \mathbb{R}[x,$$\mathcal{A}(C_{i})|$$f= \sum_{i=1}^{\ell}f_{i}$$C_{i},$$i\in\{1, \ldots,j-1\}$と表せる。

と表せる。 ここで瓦 $\subseteq\{1, \ldots, m\},$ $i=1,$$\bigcup_{i=1}^{\ell}K_{i}=\{1, \ldots, m\}$

となる。

$l$

$\ldots,$は互105
条件 1-1 の成立はの並べ方に依存する。 コーダルグラフにおける極大クリーク
族は必ずこの条件を満たし、 このような性質は running intersection property と呼ばれている [1]。条件 1-3 において
によって定まる集合族
を Aによって表す。
POP に対する疎な SDP 緩和は条件 1 を満たすとそれに付随するを用いて構築する。まず、 と A を用いて (P) の一般化ラグランジュ関数 を導入し、次に、 それから導かれるラグランジュ双対問題を考える。
$C_{1},$$C_{\ell}$$\ldots,$$\triangle=\{C_{1}, \ldots, C_{\ell}\}$$\{K_{1}, \ldots, K_{\ell}\}$$\triangle=\{C_{1}, \ldots, C_{\ell}\}$$\{K_{1}, \ldots, K_{\ell}\}$$\Lambda=$$\triangle$$L$$\omega_{0}:=\lceil\deg(f)/2\rceil,$に対して、 疎な SDP 緩和の緩和強度
るように選ぶ。 制約式偽の乗数をを次のように定義する。
$\lceil\deg(g_{k})/2\rceil$$\omega\in \mathbb{N}$$\omega_{k}:=$, 紛となとして一般化ラグランジュ関数

を $\omega\geq\max\{\omega_{0},$$\phi_{ik}\in\Sigma[x, \mathcal{A}^{\omega-\omega_{k}}(C_{i})]$$\omega_{1},$$\ldots$$\omega$$L$$L(x, \phi)=f(x)-\sum_{i=1}^{\ell}\sum_{k\in K_{i}}\phi_{ik}(x)g_{k}(x)$with$\phi\in\Phi^{\omega}$

ここで $\Phi^{\omega}:=\{(\phi_{ik}:k\in K_{i}, i=1, \ldots, \ell):\phi_{ik}\in\Sigma[x, \mathcal{A}^{\omega-\omega_{k}}(C_{i})]\}$ である。 すると、 (P)のラグランジュ双対問題はMaximize$\eta$

subject to$L(x, \phi)-\eta\geq 0$

for all$x\in \mathbb{R}^{n}$, and$\phi\in\Phi^{\omega}$(2)と書ける。 この制約条件は多項式 $L-\eta$ が上で非負であることを意味している。 それを $L-\eta$ が SOS 多項式の和で書けるという条件に置き換える。 すると、 以下の問題が得られる。
$\mathbb{R}^{n}$$L- \eta=\sum_{i=1}^{\ell}\phi_{i},$Maximize$L- \eta=\sum_{i=1}^{\ell}\phi_{i}$$\eta$

subject to

は $L-\eta$ が$\mathbb{R}^{n}$$\phi_{i}\in\Sigma[x, \mathcal{A}^{\omega}(C_{i})]$(3)$f(x)- \eta=\sum_{i=1}^{\ell}(\phi_{i}(x)+\sum_{k\in K_{i}}\phi_{ik}(x)g_{k}(x))$

上で非負であることを意味するが、 その逆は成り立たない。

したがって、 (2) から (3) への変形は等価ではない。 (3) は (P) の緩和問題になっており、(3) は (P) に対する疎な二乗和多項式緩和 (疎な SOS 緩和) と呼ばれる。 (3) において多項式の集合は$k\in K_{i}$を定義する。
によって生成される quadratic module と呼ばれる。
はを用いると (3)$\mathcal{M}_{i}:=\{\phi_{i}+\sum_{k\in K_{i}}\phi_{ik}g_{k} :\phi_{i}, \phi_{ik}\in\Sigma[x, \mathcal{A}(C_{i})]\}$$\mathcal{M}_{i}$$g_{k},$$\mathcal{M}_{i}$Maximize$\eta$

subject to$f-\eta\in \mathcal{M}_{1}+\cdots+\mathcal{M}_{\ell}$(4)と書き直すことができる。
SOS 多項式は半正定値対称行列を用いて表せるという事実 (1) を用いると、疎なSOS 緩和問題 (3) は以下のような形の SDP として書き直せる。

$(P^{\omega})$$\phi_{i},$$\phi_{ij}$:Maximizesubject to$\langle C,$$X\rangle$$\mathcal{A}(X)=b,$$X\in\Pi_{i=1}^{\ell}\mathbb{S}_{+}(\mathcal{A}^{\omega}(C_{i}))\cross\Pi_{i=1}^{\ell}\Pi_{k\in K_{i}}\mathbb{S}_{+}(\mathcal{A}^{\omega-\omega_{k}}(C_{i}))$106は半正定値対称行列集合から実ベクトル集合へのを (P) に対する疎な SDP 緩和と呼ぶことにする。疎な線形写像である。本論文ではを用いて書きなおした問題
は疎な SOS 緩和問題 (3)、及びそれをSDP 緩和問題
における行列変数 $X$ はブロック行列変数(4) と等価な問題である。
ここで $C$ は対称行列、$b$はベクトル、$\mathcal{A}$$(P^{\omega})$$(P^{\omega})$$\mathcal{M}_{i}$$X^{(i)}\in \mathbb{S}_{+}(\mathcal{A}^{\omega}(C_{i}))$$(P^{\omega})$と$X^{(i,k)}\in \mathbb{S}_{+}(\mathcal{A}^{\omega-\omega_{k}}(C_{i}))$との直積$X= \prod_{i=1}^{\ell}X^{(i)}\cross\prod_{i=1}^{\ell}\prod_{k\in K_{i}}X^{(i,k)}$で表される。

$X^{(i)}\in S_{+}(\mathcal{A}^{\omega}(C_{i}))$のサイズは$|\mathcal{A}^{\omega}(C_{i})| = (^{|C_{i}|+\omega}\omega)$$= O(|C_{i}|^{\omega})$で、$X^{(i,k)}\in \mathbb{S}_{+}(\mathcal{A}^{\omega-\omega_{k}}(C_{\iota’}))$のサイズは$|\mathcal{A}^{\omega-\omega_{k}}(C_{i})| = (\begin{array}{l}|C_{i}|+\omega-\omega_{k}\omega-\omega_{k}\end{array})$$= O(|C_{i}|^{\omega-\omega_{k}})$となるので、最も大きいブロック行列変数のサイズはである。 したがって、要素数から構成されるが少ない集合を見つけることができると、規模が小さい$i=1,$$m$$k=1,$SDP 緩和問題が構築できることが分かる。例えば、 (P) における多項式 $f,$のつまり、単項式が疎である場合、を構成する単項式の数が少ない場合、$i=1,$
要素の個数が少なくなる傾向がある。集合 $C=\{1, \ldots, n\}$ は条件 1 を自明に満たすことが分かる。 Lasserre の SDP 緩和 [7] は Waki らの疎な SDP 緩和問題において $\triangle=\{C\}$ としたものに対応している。
の最適値を
の最適値を
の双対問題をと書く。 また、$k\in
K_{i}$のによって生成されるの大域的な最適値をと書く。 (P)(P)
quadratic module
と
は に収
とすると、
が次の条件を満たすとする。 このとき、束することが知られている。
$O(|C_{i}|^{\omega})$$\triangle$$\ell$$C_{i},$$\ldots,$$g_{k},$$\ldots,$$\ell$$C_{i},$$\ldots,$$(P^{\omega})$$(P^{\omega})$$(P_{*}^{\omega})$$\zeta(P^{\omega})$$(P_{*}^{\omega})$$\zeta(P_{*}^{\omega})$、$\zeta$$\omegaarrow\infty$$\mathcal{M}_{i}$条件 2$\mathcal{M}_{i},$$\sum_{j\in C_{t}}x_{j}^{2}\in \mathcal{M}_{i}$$\zeta(P^{\omega})$はアルキメデス的である。 つまり、 $i=1,$のような正整数 が存在する。

$i=1,$、$g_{k},$$l$$\ldots,$$\zeta(P_{*}^{\omega})$$l$$\ldots,$$\zeta$に対して、$\theta_{i}-$$\theta_{i}$定理 1 ([3, 8]) 条件 1 と 2 が成立する。 このとき、$\lim_{\omegaarrow\infty}\zeta(P^{\omega})=\lim_{\omegaarrow\infty}\zeta(P_{*}^{\omega})=\zeta$となる。
定理 1 では、 (P) の大域的な最適値を計算するためにはの緩和強度 を十分大きくすることを示唆している。 しかし、経験的には の値は 2 あるいは 3 程度で (P) の大域的な最適値、 及び最適解が得られることが多いことが知られている [11]。
$(P^{\omega})$$\omega$$\omega$

107
ボックス制約を持つ 2 次計画問題に対する疎な SDP 緩和

3の性質
ボックス制約を持つ 2 次計画問題 ( $QP$ ) を考える。

Minimizesubject to$f(x)$$k=1,$$g_{k}(x)\geq 0,$$\ldots,$

$m$

,

(5)

$0\leq x_{j}\leq a_{j}, j=1, \ldots, n$$f$

式

は $n$ 変数の 2 次多項式 $f\in \mathbb{R}[x],$ $\deg(f)=2$ で、$g_{k},$$k=1,$$m$$\ldots,$

は $n$ 変数の 1 次多項(5) に対して条件 1 を満たす集合族$\deg(g_{k})=1$ である。

$g_{k}\in \mathbb{R}[x],$$\triangle=\{C_{1}, \ldots, C_{\ell}\}$を用意する。 そして、 (5) に対して適切に制約式 $Xj\geq 0,$ $aj-x_{j}\geq 0$ を追加し、 次のような冗長な表現を含んだ問題を考える。

Minimizesubject to$f(x)$

and$h_{j}^{\ell}(x)\geq 0$

ここで$h_{j}^{\ell}(x)$$k=1,$$g_{k}(x)\geq 0,$$:=x_{j、}h_{j}^{u}(x)$$:=a_{j}-x_{j}$$h_{j}^{u}(x)\geq 0,$$h_{j}^{\ell},$$h_{j}^{u},$$\ldots,$$m$,$i=1,$(6)$\ell$$\ldots,$としている。

とそれに付随して得られる$j\in C_{i}$ から生成される quadratic module$\triangle=\{C_{1}, \ldots, C_{\ell}\}$及び$j\in C_{i},$$\Lambda=\{K_{1}, \ldots, K_{\ell}\}$を考える。

$g_{k},$$k\in K_{i、}$$\mathcal{M}_{i}=\{\phi_{i}+\sum_{k\in K_{i}}\phi_{ik}g_{k}+\sum_{j\in C_{i}}\phi_{i_{J}’}^{\ell}h_{j}^{\ell}+\sum_{j\in C_{i}}\phi_{ij}^{u}h_{j}^{u}:\phi_{i}\in\Sigma[x, \mathcal{A}^{\omega}(C_{i})], \phi_{ik}, \phi_{ij}^{\ell}, \phi_{ij}^{u}\in\Sigma[x, \mathcal{A}^{\omega-1}(C_{i})]\}$(7)を用いると、 (6) に対する疎な SOS 緩和はMaximize$\eta$

subject to$f-\eta\in \mathcal{M}_{1}+\cdots+\mathcal{M}_{\ell}$と書ける。 この問題に対して等価な変形を施すことで得られる (6) に対する疎な SDP 緩
和問題を
と書く。
$(P^{\omega})$

補題 $1QP$ (6) とそれに対する疎な SDP 緩和問題

1-1. ([9] の Lemma 2) quadratic module$\mathcal{M}_{i},$$(P^{\omega})$$i=1,$$\ldots,$

は以下のような性質を持つ。
$\ell(7)$はアルキメデス的である。

1-2. ([9] の Lemma 3) (6) の実行可能領域が内点を持つとする。 このとき、 どんなしても、$(P^{\omega})$とその双対問題

1-3. ([9] の Proposition 3)
のサイズは

に対

との間に双対ギャップは存在しない。

とする。 このときとなる。

$\omega\geq 2$$O(|C_{i}|^{\omega-1})$$(P_{*}^{\omega})$$\omega$$(P^{\omega})$の最も大きいブロック行列変数

108
変数変換を施した CCTP に対する疎な SDP 緩和

4

本稿では CCTP(Q) に対して次のような仮定をする。

仮定 1(Q) は次の 2 つの条件を満たす。

1-1.
$1-2.$$a_{i},$$b_{j}>0,$$i\in I,$

$j\in J$$\sum_{i\in I}a_{i}=\sum_{j\in J}b_{j}$最初の仮定は一般性を失わずに成立する。 もし、 $a_{i}=0$ であれば $x_{i1}=\cdots=x_{iq}=0$ で、
また、 $b_{j}=0$ であれば $x_{1j}=\cdots=x_{pj}=0$ となるので、 これらの変数を除けば最初の仮定は成立する。 2 番目の仮定は (Q) が実行可能であることを保証している。

4.1

変数変換

(Q) の等式制約(8)$\{\begin{array}{l}\sum x_{ij}=a_{i}, i\in I,\sum_{i\in I}^{j\in J}x_{ij}=b_{j}, j\in J\end{array}$に対して、 $x=$ $(x_{ij} :i\in I, i\in J)\in \mathbb{R}^{pq}$ から $y=(y_{ij} :i\in I, j\in J)\in \mathbb{R}^{pq}$ への変数変換(9)$\{\begin{array}{ll}x_{ij}=y_{ij}-y_{i,j+1}, i\in I, j\in J\backslash \{q\},x_{iq}=y_{l}’q i\in I\end{array}$を施す。 これは可逆な変換で、 実際に$y_{ij}=x_{ij}+\cdots+x_{iq}, i\in I, j\in J$となる。 この変換を施すと、 (8) は$\{\begin{array}{ll}y_{i1}=a_{i}, i\in I,\sum_{i\in I}(y_{\’{i} j}-y_{i,j+1})=b_{j}, j\in J\backslash \{q\}, and \sum_{i\in I}y_{iq}=b_{q}\end{array}$となる。 2 番目の等式は$\overline{b}_{j}:=\sum_{k=}^{q}b$を用いて$\sum_{i\in I}y_{ij}=\overline{b}_{j},$$i\in J$と書き直せるので、結局、 (8) は$\{\begin{array}{ll}y_{i1}=a_{i}, i\in I,\sum_{i\in I}y_{ij}=\overline{b}_{j}, j\in J\end{array}$と変換される。

(10)

109
更に同様な変数変換を (10) に適用する。 (10) に対して $y=(y_{ij} :i\in I, j\in J)\in \mathbb{R}^{pq}$ か
ら $z=$ $(z_{ji}:i\in I, i\in J)\in \mathbb{R}^{pq}$ への変数変換(11)$\{\begin{array}{ll}y_{ij}=z_{ji}-z_{j,i+1}, i\in I\backslash \{p\}, j\in J,y_{pj}=z_{jp}, j\in J\end{array}$

を施すと、$\{\begin{array}{ll}z_{1i}-z_{1,i+1}=a_{i}, i\in I\backslash \{p\}, and z_{1p}=a_{p},z_{j1}=\overline{b}_{j}, j\in J\end{array}$が得られる。 1 番目の等式は局、 (10) は$\overline{a}_{i};=\sum_{k=i}^{p}a_{k}$を用いて$z_{1i}=\overline{a}_{i},$$i\in I$と書き直せるので、 結(12)$\{\begin{array}{l}z_{1i}=\overline{a}_{i}, i\in I,z_{j1}=\overline{b}_{j}, j\in J\end{array}$と変換される。
(8) は (12) と変数変換$(u_{ji}(z)=)x_{ij}=\{\begin{array}{ll}(z_{ji}-z_{j,i+1})-(z_{j+1,i}-z_{J+1,i+1}) , i\in I\backslash \{p\}, j\in J\backslash \{q\},z_{qi}-z_{q,i+1}, i\in I\backslash \{p\}, j=q,z_{jp}-z_{j+1,p}, i=p, j\in J\backslash \{q\},z_{qp} i=p, j=q\end{array}$の下で等価である。 この変数変換を $u_{ji}(z)$ と書こう。 すると、 CCTP (Q) はMinimiz$e$subject to$\sum_{j\in J}\sum_{i\in I}f_{ij}(u_{ji}(z))$$z_{j1}=\overline{b}_{j},$

,

(13)

$j\in J$$z_{1i}=\overline{a}_{i}, i\in I,$$u_{ji}(z)\geq 0, j\in J, i\in I$と書き直すことできる。
(13) の変数
は有界閉区間上の値を取る。 実際、 $\sum_{j\in J}x_{ij}=a_{i}$ , $x_{ij}\geq 0$ からははとなり、 故にとなる。 また、 (13) において変数$j\in J$と$i\in I$ は定数なので消去できる。 これらの変数を消去した後、の添字 と の値
を 1 ずつ減らす。 すると、 (13) は次のように書き直せる。
$z_{ji}$$0\leq y_{ij}\leq a_{i}$$y_{ij}$$z_{ji}$$0\leq z_{ji}\leq\overline{a}_{i}$$z_{j1},$$z_{1i},$$z_{ji}$

Minimizesubject to

$i$

$i$

$\sum_{i\in J}\sum_{i\in I}f_{ij}(v_{ji}(z))$$v_{ji}(z)\geq 0,$$j\in J,$

$i\in I,$

$0\leq z_{ji}\leq\delta_{ji}, j\in J’, i\in I’$

(14)

110
$\ovalbox{\tt\small REJECT}$は$\delta_{ji}>\overline{a}_{i}$を満たす実数で、 $v_{ji}(z)$ は$v_{ji}(z);=\{\begin{array}{ll}z_{(1,1)}+c, j=1, i=1,-z_{(j-1,1)}+z_{(j,1)}+b_{j}, j\in J’\backslash \{1\}, i=1,-z_{(1,i-1)}+z_{(1,i)}+a_{i}, j=1 i\in I’\backslash \{1\},(z-z)-(z-z) , j\in J’\backslash \{1\}, i\in I’\backslash \{1\},-z_{(1,p-1)}+a_{p}, j=1, i=p,z_{(j-1,p-1)}-z_{(j,p-1)}, j\in J’\backslash \{1\}, i=p,-z_{(q-1,1)}+b_{q}, j=q, i=1,z_{(q-1,i-1)}-z_{(q-1,i)}, j=q, i\in I’\backslash \{1\},z_{(q-1,p-1)}, j=q, i=p\end{array}$である。 ここで $c:=\overline{a}_{1}-\overline{a}_{2}-b_{2、}J’:=\{1, \ldots, q-1\}$ $I’:=\{1, \ldots,p-1\}$ とする。 (Q)と (14) の大域的な最適値は一致し、 (Q) の大域的な最適解は (14) の大域的な最適解に変換 (9)、 (11) に由来する線形変換を施すことで得られる。
をと選ぶとは内点を持つ。
(14) の実行可能領域を と書く。
、$\mathcal{V}$$\mathcal{V}$$\delta_{ji}>\overline{a}_{i}$$\delta_{ji}$

補題 2 ([9] の Lemma 4) 仮定 1 が成立するとする。 このとき、$\mathcal{V}$は内点を持つ。

この補題の最初の仮定は (Q) において一般性を失わずに成立する。 もし、 $a_{i}=0$ であれ
ば $x_{i1}=\cdots=x_{iq}=0$ で、 また、 $b_{j}=0$ であれば $x_{1j}=\cdots=x_{pj}=0$ となるので、 これらの変数を除けば補題の最初の仮定は成立する。 2 番目の仮定は (Q) が実行可能であることを保証している。

4.2

変数変換を施した CCTP の集合族$\triangle$(Q) の目的関数んが 2 次の凹関数$f_{ij}(x_{ij})=\mu_{ij}x_{ij}^{2}+v_{ij}$with $\mu_{ij}<0.$であるとする。 このとき、 変数変換を施した CCTP (14) は

(R):

$|$

Minimize$\sum_{j\in J}\sum_{i\in I}\mu_{ij}v_{ji}^{2}(z)+\nu_{ij}$となる。 (R) に対して、 次のような$C_{ji}$subject to$z\in \mathcal{V}$から構成される集合族 $\triangle=\{C_{\dot{j}i}:i\in J", i\in I"\}$$C_{ji}=\{(j, i), (j+1,i), \ldots, (q-1, i), (1, i+1), (2, i+1), \ldots, (j+1, i+1)\}$と、 次のような C 戸から構成される集合族 $\triangle=\sim\{\tilde{C}_{ji} :j\in J", i\in I"\}$$\tilde{C}_{ji}=\{(j, i), (j, i+1), \ldots, (j,p-1), (j+1,1), (j+1,2), \ldots, (j+1, i+1)\}$を考える。 これらは $|C_{ji}|=q+1$ and $|\tilde{C}_{ji}|=p+1$ である。 ここで $J”$ は $J”:=\{1, \ldots, q-2\}$と $I”$ は $I”:=\{1, \ldots,p-2\}$ としている。

111
補題 3 ([9] の Lemma 5) $\triangle=\{C_{ji}:j\in J", i\in I"\}$ と $\triangle=\sim\{\tilde{C}_{ji} : j\in J", i\in I"\}$ は条
件 1 を満たす。
集合族$\triangle^{O}$

を $q\geq p$ の場合は$\triangle^{o}=\triangle$とし、 そうでない場合は$\triangle^{o}=$丞とする。

$\triangle^{o}$を用いて (R) に冗長なボックス制約を追加し (6) の形に修正する。 修正した (R) に対してを用いて疎な SDP 緩和問題$\triangle^{o}$を構築する。 その双対問題をと書く。 今、 補題 3
からは条件 1 を満たすことが分かる。 また、 補題 1-1 から修正した (R) は条件 2 を満たすことが分かる。 したがって、 修正した (R) に対する疎な SDP 緩和の収束性を
定理 1 を用いて保証できる。 更に、 補題 2 から修正した (R) の実行可能領域は内点を持つので、補題 1-2 が成立する。 ここで、
の最適値を
の最適値を
(R) の大域的な最適値を と書く。
$(R^{\omega})$$(R_{*}^{\omega})$$\triangle^{o}$$(R^{\omega})$$(R^{\omega})$$\zeta(R^{\omega})$$(R_{*}^{\omega})$$\zeta(R_{*}^{\omega})$、、$\zeta$定理 2 ([9] の Proposition 1) どんな$\lim_{\omegaarrow\infty}\zeta(R^{\omega})=\lim_{\omegaarrow\infty}\zeta(R_{*}^{\omega})=\zeta$$| \triangle^{o}|=\min\{q+1, p+1\}$

サイズは、$\omega\geq 2$$\omega$に対しても$\zeta(R^{\omega})=\zeta(R_{*}^{\omega})$が成立する。 更に、となる。

であるので、 補題 1-3 から$(R^{\omega})$の最も大きいブロック行列ので$(\begin{array}{lllll}\min\{p+1 q +1\}+ \omega -1\omega -1 \end{array})=O((\min\{p, q\})^{\omega-1})$となる。 したがって、 あるいは が小さい場合は CCTP に対して規模の小さい SDP 緩和が構築できることが分かる。 例えば、 $(p, q)=(5,200)$ や $(p, q)=(10,100)$ の場合、 CCTPの大域的な最適解にかなり近い良質な解が得られることを確認した。 [9] の第 5 節におい
$P$

$q$

て、 これに関する詳しい数値実験の結果を報告している。

参考文献[1] J.R.S. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In
A. George, J.R. Gilbert, and J.W.H. Liu, editors, Graph Theory and Sparse Matrix
Computation, volume 56 of $IMA$ Volumes in Mathematics and its Applications, pages
1-29. Springer, 1993.
[2] G. Gallo, C. Sandi, and C. Sodini. An algorithm for the $\min$ concave cost flow
problem. $Eur$. J. Oper. Res., $4(4):248-255$ , 1980.

[3] D. Grimm, T. Netzer, and M. Schweighofer. note on the representation of positive
polynomials with structured sparsity. Arch. Math., $89(5):399-403$ , 2007.
$A$[4] G.M. Guisewite and P.M. Pardalos. Minimum concave cost network flow problems:applications, complexity, and algorithms. Ann. Oper. Res., $25(1):75-100$ , 1990.

112[5] M. Kojima, S. Kim, and H. Waki. Sparsity in sums of squares of polynomials. Math.
Program., Ser. $A,$ $103:45-62$ , 2005.
[6] T. Larsson, A. Migdalas, and M. Ronnqvist. A Lagrangean heuristic for the capacitated concave minimum cost network flow problem. $Eur$ . J. Oper. Res., $78(1):116-$$129$ , 1994.

[7] J.B. Lasserre. Global optimization with polynomials and the problem of moments.
SIAM J. Optim., $11(3):796-817$ , 2001.
[8] M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In
M. Putinar and S. Sulhvant, editors, Emerging Applications of Algebmic Geometw,
volume 149 of $IMA$ Volumes in Mathematics and its Applications, pages 157-270.
Springer, 2009.
[9] T. Mizutani and M. Yamashita. Correlative sparsity structures and semidefinite
relaxations for concave cost transportation problems with change of variables.
Global. Optim., Online First, 2012.
$J.$[10] P.A. Parrilo. Semidefinite programming relaxations for semialgebraic problems.
$96:293-320$ , 2003.
Math. Progmm., Ser.
$B,$

[11] H. Waki, S. Kim, M. Kojima, and M. Muramatsu. Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured
sparsity. SIAM J. Optim., $17(1):218-242$ , 2006.