混合整数二次計画法ポ,トフォリオ最適化問題:問題ベ,ス
この例では,問題ベースアプローチを使用して,混合整数二次計画法(MIQP)のポートフォリオ最適化問題の解法を示します。考え方としては,MIQP問題を局所的に近似する一連の混合整数線形計画法(MILP)の解を反復的に求めるというものです。ソルバベスのアプロチにいては,混合整数二次計画法ポトフォリオ最適化問題:ソルバベスを参照してください。
問題の概要
马科维茨が示したように,多くのポートフォリオ最適化問題は二次計画問題として表されます(“投资组合选择,”j .金融卷7,问题1,第91 - 77页,1952年3月)。N
件の項目から成る一連の資産があり,ポ,トフォリオを選ぶとします。ここで
は資産
における投資割合です。各資産の平均収益のベクトル
および収益の共分散行列
がわかっている場合,与えられた危険回避のレベル
に対し,リスク調整後の期待収益を最大化します。
quadprog
ソルバ,を使用してこの二次計画問題を解きます。しかし,そのままの二次計画問題に加えて,ポートフォリオに次のようなさまざまな制限をかけることが必要な場合があります。
ポ,トフォリオに含まれる資産が
米
個を超えないものとする。ここでM <= n
。ポ,トフォリオが少なくとも
米
個の資産を含むとする。ここで0 < m <= m
。“半連続的な”制約があるものとする。これは, であるか, および のいくいて であることを意味します。
quadprog
にこれらの制約を含めることはできません。難しいのは,制約の離散的な性質です。さらに,混合整数線形計画法ソルバ,は離散的な制約は処理できますが,二次目的関数は扱いません。
この例では,制約を満たすと共に,しだいに二次の目的関数を近似するようになる一連のMILP問題を作成します。この手法はこの例にいては機能しますが,他の問題や制約のタプには当てはまらない場合があります。
まず制約をモデル化します。
離散的な制約のモデル化
は資産配分の割合を表すベクトルであり,各 にいて です。ポ,トフォリオに含まれる資産の個数をモデル化するため, の場合は 、 の場合は になるように指標変数 を設定します。この制限を満たす変数を得るため,ベクトル をバesc escナリ変数に設定し,線形制約を課します。
これらの不等式によって, と はまったく同時にゼロになります。また, の場合は常に, になります。
また,ポ,トフォリオ内の資産数への制約を実現させるため,線形制約を課します。
目的関数および連続的線形近似
最初に定式化したように,目的関数を最大化しようと試みます。ところが、Optimization Toolbox™ のソルバーではすべて最小化されます。そこで、目的関数の負の値を最小化するように問題を定式化します。
この目的関数は非線形です。米ILP ソルバーには線形目的関数が必要です。この問題を線形目的関数と非線形な制約をもつ問題に再度定式化する標準の手法があります。二次の項を表すためにスラック変数 を導入します。
MILP近似を反復的に解く際,新規の線形制約を組み込み,各制約によって,現在の点の近くにある非線形な制約を局所的に近似します。具体的には, が定数ベクトル, が変数ベクトルである に。
を で置き換えると,次のようになります。
各中間解 にいて,上式の線形部分として と に新しい線形制約を導入します。
これは という形式になります。ここで, 、 項の乗数は 、 です。
問題に新規の線形制約を追加するこの方法は,切除平面法と呼ばれます.詳細にいては,j。小凯利求解凸程序的切平面法j . Soc.Indust.Appl.Math.Vol。8,第4期,第703-712页,1960年12月を参照してください。
Matlab®での問題の定式化
最適化問題を表すには,次を行います。
変数が表す内容の決定
これらの変数の下限と上限の明示
線形の等式および不等式の指定
問題のデ,タを読み込みます。このデ,タには,ベクトルr
に含まれる225個の期待される収益と,225行225列の行列问
に含まれる収益の共分散があります。デ,タは,“ポ,トフォリオ最適化問題に対する二次計画法の使用”の例と同じです。
负载port5R = mean_return;Q =相关性。* (stdDev_return * stdDev_return');
資産の数をN
に設定します。
N =长度(r);
問題の変数,制約および目的の作成
資産配分の割合を表す連続変数xvars
,関連付けられたxvars
がゼロと厳密に正のどらであるかを示すバナリ変数vvars
,および正のスカラ,である変数
を表すzvar
を作成します。
Xvars = optimvar(“xvars”N 1下界的0,“UpperBound”1);vars = optimvar(“vvars”N 1“类型”,“整数”,下界的0,“UpperBound”1);Zvar = optimvar(“zvar”,1,下界的, 0);
問題において2 n + 1
個のすべての変数の下限はゼロです。変数xvars
およびyvars
の上限は1で,zvar
には上限はありません。
解における資産の数を100 ~ 150に設定します。この制約を次の形式で問題に組み込みます。
2の線形制約で記述するとこうなります。
M = 150;M = 100;Qpprob =优化问题(“ObjectiveSense”,“最大化”);qpprov . constraints .mconstr = sum(vars) <= M;qpprob.Constraints。米constr2 = sum(vvars) >= m;
半連続的な制約を含めます。それぞれの資産タ▪▪プに▪▪いて,非ゼロの最小の資産の割合を0.001
に,また,最大の割合を0.05
にします。
Fmin = 0.001;Fmax = 0.05;
不等式 および を含めます。
qpprov . constraints .fmaxconstr = xvars <= fmax* vars;qpprov . constraints .fminconstr = fmin* vars <= xvars;
ポトフォリオは100%運用であるという制約を含めます。これは, を意味します。
qpprov . constraints .allin = sum(xvars) == 1;
危険回避係数
をOne hundred.
に設定します。
Lambda = 100;
目的関数 を定義し,問題に含めます。
qpprob。Objective = r'*xvars - lambda*zvar;
問題を解く
問題を反復的に解くために,現在の制約をも問題を解くことから始めます。現在の制約にいては,いかなる線形化も実施していません。
选项= optimoptions(@intlinprog,“显示”,“关闭”);抑制迭代显示[xLinInt,fval,exitFlagInt,output] = solve(qpprob,“选项”、选择);
反復の停止条件を決めます。スラック変数 が真の二次値の0.01%以内になったときに反復を止めます。
Thediff = 1e-4;Iter = 1;%迭代计数器assets = xLinInt.xvars;truequadatic =资产的*Q*资产;zslack = xLinInt.zvar;
プロットするために二次の真値とスラック変数の計算履歴を保存します。反復が正しい解に収束するように,許容誤差を既定より小さくします。
History = [truequadratic,zslack];选项= optimoptions(选项,“LPOptimalityTolerance”1平台以及“RelativeGapTolerance”1 e-8...“ConstraintTolerance”1 e-9“IntegerTolerance”1 e-6);
二次の値およびスラック変数の値を計算します。それらが異なる場合は,別の線形制約を追加して再度解を求めます。
新しい各線形制約 は次の線形近似から得られます。
新規の解が求まったら,元の解と新規解の中間にある線形制約を使用します。線形制約を含んでいるこのヒューリスティックな方法のほうが,単純に新規解を用いるよりも高速になる場合があります。この中間のヒューリスティックな方法の代わりに解を使う場合は,下記の中途“の行にコメントし,その次の行のコメントを解除します。
而Abs ((zslack - truequadatic)/ truequadatic) > thediff%相对误差constr = 2*assets'*Q*xvars - zvar <= assets'*Q*assets;新名字= [“迭代”num2str (iter)];qpprop . constraints .(newname) = constr;用新的约束条件解决问题。[xLinInt,fval,exitFlagInt,output] = solve(qpprob,“选项”、选择);assets = (assets+xLinInt.xvars)/2;从以前到现在的中途% assets = xLinInt(xvars);使用前一行或这一行truequadratic = xLinInt.xvars'*Q*xLinInt.xvars;zslack = xLinInt.zvar;历史=[历史;truequadratic,zslack];Iter = Iter + 1;结束
解と収束率の検証
スラック変数と目的関数の二次の部分の計算履歴をプロットしてどのように収束するかを確認します。
情节(历史)传说(“二次”,“松弛”)包含(的迭代次数)标题(二次和线性逼近(松弛))
米尔普の解はどのような品質でしょうか。输出
構造体に,その情報が含まれます。解における,内部で計算された目的関数の限界値間のギャップの絶対値を検証します。
disp (output.absolutegap)
0
ギャップの絶対値はゼロであり,milpの解は正確であることを示しています。
最適な資産配分をプロットします。中間位置での更新を使用すると,资产
は制約を満たさない可能性があるため,资产
ではなく,xLinInt.xvars
を使用します。
栏(xLinInt.xvars)网格在包含(“资产指数”) ylabel (“投资比例”)标题(“最优资产配置”)
非ゼロの資産配分のすべてが半連続的な範囲 と の間にあることが簡単に確認できます。
非ゼロの資産がいくあるでしょうか。制約は,非ゼロの資産の数が100 ~ 150です。
总和(xLinInt.vvars)
Ans = 100
この資産配分により期待される収益,そしてリスク調整された収益値はどれほどでしょうか。
流(“预期收益为%g,风险调整收益为%g。\n”,...r * xLinInt.xvars, fval)
预期收益为0.000595107,风险调整收益为-0.0360382。
特にポートフォリオ最適化用に設計された機能を金融工具箱®で使用すると,より詳細な分析が可能です。ポトフォリオクラスを使用して半連続および濃度の制約を直接処理する方法を示す例にいては,基于半连续和基数约束的投资组合优化(金融工具箱)を参照してください。