choosing algorithm for optimization problem

Dear all,

I have a system of nonlinear equations, F(x)=0 to solve. I am using lsqnonlin to find the minimum of F1^2+F2^2+...+FN^2, which is equivalent to solve F(x)=0.

My problem normally requires N=1e+4. Currently, I can solve the problem with N=400 taking 34s, in which 75% of the time is used for lsqnonlin optimization. Here are some approaches I am thinking about for improving efficiency:

1. Include an explicit Jacobian form and use large-scale algorithm.

2. Parallel computing by setting 'UseParallel' to 'Always', but this only works in fmincon, which is about 30 times slower than lsqnonlin in serial computing. Thus, I am not positive about the trade-off of prallel computing.

3. Use algorithms that do not require Jacobian, such as patternsearch and genetic algorithm, but they are as inefficient as fmincon.

Hope that you can give advice on this problem. Thanks.

[Matt J]

which is about 30 times slower than lsqnonlin in serial computing

Are you sure you have the Parallel Computing Toolbox? If so, how many workers did you open in your matlabpool?

[Marrie]

No, i am comparing fmincon and lsqnonlin both in serial computing.

Answer 1

[Matt J]

Advice will be limited, since we cannot see your objective function. However, in addition to an explicit Jacobian, you could also try parallelizing the computation of the different Fi, i=1...N.

Also, if you have no actual lb,ub constraints, you might try using FSOLVE instead of LSQNONLIN.

[Alan Weiss]

Parallel fmincon only parallelizes the gradient estimation, so would not be helpful if you can calculate the Jacobian analytically. I, too, recommend that you try fsolve, which is tailored for solving this type of problem. patternsearch and ga are sure to be a waste of time, so don't bother; patternsearch is much less efficient on smooth problems, and ga is generally inefficient and unreliable.

If it is difficult to compute the exact Jacobian, you can often improve speed by including a JacobPattern option, which speeds finite difference estimation by taking only the useful finite difference steps. Or you might be able to use Symbolic Math toolbox to evaluate your Jacobian. See this documentation example and this similar example.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Marrie]

Many thanks. I will try to get the Jacobian using Symbolic Math toolbox