Issue with large memory required for non-linear optimizer

Dear Matlab community hi.

I tried to run the following optimization problem for a 2-dimensional optimization variable of size 150x150. For some reason, the system creates somehow in the optimization process (I guess) some matrix of size (150^2)x(150^2). I tried to solve the issue for several days now (with the different options shown in comments) but I cannot understand why MATLAB creates such a huge matrix in the solution process. Is there, perhaps, some other nonlinear optimizer in MATLAB that does not require such huge matrices? Any help on this issue would be very helpful.

With best wishes,

Yannis

a = 4;
b = 2.1;
c = 4;
x = optimvar('x',150,150);
prob = optimproblem;
prob.Objective = parameterfun(x,a,b,c);
%opts=optimoptions('fmincon','Algorithm','interior-point','SpecifyObjectiveGradient',true,'HessianFcn','objective');
%opts=optimoptions('quadprog','Algorithm','trust-region-reflective','Display','off');
opts = optimoptions('fminunc','Algorithm','trust-region');
opts.HessianApproximation = 'lbfgs';
opts.SpecifyObjectiveGradient = false;

x0.x = 0.5 * ones([150,150]);

%[sol,qfval,qexitflag,qoutput] = solve(prob,x0,'options',opts);

[sol,fval] = solve(prob,x0)

[Torsten]

Try a simple gradient descend method.

All MATLAB optimizers seem to use 2nd order information of the function to be minimized. This means the Hessian must be built/approximated which has dimension n^2 if you have n variables to be optimized.

@Alan Weiss

Correct me if I'm wrong.

[Yannis Stamatiou]

Hi,

thank you all for your replies!

With best wishes,

Yannis

[Torsten]

And what did you decide to do ?

Answer 1

[Alan Weiss]

You have 150^2 optimization variables. I do not see your parameterfun function, but if it is not a supported function for automatic differentiation, then fminunc cannot use the 'trust-region' algorithm because that algorithm requires a gradient function. The LBFGS Hessian approximation is not supported in the 'quasi-newton' algorithm. Sorry.

Alan Weiss

MATLAB mathematical toolbox documentation

[Yannis Stamatiou]

Hi,

I really thank you both for your prompt reply! You really helped. I think that there is no way to accomodate my problem with the usual non-linear oprimizatiton solvers of matlab. I will try to find some other method which will not require to compute so much auxilliary information.

With best wishes,

Yannis

[Bruno Luong]

@Alan Weiss "The LBFGS Hessian approximation is not supported in the 'quasi-newton' algorithm. Sorry."

Tiy probably want to say "Trust-region" algorithm, since LBFGS and quasi-newton are often recommended and used for large sale problem.

This code is modified version of example from the help page

N = 1e5;
x0 = -2*ones(N,1);
x0(2:2:N) = 2;
options = optimoptions("fminunc",Algorithm="quasi-newton", HessianApproximation="lbfgs",...
    SpecifyObjectiveGradient=true);
[x,fval] = fminunc(@multirosenbrock,x0,options);

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

function [f,g] = multirosenbrock(x)
% Get the problem size
n = length(x);  
if n == 0, error('Input vector, x, is empty.'); end
if mod(n,2) ~= 0
   error('Input vector, x ,must have an even number of components.');
end
% Evaluate the vector function
odds  = 1:2:n;
evens = 2:2:n;
F = zeros(n,1);
F(odds,1)  = 1-x(odds);
F(evens,1) = 10.*(x(evens)-x(odds).^2); 
f = sum(F.^2);
if nargout >= 2 % Calculate gradient
    g = zeros(n,1);
    g(evens) = 200*(x(evens)-x(odds).^2);
    g(odds) = -2*(1 - x(odds)) - 400*(x(evens)-x(odds).^2).*x(odds);
end
end

[Alan Weiss]

Sorry! Of course, you are right, as of R2022a the quasi-Newton algorithm in fminunc supports the lbfgs Hessian approximation. Mea culpa.

Alan Weiss

MATLAB mathematical toolbox documentation

[Yannis Stamatiou]

Hi again.

I tried to find an existing gradient descent implementation in matlab but non of the ones I found was fit for my problem. Then, after your advice, I fiddled a bit with the parameters and I found out that the following works even for 256x256 variables! I cannot figure out exactly why, but it did not display a memory limitation error.

Thank you all, again, for your advice!

With best wishes,

Yannis

x = optimvar('x',256,256,'LowerBound',0,'UpperBound',0.9);

prob = optimproblem;
prob.Objective = parameterfun(x,a,b,c);

opts = optimoptions("fminunc",Algorithm="quasi-newton", HessianApproximation="lbfgs",...
    SpecifyObjectiveGradient=true);

x0.x = 0.5 * ones([256,256]);
[sol,qfval,qexitflag,qoutput] = solve(prob,x0,'options',opts);

[Bruno Luong]

@Yannis Stamatiou " I cannot figure out exactly why"

The lbfgs formula approximate the inverse of the Hessian by low-rank approximation and does not require to store the full Hessian or its inverse.

That's why the memory requirement is reduced and it is suitable for lare-scale problem.

[Yannis Stamatiou]

Hi,

I now understand why it worked. In fact it is not very easy to see what is the best approach for large optimization problems, I was a bit lost in the documentation with the several optimization options, algorithms and settings. However, all the replies to my post, and yours in particular with respect to why the method worked, were very helpful, thanks!

Yannis