Exponenta Banner
exponenta event banner

Квадратичное программирование для задач оптимизации портфеля на основе решателей

Открыть сценарий

В этом примере показано, как решить задачи оптимизации портфеля с помощью алгоритма квадратичного программирования внутренних точек в quadprog. Функция quadprog принадлежит Toolbox™ оптимизации.

Матрицы, определяющие задачи в этом примере, являются плотными; однако алгоритм внутренней точки в quadprog может также использовать разреженность в матрицах задач для увеличения скорости. Разреженный пример см. в разделе Большая разреженная квадратичная программа с алгоритмом внутренних точек.

Квадратичная модель

Предположим, что есть$n$ разные активы. Норма доходности актива$i$ является случайной величиной с ожидаемой стоимостью. $m_i$Проблема заключается в том, чтобы найти, какую фракцию$x_i$ инвестировать в каждый актив$i$, чтобы минимизировать риск при условии определенной минимальной ожидаемой нормы прибыли.

Пусть$C$ обозначает ковариационную матрицу скоростей возврата активов.

Классическая модель средней дисперсии состоит из минимизации риска портфеля, измеряемого

$$\frac{1}{2}x^T C x$$

с учетом набора ограничений.

Ожидаемая доходность должна быть не меньше минимальной нормы доходности портфеля$r$, которую хочет инвестор,

$$\sum_{i=1}^n m_i \; x_i \ge r,$$

сумма инвестиционных долей $x_i$должна складываться в сумме с единицей,

$$\sum_{i=1}^n x_i = 1,$$

и, будучи дробями (или процентами), они должны быть числами от нуля до единицы,

$$0 \le x_i \le 1, \;\;\; i = 1 \ldots n.$$

Поскольку цель минимизации риска портфеля - квадратичная, а ограничения - линейные, результирующей задачей оптимизации является квадратичная программа, или QP.

225-Asset Проблема

Давайте теперь решим QP с 225 активами. Набор данных получен из библиотеки OR [Chang, T.-J., Meade, N., Beasley, J.E. и Sharaiha, Y.M., «Эвристика для оптимизации портфеля ограниченных возможностей» Computers & Operations Research 27 (2000) 1271-1302].

Мы загружаем набор данных, а затем настраиваем ограничения в формате, ожидаемом quadprog. В этом наборе данных коэффициенты возврата$m_i$ находятся в диапазоне от -0.008489 до 0,003971; мы выбираем желаемую отдачу$r$ между, например, 0,002 (0,2 процента).

Загрузить набор данных, хранящийся в MAT-файле.

load('port5.mat','Correlation','stdDev_return','mean_return')

Вычислите ковариационную матрицу из корреляционной матрицы.

Covariance = Correlation .* (stdDev_return * stdDev_return');
nAssets = numel(mean_return); r = 0.002;     % number of assets and desired return
Aeq = ones(1,nAssets); beq = 1;              % equality Aeq*x = beq
Aineq = -mean_return'; bineq = -r;           % inequality Aineq*x <= bineq
lb = zeros(nAssets,1); ub = ones(nAssets,1); % bounds lb <= x <= ub
c = zeros(nAssets,1);                        % objective has no linear term; set it to zero

Выберите алгоритм внутренних точек в Quadprog

Чтобы решить QP с помощью алгоритма внутренней точки, мы задаем опцию Algorithm на 'внутренняя точка-выпукло'.

options = optimoptions('quadprog','Algorithm','interior-point-convex');

Решить проблему 225-Asset

Теперь мы задаем некоторые дополнительные опции и называем решатель квадрограммой.

Задайте дополнительные параметры: включите итеративный дисплей и установите более жесткий допуск окончания оптимальности.

options = optimoptions(options,'Display','iter','TolFun',1e-10);

Вызовите решатель и измерьте время настенных часов.

tic
[x1,fval1] = quadprog(Covariance,c,Aineq,bineq,Aeq,beq,lb,ub,[],options);
toc

 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0    2.384401e+01   2.253410e+02   1.337381e+00     1.000000e+00  
    1    1.338822e-03   7.394864e-01   4.388791e-03     1.038098e-02  
    2    1.186079e-03   6.443975e-01   3.824446e-03     8.727381e-03  
    3    5.923977e-04   2.730703e-01   1.620650e-03     1.174211e-02  
    4    5.354880e-04   5.303581e-02   3.147632e-04     1.549549e-02  
    5    5.181994e-04   2.651791e-05   1.573816e-07     2.848171e-04  
    6    5.066191e-04   9.285375e-06   5.510794e-08     1.041224e-04  
    7    3.923090e-04   7.619855e-06   4.522322e-08     5.536006e-04  
    8    3.791545e-04   1.770065e-06   1.050519e-08     1.382075e-04  
    9    2.923749e-04   8.850332e-10   5.252599e-12     3.858983e-05  
   10    2.277722e-04   4.422799e-13   2.626104e-15     6.204101e-06  
   11    1.992243e-04   1.140581e-16   2.161231e-18     4.391483e-07  
   12    1.950468e-04   0.000000e+00   1.387779e-17     1.429441e-08  
   13    1.949141e-04   1.114560e-16   1.206517e-18     9.731942e-10  
   14    1.949121e-04   6.670012e-16   2.483738e-18     2.209702e-12  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Elapsed time is 0.153874 seconds.

Результаты графика.

plotPortfDemoStandardModel(x1)

225-Asset Проблема с групповыми ограничениями

Теперь мы добавим к модельной группе ограничения, которые требуют, чтобы 30% деньги инвестора были вложены в активы 1 75, 30% в активы, 76 в 150, и 30% в активы, 151 в 225. Каждая из этих групп активов может быть, например, различными отраслями, такими как технология, автомобилестроение и фармацевтика. Ограничения, фиксирующие это новое требование:

$$\sum_{i=1}^{75} x_i \ge 0.3, \qquad$$&#xA;$$\sum_{i=76}^{150} x_i \ge 0.3, \qquad$$&#xA;$$\sum_{i=151}^{225} x_i \ge 0.3.$$

Добавление групповых ограничений к существующим равенствам.

Groups = blkdiag(ones(1,nAssets/3),ones(1,nAssets/3),ones(1,nAssets/3));
Aineq = [Aineq; -Groups];         % convert to <= constraint
bineq = [bineq; -0.3*ones(3,1)];  % by changing signs

Вызовите решатель и измерьте время настенных часов.

tic
[x2,fval2] = quadprog(Covariance,c,Aineq,bineq,Aeq,beq,lb,ub,[],options);
toc

 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0    2.384401e+01   4.464410e+02   1.337324e+00     1.000000e+00  
    1    1.346872e-03   1.474737e+00   4.417606e-03     3.414918e-02  
    2    1.190113e-03   1.280566e+00   3.835962e-03     2.934585e-02  
    3    5.990845e-04   5.560762e-01   1.665738e-03     1.320038e-02  
    4    3.890097e-04   2.780381e-04   8.328691e-07     7.287370e-03  
    5    3.887354e-04   1.480950e-06   4.436214e-09     4.641988e-05  
    6    3.387787e-04   8.425389e-07   2.523842e-09     2.578178e-05  
    7    3.089240e-04   2.707587e-07   8.110631e-10     9.217509e-06  
    8    2.639458e-04   6.586818e-08   1.973094e-10     6.509001e-06  
    9    2.252657e-04   2.225507e-08   6.666550e-11     6.783212e-06  
   10    2.105838e-04   5.811527e-09   1.740855e-11     1.967570e-06  
   11    2.024362e-04   4.129608e-12   1.237090e-14     5.924109e-08  
   12    2.009703e-04   4.289971e-15   1.369512e-17     6.353270e-10  
   13    2.009650e-04   5.555452e-16   6.938894e-18     1.596041e-13  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Elapsed time is 0.042448 seconds.

Печать результатов, наложенных на результаты предыдущей задачи.

plotPortfDemoGroupModel(x1,x2);

Резюме результатов на данный момент

Из второго штрих-графика видно, что в результате дополнительных групповых ограничений портфель теперь распределяется более равномерно по трем группам активов, чем первый портфель. Эта навязанная диверсификация также привела к небольшому увеличению риска, измеряемого целевой функцией (см. столбец «f (x)» для последней итерации в итеративном дисплее для обоих прогонов).

Проблема с 1000 активами Используя случайные данные

Для того, чтобы показать, как quadprogАлгоритм внутренней точки ведет себя с большей проблемой, мы будем использовать 1000 активов случайным образом сгенерированный набор данных. Мы генерируем случайную корреляционную матрицу (симметричную, положительно-полудефинитную, с единицами на диагонали), используя gallery функция в MATLAB ®.

Сброс случайного потока для воспроизводимости.

rng(0,'twister');
nAssets = 1000; % desired number of assets

Создать средство возврата от -0.1 до 0.4.

a = -0.1; b = 0.4;
mean_return = a + (b-a).*rand(nAssets,1);

Создайте стандартные отклонения возвратов от 0,08 до 0,6.

a = 0.08; b = 0.6;
stdDev_return = a + (b-a).*rand(nAssets,1);
% Correlation matrix, generated using Correlation = gallery('randcorr',nAssets).
% (Generating a correlation matrix of this size takes a while, so we load
% a pre-generated one instead.)
load('correlationMatrixDemo.mat','Correlation');
% Calculate covariance matrix from correlation matrix.
Covariance = Correlation .* (stdDev_return * stdDev_return');

Определение и решение случайно созданной проблемы 1000-Asset

Теперь мы определяем стандартную задачу QP (здесь нет групповых ограничений) и решаем.

r = 0.15;                                     % desired return
Aeq = ones(1,nAssets); beq = 1;               % equality Aeq*x = beq
Aineq = -mean_return'; bineq = -r;            % inequality Aineq*x <= bineq
lb = zeros(nAssets,1); ub = ones(nAssets,1);  % bounds lb <= x <= ub
c = zeros(nAssets,1);                         % objective has no linear term; set it to zero

Вызовите решатель и измерьте время настенных часов.

tic
x3 = quadprog(Covariance,c,Aineq,bineq,Aeq,beq,lb,ub,[],options);
toc

 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0    7.083800e+01   1.142266e+03   1.610094e+00     1.000000e+00  
    1    5.603619e-03   7.133717e+00   1.005541e-02     9.857295e-02  
    2    1.076070e-04   3.566858e-03   5.027704e-06     9.761758e-03  
    3    1.068230e-04   2.513041e-06   3.542286e-09     8.148386e-06  
    4    7.257177e-05   1.230928e-06   1.735068e-09     3.979480e-06  
    5    3.610589e-05   2.634706e-07   3.713780e-10     1.175001e-06  
    6    2.077811e-05   2.562892e-08   3.612554e-11     5.617206e-07  
    7    1.611590e-05   4.711765e-10   6.641535e-13     5.652911e-08  
    8    1.491953e-05   4.924477e-12   6.940646e-15     2.427880e-09  
    9    1.477930e-05   1.308120e-13   1.850666e-16     2.454705e-10  
   10    1.476910e-05   1.165734e-15   7.679047e-19     2.786060e-11  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Elapsed time is 0.429395 seconds.

Резюме

Этот пример иллюстрирует использование алгоритма внутренних точек в quadprog на задаче оптимизации портфеля и показывает время выполнения алгоритма для квадратичных задач различных размеров.

Более детальный анализ возможен с помощью функций, специально разработанных для оптимизации портфеля в Financial Toolbox™.

См. также

Документация по панели инструментов оптимизации

Поддержка