Максимизируйте долгосрочные инвестиции Используя линейное программирование: основанный на решателе

Этот пример показывает, как использовать решатель linprog в Optimization Toolbox®, чтобы решить инвестиционную проблему с детерминированными возвратами по постоянному числу лет T. Проблема состоит в том, чтобы выделить ваши деньги по доступным инвестициям, чтобы максимизировать ваше итоговое богатство. Этот пример использует основанный на решателе подход.

Проблемная формулировка

Предположим, что у вас есть начальная сумма денег Capital_0, чтобы вложить капитал по периоду времени лет T в облигациях с нулевым купоном N. Каждая связь платит процентную ставку, которая соединяет каждый год и платит принципал плюс начисленные проценты в конце срока погашения. Цель состоит в том, чтобы максимизировать общую сумму денег после лет T.

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

Этот пример показывает настройку задач на маленьком случае сначала, и затем формулирует общий случай.

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

Вводный пример

Запустите с небольшого примера:

Стартовая сумма, чтобы инвестировать Capital_0 составляет 1 000$.
Период времени T составляет 5 лет.
Количество связей N равняется 4.
К модели неинвестированные деньги имейте в наличии одну опцию B0 каждый год, которая имеет срок погашения 1 года и процентную ставку 0%.
Связь 1, обозначенный B1, может быть куплена в году 1, имеет срок погашения 4 лет и процентную ставку 2%.
Связь 2, обозначенный B2, может быть куплена в году 5, имеет срок погашения 1 года и процентную ставку 4%.
Связь 3, обозначенный B3, может быть куплена в году 2, имеет срок погашения 4 лет и процентную ставку 6%.
Связь 4, обозначенный B4, может быть куплена в году 2, имеет срок погашения 3 лет и процентную ставку 6%.

Путем разделения права преимущественной покупки B0 на 5 связей со сроком погашения 1 года и процентной ставкой 0%, эта проблема может быть эквивалентно смоделирована как наличие в общей сложности 9 доступных связей, таких это для k=1..9

k записи векторного PurchaseYears представляет год, что связь k доступна для покупки.
Запись k векторного Maturity представляет срок погашения $m_{k}$ из связи k.
Запись k векторного InterestRates представляет процентную ставку $ρ_{k}$ из связи k.

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

% Time period in years
T = 5;
% Number of bonds
N = 4;
% Initial amount of money
Capital_0 = 1000;
% Total number of buying oportunities
nPtotal = N+T;
% Purchase times
PurchaseYears = [1;2;3;4;5;1;5;2;2];
% Bond durations
Maturity = [1;1;1;1;1;4;1;4;3];
% Interest rates
InterestRates = [0;0;0;0;0;2;4;6;6];

plotInvestments(N,PurchaseYears,Maturity,InterestRates)

Переменные решения

Представляйте свои переменные решения векторным x, где x(k) является суммой в долларах инвестиций в связь k для k=1..9. На зрелость выплату для инвестиций x(k)

$x (k) (1 + ρ_{k} / 100)^{m_{k}} .$

Define $r_{k}$ как совокупный доход связи k:

$r_{k} = (1 + ρ_{k} / 100)^{m_{k}} .$

% Total returns
finalReturns = (1+InterestRates/100).^Maturity;

Целевая функция

Цель состоит в том, чтобы выбрать инвестиции, чтобы максимизировать сумму денег, собранную в конце года T. Из графика вы видите, что инвестиции собирают в различные промежуточные годы и повторно инвестируют. В конце года T, деньги, возвращенные в инвестиции 5, 7, и 8, может быть собран и представляет ваше итоговое богатство:

$\max_{x} x_{5} r_{5} + x_{7} r_{7} + x_{8} r_{8}$

Чтобы поместить эту проблему в форму, linprog решает, превратите эту проблему максимизации в проблему минимизации с помощью отрицания коэффициентов x(j):

$\min_{x} f^{T} x$

$f = [0; 0; 0; 0; - r_{5}; 0; - r_{7}; - r_{8}; 0]$

f = zeros(nPtotal,1);
f([5,7,8]) = [-finalReturns(5),-finalReturns(7),-finalReturns(8)];

Линейные ограничения: вложите капитал не больше, чем, вы имеете

Каждый год вы имеете определенную сумму в наличии денег, чтобы купить связи. Начиная с года 1, можно инвестировать первоначальный капитал в опции покупки $x_{1}$ и $x_{6}$ , так:

$x_{1} + x_{6} = {C a p i t a l}_{0}$

Затем в течение следующих лет, вы собираете возвраты из назревающих связей и повторно инвестируете их в новые доступные связи, чтобы получить систему уравнений:

$\begin{array}{ll} x_{2} + x_{8} + x_{9} & = r_{1} x_{1} \\ x_{3} & = r_{2} x_{2} \\ x_{4} & = r_{3} x_{3} \\ x_{5} + x_{7} & = r_{4} x_{4} + r_{6} x_{6} + r_{9} x_{9} \end{array}$

Напишите эти уравнения в форме $A e q x = b e q$ , где каждая строка $A e q$ матрица соответствует равенству, которое должно быть удовлетворено в том году:

$A e q = [\begin{array}{ccccccccc} 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ - r_{1} & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & - r_{2} & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - r_{3} & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - r_{4} & 1 & - r_{6} & 1 & 0 & - r_{9} \end{array}]$

$b e q = [\begin{array}{c} {C a p i t a l}_{0} \\ 0 \\ 0 \\ 0 \end{array}]$

Aeq = spalloc(N+1,nPtotal,15);
Aeq(1,[1,6]) = 1;
Aeq(2,[1,2,8,9]) = [-1,1,1,1];
Aeq(3,[2,3]) = [-1,1];
Aeq(4,[3,4]) = [-1,1];
Aeq(5,[4:7,9]) = [-finalReturns(4),1,-finalReturns(6),1,-finalReturns(9)];

beq = zeros(T,1);
beq(1) = Capital_0;

Связанные ограничения: никакое заимствование

Поскольку каждая сумма, которую инвестируют, должна быть положительной, каждая запись в векторе решения $x$ mustBePositive. Включайте это ограничение путем установки нижней границы lb на векторе решения $x$ . На векторе решения нет никакой явной верхней границы. Таким образом установите верхнюю границу ub пустеть.

lb = zeros(size(f));
ub = [];

Решите проблему

Решите эту проблему без ограничений на сумму, которую можно инвестировать в связь. Алгоритм внутренней точки может использоваться, чтобы решить этот тип линейной проблемы программирования.

options = optimoptions('linprog','Algorithm','interior-point');
[xsol,fval,exitflag] = linprog(f,[],[],Aeq,beq,lb,ub,options);

Solution found during presolve.

Визуализируйте решение

Выходной флаг равняется 1, указывая, что решатель нашел решение. Значение -fval, возвращенный как второй выходной аргумент linprog, соответствует итоговому богатству. Стройте свои инвестиции в зависимости от времени.

fprintf('After %d years, the return for the initial $%g is $%g \n',...
    T,Capital_0,-fval);

After 5 years, the return for the initial $1000 is $1262.48

plotInvestments(N,PurchaseYears,Maturity,InterestRates,xsol)

Оптимальные инвестиции с ограниченными активами

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

$\begin{array}{ll} x_{1} & \leq P m a x \times {C a p i t a l}_{0} \\ x_{2} & \leq P m a x \times (ρ_{1} x_{1} + ρ_{6} x_{6}) \\ x_{3} & \leq P m a x \times (ρ_{2} x_{2} + ρ_{6}^{2} x_{6} + ρ_{8} x_{8} + ρ_{9} x_{9}) \\ x_{4} & \leq P m a x \times (ρ_{3} x_{3} + ρ_{6}^{3} x_{6} + ρ_{8}^{2} x_{8} + ρ_{9}^{2} x_{9}) \\ x_{5} & \leq P m a x \times (ρ_{4} x_{4} + ρ_{6}^{4} x_{4} + ρ_{8}^{3} x_{8} + ρ_{9}^{3} x_{9}) \\ x_{6} & \leq P m a x \times {C a p i t a l}_{0} \\ x_{7} & \leq P m a x \times (ρ_{4} x_{4} + ρ_{6}^{4} x_{4} + ρ_{8}^{3} x_{8} + ρ_{9}^{3} x_{9}) \\ x_{8} & \leq P m a x \times (ρ_{1} x_{1} + ρ_{6} x_{6}) \\ x_{9} & \leq P m a x \times (ρ_{1} x_{1} + ρ_{6} x_{6}) \end{array}$

Поместите эти неравенства в матричную форму Ax <= b.

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

% Maximum percentage to invest in any bond
Pmax = 0.6;

% Build the return for each bond over the maturity period as a sparse
% matrix
cumMaturity = [0;cumsum(Maturity)];
xr = zeros(cumMaturity(end-1),1);
yr = zeros(cumMaturity(end-1),1);
cr = zeros(cumMaturity(end-1),1);
for i = 1:nPtotal
    mi = Maturity(i); % maturity of bond i
    pi = PurchaseYears(i); % purchase year of bond i
    idx = cumMaturity(i)+1:cumMaturity(i+1); % index into xr, yr and cr
    xr(idx) = i; % bond index
    yr(idx) = pi+1:pi+mi; % maturing years
    cr(idx) = (1+InterestRates(i)/100).^(1:mi); % returns over the maturity period
end
yearlyReturns = sparse(xr,yr,cr,nPtotal,T+1);

% Build the system of inequality constraints
A = -Pmax*yearlyReturns(:,PurchaseYears)'+ speye(nPtotal);

% Left-hand side
b = zeros(nPtotal,1);
b(PurchaseYears == 1) = Pmax*Capital_0;

Решите проблему путем инвестирования не больше, чем 60% в любой актив. Постройте получившиеся покупки. Заметьте, что ваше итоговое богатство является меньше, чем инвестиции без этого ограничения.

[xsol,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,ub,options);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the selected value of the function tolerance,
and constraints are satisfied to within the selected value of the constraint
tolerance.

fprintf('After %d years, the return for the initial $%g is $%g \n',...
    T,Capital_0,-fval);

After 5 years, the return for the initial $1000 is $1207.78

plotInvestments(N,PurchaseYears,Maturity,InterestRates,xsol)

Модель произвольного размера

Создайте модель для общей версии проблемы. Проиллюстрируйте его с помощью T = 30 лет и 400 случайным образом сгенерированных связей с процентными ставками от 1 до 6%. Эта настройка приводит к линейной проблеме программирования с 430 переменными решения. Система ограничений равенства представлена разреженной матрицей, Aeq размерности 30 430 и системы неравенств представлен разреженной матрицей A размерности 430 430.

% for reproducibility
rng default 
% Initial amount of money
Capital_0 = 1000;
% Time period in years
T = 30;
% Number of bonds
N = 400;
% Total number of buying oportunities
nPtotal = N+T;
% Generate random maturity durations
Maturity = randi([1 T-1],nPtotal,1);
% Bond 1 has a maturity period of 1 year
Maturity(1:T) = 1;
% Generate random yearly interest rate for each bond
InterestRates = randi(6,nPtotal,1);
% Bond 1 has an interest rate of 0 (not invested)
InterestRates(1:T) = 0;
% Compute the return at the end of the maturity period for each bond:
finalReturns = (1+InterestRates/100).^Maturity;

% Generate random purchase years for each option
PurchaseYears = zeros(nPtotal,1);
% Bond 1 is available for purchase every year
PurchaseYears(1:T)=1:T;
for i=1:N
    % Generate a random year for the bond to mature before the end of
    % the T year period
    PurchaseYears(i+T) = randi([1 T-Maturity(i+T)+1]);
end

% Compute the years where each bond reaches maturity
SaleYears = PurchaseYears + Maturity;

% Initialize f to 0
f = zeros(nPtotal,1);
% Indices of the sale oportunities at the end of year T
SalesTidx = SaleYears==T+1;
% Expected return for the sale oportunities at the end of year T
ReturnsT = finalReturns(SalesTidx);
% Objective function
f(SalesTidx) = -ReturnsT;


% Generate the system of equality constraints.
% For each purchase option, put a coefficient of 1 in the row corresponding
% to the year for the purchase option and the column corresponding to the
% index of the purchase oportunity
xeq1 = PurchaseYears;
yeq1 = (1:nPtotal)';
ceq1 = ones(nPtotal,1);

% For each sale option, put -\rho_k, where \rho_k is the interest rate for the
% associated bond that is being sold, in the row corresponding to the
% year for the sale option and the column corresponding to the purchase
% oportunity
xeq2 = SaleYears(~SalesTidx);
yeq2 = find(~SalesTidx);
ceq2 = -finalReturns(~SalesTidx);

% Generate the sparse equality matrix
Aeq = sparse([xeq1; xeq2], [yeq1; yeq2], [ceq1; ceq2], T, nPtotal);

% Generate the right-hand side
beq = zeros(T,1);
beq(1) = Capital_0;

% Build the system of inequality constraints
% Maximum percentage to invest in any bond
Pmax = 0.4;

% Build the returns for each bond over the maturity period
cumMaturity = [0;cumsum(Maturity)];
xr = zeros(cumMaturity(end-1),1);
yr = zeros(cumMaturity(end-1),1);
cr = zeros(cumMaturity(end-1),1);
for i = 1:nPtotal
    mi = Maturity(i); % maturity of bond i
    pi = PurchaseYears(i); % purchase year of bond i
    idx = cumMaturity(i)+1:cumMaturity(i+1); % index into xr, yr and cr
    xr(idx) = i; % bond index
    yr(idx) = pi+1:pi+mi; % maturing years
    cr(idx) = (1+InterestRates(i)/100).^(1:mi); % returns over the maturity period
end
yearlyReturns = sparse(xr,yr,cr,nPtotal,T+1);

% Build the system of inequality constraints
A = -Pmax*yearlyReturns(:,PurchaseYears)'+ speye(nPtotal);

% Left-hand side
b = zeros(nPtotal,1);
b(PurchaseYears==1) = Pmax*Capital_0;

% Add the lower-bound constraints to the problem.
lb = zeros(nPtotal,1);

Решение без содержания предела

Во-первых, решите линейную проблему программирования без ограничений неравенства с помощью алгоритма внутренней точки.

% Solve the problem without inequality constraints
options = optimoptions('linprog','Algorithm','interior-point');
tic
[xsol,fval,exitflag] = linprog(f,[],[],Aeq,beq,lb,[],options);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the selected value of the function tolerance,
and constraints are satisfied to within the selected value of the constraint
tolerance.

toc

Elapsed time is 0.045992 seconds.

fprintf('\nAfter %d years, the return for the initial $%g is $%g \n',...
    T,Capital_0,-fval);

After 30 years, the return for the initial $1000 is $5167.58

Решение с ограниченными активами

Теперь, решите проблему с ограничениями неравенства.

% Solve the problem with inequality constraints
options = optimoptions('linprog','Algorithm','interior-point');
tic
[xsol,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,[],options);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the selected value of the function tolerance,
and constraints are satisfied to within the selected value of the constraint
tolerance.

toc

Elapsed time is 1.196927 seconds.

fprintf('\nAfter %d years, the return for the initial $%g is $%g \n',...
    T,Capital_0,-fval);

After 30 years, the return for the initial $1000 is $5095.26

Даже при том, что количество ограничений, увеличенных порядком 10, время для решателя, чтобы найти решение увеличенным порядком 100. Это несоответствие производительности частично вызывается плотными столбцами в системе неравенства, показанной в матричном A. Эти столбцы соответствуют связям с долгим сроком погашения, как показано в следующем графике.

% Number of nonzero elements per column
nnzCol = sum(spones(A));

% Plot the maturity length vs. the number of nonzero elements for each bond
figure;
plot(Maturity,nnzCol,'o');
xlabel('Maturity period of bond k')
ylabel('Number of nonzero in column k of A')

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

% Solve the problem with inequality constraints using dual simplex
options = optimoptions('linprog','Algorithm','dual-simplex');
tic
[xsol,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,[],options);

Optimal solution found.

toc

Elapsed time is 0.348326 seconds.

fprintf('\nAfter %d years, the return for the initial $%g is $%g \n',...
    T,Capital_0,-fval);

After 30 years, the return for the initial $1000 is $5095.26

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

Качественный анализ результата

Чтобы получить ощущение решения, найденного linprog, сравните его с суммой fmax, который вы получили бы, если вы могли бы инвестировать все свои стартовые деньги в одной связи с 6%-й процентной ставкой (максимальная процентная ставка) за полный 30-летний период. Можно также вычислить эквивалентную процентную ставку, соответствующую итоговому богатству.

% Maximum amount
fmax = Capital_0*(1+6/100)^T;
% Ratio (in percent)
rat = -fval/fmax*100;
% Equivalent interest rate (in percent)
rsol = ((-fval/Capital_0)^(1/T)-1)*100;

fprintf(['The amount collected is %g%% of the maximum amount $%g '...
    'that you would obtain from investing in one bond.\n'...
    'Your final wealth corresponds to a %g%% interest rate over the %d year '...
    'period.\n'], rat, fmax, rsol, T)

The amount collected is 88.7137% of the maximum amount $5743.49 that you would obtain from investing in one bond.
Your final wealth corresponds to a 5.57771% interest rate over the 30 year period.

plotInvestments(N,PurchaseYears,Maturity,InterestRates,xsol,false)

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