1 , 0
j j
j Asset
x x
StQP
StQP
の最適解はが強凸であるようなフェース
の
relative interior
に 存在する．( ) I
x Qx t
Francesco Cesarone,Andrea Scozzari, and Fabio Tardella, A new method for mean-variance portfolio optimization with cardinality constraints
半正定値に 限らない
最小化 制約
x Qx t
1 , 0
j j
j I Asset
x x
これも
StQP
が強凸であるようなフェース
を
について
調べ尽くせば銘柄数制約付き分散モデルの 大域的最適解を見逃すことはない
x Qx t ( ) I
,
I Asset I K
I K
エレガントな解決：
StQP に関する事実の応用
正定値な
の部分行列の
インデックスの集合の中に はある ⇒ インデックス について
の部分行列が正定値でなければ，
を含むあらゆる集合は に成り得ない ⇒
Increasing Set Algorithm
Q
I 0
I *
I 0
I *
最適解を与える集合
複数のベンチマーク問題に厳密解を 与えることに成功
Q
エレガントな解決：
StQP に関する事実の応用
StQP
に関する事実の応用そういえば．．
•
ポートフォリオ最適化問題で選択される銘柄は一般に少ない
（⇒有効制約法が有利）
ヘッセ行列が 低ランク
なことが理由では？
long/short ポジションを許容する リスク最小化
最小化
制約
L 1 , L 0
j j
j Asset
x x
0 0
L S
j j
x
またはx
( x L x S t ) Q x ( L x S )
1 , 0
S S
j j
j Asset
x x
とりあえず
分枝限定法（ MIQP ）
最小化
制約
L 1 , L 0
j j
j Asset
x x
( x L x S t ) Q x ( L x S )
1 , 0
S S
j j
j Asset
x x
, (1 ) , {0,1}
L S
j x j j x j j
•
連続緩和問題の補強とりあえず
分枝限定法（ MIQP ）
収益率制約や複雑な投資制約が助けになっていた．．
PROBLEM_NAME iqp NUMBER_OF_VARIABLES 600 (#INTEGER/DISCRETE) 200 NUMBER_OF_FUNCTIONS 603 PROBLEM_TYPE MINIMIZATION METHOD ACTIVE_SET_QP
<preprocess begin>...<preprocess end>
<iteration begin>
.1.2B
up: 1e+050 lo:7.2290069e-020 time: 0.5s:mem(Mb)=77/57:avail(Mb)=4039/1872 llen:0 #prob:0 #piv:173
#1 up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time: 33.4s:mem(Mb)=111/91:avail(Mb)=4004/1837 llen:1286 #prob:2702 #piv:181822
up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time: 61.8s:mem(Mb)=139/119:avail(Mb)=3977/1808 llen:2364 #prob:5329 #piv:345892
up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time:124.7s:mem(Mb)=153/133:avail(Mb)=3963/1793 llen:2904 #prob:7589 #piv:720381
up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time:184.0s:mem(Mb)=177/157:avail(Mb)=3938/1768 llen:3808 #prob:9569 #piv:1046687
up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time:187.2s:mem(Mb)=178/157:avail(Mb)=3939/1767 llen:3856 #prob:9689 #piv:1066187
•
制約なしの場合．．とりあえず
分枝限定法（ MIQP ）
PROBLEM_NAME iqp NUMBER_OF_VARIABLES 600 (#INTEGER/DISCRETE) 200 NUMBER_OF_FUNCTIONS 603 PROBLEM_TYPE MINIMIZATION METHOD ACTIVE_SET_QP
<preprocess begin>...<preprocess end>
<iteration begin>
.1.2B
up: 1e+050 lo:7.2290069e-020 time: 0.5s:mem(Mb)=77/57:avail(Mb)=4039/1872 llen:0 #prob:0 #piv:173
#1 up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time: 33.4s:mem(Mb)=111/91:avail(Mb)=4004/1837 llen:1286 #prob:2702 #piv:181822
up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time: 61.8s:mem(Mb)=139/119:avail(Mb)=3977/1808 llen:2364 #prob:5329 #piv:345892
up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time:124.7s:mem(Mb)=153/133:avail(Mb)=3963/1793 llen:2904 #prob:7589 #piv:720381
up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time:184.0s:mem(Mb)=177/157:avail(Mb)=3938/1768 llen:3808 #prob:9569 #piv:1046687
up: 211.13232 lo:7.2290069e-020 gap: 211.13232 time:187.2s:mem(Mb)=178/157:avail(Mb)=3939/1767 llen:3856 #prob:9689 #piv:1066187
•
制約なしの場合．．分枝限定法は全探索と同じ：
緩和解は相補性を満たさず 目的関数は零
とりあえず
分枝限定法（ MIQP ）
•
相補性条件を緩和した問題( )
L t L
S S
x x
x M x
M ( ) Q Q
Q Q
最小化
制約
L j 1
j Asset
x
S j 1
j Asset
x
, 0,
L S
j j
x x j Asset
が半正定値ならば解ける！
( ) L
( ) M
緩和⇒ＳＤＰを利用した補強の導出
•
の最小値を最大化する問題 （ＳＤＰ）最小化 制約
( ) L
,( ) ,( )
,( ) ,( )
,( ) ,( )
L i T L i
L i S i
j j j
S i S i
j S
Q Q
x x
x x
Q Q
x x
1,.., i I ( ) 0
M
（半正定値）過去の反復で得られた解 変数
緩和⇒ＳＤＰを利用した補強の導出
• n=200
での実験結果緩和⇒ＳＤＰを利用した補強の導出
• λ
を用いて補強されたMIQP
最小化
制約
L 1 , L 0
j j
j Asset
x x
1 , 0
S S
j j
j Asset
x x
( )
L t L
S S
x x
x M x
, (1 ) , {0,1}
L S
j x j j x j j
緩和⇒ＳＤＰを利用した補強の導出
PROBLEM_NAME qp_int NUMBER_OF_VARIABLES 600 (#INTEGER/DISCRETE) 200 NUMBER_OF_FUNCTIONS 603 PROBLEM_TYPE MINIMIZATION METHOD ACTIVE_SET_QP
<preprocess begin>...<preprocess end>
<iteration begin>
.1...2B
up: 1e+050 lo: 65.069268 time: 1.4s:mem(Mb)=51/32:avail(Mb)=4064/1897 llen:0 #prob:0 #piv:797
up: 1e+050 lo: 65.202836 time: 65.1s:mem(Mb)=59/39:avail(Mb)=4058/1890 llen:1 #prob:349 #piv:136291
up: 1e+050 lo: 65.507298 time:127.3s:mem(Mb)=59/40:avail(Mb)=4055/1888 llen:360 #prob:1119 #piv:357707
up: 1e+050 lo: 65.507298 time:189.1s:mem(Mb)=75/56:avail(Mb)=4041/1874 llen:985 #prob:2369 #piv:649083
#1 up: 78.939007 lo: 65.507298 gap: 13.431709 time:192.7s:mem(Mb)=77/57:avail(Mb)=4039/1872 llen:1034 #prob:2472 #piv:670000
#2 up: 77.947918 lo: 65.507298 gap: 12.44062 time:192.8s:mem(Mb)=77/58:avail(Mb)=4038/1871 llen:1007 #prob:2473 #piv:670194
#3 up: 77.930633 lo: 65.507298 gap: 12.423335 time:193.5s:mem(Mb)=76/57:avail(Mb)=4040/1873 llen:1006 #prob:2498 #piv:674716
#4 up: 77.928705 lo: 65.507298 gap: 12.421407 time:193.8s:mem(Mb)=76/57:avail(Mb)=4039/1872 llen:1006 #prob:2508 #piv:676891
up: 77.928705 lo: 65.507298 gap: 12.421407 time:249.1s:mem(Mb)=88/68:avail(Mb)=4028/1860 llen:1455 #prob:3488 #piv:919435
50
銘柄程度ならば厳密解が得られる場合も．．
緩和⇒ＳＤＰを利用した補強の導出
Copositive Programming に帰着
•
等価な定式化（Copositive Programming
の 双対形）completely positive
matrix
のcone
の集合エレガントな解決：
？
偏微分方程式制約付き最適化 PDE constrained optimization
( i i ) 2 i
( , ) 0 F
最小化
変数
, i i
制約
離散点での物理量 パラメータ
観測点での値
離散化された 物理方程式
パラメータと物理量を同時に解く
偏微分方程式制約付き最適化 動機づけ
Gassan S Abdoulaev, Kui Ren and Andreas H Hielscher,
Optical tomography as a PDE-constrained optimization problem,
Inverse Problems 21 (2005) 1507–1530
偏微分方程式制約付き最適化
「最適化」の位置づけ
協働の絶好の素材ではないでしょうか．．．
偏微分方程式制約付き最適化 最適化問題としての側面
○ 不等式制約はほぼ効かない
○ ＫＫＴ条件は線形性が強い
× 超大規模（⇒反復法必須）
× ヘッセ行列の正定値性は保障できない
（⇒正規化項の導入）
偏微分方程式制約付き最適化
解くべき一次方程式
t
x
y
x b H A
y b
A W
またお会いしましたね．．
“
Saddle Point System
”正規化項を加えて優対角にはできる
Augumented Lagrangean
のペナルティの逆数偏微分方程式制約付き最適化
内点法の場合との違い
61
t
x
y
x b H A
y b
A W
超大規模（⇒反復法必須
）正定値性への目配りが必要に
前処理なし反復法での限界
•
正規化項を手厚くする•
次の形に変形してＣＧ法
1
H AW A t x b
似たような方に以前お目にかか ったような．．
計算の安定化（ＣＧ反復減少）
正規化項増大で非物理的解
の構成が鍵
（
approximate Schur complement
）エレガントな解決？
Constraint Preconditioner
1
1
t t
t
H A H A
A AH A S A W
, 1 t
H H S AH A W
あなたは．．!
S
エレガントな解決？
Approximate Schur complement
を左辺とする一次方程式解法•
を対角行列に置き換えてコレスキー分解• multigrid
法による前処理行列でCG
法•
ノルムの定義を変更してCG
法•
対角スケーリングしてCG
法を数回適用したものを前処理 行列としてGMRES
法•
ピボット選択付きの分解を数ステップ行ったものを前処理 行列としてGMRES
法
, 1 t
H H S AH A W
今度は近似で良いので自由度が高い