Last years for continuous multi-extremal optimization were developed a few random search oriented methods. There are Simulated Annealing and Genetic algorithms (implemented on the Matlab Global Optimization Toolbox), Ant Colony method, Cross-Entropy Method (see, e.g., https://www.researchgate.net/publication/225551595_The_Cross-Entropy_Method_for_Continuous_Multi-Extremal_Optimization ), etc. But a lot of researches yet often use traditional, gradient-based methods, as Newton-Raphson. The main drawback of these methods is that they, by their nature, do not cope well with optimization problems that have non-convex objective functions and/or many local optima. Optimization results essentially depend of the initial point selection. So, please, explain me, why researches don’t use random search oriented methods ?
Article The Cross-Entropy Method for Continuous Multi-Extremal Optimization
Sergey,
Plenty of researchers use combinations of traditional methods - such as cutting plane approaches or branch-and-bound - together with either local search procedures, or a variety of heuristics, based on multi-start techniques and a vast array of others. It is quite natural to work with a combination of tools when dealing with these non-convex problems. So you'll see many varieties of methods that are combined, simply because using only one strategy may not work.
There are several reasons why this happens. One is that the "No Free Lunch" theorem simply says that whatever you do you may fail. NO algorithm is guaranteed to be better than another one on a sufficiently rich set of test problems, unless you can show that the problem you are solving has some nice theoretical properties (convexity, for example, or local Lipschitz continuity). So you can just as well test a whole bunch of strategies, because theory states that none is guaranteed to be better than another one over a well-defined set of test problems.
A SERIOUS problem is that plenty of rather bland and boring publications result from someone - or entire teams - running a few optimization tools on the same, and often rather few, test problems, and then - WITHOUT a proper analysis - making strong claims about one algorithm being better than another one. Such publications can be interesting reading, but the claims are ALMOST NEVER supported by the tests that are made. It is definitely not enough to run 10, or even 100 test cases, and then claim that there is conclusive evidence that one algorithm is better than another one. This is a rather often used methodology, but it is NOT a correct one. It's even unscientific. I am sure you understand that.
But there are also other reasons why researchers wish to use traditional methods. One is that non-traditional methods do not come with a neat theory, while, for example, Benders decomposition does. But even Benders decomposition requires one to be able to solve non-convex problems, and we all know that we do NOT know how to solve all such problems efficiently.
Partly this issue is different depending on whether you are interested in theory or in solving actual, industrial, problems. If you have an industrial problem then it is fine to run your heuristics. Why? Because you can probably rely on the fact that the variety within the problems you are solving is not extremely large, and so you have the chance of designing a heuristic that works just for you for the variations of problems that you have. This is however NOT an option in general for someone in the academy who wants to publish a scientific paper on a methodology - in those cases claims need to be substantiated by theory or a VAST array of tests with randomly well selected problem instances that the scientific community can test and evaluate.
Dear Michael, thanks a lot for your answer. It was very interesting for me to read it. Regards, Sergey.
Ales: I remember my first algorithms course at my university's computer science department - Hill climbing and A* were the most popular then, at least teaching-wise. I wonder if that still is the case. We then learnt heuristic branch-and-bound and rollout like techniques to code a chess program. (In LISP!) That was quite nice. Gosh - more than 30 years has passed since then!
Dear Ales, first thank you very much for your answer. I agree with you, but not fully, rather "partially". Yes, you are right according Cross-Entropy algorithm - it yet isn't implemented on Matlab. But Genetic and Simulated annealing algorithms are implemented on Matlab and can be used as"black box" algorithms.
I agree with Ales. In my opinion, to use traditional optimization procedures is very easy, but it isn't right for random search procedures.
OK, I agree both with Alex and Ales : GA, SimAn, CE, etc. are some difficult. But in differ from "traditional optimization procedures" they provide correct solution, don't depend on initial point. etc and etc. Certainly, they require a lot of CPU time, but it isn't problem for modern PC.
Sergey, Hi! Thanks for explanation, I will try to use GA or CE algorithms.
There are of course upsides and downsides to all algorithms for the most difficult problems - unless P=NP. Hence, one cannot state that - for example - GA will win, or that branch-and-bound will win. No-one knows. But if you are only interested in a narrow part of the problems, such as a variety of instances with the very same model, then experience will help you to some degree. You still, however, face the not too improbable risk that a few instances will be extremely difficult to solve optimally - it's just the nature of NP-completeness.
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication