Optimization

Optimization

I include here some very limited information for optimization algorithms, researchers and software that I will as time permits extend. I have considered the use of optimization algorithms for various problems in radiotherapy that consider as many as 5000 parameters, including constraints and objectives that for some problems are differentiable and for some other problems are not. The problems include also combinatorial optimization problems and discrete or continuous problems or a mix of both.

W. Yourgrau and S. Mandelstam have traced the development of the variational methodology, starting with Aristotle's observation that most motion appears to be in either straight lines or circles. Aristotle suggested a common generating principle, namely minimalization:

The straight line is the shortest route between two points, while the circle is the shortest periphery for a given area.

The principle was then applied by Heron of Alexandria to prove that in a mirror, the angle of reflection is equal to the angle of incidence. Fifteen centuries later, Fermat (1601- 1665) used the same principle of the fastest route or minimal travel-time for the transition of light between two media, i.e. for the derivation of Snell's law.

(References: Yourgrou, W. and Mandelstam, S., Variational Principles in Dynamics and Quantum Theory, Dover Pub., New York (1968), 201 pp.)
Yuval Ne'eman in Symmetry and “Magic" Numbers or From the Pythagoreans to Eugene Wigner, Proceedings of the Wigner Centennial Conference

Optimization Researchers

This is my personal list. It is not my intention or possible for me to include all important optimization experts.

Deterministic algorithms

Sir Isaac Newton
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Newton.html

Some of his ideas are still used heavily in gradient based optimization algorithms.

Joseph-Louis Lagrange
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Lagrange.html At least known for his multipliers

Leonhard Euler
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Euler.html

An incredible paper production machine in mathematics. Together with Lagrange showed that mechanical laws can be considered as solutions of optimization problems, such as also in optics or quantum mechanics later shown by Richard Feynman.

Jorge Nocedal
http://www.ece.northwestern.edu/~nocedal/ One of the authors of L-BFGS(-B) and other unconstrained optimization algorithms.

The Greek Deterministic Optimization Mafia

Panos Pardalos
http://www.ise.ufl.edu/pardalos/index.htm
Is a world leading expert in global and combinatorial optimization. He is the editor-in-chief of the Journal of Global Optimization, managing editor of several book series, and a member of the editorial board of ten international journals. He is the author of 7 books and the editor of more than 40 books. He has written numerous articles and developed several well known software packages.

Stochastic algorithms

Hans-Paul Schwefel

http://ls11-www.informatik.uni-dortmund.de/people/schwefel/WelcomeE.html. The German pioneer of evolutionary algorithms together with Rechenberg.

John Holland

The American genetic algorithms pioneer

David Goldberg

http://gal4.ge.uiuc.edu/goldberg/d-goldberg.html
Pioneering work for single objective optimization with Gas.

Kalyanmoy Deb
http://www.iitk.ac.in/kangal/deb.htm A significant part of MOEAs algorithm development was done by K. Deb at the Kangal Institute in India and elsewhere.

Carlos Artemio Coello Coello

http://www.lania.mx/~ccoello/

Responsible for a large MOEA database of papers and for my interest for MO optimization.

S. Kirkpatrick

Pioneer of the simulated annealing method

Ingber Lester

http://www.ingber.com/ The creator of ASA, unfortunately a very chaotic SA code in C, but the most advanced free SA code available.

Nature Inspired algorithms

Marco Dorigo
Uses methods inspired by ants that mark their paths, trying to find food, with a chemical substance used by others like an anti-tabu search. Visit for details about Ant Colony Optimization http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html.

For a more complete list see:

http://solon.cma.univie.ac.at/~neum/glopt/people.html

Optimization Algorithms

Pro and contra

Unfortunately there is no algorithm that works for all cases due to various reasons (no free-lunch theorem), multiple local minima, premature convergence or very slow convergence. Necessary to fine tune parameters (evolution windows). Some methods use self adaptation but this is not always practical possible such as for density estimation algorithms. Sometimes even random search is better, but unfortunately researchers don’t include comparison with random search.

Deterministic algorithms

A lot of mathematical theory, thousand of pages with theory but can fail even for simple objective functions and especially if constraints are required. If they work for a problem then it is difficult for other algorithms to compete.

Simulated annealing

Simple and nice method, in principle should converge to global optimal solution but parameter settings could be a problem and time required could be too much for time critical applications. For optimization of a large number of parameters it is especially difficult to obtain really optimal results.

Genetic algorithms

Now a significant theoretical work on GAs exists, at least for some ES or GA methods using objective functions such as ONEMAX that counts the number of 1 in a binary chromosome. In principle simple algorithms but sometimes too simple to produce optimal results just by selection, recombination and mutation operators. Independent of benefits such as described by schemata theory and using more complex genetic operators convergence sometime is not achieved close to the global optimum in practical time. Use any possibility to support the algorithm if possible including a good initialization. My opinion is that these optimization methods especially for multidimensional problems are more local optimization methods. Usually improved performance if used in combination with more powerful local search methods, which then form hybrid or memetic algorithms.

Free “or Quasi-free” Optimization Software

This is my personal review of some software I was involved and of course my opinion.

I use only software written in C or C++ code. Although I used FORTRAN in the past even by “punching” holes in cards with IBM typewriters its time for FORTRAN to become history. Probably the huge historical piece of code is responsible like COBOL that it is still alive like the UNIX OS

Deterministic algorithms

GLPK

Linear Programminf including Mixed Integer Programming code http://www.gnu.org/software/glpk/glpk.html

L-BFGS and L-BFGS-B
Fortran code available at http://www.ece.northwestern.edu/~nocedal/lbfgsb.html. Various C and C++ implementations exist. A very good piece of code for unconstrained (L-BFGS) or simple bound constrained (L-BFGS-B) optimization, if gradient information is available and if local minima are negligible or don’t exist. I agree usually this is almost never the case for real problems.

C-FSQP

A sequential quadratic programming code in C. For FORTRAN freaks use the FORTRAN code J. For research it could be in principle possible to get the code http://64.238.116.66/aemdesign/FSQPframe.htm. Should be used carefully, try with different starting points since convergence to optimum may fail.

Stochastic algorithms

ASA

Unfortunately a very chaotic SA code in C with a huge list of parameters a chaotic manual but the most advanced free SA code available. Probably the most used #ifdef flags per number of code lines J http://www.ingber.com/#ASA-CODE. Sometimes the much more simple SA code from Taygeta is also good enough (http://www.taygeta.com/annealing/simanneal.html ) (Does anybody have an n-dimensional Cauchy random number generator?)

GALIB

An old C++ library of genetic algorithm components at http://lancet.mit.edu/galib-2.4/ by Matthew Wall.

NSGA-II

Probably the best free available MOEA code. UNIX code available at http://www.iitk.ac.in/kangal/code/new_nsga/nsga2code.tar. Nice feature includes the possibility of using constraints although as a weighted penalty term. Probably programmer freaks will not like the c code with the many nested ifs but object oriented code using C++ and STL is not necessary better in terms of “usability”.

PISA

C code of NSGA-II, SPEA, SPEA2 and other algorithms, http://www.tik.ee.ethz.ch/pisa/

MOMHLIB

A Metaheuristics multiobjective optimization library. Includes NSGA-II (c), SPEA, MOGLS etc. A C++ code, that uses STL and an archiving of all non-dominated solutions. http://www-idss.cs.put.poznan.pl/~jaszkiewicz/MOMHLib/

TEA Library

A C++ code including single and multiobjective GAs from Germany. http://sfbci.cs.uni-dortmund.de/home/German/derSFB/Software/TEA/ The main problem is the missing possibility of constrained optimization. Could be used more but either C++ code and or missing possibility of constraints is responsible that is less known or used than the NSGA-II code. My colleague Natasha Milickovic ported the UNIX code to Windows.

Sir Isaac Newtonhttp://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Newton.html

Leonhard Eulerhttp://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Euler.html

Jorge Nocedalhttp://www.ece.northwestern.edu/~nocedal/ One of the authors of L-BFGS(-B) and other unconstrained optimization algorithms.

Dimitri Bertsekas

Christodoulos Floudas

Nikolaos V. Sahinidis

Marco DorigoUses methods inspired by ants that mark their paths, trying to find food, with a chemical substance used by others like an anti-tabu search. Visit for details about Ant Colony Optimization http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html.