В этом примере показано, как использовать 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
представляет срок погашения из связи 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)
Define как совокупный доход связи k
:
% Total returns
finalReturns = (1+InterestRates/100).^Maturity;
Цель состоит в том, чтобы выбрать инвестиции, чтобы максимизировать сумму денег, собранную в конце года T
. Из графика вы видите, что инвестиции собирают в различные промежуточные годы и повторно инвестируют. В конце года T
, деньги, возвращенные в инвестиции 5, 7, и 8, могут быть собраны и представляют ваше итоговое богатство:
Поместить эту проблему в форму linprog
решает, превратите эту проблему максимизации в проблему минимизации с помощью отрицания коэффициентов x(j)
:
с
f = zeros(nPtotal,1); f([5,7,8]) = [-finalReturns(5),-finalReturns(7),-finalReturns(8)];
Каждый год вы имеете определенную сумму в наличии денег, чтобы купить связи. Начиная с года 1, можно инвестировать первоначальный капитал в опции покупки и , так:
Затем в течение следующих лет, вы собираете возвраты из назревающих связей и повторно инвестируете их в новые доступные связи, чтобы получить систему уравнений:
Напишите эти уравнения в форме , где каждая строка матрица соответствует равенству, которому нужно удовлетворить в том году:
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;
Поскольку каждая сумма, которую инвестируют, должна быть положительной, каждая запись в векторе решения mustBePositive. Включайте это ограничение путем установки нижней границы lb
на векторе решения . На векторе решения нет никакой явной верхней границы. Таким образом установите верхнюю границу 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
из совокупного капитала в том году (включая возвраты для связей, которые находятся в настоящее время в их срок погашения). Вы получаете следующую систему неравенств:
Поместите эти неравенства в матричную форму 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.055076 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.025611 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.312539 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)