Multi-Parameter function minimization with many many parameters

I am trying to minimize (find local minimum) a function of 100-1000 parameters. Generaly I realize this is nearly an impossible task, but I do have an advantage- I know that I am very close to the minimum. In other words, my initial condition is very close to the minumum. generally all parameters are 0.99-1.01 times the values of the minima. I thought this would give me a fighting chance.

However, so far fminsearch, fmincon and fminun and fminunc fail misserably. Are there any alternatives that might be more suitable for a so-called "multi-multi parameter" optimization?

Many thanks in advance

Nathan

[Torsten]

https://uk.mathworks.com/help/gads/product-description.html

What do you mean that your listed solvers "fail miserably" ?

[Matt J]

fminsearch is definitely the wrong solver for any problem with more than about 6 variables. As for why fminunc isn't working, we need to see how you are using it, and the results.

[John D'Errico]

fminsearch is a waste of time there. It will NEVER work on a problem of that size. A reasonable upper limit for fminsearch is more like maybe 10 parameters, and I would try to keep it under 6 or 8.

As far as why it did not succeed in your case, even though the search space is relatively small, it is not as small as you think. A 1000 dimensional space is immense. Even 100 dimensions. Should fminunc work? Well, possibly. Even probably. 1000 dimensions is not that truly huge for a gradient based solver to converge. But we don't know what is happening in your objective.

Why did it fail? What was the termination code? If you want better anwers, it helps to provide as much information as possible. Otherwise people are left guessing. And those wild guesses always seem to be wrong.

[Nathan Bblanc]

Thank you John for your detailed response.

I let it run for ~2 hours (~5000 iterations) and the objective function was not reduced. maybe the steps the algorithm was taking were too small? no sure

Answer 1

[John D'Errico]

Let me try to help, a little at least.

Why is fminsearch so bad at high dimensions? It is just not designed for that class of problem. Not in the least. For example, even on a relatively small problem (I can't solve a much larger one and stay in the couple of minute long time slot they give us on Answers.)

N = 100;
H = randn(N); H = H'*H;
obj = @(x) x(:)'*H*x(:);

This is a VERY simple objective function. H is positive definiite. So the solution lies at all zeros. How much easier can it get?

x0 = 0.1*ones(N,1);
[xval,fval] = fminsearch(obj,x0);

 
Exiting: Maximum number of function evaluations has been exceeded
         - increase MaxFunEvals option.
         Current function value: 19.006280 

max(abs(xval))

ans = 0.4750

plot(x0,'rx')
hold on
plot(xval,'ob')

Did it reduce the objective at all?

disp([fval,obj(x0)])

   19.0063  120.3257

So, yes, it did reduce the objective, but I doubt anyone would be happy with the result.

How well does a gradient based solver work?

[xval2,fval2] = fminunc(obj,x0);

Solver stopped prematurely.

fminunc stopped because it exceeded the function evaluation limit,
options.MaxFunctionEvaluations = 1.000000e+04.

norm(xval2)

ans = 0.0648

fval2

fval2 = 2.4617e-04

And for only a few seconds of work, it did hugely better than fminsearch.

plot(xval2,'gs')

This is to be expected.

ub = 0.3*ones(N,1);
lb = -ub;
[xval3,fval3] = ga(obj,N,[],[],[],[],lb,ub)

ga stopped because it exceeded options.MaxGenerations.

xval3 = 1×100

-0.0033 0.0156 0.2115 -0.0465 0.0803 -0.1139 0.0128 -0.0289 -0.0477 0.0742 -0.0119 0.0227 0.0292 -0.1154 0.0380 -0.0798 -0.1280 -0.1633 0.0595 0.0139 0.0290 -0.0009 0.0302 0.0906 0.0150 0.1470 0.0857 0.0791 -0.0471 0.0369

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

fval3 = 0.4342

plot(xval3,'kx')
legend('Start point','fminsearch','fminunc','ga')

All of these behaviors are completely expected. ga will not be terribly fast, but it did better than fminsearch. Remember however, that our genes were themselves determined by essentially a genetic algorithm. It is just that nature had many, many millions of years to refine them.

That your problem did not work out well, we cannot know why.