Find minimum of an n variable function, n is like 800+

9 views (last 30 days)
Hello
Do you think it's possible to get a solution on a problem like this in a reasonable time?
I need to solve a problem where the distance between a point and a nonlinear function/curve is needed in high dimensions(at least ~800). So I should find the minimum of the distance function https://en.wikipedia.org/wiki/Euclidean_distance#n_dimensions . Do you think a global optimizer of Matlab can solve this?

Answers (3)

Matt J
Matt J on 18 Sep 2019
Edited: Matt J on 18 Sep 2019
Depends on the surface. It's trivial, for example, if the surface is a hyperplane or a hypersphere.

John D'Errico
John D'Errico on 18 Sep 2019
In theory, of course it is possible. Maybe not even that difficult. In practice, there are always issues that involve the skill of the person writing the code, their knowledge of optimization, etc. I might also bring up questions of starting values, which may or may not be important, since we are given no clue as to the real nature of your problem. Starting values will be important, since there will probably be multiple solutions, and the starting value will impact which solution is found.
But all of these factors are not particular to MATLAB optimization tools. ANY optimization algorithm is subject to the same issues, in any language or environment.
All that said is subject to the caveat that you will need to choose a reasonable optimization algorithm. For example, trying to solve an 800 variable optmiization problem using a Nelder-Mead polytope scheme (fminsearch) would be a patently foolish task. But that would also be true using Nelder-Mead in any other environment too. Again, what matters is your knowledge of optimization and your skill in using the necessary tools. Part of that knowledge is simply knowing which tool is appropriate to solve any given problem.

Walter Roberson
Walter Roberson on 18 Sep 2019
No. With 800 variables and non linear curv, it is unlikely that a global minimizer will find the global minimum. Especially so if the function involves periodic expressions such as trig, or involves use of hypergeometric functions or Jacobi functions.
Furthermore, if the function is highly nonlinear, then precision problems become very important, and finding the true minimum can become numerical impossible.
In some cases, especially multinomials, calculus approaches can be productive. But with 800 variables you are more likely to be bogged down with roots of polynomial of degree higher than 4.
  3 Comments
Richárd Tóth
Richárd Tóth on 19 Sep 2019

I need to search only in the [0,1]^n hypercube, don't know if it changes anything.

Also,instead of minimizing the function, I could take partial derivatives and solve them for 0 ,but solving a system of 800 equations with 800 variables... Maybe it could work like this? https://www.mathworks.com/help/optim/ug/nonlinear-equations-with-jacobian.html

Walter Roberson
Walter Roberson on 19 Sep 2019
[0,1]^800 unfortunately makes no difference for the feasibility of the discretization method I mentioned. You would have to get down to freezing roughly 780 of the variables and discretizing on the 20 that remained, at which point you might be able to afford the memory for 3 levels (e.g., 0, 1/2, 1)
How coupled are your variables, and what kind of nonlinear operations do you use? For example if the equation is multinomial with Total Degree of any term no more than 2 (e.g, constant * x(K)^2 or constant * X(K) * X(L) then that would probably be a lot more feasible than if there is a hypergeom(X([K L M N]), X([P Q R S T], exp(-gamma(X(K)-X(P)))) term.

Sign in to comment.

Categories

Find more on Get Started with Optimization Toolbox 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!