Проблемная схема

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

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 требует линейной целевой функции. Существует стандартный метод, чтобы переформулировать эту проблему в одну с линейными объективными и нелинейными ограничениями. Введите слабую переменную $$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$$, существует a $$-1$$ множитель для $$z$$ назовите, и $$b=x_k^{T}Q{x}_k$$.

Этот метод добавления новых линейных ограничений к проблеме называется сокращающим плоским методом. Для получения дополнительной информации смотрите Дж. Э. Келли младшего "Плоский Сокращением Метод для Решения Выпуклых Программ". Дж. Сок. Indust. Прикладная Математика. Издание 8, № 4, стр 703-712, декабрь 1960.

MATLAB® Problem Formulation

Выражать задачи оптимизации:

Загрузите данные для проблемы. Эти данные имеют 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)\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);

Подготовьте останавливающееся условие к итерациям: остановитесь когда слабая переменная $$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);

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

Каждое новое линейное ограничение $$Ax\le b$$ прибывает из линейной аппроксимации

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

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')

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

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