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

Hello

Do you think it's possible to get a solution on a problem like this in a reasonable time?

https://math.stackexchange.com/questions/2264702/shortest-distance-from-point-to-curve

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?

Answer 1

[Matt J]

Depends on the surface. It's trivial, for example, if the surface is a hyperplane or a hypersphere.

Answer 2

[John D'Errico]

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.

Answer 3

[Walter Roberson]

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.

[Walter Roberson]

In some situations, it is effective to discretize the possible ranges of the variables, solve the equation for one variable in terms of the others, apply the formula for all of the combinations of the other values, and write at a discretized value of the solution in an array -- sampling the curve, so to speak. Then finding the cloest point on the curve to some specific point gets reduced to finding the closest point that is set in the array. This will, of course, only be an approximation, but there are times when it is Good Enough, and there are other times when what is Good Enough about it is providing initial coordinates (and implicit bounds) for a more detailed search.

However, in your situation with 800 variables, this approach is hopeless. Even if you write at the bit level, it would be hopeless. In order to discretize each of 800 variables into even just 2 levels, you would need an array of 2^800 bits, which is about 2E231 gigabytes.

[Richárd Tóth]

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]

[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.