How to speed up fmincon for a large optimization?
42 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Jamais avenir
el 25 de Abr. de 2015
Respondida: Nayan Rawat
el 25 de Jun. de 2019
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 comentarios
Matt J
el 25 de Abr. de 2015
Editada: Matt J
el 25 de Abr. de 2015
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.
Respuesta aceptada
Matt J
el 25 de Abr. de 2015
Editada: Matt J
el 25 de Abr. de 2015
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.
Más respuestas (1)
Ver también
Categorías
Más información sobre Get Started with Optimization Toolbox en Help Center y File Exchange.
Productos
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!