金融工学
アプリケーションにおける数理計画法の実際
田辺隆人
tanabe@msi.co.jp
nuopt-info@msi.co.jp（株）数理システム

ポートフォリオ
R ( x )   rj x j  r x
tjAsset x 1 , x  0j Assetjj収益率の期待値とリスクE  R ( x )    rj x j  r xtjAssetV  R( x)  Q x x  x Qx
ti , jAssetij ijファクターモデル（収益率）
rj   j    jk f k   jkfr  ファクターモデル（分散共分散）Qij Q Q     fk ,lk ,lFactorQfj ,ki ,lij

2it



2

中間変数の導入
ｎ×ｎx Qx  x  Q  x  x diag ( ) xttftt2

 s Q s  x diag ( ) x,t

ft

2s xt

m×mm×n中間変数なし.vs.あり• 計算結果
内点法

有効制約法

計算時間

メモリ所要

計算時間

メモリ所要

なし

201秒

550M

74秒

550M

あり

1秒

30M

0.75秒

30M

（使用環境：NUOPT9.1

Core2 1.6GHz メモリ2GBytes）

中間変数なし.vs.あり• サンプル点 k における収益率kk
R ( x )   rj x jjAsset• 全サンプル点の収益率

r  x  R  xkj

中間変数なし.vs.ありｎ×ｎ

 Q x x  x Qx
ti , jAssetij i

j1 t
1 tt

x (R  R) (R  R) x s s,KKs  (R  R ) x|K|×ｎ中間変数なし.vs.あり• |K| = 60の場合
内点法

有効制約法

n=1000n=2000n=1000n=2000

なし

40秒

219秒

1秒

6秒

あり

1秒

4秒

0.3秒

0.5秒

（使用環境：NUOPT9.1

Core2 1.6GHz メモリ2GBytes）

中間変数なし.vs.あり• その他にもあえて変数を消去しない方が有利なケースありx z  x  z 1

内点法.vs.有効制約法
tQDAAO

非零な変数に対応する列内点法.vs.有効制約法• インデックス運用の場合の目的関数
V  R( x)  R( x B )  i , jAsset k ,lFactor

Qkf,l  j ,k  j ,l ( xi  xiB )( x j  x Bj )   2j ( x j  x Bj ) 2jAssetxBの非零が多いと有効制約法は不利

内点法.vs.有効制約法

xB の組み入れ銘柄数1329
組み入れ銘柄数

内点法

有効制約法

リスク最小化
指向

782

1.0秒

2.6秒

中庸

404

1.0秒

1.2秒

収益率
179
1.0秒
0.8秒
最大化
指向
（使用環境：NUOPT9.1 Core2 1.6GHz メモリ2GBytes）

内点法.vs.有効制約法• 有効制約法○基底が得られる○リスタートの効率が良い○組み入れ銘柄が尐ない• 内点法○縮退に関する情報が得られる

リスク尺度の一般化• サンプル点 k における収益率

R ( x)   r x jkjAssetkj

リスク尺度の一般化
リスク尺度意味2kk

分散 E R ( x)  E  R ( x)  kk
絶対偏差 E  R ( x)  E  R ( x)  


下方リスク

一次の下方積分積率

R k ( x) で負のものの絶対値の和R k ( x) が所与の定数値を下回るものの和の合計

CVaR最小化Maximum drawdown R ( x) の最大から p（所与）個の平均値
kk

R ( x) の部分列の最大と最小の差

CVaR最小化
最小化

1sk  
p kSample

制約sk     R ( x)ksk  0,x
投資可能集合分散.vs.CVaR
分散最小化による社債ポートフォリオ
期待収益率＝1.281（最小）分散.vs.CVaR
分散最小化による社債ポートフォリオ
期待収益率＝1.4

分散.vs.CVaR
分散最小化による社債ポートフォリオ
期待収益率＝1.5

分散.vs.CVaR
CVaR最小化による社債ポートフォリオ
期待収益率＝1.504（最小）一般の分布
分散最小化による社債ポートフォリオ
期待収益率＝1.55

分散.vs.CVaR
分散最小化による社債ポートフォリオ
期待収益率＝1.6

分散.vs.CVaR• 分散○簡便×fat tail なケースへの対処• CVaR
×大量データ必要○ＬＰとなる○fat tail なケースのコントロール

内点法.vs.単体法
CVaR最小化
サンプル数

内点法

単体法

5000

0.6秒

3.3秒

10000

2.1秒

24.3秒

20000

4.7秒

107.5秒

50000

12.9秒

――

10000042.3秒――（使用環境：NUOPT9.1

Core2 1.6GHz メモリ2GBytes）

内点法.vs.単体法
CVaR最小化の双対問題
サンプル数

内点法

単体法

5000

0.4秒

0.2秒

10000

1.5秒

0.7秒

20000

4.0秒

2.6秒

50000

18.6秒

15.0秒

100000

41.7秒

67.9秒

（使用環境：NUOPT9.1

Core2 1.6GHz メモリ2GBytes）

内点法.vs.単体法
CVaR最小化でフロンティア曲線• 内点法＋クロスオーバー⇒基底解⇒リスタート
１６点の描画，サンプル数10000
クロスオーバー

0.1秒

リスタート時間平均

23.7秒

リスタート時間最小12.8秒

リスタート時間最大

24.9秒

総合計

397.8秒（使用環境：NUOPT9.1

Core2 1.6GHz メモリ2GBytes）

ロング・ショートモデル• 組み入れ比率の定義

xj  xlongj

xx

shortj x dlongj

shortj,x0j,dbuy
jbuyj

dselljsell
j0,d整数変数不要な要件• ターンオーバー上限制約

dbuyjsellj

dTbuyj  dj• 取引コスト最小化

最小化    djsellj

整数変数が必要となる要件• ポジションの等式制約

xlongj LTj• 一般の投資制約

A xi
jjlongj

bi

C di
j

jbuyj

di

整数変数の導入• ロング・ショート

xlongj

U



longj



buy
j

longj, xshortj

Ushortj(1  longj• 購入・売却

dbuyj

Ubuyj, dsellj

Usellj(1  buyj))

分枝限定法の性能• 収益率最大化＞リスク最小化⇒ 組み入れ銘柄数• 相補性制約＞＞銘柄数制約⇒ 効率的な補強の有無

ロングショートモデルの補強• 制約追加dbuyjxxshortjlongjd x d0jbuyj, j  Longsellj• 表現の変更(x j )  (x2)  (xlong 2jshort 2j)

ロングショートモデルの性能• １６点のフロンティア曲線描画
計算時間平均23.7秒

計算時間最小11.2秒

計算時間最大

34.0秒

総時間合計

392.3秒（使用環境：NUOPT9.1

Core2 1.6GHz メモリ2GBytes）

非線形計画法の用途• フィッティング– 誤差最小化• 判別分析
– 誤判別最小化

一階微係数のみ.vs.二階微係数
主双対内点法の理論的成果• メリット関数(バリアペナルティ関数）

F ( x,  )  f ( x)    log( xi )    gi ( x)のもとでの大域的収束• 適当な  の更新方法のもとでの超一次収束
H. Yamashita, H. Yabe, and T. Tanabe,
A globally and superlinearly convergent primal-dual interior point trust region
method for large scale constrained optimization, Mathematical Programming
Ser.B,January 2005, Vol.102, Number 1, pp.111-151 (2005)

超一次収束（n=20000）

解近傍ではNewton法が効果を発揮

一階微係数のみ.vs.二階微係数
実務的なフィッティング問題

方法

反復回数

停留条件残差

誤差二乗和

計算時間

二階微係数

112回

5.0e-71257.667.8秒

一階微係数のみ

300回

1.8e-22452.8105.5秒（使用環境：NUOPT9.1 Core2 1.6GHz メモリ2GBytes）

一階微係数のみ.vs.二階微係数
実務的なフィッティング問題

一階微係数のみ.vs.二階微係数
格付け推移確率行列推定問題

二階微係数
計算コストに見合う効果
反復回数

微係数計算
時間

誤差二乗和

二階微係数

9回

925秒

1秒

一階微係数のみ128回

3676秒

3秒

方法

（使用計算機：PentiumM1.4GHz,メモリ1.5GBytes）

一階微係数のみ.vs.二階微係数
格付け推移確率行列推定問題• 繰り返し構造を利用した自動微分法の工夫
微係数計算時間
９２５秒 ⇒ １００秒
（使用計算機：PentiumM1.4GHz,メモリ1.5GBytes）
田辺隆人，
数理計画法に適した自動微分算法の開発と実装
中央大学博士論文

微係数が連続.vs.不連続絶対値関数の扱い• イディオム

最小化 f最小化s
制約 s  f  ss0

微係数が連続.vs.不連続絶対値関数の扱い

判別分析• 計測結果から性質を予想する

判別分析• 計測結果から性質を予想する

Iris virsinica

Iris virsinica

Iris versicolor

Iris versicolor

数理計画モデル• 変数a0 , a1 , a2 , a3 , a4 (パラメータ）• 目的関数eversicolorなのにが1/2以上になる1 e(誤判定）確率  a0  a1 X1  a2 X 2  a3 X 3  a4 X 4X1 , X 2 , X 3 , X 4 (計測データ）

判別分析• ロジスティクス関数 ( )versicolor virsinica

判別の実際（パラメータ推定）

数理計画モデル
入力

判別モデルパラメータ
NUOPT

非線形最適化
アルゴリズム

出力

判別の実際（予測力検証）

正解率１００％

判別分析• ロジスティクス関数 ( )ηの値によって倒産確率が決定η：財務諸表の関数形• 線形モデル  a0  a1 X1  a2 X 2  a3 X 3  a4 X 4
 a0  a Xt

X1 , X 2 , X 3 , X 4 ( X)

財務諸表の値

a0 , a1 , a2 , a3 , a4 ( a)パラメータ

η：財務諸表の値の関数• 二次モデル  a0  a X  X QXt

 q11 q12
qq
2122

 q31 q32
 q41 q42

q13q23
q33q43t

表現力
q14 増大q24 
Qq34 パラメータ
q44 （二次項）倒産判別のための数理計画モデル• 変数

a0 , a, Q（パラメータ）• 目的関数e
倒産データについてはが１に近い1 ee
存続データについてはが０に近い
1 e  a0  a X  X QXtt

倒産判別のための数理計画モデル• 制約

Qが半正定値予測力向上

半正定値制約の意義• 倒産・存続の境界線の形状（制約なし）

X2
囲われる領域は非有界

X1半正定値制約の意義• 倒産・存続の境界線の形状（制約あり）

X2

X1
予測力向上

切除平面法による解法
1. 内点法起動
2. 半正定値性のチェック（ＯＫなら終了）
3. カットの追加，１へループ（～３０回）

切除平面法.vs.非線形ＳＤＰ用内点法
方法

尤度

計算時間

切除平面法

143.74530.3秒

非線形SDP

143.747

1.5秒（使用計算機：Pentium4 3.2GHz,メモリ1GBytes）

ノルム最小化問題
Given

最小化

G X F

制約

X0

非線形ＳＤＰの応用例⇒相関行列の生成

相関を持った乱数を発生したい• 相関行列Gを恣意的に決定したい– アセット１とアセット２は逆相関だから
G[1,2] = -0.6くらいかな– アセット２とアセット３は強い相関があるのでG[2,3] = 0.8 にしたい
– ．．．

相関行列は G  LL と分解できねばならない
T⇒ 正定値でなければならない

正定値？
• 固有値がすべて正• あらゆる v についてv Gv  0t

無限個の制約が必要

半正定値：最小固有値で０を許す

半正定値行列
ノルム最小化問題
最小化制約

G X FX    I : 半正定値

最も近い相関行列の生成

SIMPLEによるモデル記述
Set N; // 行列の各要素
Element i(set=N),j(set=N);
Variable x(index=(i,j));Parameter a(index=(i,j)); // 与えられた行列の要素
SymmetricMatrix m((i,j));Parameter minEig; // 出力される相関行列の最小固有値
m[i,i] = 1 - minEig;// 対角は 1 とする
m[i,j] = x[i,j], i > j; // 下三角部分の定義
m >= 0; // 半正定値制約
Objective diffnrm(type=minimize); // 差の行列のノルム
diffnrm = sum(pow(x[i,j]-a[i,j],2),(i,j,i < j));実行

ロバストポートフォリオ• 収益率のぶれ（線形）U r  {r || r  r |  }• 収益率のぶれ（二次）

U r  {r | (r  r )  (r  r )   }t

1r2• 共分散のぶれU Q  {Q | Q  Q  Q }UL

non-ロバスト
リスク回避係数• マルコビッツモデル

max r x   x Qx
TTxs.t. x e  1
T

Qの変動を考慮しないロバスト• 分散のぶれを考慮

max r x   max  x Qx
w

Ts.t. x e  1
TTQL Q QU

ロバストマルコビッツモデル• 等価な問題への変形
max r T x    QU  U  QL  L xs.t.

xT e  1
U  L x  T
 01
 x
U  0, L  0

Fabozzi Kolm, Pachamanova Focardi,
Robust Portfolio Optimization and Management,2007

実行

ロバスト性の検証• 正定値行列１００ケースについてリスクを比較

端株処理• 組み入れ比率 ⇒ 購入量を得たいlongyj longrd j    mb j mb j ylongj rdlongj

理想購入量

 mb j  d

実現可能購入量

最小取引金額（価格情報含む）
longj

丸めは上か下か（０－１変数）

端株処理• 目的関数（例）– 指定した購入，売却量との差2longlongshort   y j   M short  y j   M
 1 j  T

1
j

T




2

– 理想購入量との差

 y1 j  Tlongj

ylong 2j– その他リスク尺度

  y1 j  Tshortj

yshort 2j

銘柄分割• ポートフォリオを全体属性（金額，ファクター構成）の制約下でグループ分け

 u j ,k  1k

銘柄jはグループkに属するか（０－１変数）銘柄分割
• 制約

銘柄jのmという属性の値

グループkの属性値

F   f u j ,kmkm
HIGHFjJmj

F Fmkm
LOW

属性値に関する制約

メタヒューリスティクスアルゴリズムの利用• 離散計画について
妥当な時間で良質な実行可能解⇒ グルーピング
端株処理には好適