Контур задачи

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

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

Вы не можете включать эти ограничения в quadprog. Сложность является дискретной природой ограничений. Кроме того, в то время как смешано-целочисленный решатель линейного программирования обрабатывает дискретные ограничения, он не затрагивает квадратичные целевые функции.

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

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

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

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

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

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

Целевые и последующие линейные приближения

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

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

Когда вы итерационно решаете приближения MILP, вы включаете новые линейные ограничения, каждый из которых аппроксимирует нелинейное ограничение локально вблизи текущей точки. В частности, для $$x=x_0+\delta$$ где $$x_0$$ является постоянным вектором и $$\delta$$ является вектором, приближение Тейлора первого порядка к ограничению является

Замена $$\delta$$ около $$x-x_0$$ дает

Для каждого промежуточного решения $$x_k$$ вы вводите новое линейное ограничение в $$x$$ и $$z$$ как линейная часть выражения выше:

Это имеет форму $$Ax\le b$$, где $$A=2x_k^{T}Q$$, существует $$-1$$ множитель для $$z$$ термин, и $$b=x_k^{T}Q{x}_k$$.

Этот метод добавления новых линейных ограничений к задаче называется методом секущей плоскости. Для получения дополнительной информации см. J. E. Kelley, Jr. Метод секущей плоскости для решения выпуклых программ. J. Soc. Indust. Appl. Math. Vol. 8, No 4, pp. 703-712, December, 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$$ переменная, a положительной скалярной величины.

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)\le fmax(i)*v(i)$$ и $$fmin(i)*v(i)\le x(i)$$.

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

Включите ограничение, что портфель инвестирован на 100%, что означает $$\sum x_i=1$$.

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

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

lambda = 100;

Определите целевую функцию $$r^{T}x-\lambda z$$ и включить его в задачу.

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

Решите задачу

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

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

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

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

Сохраните историю вычисленных переменных true quadratic и slack для графического изображения. Установите более жесткие допуски, чем по умолчанию, чтобы итерации сходились к правильному решению.

history = [truequadratic,zslack];

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

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

Каждое новое линейное ограничение $$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

Исследуйте решение и скорость сходимости

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

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

Каково качество решения MILP? The 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')

Можно легко увидеть, что все ненулевые распределения активов находятся между полунепрерывными границами $$fmin=0.001$$ и $$fmax=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).