PowerPoint プレゼンテーション

Transcription

1 二次元空間 Fujita-Ogawa モデルの数値解法の開発 第 56 回土木計画学研究発表会 秋本克哉, 赤松隆 東北大学 情報科学研究科 1

2 研究の背景 (1) 中心市街地空洞化の問題 中心市街地の活性化が求められる 都心形成現象を説明する理論が必要 Fujita and Ogawa [FO] (1982) モデル 企業と消費者が立地競争する 企業が複数の都心に集積する立地パターンが均衡解となるメカニズムを示した 居住地区 業務地区 問題点 一次元空間では複数都心が創発する可能性は示されたが二次元空間では集積パターンは未解明 均衡解の安定性は検証されていない 2

3 研究の背景 (2) 最近の FO モデルに関する研究 (Osawa and Akamatsu (2016)) 一次元空間を想定 業務地区 居住地区 中心に業務地区, その周りに居住地区をもつ空間を単位空間とすると, 安定な均衡解は, 規則性をもつ単位空間の集合である 単位空間 単位空間 パラメータ平面で, さまざまな集積パターンが安定な均衡解として創発する 複数都心パターン 二次元空間 FO モデルでは, 安定な均衡解がどのような集積パターンであるのか不明 3

4 二次元空間 FO モデルを分析した研究 (1) 同心円周状パターンを仮定した理論研究 (Ogawa and Fujita (1989), Lucas and Rossi-Hansberg (2002), Kantor et al. (2014)) 業務地区 居住地区 Osawa and Akamatsu (2016) の結果から, 同心円周状パターンは安定な均衡解ではないと考えられる 4

5 二次元空間 FO モデルを分析した研究 (2) シミュレーションに基づく研究 (Delloye et al.(2015)) FO モデルと同様のモデル構造 Agent-based simulation によって立地パターンを計算 Osawa and Akamatsu (2016) の結果と同様, 複数都心に分かれた集積パターン 業務地区 居住地区 問題点 低い空間解像度 ( 都市を表現する格子の細かさ ) では, 集積パターンが正確にはわからない 立地パターンが均衡条件を満たしている保証がない 二次元空間 FO モデルの均衡解を高解像度で求めたい! 5

6 FO モデルの均衡解を求める際の問題点 数値計算による方法を用いた場合 集積パターンを正確に調べるためには, 高解像度にする必要がある 大規模な相補性問題を解かなくてはならない 例えば立地点数が 10 6 の場合, 未知変数の個数は立地点数 2 = のオーダー 必要な計算量と記憶容量が膨大で工夫が必要! 6

7 研究の目的 二次元空間 FO モデルの均衡解を高解像度で効率的に求めるアルゴリズムを開発し, その有効性を検証する 研究のアプローチ FO モデルと等価な最適化問題の構築 効率的に求めるための方法 :Benders Decomposition アルゴリズムで必要とされる演算および記憶させる要素数を大幅に削減 数値実験によって, アルゴリズムの有効性を示す 均衡解の計算 7

8 二次元空間 FO モデルの基本設定 空間 二次元空間 K 個の離散的な立地点集合から構成される 立地主体の行動 消費者 : 居住地 勤務地を選択し, 効用最大化行動を行う 企業 : 立地点を選択し, 利潤最大化行動を行う 8

9 均衡条件 空間均衡条件と市場均衡条件から構成される 消費者 : 効用最大化 通勤パターン 労働市場の需給均衡賃金 労働 企業 : 利潤最大化 立地パターン 土地市場の需給均衡消費者の地代土地居住地 勤務地選択不在地主 土地 企業の立地選択 すべての未知変数を同時に求めなくてはならない の要素数が極めて大きい 9

10 必要な記憶容量と計算量 空間解像度と必要な記憶容量の関係 地点数 1GB 以上 地点数 1TB 以上 2 10 消費者の通勤パターン は地点数 の 要素数を持つ 2 10 さらに, 膨大な計算量が必要! の要素のうちすべてを演算および記憶させずに済むアルゴリズムを提案する 10

11 等価な最適化問題 命題 :FO モデルは次の最適化問題と等価である 生産関数 コミュニケーション費用に対応通勤費用に対応 総企業数制約 土地制約 労働制約 総消費者数制約 11

12 提案アルゴリズム (1) に関するサブ問題とに関するマスター問題に分解 ( Benders Decomposition ) する マスター問題 ( が未知変数 ) サブ問題 ( が未知変数 ) Hitchcock 型問題工夫を施せば容易に解くことができる 収束性を保証するため, ポテンシャル問題に Frank-Wolfe 法を適用し, 線形近似する 12

13 提案アルゴリズム (2) Hitchcock 型問題の効率的解法 着眼点 : 非零の要素が極めて少なく, その要素番号と値のみ記憶させ操作すればよい 最適解はシンプレックスの端点であり, 制約条件の本数 ( ) と非零の要素数が等しい n 要素数 ( ) 記憶させる要素 汎用の数理計画パッケージでは, アルゴリズムで記憶させ操作する要素数はK 2 個 必要な計算量や記憶容量を大幅に削減 13

14 logt アルゴリズムの有効性の検証 実験条件 正方形格子を想定し, 比較ベンチマーク :MATLAB の最適化ツールの linprog 線形近似問題を解く際の問題のサイズ ( 地点数 K) とCPU time( 秒 )Tの関係 パッケージ 本アルゴリズム log K 4 CPU time を 1/1000 に削減し, 必要とされる解像度まで解くことができた : 最悪 : 平均 : 最善 必要とされる解像度 14

15 得られた均衡立地パターン 空間パターンの推移 の増加に伴い様々な極数の多極パターンが得られた 業務地区居住地区 通勤圏の境界 一次元空間 FO モデルの結果と定性的に類似 他にも様々なパターンが創発すると考えられる 15

16 おわりに FO モデルの均衡解を求めるための方法を提案した FO モデルと等価な最適化問題を構築した Benders Decomposition の考え方を用いて, 等価な最適化問題の効率的解法を提案した 数値実験によって本アルゴリズムの有効性を示した パッケージでは解くことができない, 必要とされる解像度まで解くことができた 計算時間を 1/1000 に削減 今後の課題 二次元空間 FO モデルの均衡解の特性の解明 16

17 参考文献 1 Masahisa Fujita and Hideaki Ogawa. Multiple equilibria and structural transition of non-monocentric urban configurations. Regional science and urban economics, Vol. 12, No. 2, pp , Ogawa, H. and Fujita, M. Equilibrium land use patterns in a nonmonocentric city. Journal of Regional Science, 20(4), Fujita, M. and Thisse, J.-F. Spatial duopoly and residential structure. Journal of Urban Economics,30(1),

18 参考文献 2 Berliant, M., Peng, S.-K., and Wang, P. Production externalities and urban configuration. Journal of Economic Theory, 104(2), Minoru Osawa. Monocentric and polycentric patterns in the space economy: A unification of intra-urban and inter-regional theories Hiroshi Ogawa and Masahisa Fujita. Nonmonocentric urban configurations in a two-dimensional space. Environment and planning A, Vol. 21, No. 3, pp ,

19 参考文献 3 Robert E Lucas and Esteban Rossi-Hansberg. On the internal structure of cities. Econometrica,Vol. 70, No. 4, pp , Yuval Kantor, Piet Rietveld, and Jos van Ommeren. Towards a general theory of mixed zones: The role of congestion. Journal of Urban Economics, Vol. 83, pp , Justin Delloye, Dominique Peeters, and Isabelle Thomas. On the morphology of a growing city: A heuristic experiment merging static economics with dynamic geography. PloS one, Vol. 10, No. 8, p. e ,

20 付録 : 関連研究 1 一次元空間 FO モデルの拡張 Berliant et al. (2002), Berliant and Wang (2008) 知識のスピルオーバー効果を導入し利潤関数を一般化 Fujita (1988), Liu and Fujita (1991) 独占的競争モデルに拡張 Lucas and Rossi-Hansberg (2002) など 企業行動や消費者行動を一般化 20

21 付録 : 関連研究 2 Fujita and Ogawa (1982) と異なるアプローチ Heikkila and Wang (2009), Delloye et al. (2015) シミュレーションによって, 集積パターンを計算した Osawa and Akamatsu (2016) FO モデルがポテンシャル ゲームであることを用いて, 確率安定な均衡解を明らかにした 21

22 付録 : ポテンシャル関数の非凸性 ポテンシャル関数 : の非凸性は が負定値であるのかどうかに依存 : は負定値 は一意 : は負定値ではない は一意でない ( 複数均衡が存在 ) 22

23 付録 : スパース行列を用いた場合の実験 実験条件 線形近似問題を解くための問題のサイズ ( 立地点数 K) と CPU 処理時間 ( 秒 )T の関係 正方形格子を想定し, さまざまな条件 ( パラメータ t など ) で実験 比較ベンチマーク :MATLABの最適化ツールの linprog ( アルゴリズムはシンプレックス法 ) CPU: Intel Core i7-4930k 3.40GHz, メモリ : 16GB 実験結果 までしか解くことができず, 必要とされる解像度で解くことはできなかった 23

24 付録 :Hitchcock 型問題アルゴリズム 24

25 付録 : 消費者行動 効用最大化行動 地点 j での賃金 地点 (i, j) 間の通勤費用 地点 i の地代 (t: パラメータ ) 消費者は, 直接効用 U(z,s) を最大化するように合成財需要量 z と土地消費量 ( 定数 ) を選択する より消費者は合成財需要量を最大化するように地点を選択する 25

26 付録 : 企業行動 利潤最大化行動 一定量の消費土地面積と労働需要 L を用いて財を生産する 利潤を最大化するように, 地点を選択する : 生産関数 コミュニケーション費用 : 空間割引関数 (τ: パラメータ ) 26

27 付録 : 均衡条件 空間均衡条件 : 均衡効用 : 均衡利潤 市場均衡条件 27

28 付録 : 最適化問題への変換 (1) 補題 : 企業立地パターンを与件とすれば, 均衡条件は Hitchcock 型問題と等価である 消費者行動には外部性が含まれていないため, 均衡状態は社会的最適状態である を与件とした最適地代と最適賃金が求まる 28

29 付録 : 最適化問題への変換 (2) ポテンシャルゲーム 定義 : 下記の性質を満たす関数が存在する集団ゲーム : 利得関数 : 命題 : 利得関数に対するポテンシャル : をもつ, のみを未知変数としたポテンシャルゲームとなる 29

30 付録 :FO モデルの等価最適化問題の証明 KKT 条件から等価性を証明する 企業についての空間均衡条件 消費者についての空間均衡条件 総企業数制約 総消費者数制約 土地市場の需給均衡条件 労働市場の需給均衡条件 30

31 付録 : 必要な記憶容量と計算量 精度よく均衡解を求めるために必要な空間解像度 例えば, 正方形格子の場合, 最低でも一辺あたり百等分 = 地点数 必要な記憶容量と計算量 消費者の通勤パターンは地点数であるの要素数を持ち,1GB 以上の記憶容量と膨大な計算量が必要 の要素のうちすべてを演算および記憶させずに済むアルゴリズムを提案する 31

32 付録 : 実験条件 実験条件 問題のサイズ ( 立地点数 K) と CPU 処理時間 ( 秒 )T の関係 正方形格子を想定し, さまざまな条件 ( パラメータ t など ) で実験 比較ベンチマーク :MATLAB の最適化ツールの linprog ( アルゴリズムはシンプレックス法 ) CPU: Intel Core i7-4930k 3.40GHz, メモリ : 16GB 32

33 付録 : 均衡解の局所安定性について 本アルゴリズムで解いた解は局所最適解である FO モデルはポテンシャル ゲームなので, ポテンシャル極小点は局所安定性を満たす 33

34 付録 : 前スライドの証明 回目の繰り返しにおける解と改訂方向の凸結合を で与える, ここで, はステップサイズ とすると, ( 等号成立はのみ ) であり, となるように降下方向を決めた場合, は単調減少で常にが成立する 34

35 付録 : 均衡解の計算例 (1) 一極パターン 35

36 付録 : 均衡解の計算例 (2) 二極パターン 36

37 付録 : 均衡解の計算例 (3) 四極パターン (1) 37

38 付録 : 均衡解の計算例 (4) 四極パターン (2) 38

39 付録 : 均衡解の計算例 (5) Christaller パターン 39

40 付録 : 均衡解の計算例 (6) 十二極パターン 40