GA, Could not find a feasible initial point
Show older comments
I'm triying to make a portfolio optimization using genetic algorithm.
This is the model that I made, with some constraints, but when I run it, I can't reach a solution, just appear "Could not find a feasible initial point".
Someone could help me fixing my code or helping me to find the mistake.
Thanks.
data = xlsread('Returns.xlsx');
nAssets = size(data, 2);
%Returns and covariance
mu = mean(data);
sigma = cov(data);
%formulate the problem/optimization
r_target = 0.10; %r_target is the required return
f = zeros(nAssets, 1); %there is no constant
A = [-mu; -eye(nAssets)]; %besides the returns we forbid short selling
b = [-r_target; zeros(nAssets, 1)]; % required return and weights greater/eqauls 0
Aeq = ones(1, nAssets); %All weights should sum up...
beq = 1; %... to one (1)
%solve the optimization
w = ga(@MaxReturn,nAssets,A,b,Aeq,beq);
w
%print the solution
fprintf(2, 'Risk: %.3f%%\n', sqrt(w'*sigma*w)*100);
fprintf(2, 'Ret: %.3f%%\n', w'*mu'*100);
function f = MaxReturn(w,mu);
f = mtimes(w'*mu');
end
4 Comments
John D'Errico
on 15 Dec 2021
Edited: John D'Errico
on 15 Dec 2021
I'm not sure what you think this does?
f = mtimes(w'*mu');
Well, besides generate an error, since mtimes is not a monadic operator.
w'*mu' is a valid operation. But then to try to pass that to mtimes, it will fail.
Anyway, without your data, we cannot even test your code.
Santiago
on 16 Dec 2021
John D'Errico
on 16 Dec 2021
Edited: John D'Errico
on 16 Dec 2021
My point is, IF you want to multiply w' with mu', then just write
f = w'*mu';
The mtimes there as you wrote it is redundant, thus mtimes(w'*mu'), and in fact, will generate a runtime error.
Walter Roberson
on 16 Dec 2021
ga() always passes in row vectors for the unknowns. If you transpose that you would get a column vector, and matrix multiply of a column vector on the left is not going to result in a scalar as required for ga.
The corrected code is in my Answer: f = w*mu'
Accepted Answer
format long g
filename = 'https://www.mathworks.com/matlabcentral/answers/uploaded_files/835520/Returns.xlsx';
data = readmatrix(filename);
nAssets = size(data, 2);
%Returns and covariance
mu = mean(data);
mu.'
sigma = cov(data);
%formulate the problem/optimization
r_target = 0.10; %r_target is the required return
f = zeros(nAssets, 1); %there is no constant
A = [-mu; -eye(nAssets)] %besides the returns we forbid short selling
b = [-r_target; zeros(nAssets, 1)] % required return and weights greater/eqauls 0
Aeq = ones(1, nAssets) %All weights should sum up...
beq = 1 %... to one (1)
%solve the optimization
fcn = @(w)MaxReturn(w,mu);
[w, fval, flag, output] = ga(fcn, nAssets, A, b, Aeq, beq)
if isempty(w)
warning('could not find any solution')
else
%print the solution
fprintf(2, 'Risk: %.3f%%\n', sqrt(w'*sigma*w)*100);
fprintf(2, 'Ret: %.3f%%\n', w'*mu'*100);
end
[wF, fvalF, flagF, outputF] = fmincon(fcn, .05*ones(1,nAssets), A, b, Aeq, beq)
function f = MaxReturn(w,mu)
f = w * mu';
end
What's happening is that ga() decides that the constraints cannot be satisfied by any sets of values, and so never calls the function at all. fmincon() cannot find a feasible point either.
3 Comments
Santiago
on 16 Dec 2021
The sum of the coefficients must be 1, right? Now suppose that you put all of that into a single coefficient and made the others zero, then what is the maximum w * mu sum that you could have? It would occur when you put the entire "1" into the largest element of mu and let the other elements be 0. So let us check, is max(mu) >= r_target ? NO! max(mu) is about 0.005 but r_target is 0.1 .
The configuration is impossible.
format long g
filename = 'https://www.mathworks.com/matlabcentral/answers/uploaded_files/835520/Returns.xlsx';
data = readmatrix(filename);
nAssets = size(data, 2);
%Returns and covariance
mu = mean(data);
mu.'
sigma = cov(data);
%formulate the problem/optimization
r_target = 0.10; %r_target is the required return
f = zeros(nAssets, 1); %there is no constant
A = [-mu; -eye(nAssets)] %besides the returns we forbid short selling
b = [-r_target; zeros(nAssets, 1)] % required return and weights greater/eqauls 0
Aeq = ones(1, nAssets) %All weights should sum up...
beq = 1 %... to one (1)
%solve the optimization
fcn = @(w)MaxReturn(w,mu);
%{
[w, fval, flag, output] = ga(fcn, nAssets, A, b, Aeq, beq)
if isempty(w)
warning('could not find any solution')
else
%print the solution
fprintf(2, 'Risk: %.3f%%\n', sqrt(w'*sigma*w)*100);
fprintf(2, 'Ret: %.3f%%\n', w'*mu'*100);
end
%}
N = 100000;
x0 = rand(N,nAssets);
x0 = x0 ./ sum(x0,2);
Alhs = mu * x0';
mask = Alhs >= r_target;
x0 = x0(mask,:);
if isempty(x0)
fprintf('failed all %d initial conditions\n', N);
fprintf('greatest was %g but need %g\n', max(Alhs), r_target);
fprintf('mu max is %g\n', max(mu));
else
fprintf('Succeeded on %d initial conditions\n', size(x0,1));
[wF, fvalF, flagF, outputF] = fmincon(fcn, x0(1,:), A, b, Aeq, beq)
end
[wF, fvalF, flagF, outputF] = fmincon(fcn, .05*ones(1,nAssets), A, b, Aeq, beq)
function f = MaxReturn(w,mu)
f = w * mu';
end
In the below I lower the required return to 0.004 (a little smaller than the largest mu, so the target becomes do-able.)
You can see that ga() succeeds.
I also create a whole lot of random starting points for fmincon and extract ones that meet the constraints and use one of those as a starting point. You can see that if you start with random points that it is rare but possible to get a feasible starting point (and thus to be sure that fmincon will find some solution.)
We know from the experiments I posted above that fmincon with a starting point that is not feasible might not be able to find a solution.
format long g
filename = 'https://www.mathworks.com/matlabcentral/answers/uploaded_files/835520/Returns.xlsx';
data = readmatrix(filename);
nAssets = size(data, 2);
%Returns and covariance
mu = mean(data);
mu.'
sigma = cov(data);
%formulate the problem/optimization
r_target = 0.004; %r_target is the required return
f = zeros(nAssets, 1); %there is no constant
A = [-mu; -eye(nAssets)] %besides the returns we forbid short selling
b = [-r_target; zeros(nAssets, 1)] % required return and weights greater/eqauls 0
Aeq = ones(1, nAssets) %All weights should sum up...
beq = 1 %... to one (1)
%solve the optimization
fcn = @(w)MaxReturn(w,mu);
[w, fval, flag, output] = ga(fcn, nAssets, A, b, Aeq, beq)
if isempty(w)
warning('could not find any solution')
else
%print the solution
fprintf(2, 'Risk: %.3f%%\n', sqrt(w*sigma*w')*100);
fprintf(2, 'Ret: %.3f%%\n', w*mu'*100);
end
N = 100000;
x0 = rand(N,nAssets);
x0 = x0 ./ sum(x0,2);
Alhs = mu * x0';
mask = Alhs >= r_target;
x0 = x0(mask,:);
if isempty(x0)
fprintf('failed all %d initial conditions\n', N);
fprintf('greatest was %g but need %g\n', max(Alhs), r_target);
fprintf('mu max is %g\n', max(mu));
else
fprintf('Succeeded on %d initial conditions\n', size(x0,1));
[wF, fvalF, flagF, outputF] = fmincon(fcn, x0(1,:), A, b, Aeq, beq)
end
[wF, fvalF, flagF, outputF] = fmincon(fcn, .05*ones(1,nAssets), A, b, Aeq, beq)
function f = MaxReturn(w,mu)
f = w * mu';
end
More Answers (0)
Categories
Find more on Problem-Based Optimization Setup in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
