В этом примере показано, как решить задачу оптимизации портфеля MIQP с использованием основанного на проблеме подхода. Идея состоит в том, чтобы итерационно решить последовательность задач смешано-целочисленного линейного программирования (MILP), которые локально аппроксимируют задачу MIQP. Для основанного на решателе подхода смотрите Mixed-Integer Quadratic Programming Portfolio Optimization: Solver-Based.
Как показал Марковиц («Выбор портфеля», J. Finance Volume 7, Issue 1, pp. 77-91, March 1952), можно выразить множество задач оптимизации портфеля как квадратичные задачи программирования. Предположим, что у вас есть набор N
активы и хотят выбрать портфель, с будучи частью ваших инвестиций, которые находятся в активе . Если вы знаете вектор средних возвратов каждого актива и ковариационной матрицы из возвратов, затем для заданного уровня риска-отвращения Вы максимизируете ожидаемый возврат, скорректированную по риску:
The quadprog
решатель решает эту квадратичную задачу программирования. Однако в дополнение к простой квадратичной задаче программирования можно хотеть ограничить портфолио различными способами, такими как:
Имеющий не более M
активы в портфеле, где M <= N
.
Иметь по крайней мере m
активы в портфеле, где 0 < m <= M
.
Имеющий полунепрерывные ограничения, означающие либо , или для некоторых фиксированных дробей и .
Вы не можете включать эти ограничения в quadprog
. Сложность является дискретной природой ограничений. Кроме того, в то время как смешано-целочисленный решатель линейного программирования обрабатывает дискретные ограничения, он не затрагивает квадратичные целевые функции.
Этот пример создает последовательность задач MILP, которые удовлетворяют ограничениям и которые все чаще аппроксимируют квадратичную целевую функцию. Хотя этот метод работает для этого примера, он может не применяться к другим типам задач или ограничений.
Начните с моделирования ограничений.
- вектор дробей распределения активов, с для каждого . Чтобы смоделировать количество активов в портфеле, нужны переменные показателя таким, что когда , и когда . Чтобы получить переменные, которые удовлетворяют этому ограничению, установите вектор, который будет двоичной переменной и накладывает линейные ограничения
Оба эти неравенства приводят в действие то, что и являются нулем в точно то же время, и они также обеспечивают, что каждый раз, когда .
Кроме того, чтобы применить ограничения на количество активов в портфеле, накладывайте линейные ограничения
Как впервые сформулировано, вы пытаетесь максимизировать целевую функцию. Однако все решатели Optimization Toolbox™ минимизируют. Так сформулируйте задачу как минимизацию негатива цели:
Эта целевая функция нелинейна. Решатель MILP требует линейной целевой функции. Существует стандартный метод для преобразования этой задачи в задачу с линейными целевыми и нелинейными ограничениями. Введите переменную slack для представления квадратичного термина.
Когда вы итерационно решаете приближения MILP, вы включаете новые линейные ограничения, каждый из которых аппроксимирует нелинейное ограничение локально вблизи текущей точки. В частности, для где является постоянным вектором и является вектором, приближение Тейлора первого порядка к ограничению является
Замена около дает
Для каждого промежуточного решения вы вводите новое линейное ограничение в и как линейная часть выражения выше:
Это имеет форму , где , существует множитель для термин, и .
Этот метод добавления новых линейных ограничений к задаче называется методом секущей плоскости. Для получения дополнительной информации см. J. E. Kelley, Jr. Метод секущей плоскости для решения выпуклых программ. J. Soc. Indust. Appl. Math. Vol. 8, No 4, pp. 703-712, December, 1960.
Для выражения задач оптимизации:
Решите, что ваши переменные представляют
Выразите нижнюю и верхнюю границы в этих переменных
Задайте линейные выражения равенства и неравенства
Загрузите данные для задачи. Эти данные имеют 225 ожидаемые возвраты в векторе r
и ковариация возвратов в матрице 225 на 225 Q
. Данные те же, что и в примере «Использование квадратичного программирования в задачах оптимизации портфеля».
load port5
r = mean_return;
Q = Correlation .* (stdDev_return * stdDev_return');
Установите количество активов следующим N
.
N = length(r);
Создайте непрерывные переменные xvars
представление дроби распределения активов, двоичных переменных vvars
представление информации о том, является ли связанный xvars
является нулем или строго положительным, и zvar
представляющий переменная, 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;
Включите неравенства и .
qpprob.Constraints.fmaxconstr = xvars <= fmax*vvars; qpprob.Constraints.fminconstr = fmin*vvars <= xvars;
Включите ограничение, что портфель инвестирован на 100%, что означает .
qpprob.Constraints.allin = sum(xvars) == 1;
Установите коэффициент отвращения к риску на 100
.
lambda = 100;
Определите целевую функцию и включить его в задачу.
qpprob.Objective = r'*xvars - lambda*zvar;
Чтобы решить задачу итеративно, начните с решения задачи с текущими ограничениями, которые пока не отражают никакой линеаризации.
options = optimoptions(@intlinprog,'Display','off'); % Suppress iterative display [xLinInt,fval,exitFlagInt,output] = solve(qpprob,'options',options);
Подготовьте условие остановки для итераций: остановите, когда переменная slack находится в пределах 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);
Вычислите квадратичные и слабые значения. Если они различаются, добавьте другое линейное ограничение и решите снова.
Каждое новое линейное ограничение происходит от линейного приближения
После того, как вы найдете новое решение, используйте линейное ограничение на полпути между старым и новым решениями. Этот эвристический способ включения линейных ограничений может быть быстрее, чем просто взять новое решение. Чтобы использовать решение вместо полуевристического, закомментируйте линию «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')
Можно легко увидеть, что все ненулевые распределения активов находятся между полунепрерывными границами и .
Сколько ненулевых активов? Ограничение состоит в том, что существует от 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).