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

Открыть скрипт

В этом примере показано, как решить задачи оптимизации портфеля с помощью квадратичного алгоритма программирования внутренних точек в quadprog. Функция quadprog принадлежит Optimization 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. and Sharaiha, Y.M., «Eurististics for cardinality constabled portfolio optimization» Computers & Операции 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 на 'interior-point-convex'.

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

Решите 225-Asset задачу

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

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

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-Asset задачи с использованием случайных данных

В порядок показать, как quadprogалгоритм внутренней точки ведет себя на большей задаче, мы будем использовать 1000-asset случайным образом сгенерированный набор данных. Мы генерируем матрицу случайной корреляции (симметричную, положительно-полусемидефинитную, с таковыми на диагонали), используя 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™.

См. также

Документация по Optimization Toolbox

Поддержка

Для просмотра документации необходимо авторизоваться на сайте