Use fmincon to solve very large optimization problem

I have a nonlinear constraint nonlinear objective problem which contains 640 decision variables with 129 constraints . I have tried both direct method and user-supplied gradient and Hessian as documented in the following link

http://www.mathworks.com/help/optim/ug/symbolic-math-toolbox-calculates-gradients-and-hessians.html

The direct method works fine but the solving speed is very slow. So I tried the user-supplied gradient and Hessian method. Since my objective and constraints are complicated, I used the symbolic expression and matlabFunction to create *.m files of gradient and Hessian of the objective and constraints. The problem is that my computer takes at least a night to generate gradient and Hessian files for objective and constraints, particularly, Hessians of objective and constraints (I terminated the process before it finish creating all files).

(I also checked the size(char) of the objective Hessian and found that there are 19 million characters).

However, by using spy(), I found that the Hessians are quite sparse (about 50%). I was trying to convert the Hessians to sparse matrices but it did not work because the Hessians were in symbolic expression.

My question is that is there anyway to speed up Hessian and gradient file generation?

Any tip and help is greatly appreciated!!

[John D'Errico]

50% is NOT what I would call quite sparse! Not even remotely sparse.

Odds are you won't gain any speed at all from using an array that non-sparse. Sparse matrices take more overhead to work with them.

Answer 1

[Alan Weiss]

I'm sorry, but as far as I know there is not way to speed the process. If you have not declared all your symbolic variables as real, then that might save some time, but other than that I do not know how to help matlabFunction to run any faster.

You could try to use the fmincon 'trust-region-reflective' algorithm along with the HessPattern option for numerical optimization.

One more thought. matlabFunction probably returns the objective and constraint gradients quickly enough, so you could use them along with the 'interior-point' algorithm and 'fin-diff-grads' and its associated options as explained here.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Siwanon Thampibul]

Thank you, Alan. I have tried the option 'fin-diff-grads' you suggested. With this option, the solver speed was much faster than that with the direct method. I have also tried 'bfgs' option and realized that it was faster than the 'fin-diff-grads' method.

In brief, I have tried 3 methods which are direct, 'fin-diff-grads' and 'bfgs'. The solving speed is bfgs<fin-diff-grads<<<direct from the fastest to the slowest one. Talking about results, the best solution (the most minimal solution) i got was from the direct method.

So i am wondering that is this normal ?? Aren't I supposed to get a better result from using user-supplied gradient (bfgs, fin-diff-grads) than the direct method because the prior method is more reliable?? Also, should the fin-diff-grads be faster than the bfgs because the latter one consumes more memory??

Thank you

[Alan Weiss]

There are a lot of things that go into an optimization, and it is impossible to know, in general, which method will be the fastest. The documentation states that, generally, 'bfgs' is the fastest method, and explains why fin-diff-grads can be less efficient than you might expect. It also states that the efficiency of a user-supplied Hessian varies depending on your code. Sorry, that's the best general advice I can give.

Alan Weiss

MATLAB mathematical toolbox documentation

[Siwanon Thampibul]

Yeah, as I am very new to Matlab, I also believe that my code needs a lot of improvements to speed up the process. Thanks again for your advice!!

[John D'Errico]

This is a mistake that MANY people make, thinking that because they supply a gradient or Hessian matrix, that the optimization MUST be faster, and more efficient.

Sadly, these are often fallacies. The fact is, very often for an n variable problem, it takes roughly n times as much work to compute an analytical gradient vector as it does to compute one function value. So if you have n variables, there is no real gain in speed, because computing a finite difference approximation for the gradient is also an O(n) operation. Likewise for the hessian, both operations will probably be an O(n^2) computation. What is worse, see that when you take the derivative of a function, it often gets more complex, not less so.

syms x

f = 1/(1+x^2);

diff(f,x)
ans =
-(2*x)/(x^2 + 1)^2

diff(f,x,2)
ans =
(8*x^2)/(x^2 + 1)^3 - 2/(x^2 + 1)^2

As you can see, for a simple function f(x), the derivatives actually get more messy. They take more work to compute than just a function value. If you are careful and creative, you can precompute some of those operations to make the code more efficient, but this is not always trivial when you have expressions that cover the page.

Finally, having more accuracy in the gradient or Hessian does not always insure the function will converge more rapidly, especially if any error in the gradient is down in the 8th significant digit. And analytical expressions for a derivative, especially those generated symbolically, tend to be a nasty mess of subtractive cancellation. In the end, you often do not even gain accuracy. (I had a friend who was so impressed and even proud of the hundreds of pages of symbolic derivatives he had generated for one problem. I never had the heart to tell him that odds are, those derivatives were probably no better than a simple finite difference, and very possibly worse.)

[Siwanon Thampibul]

Thank you John. What you said is true but the reason why I have been trying to generate the m.file even though it consumes a lot of time is that I will need to perform GlobalSearch or MultiStart to find a global minimum. By this reason, I believe that it would take less total time if I just create the m files once and get faster calculation speed for multiple calculations by the Multistart rather than using the direct method, which has much slower calculation speed, for multiple calculations.

By the way, thank you for your comment!

Answer 2

[Matt J]

My question is that is there anyway to speed up Hessian and gradient file generation?

I'm guessing the long processing time might be because your symbolic expressions are written in terms of the 640 unknowns separately, resulting in horribly huge expressions. If that's the case, you've probably gone about it the wrong way. You should be writing your objective, gradient, and Hessian functions in terms of vectorized expressions, which tend to make them more compact. Then, the matlabFunction command should crunch faster, if you even need it at all.

[Siwanon Thampibul]

Thank you for your advice Matt. My objective is a scalar containing the 640 unknowns. My gradient is thus a 640 x 1 vector. However, my Hessian is a 640 x 640 matrix. I believe that the 'user-supplied' Hessian can be in a matrix form as what was done in the following link

http://www.mathworks.com/help/optim/ug/symbolic-math-toolbox-calculates-gradients-and-hessians.html

[Matt J]

Yes, but we're talking about why it takes so long for you to generate the mfiles. They would have to be horribly long and complicated for the matlabFunction command to take as long as you've mentioned. I can see that happening if you haven't used vector notation to write the symbolic expressions.

[Siwanon Thampibul]

Thank you Matt. I will try vectorizing the inputs and will report the results!