How to speed up fmincon for a large optimization?

Question

Jamais avenir 2015-4-25

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/213542-how-to-speed-up-fmincon-for-a-large-optimization

回答： Nayan Rawat 2019-6-25

I am using fmincon to solve a problem with almost 600 optimization variables and few hundreds of constraints. Amongst those 600 optimization variables, 77 of them directly participate in the objective function and 79 linear constraints (const 1). The other variables only participate in the other nonlinear constraints, they are few hundreds,*(const 2)*. I did the basics, such as defining linear constrains with A,Aeq matrices, selecting correct lb and ub instead of adding extra inequality constraints, providing a good starting point, to speed up the optimization. I performed 3 tests to see what is the origin of this slowness, the number of variables or the nonlinear constraint (const 2).

# In the 1st case, I have tried to solve this problem considering all 600 optimization variables and all hundreds of constraints. In this case, computational burden was huge.
# In the 2nd case, I disabled the second set of constraints (const 2) which use the most number of optimization variables that do not directly participate in the objective function. So, Only 79 constraints that use the 77 optimization variables were kept. In this case, I didn't change the optimization vector (still 600) but only (const 1) were considered. The computational burden still was huge (maybe a bit less).
# In the 3rd case, I did the same thing as pervious case, but I shorten the optimization vector and removed the useless variables. So only 77 optimization variables along 79 constraints were considered. Calculation was so fast in this case.

I all these cases I put a line a=1 in nonlinear constraint file to see how fast fmincon calls constraints file. During the optimization, sometimes it calls it fast and sometime it almost stops calling the constraint file.

Based on the above, number of optimization variables play a major role in computational burden of fmincon. Is that correct? If so, as most of my variables do not participate in objective function, is there a way to speed up this optimization? Also, I know this problem was solved with GAMS in few seconds.

2 个评论
显示无隐藏无

Matt J 2015-4-25

编辑：Matt J 2015-4-25

There is little that can be said without seeing the code for your tests. The computation time is not attributable to number of variables alone. It depends on your stopping criteria, how you are computing derivatives, and many other things

For now, though, this part of your post sounded strange:

I all these cases I put a line a=1 in nonlinear constraint file to see how fast fmincon calls constraints file. During the optimization, sometimes it calls it fast and sometime it almost stops calling the constraint file.

If the constraint file is called at all in cases 2 and 3, then something is wrong. You only have linear constraints in those cases.

Jamais avenir 2015-4-25

Dear Matt J. Well, I wrote some linear constraints in case 2 in nonlinear constraint file (intead of putting them in A,B), just to see is fmincon call it faster or not. Actual, compare to case 3 (only 77 optimization variable,79 constraint), it was so slow. however, it was the same problem with same number of constraints , but with extra and useless optimization variables (600 optimization variable,79 constraints). In the first case, it was even more slower. (600 variables that participates in hounded of constraints). I am not sure if my code and constraints are completely correct, but I dont have anyway to check them. But, if we assume its correct, what things i can do to make it faster. Thanks for your help

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2015-4-25

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/213542-how-to-speed-up-fmincon-for-a-large-optimization#answer_176676

编辑：Matt J 2015-4-25

It sounds like you are allowing fmincon to compute gradients and Hessians of the objective and nonlinear constraints using finite difference calculations (the default). In this case, computational effort will have a strong dependence on the number of variables, N. It is O(N) for gradient calculations and O(N^2) for any Hessian calculations that the algorithm requires. You should read about including your own analytical derivative calculations.

Note that this is also another example of why it is wasteful to put linear constraints inside your nonlinear constraint file. Linear constraints always have a Hessian of zero and so there is never any point computing those. But fmincon cannot know which constraints are linear when you don't use A,b,Aeq,beq,ub,lb to express them. Therefore, fmincon wastes time computing finite difference Hessians for those just like any other constraints.