В этом примере показано, как использовать linprog решатель в Optimization Toolbox ® для решения инвестиционной задачи с детерминированной доходностью в течение фиксированного количества летT. Проблема в том, чтобы распределить ваши деньги по доступным инвестициям, чтобы максимизировать ваше конечное богатство. В этом примере используется подход, основанный на решателе.
Предположим, что у вас есть начальная сумма денег Capital_0 инвестировать в течение периода времени T года в N облигации с нулевым купоном. Каждая облигация выплачивает процентную ставку, которая складывается каждый год, и выплачивает основную сумму плюс совокупные проценты в конце срока погашения. Цель заключается в максимизации общей суммы денег после T годы.
Можно включить ограничение, заключающееся в том, что ни одна инвестиция не превышает определенной доли общего капитала.
В этом примере сначала показана настройка проблемы в небольшом регистре, а затем формулируется общий регистр.
Вы можете смоделировать это как проблему линейного программирования. Поэтому, чтобы оптимизировать свое богатство, сформулируйте проблему для решения linprog решатель.
Начните с небольшого примера:
Стартовая сумма для инвестирования Capital_0 составляет 1000 долларов.
Период времени 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 представляет собой срок погашения облигации k.
Вход k вектора InterestRates представляет собой процентную ставку, 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) является
) мк.
Определить как общий возврат облигации k:
) мк.
% Total returns
finalReturns = (1+InterestRates/100).^Maturity;Цель - выбрать инвестиции, чтобы максимально увеличить объем собранных денег в конце года T. Из сюжета вы видите, что инвестиции собираются в различные промежуточные годы и реинвестируются. В конце года T, деньги, возвращенные из инвестиций 5, 7 и 8, могут быть собраны и представляют ваше конечное богатство:
Чтобы поместить эту проблему в форму linprog решает, превращает эту задачу максимизации в задачу минимизации, используя отрицательный из коэффициентов x(j):
с
r7; -r8; 0]
f = zeros(nPtotal,1); f([5,7,8]) = [-finalReturns(5),-finalReturns(7),-finalReturns(8)];
Каждый год у вас есть определенное количество денег, доступных для покупки облигаций. Начиная с 1 года, можно инвестировать начальный капитал в варианты покупки и , так что:
Затем в течение следующих лет вы собираете доходы от погашения облигаций и реинвестируете их в новые доступные облигации для получения системы уравнений:
Запишите эти уравнения в виде beq, где каждая строка матрицы Aeq соответствует равенству, которое должно быть удовлетворено в том году:
Капитал0000]
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;
Поскольку каждая вложенная сумма должна быть положительной, каждая запись в векторе решения должна быть положительной. Включить это ограничение, задав нижнюю границу 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 общего капитала в этом году (включая доходность по облигациям, которые в настоящее время находятся в сроке погашения). Получается следующая система неравенств:
x9≤Pmax× (ρ1x1 +ρ6x6)
Поместить эти неравенства в матричную форму 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.053286 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.360809 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.244413 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)
