|Norvig I 133
Optimization/Norvig/Russell: Linear programming is probably the most widely studied and broadly useful class of optimization problems. It is a special case of the more general problem of convex optimization, which allows the constraint region to be any convex region and the objective to be any function that is convex within the constraint region.
Linear programming problems: here, constraints must be linear inequalities forming a convex set and the objective function is also linear. The time complexity of linear programming is polynomial in the number of variables.
Def Convex: A set of points S is convex if the line joining any two points in S is also contained in S. A convex function is one for which the space “above” it forms a convex set; by definition, convex functions have no local (as opposed to global) minima.
Under certain conditions, convex optimization problems are also polynomially solvable and may be feasible in practice with thousands of variables. Several important problems in machine learning and control theory can be formulated as convex optimization problems. >Search algorithms.
Norvig I 155
Finding optimal solutions in continuous spaces is the subject matter of several fields, including optimization theory, optimal control theory, and the calculus of variations. The basic techniques are explained well by Bishop (1995)(1); Press et al. (2007)(2) cover a wide range of algorithms and provide working software.
As Andrew Moore points out, researchers have taken inspiration for search and optimization algorithms from a wide variety of fields of study: metallurgy (simulated annealing), biology (genetic algorithms), economics (market-based algorithms), entomology (ant colony optimization), neurology (neural networks), animal behavior (reinforcement learning), mountaineering (hill climbing), and others.
In the 1950s, several statisticians, including Box (1957)(3) and Friedman (1959)(4), used evolutionary techniques for optimization problems, but it wasn’t until Rechenberg (1965)(5) introduced evolution strategies to solve optimization problems for airfoils that the approach gained popularity.
1. Bishop, C. M. (1995). Neural Networks for Pattern Recognition. Oxford University Press
2. Press,W. H., Teukolsky, S. A., Vetterling,W. T., and Flannery, B. P. (2007). Numerical Recipes: The Art of Scientific Computing (third edition). Cambridge University Press
3. Box, G. E. P. (1957). Evolutionary operation: A method of increasing industrial productivity. Applied
Statistics, 6, 81–101.
4. Friedman, G. J. (1959). Digital simulation of an evolutionary process. General Systems Yearbook, 4,
5. Rechenberg, I. (1965). Cybernetic solution path of an experimental problem. Library translation 1122, Royal Aircraft Establishment_____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010