Смешано-целочисленная оптимизация портфеля квадратичного программирования: основанный на решателе

В этом примере показано, как решить задачу оптимизации портфеля Смешано-целочисленного квадратичного программирования (MIQP) с помощью intlinprog Решатель Смешано-целочисленного линейного программирования (MILP). Идея состоит в том, чтобы итеративно решить последовательность проблем MILP, которые локально аппроксимируют проблему MIQP. Для подхода, основанного на проблеме смотрите Смешано-целочисленную Оптимизацию Портфеля Квадратичного программирования: основанный на проблеме.

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

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

$\max_{x} (r^{T} x - λ x^{T} Q x) .$

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

Наличие не больше, чем M активы в портфеле, где M <= N.
Наличие, по крайней мере, m активы в портфеле, где 0 < m <= M.
Наличие полунепрерывных ограничений, значение также $x (i) = 0$ , или $f m i n \leq x (i) \leq f m a x$ для некоторых фиксированных частей $f m i n > 0$ и $f m a x \geq f m i n$ .

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

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

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

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

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

$v (i) f m i n \leq x (i) \leq v (i) f m a x .$

Эти неравенства оба осуществляют это $x (i)$ и $v (i)$ нуль в точно то же время, и они также осуществляют это $f m i n \leq x (i) \leq f m a x$ каждый раз, когда $x (i) > 0$ .

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

$m \leq \sum_{i} v (i) \leq M .$

Объективные и последовательные линейные аппроксимации

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

$\min_{x} λ x^{T} Q x - r^{T} x .$

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

$\min_{x, z} λ z - r^{T} x таким образом , что x^{T} Q x - z \leq 0, z \geq 0 .$

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

$x^{T} Q x - z = x_{0}^{T} Q x_{0} + 2 x_{0}^{T} Q δ - z + O (| δ |^{2}) .$

Заменяя $δ$ $x - x_{0}$ дает

$x^{T} Q x - z = - x_{0}^{T} Q x_{0} + 2 x_{0}^{T} Q x - z + O (| x - x_{0} |^{2}) .$

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

$- x_{k}^{T} Q x_{k} + 2 x_{k}^{T} Q x - z \leq 0 .$

Это имеет форму $A x \leq b$ , где $A = 2 x_{k}^{T} Q$ , существует a $- 1$ множитель для $z$ назовите, и $b = x_{k}^{T} Q x_{k}$ .

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

MATLAB® Problem Formulation

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

Решите то, что представляют ваши переменные
Выразите нижние и верхние границы в терминах этих переменных
Дайте линейные матрицы равенства и неравенства

Имейте первое $N$ переменные представляют $x$ вектор, следующее $N$ переменные представляют двоичный файл $v$ вектор и последняя переменная представляют $z$ слабая переменная. Существуют $2 N + 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. Включите это ограничение в проблему в форме, а именно,

$m \leq \sum_{i} v (i) \leq M,$

путем записи двух линейных ограничений формы $A x \leq b$ :

$\sum_{i} v (i) \leq M$

$\sum_{i} - v (i) \leq - m .$

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) \leq f m a x (i) * v (i)$ и $f m i n (i) * v (i) \leq 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;

Установите коэффициент нерасположенности к риску $λ$ к 100.

lambda = 100;

Задайте целевую функцию $λ 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);

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

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

history = [truequadratic,zslack];

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

В синтаксисе тулбокса, каждом новом линейном ограничении $A x \leq b$ прибывает из линейной аппроксимации

$- x_{k}^{T} Q x_{k} + 2 x_{k}^{T} Q x - z \leq 0 .$

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

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

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

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

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

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

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

disp(output.absolutegap)

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

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

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

Можно легко видеть, что все ненулевое распределение активов между полунепрерывными границами $f m i n = 0 . 001$ и $f m a x = 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™. Для примера, который показывает, как использовать класс Портфеля, чтобы непосредственно обработать полунепрерывный и ограничения кардинальности, смотрите Оптимизацию Портфеля с Полунепрерывным и Ограничения Кардинальности (Financial Toolbox).

Документация