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

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

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

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

Этот пример создает последовательность задач 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™ минимизируют. Так сформулируйте задачу как минимизацию негатива цели:

Эта целевая функция нелинейна. The intlinprog Решатель 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 ®

Чтобы выразить проблемы для intlinprog решатель, вам нужно сделать следующее:

Иметь первое $$N$$ переменные представляют $$x$$ вектор, следующий $$N$$ переменные представляют двоичную единицу $$v$$ вектор, и конечная переменная представляет $$z$$ переменная slack. Есть $$2N+1$$ переменные в задаче.

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

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

Установите количество активов следующим N.

N = length(r);

Установите индексы для переменных

xvars = 1:N;
vvars = N+1:2*N;
zvar = 2*N+1;

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

lb = zeros(2*N+1,1);
ub = ones(2*N+1,1);
ub(zvar) = Inf;

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

путем написания двух линейных ограничений вида $$Ax\le b$$:

M = 150;
m = 100;
A = zeros(1,2*N+1); % Allocate A matrix
A(vvars) = 1; % A*x represents the sum of the v(i)
A = [A;-A];
b = zeros(2,1); % Allocate b vector
b(1) = M;
b(2) = -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)$$ как линейное неравенство.

Atemp = eye(N);
Amax = horzcat(Atemp,-Atemp*fmax,zeros(N,1));
A = [A;Amax];
b = [b;zeros(N,1)];
Amin = horzcat(-Atemp,Atemp*fmin,zeros(N,1));
A = [A;Amin];
b = [b;zeros(N,1)];

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

Aeq = zeros(1,2*N+1); % Allocate Aeq matrix
Aeq(xvars) = 1;
beq = 1;

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

lambda = 100;

Определите целевую функцию $$\lambda z-r^{T}x$$ как вектор. Включите нули для множителей $$v$$ переменные.

f = [-r;zeros(N,1);lambda];

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

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

options = optimoptions(@intlinprog,'Display','off'); % Suppress iterative display
[xLinInt,fval,exitFlagInt,output] = intlinprog(f,vvars,A,b,Aeq,beq,lb,ub,options);

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

thediff = 1e-4;
iter = 1; % iteration counter
assets = xLinInt(xvars); % the x variables
truequadratic = assets'*Q*assets;
zslack = xLinInt(zvar); % slack variable value
options = optimoptions(options,'LPOptimalityTolerance',1e-10,'RelativeGapTolerance',1e-8,...
                      'ConstraintTolerance',1e-9,'IntegerTolerance',1e-6);

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

history = [truequadratic,zslack];

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

В синтаксисе тулбокса каждое новое линейное ограничение $$Ax\le b$$ происходит от линейного приближения

Вы видите, что новая строка $$A=2x_k^{T}Q$$ и новый элемент в $$b=x_k^{T}Q{x}_k$$, с $$z$$ член, представленный коэффициентом -1 в $$A$$.

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

while abs((zslack - truequadratic)/truequadratic) > thediff % relative error
    newArow = horzcat(2*assets'*Q,zeros(1,N),-1); % Linearized constraint
    rhs = assets'*Q*assets;                       % right hand side of the linearized constraint
    A = [A;newArow];
    b = [b;rhs];
    % Solve the problem with the new constraints
    [xLinInt,fval,exitFlagInt,output] = intlinprog(f,vvars,A,b,Aeq,beq,lb,ub,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).