Структура проблемы

Как показал Марковиц («Portfolio Selection», J. Finance Volume 7, Issue 1, pp. 77-91, March 1952), многие задачи оптимизации портфеля можно выразить как задачи квадратичного программирования. Предположим, что у вас есть набор N Если $$$$$$$$вы знаете вектор $$$$r средней доходности каждого актива и ковариационную матрицу $$$$Q доходности, то для данного уровня отклонения от риска $$$$λ вы максимизируете скорректированную на риск ожидаемую доходность:

quadprog решатель решает эту проблему квадратичного программирования. Однако в дополнение к проблеме простого квадратичного программирования можно ограничить портфолио различными способами, такими как:

Нельзя включать эти ограничения в quadprog. Трудность заключается в дискретном характере ограничений. Кроме того, хотя решатель линейного программирования со смешанными целыми значениями действительно обрабатывает дискретные ограничения, он не обращается к квадратным объективным функциям.

Этот пример строит последовательность задач MILP, которые удовлетворяют ограничениям, и которые все больше аппроксимируют квадратичную целевую функцию. Хотя этот метод работает в этом примере, он может не применяться к другим типам проблем или ограничений.

Начните с моделирования зависимостей.

Моделирование дискретных ограничений

$$x$$ - вектор дробей распределения основных средств, с $$\mathrm{}\mathrm{0\le x}(i)\mathrm{}$$≤1 для $$\mathrm{каждого}$$из них. Для моделирования количества основных средств в портфеле необходимы $$\mathrm{переменные\; индикатора}$$v, так $$\mathrm{что}v(\mathrm{i}$$) = 0, $$когда\mathrm{x}$$(i) = $$0,\mathrm{}$$и v (i$$)=1,\mathrm{}$$когда x (i) > 0. Чтобы получить переменные, удовлетворяющие этому $$$$ограничению, задайте вектор v как двоичную переменную и наложите линейные ограничения

Эти неравенства обеспечивают, что $$x(i$$) и $$v($$i) равны нулю точно в одно и то же время, и они также обеспечивают, $$\mathrm{что}\mathrm{fmin\le x}(i)$$≤fmax $$\mathrm{всякий\; раз,\; когда}x\mathrm{}$$(i) > 0.

Кроме того, для обеспечения соблюдения ограничений на количество активов в портфеле, наложить линейные ограничения

Целевые и последовательные линейные приближения

В соответствии с первой формулировкой, вы пытаетесь максимизировать целевую функцию. Однако все решатели Optimization Toolbox™ минимизируются. Так что сформулируйте проблему как минимизирующую негатив цели:

Эта целевая функция нелинейна. Решателю MILP требуется линейная целевая функция. Существует стандартный метод переформулировать эту проблему в задачу с линейными объективными и нелинейными ограничениями. Введите переменную провисания $$z$$ для представления квадратичного члена.

При итеративном решении аппроксимаций MILP включаются новые линейные ограничения, каждое из которых аппроксимирует нелинейное ограничение локально вблизи текущей точки. В частности, для $$x{=}_{\mathrm{}}\mathrm{x0}$$ + δ, $${}_{\mathrm{}}$$где x0 - постоянный вектор, $$$$а δ - переменный вектор, аппроксимация Тейлора первого порядка к ограничению равна

Замена $$\delta$$ на $${}_{\mathrm{x-x0}}$$ дает

Для каждого промежуточного решения $${}_{\mathrm{xk}}$$ вводится новое линейное ограничение в $$x$$ и $$z$$ в качестве линейной части выражения выше:

Имеет вид $$\mathrm{Ax\le b}$$, где $$A\mathrm{=}{}_{}^{}$$2xkTQ, имеется $$\mathrm{}$$множитель -1 для $$$$z-члена $$иb_{}^{=}{}_{}$$xkTQxk.

Этот метод добавления новых линейных ограничений к задаче называется методом секущей плоскости. Подробнее см. J. E. Kelley, Jr. «Метод секущей плоскости для решения выпуклых программ». Дж. Соц. Индуст. прим. мат. т. 8, № 4, стр. 703-712, декабрь 1960.

Формулировка проблемы MATLAB ®

Чтобы выразить проблемы оптимизации:

Загрузите данные для проблемы. Эти данные имеют 225 ожидаемых результатов в векторе r и ковариация возвратов в матрице 225 на 225 Q. Данные те же, что и в примере Использование квадратичного программирования для задач оптимизации портфеля.

load port5
r = mean_return;
Q = Correlation .* (stdDev_return * stdDev_return');

Установить количество основных средств как N.

N = length(r);

Создание переменных проблемы, ограничений и цели

Создание непрерывных переменных xvars представление доли распределения активов, двоичные переменные vvars представление, является ли связанный xvars является нулевым или строго положительным, и zvar представляет $$$$переменную z, положительный скаляр.

xvars = optimvar('xvars',N,1,'LowerBound',0,'UpperBound',1);
vvars = optimvar('vvars',N,1,'Type','integer','LowerBound',0,'UpperBound',1);
zvar = optimvar('zvar',1,'LowerBound',0);

Нижние границы всех 2N+1 переменные в задаче равны нулю. Верхние границы xvars и yvars переменные равны единице, и zvar не имеет верхней границы.

Установите количество основных средств в решении в диапазоне от 100 до 150. Включить это ограничение в проблему в форме, а именно

путем записи двух линейных зависимостей:

M = 150;
m = 100;
qpprob = optimproblem('ObjectiveSense','maximize');
qpprob.Constraints.mconstr = sum(vvars) <= M;
qpprob.Constraints.mconstr2 = sum(vvars) >= m;

Включить полунепрерывные ограничения. Возьмите минимальную ненулевую долю активов, чтобы быть 0.001 для каждого вида основного средства и максимальная доля, которая должна быть 0.05.

fmin = 0.001;
fmax = 0.05;

Включают неравенство $$x(i)\mathrm{\le fmax}(i)*$$ v (i$$)иfmin(i)*$$v (i) ≤x (i).

qpprob.Constraints.fmaxconstr = xvars <= fmax*vvars;
qpprob.Constraints.fminconstr = fmin*vvars <= xvars;

Включите ограничение, заключающееся в том, что портфель инвестирован на 100%, что означает $${}_{}\mathrm{\sum xi=1}$$.

qpprob.Constraints.allin = sum(xvars) == 1;

Установите коэффициент отклонения от риска $$\lambda$$ в значение 100.

lambda = 100;

Определите целевую функцию $${}^{}\mathrm{rTx-\lambda \; z}$$ и включите ее в задачу.

qpprob.Objective = r'*xvars - lambda*zvar;

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

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

options = optimoptions(@intlinprog,'Display','off'); % Suppress iterative display
[xLinInt,fval,exitFlagInt,output] = solve(qpprob,'options',options);

Подготовьте условие остановки для итераций: остановитесь, если переменная провисания $$z$$ находится в пределах 0,01% от истинного квадратичного значения.

thediff = 1e-4;
iter = 1; % iteration counter
assets = xLinInt.xvars;
truequadratic = assets'*Q*assets;
zslack = xLinInt.zvar;

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

history = [truequadratic,zslack];

options = optimoptions(options,'LPOptimalityTolerance',1e-10,'RelativeGapTolerance',1e-8,...
                      'ConstraintTolerance',1e-9,'IntegerTolerance',1e-6);

Вычислите квадратичные и слабые значения. Если они отличаются, добавьте еще одно линейное ограничение и решите снова.

Каждая новая линейная зависимость $$\mathrm{Ax\le b}$$ происходит от линейной аппроксимации

После поиска нового решения используйте линейное ограничение на полпути между старым и новым решениями. Этот эвристический способ включения линейных ограничений может быть более быстрым, чем простой выбор нового решения. Чтобы использовать решение вместо эвристики половины пути, прокомментируйте строку «Midway» ниже и раскомментируйте следующую.

while abs((zslack - truequadratic)/truequadratic) > thediff % relative error
    constr = 2*assets'*Q*xvars - zvar <= assets'*Q*assets;
    newname = ['iteration',num2str(iter)];
    qpprob.Constraints.(newname) = constr;
    % Solve the problem with the new constraints
    [xLinInt,fval,exitFlagInt,output] = solve(qpprob,'options',options);
    assets = (assets+xLinInt.xvars)/2; % Midway from the previous to the current
%     assets = xLinInt(xvars); % Use the previous line or this one
    truequadratic = xLinInt.xvars'*Q*xLinInt.xvars;
    zslack = xLinInt.zvar;
    history = [history;truequadratic,zslack];
    iter = iter + 1;
end

Анализ решения и скорости сходимости

Постройте график истории переменной слабости и квадратичной части целевой функции, чтобы увидеть, как они сошлись.

plot(history)
legend('Quadratic','Slack')
xlabel('Iteration number')
title('Quadratic and linear approximation (slack)')

Каково качество решения MILP? output структура содержит эту информацию. Проверьте абсолютный разрыв между внутренними вычисленными границами цели в решении.

disp(output.absolutegap)

     0

Абсолютный промежуток равен нулю, что указывает на точность решения MILP.

Постройте график оптимального распределения. Использовать xLinInt.xvars, не assets, потому что assets может не удовлетворять ограничениям при использовании промежуточного обновления.

bar(xLinInt.xvars)
grid on
xlabel('Asset index')
ylabel('Proportion of investment')
title('Optimal asset allocation')

Легко увидеть, что все ненулевые соотнесения основных средств находятся между полунепрерывными границами $$\mathrm{fmin}\mathrm{=}\mathrm{}\mathrm{}\mathrm{}$$0,001 $$и\mathrm{fmax}\mathrm{=}\mathrm{}$$0,05.

Сколько ненулевых активов? Ограничение состоит в том, что имеется от 100 до 150 ненулевых активов.

sum(xLinInt.vvars)

ans = 100

Какова ожидаемая доходность для этого распределения и значение доходности с поправкой на риск?

fprintf('The expected return is %g, and the risk-adjusted return is %g.\n',...
    r'*xLinInt.xvars,fval)

The expected return is 0.000595107, and the risk-adjusted return is -0.0360382.

Более детальный анализ возможен с помощью функций, специально разработанных для оптимизации портфеля в Financial Toolbox ®. Пример использования класса Portfolio для непосредственной обработки полунепрерывных ограничений и ограничений количества элементов см. в разделе Оптимизация портфеля с полунепрерывными ограничениями и ограничениями количества элементов (Financial Toolbox).