A BRIEF HISTORY OF OPTIMIZATION
A BRIEF HISTORY OF OPTIMIZATION
Optimization is everywhere, from engineering design to financial markets,
from our daily activity to planning our holidays, and computer sciences to industrial
applications. We always intend to maximize or minimize something.
An organization wants to maximize its profits, minimize costs, and maximize
performance. Even when we plan our holidays, we want to maximize our
enjoyment with least cost (or ideally free). In fact, we are constantly searching
for the optimal solutions to every problem we meet, though we are not
necessarily able to find such solutions.
It is no exaggeration to say that finding the solution to optimization problems,
whether intentionally or subconsciously, is as old as human history itself.
For example, the least effort principle can often explain many human behaviors.
We know the shortest distance between any two different points on a
plane is a straight line, though it often needs complex maths such as the calculus
of variations to formally prove that a straight line segment between the
two points is indeed the shortest.
In fact, many physical phenomena are governed by the so-called least action
principle or its variants. For example, light travels and obeys Fermat's
principle, that is to travel at the shortest time from one medium to another,
1.1 BEFORE 1900
The study of optimization problems is also as old as science itself. It is known
that the ancient Greek mathematicians solved many optimization problems.
For example, Euclid in around 300BC proved that a square encloses the greatest
area among all possible rectangles with the same total length of four sides.
Later, Heron in around 100BC suggested that the distance between two points
along the path reflected by a mirror is the shortest when light travels and reflects
from a mirror obeying some symmetry, that is the angle of incidence
is equal to the angle of reflection. It is a well-know optimization problem,
called Heron's problem, as it was first described in Heron's Catoptrica (or On
Mirrors).
The celebrated German astronomer, Johannes Kepler, is mainly famous for
the discovery of his three laws of planetary motion; however, in 1613, he solved
an optimal solution to the so-called marriage problem or secretary problem
when he started to look for his second wife. He described his method in his
personal letter dated October 23, 1613 to Baron Strahlendorf, including the
balance of virtues and drawbacks of each candidate, her dowry, hesitation,
and advice of friends. Among the eleven candidates interviewed, Kepler chose
the fifth, though his friend suggested him to choose the fourth candidate. This
may imply that Kepler was trying to optimize some utility function of some
sort. This problem was formally introduced by Martin Gardner in 1960 in his
mathematical games column in the February 1960 issue of Scientific American.
Since then, it has developed into a field of probability optimization such as
optimal stopping problems.
W. van Royen Snell discovered in 1621 the law of refraction, which remained
unpublished; later, Christiaan Huygens mentioned Snell's results in his Dioptrica
in 1703. This law was independently rediscovered by Rene Descartes
and published in his treatise Discours de la Methode in 1637. About 20 years
later, when Descartes' students contacted Pierre de Fermat collecting his correspondence with Descartes, Fermat looked again in 1657 at his argument
with the unsatisfactory description of light refraction by Descartes, and derived
Snell and Descartes' results from a more fundamental principle - light
always travels in the shortest time in any medium, and this principle for light
is now referred to as Fermat's principle, which laid the foundation of modern
optics.
In his Principia Mathematica published in 1687, Sir Isaac Newton solved
the problem of the body shape of minimal resistance that he posed earlier in
1685 as a pioneering problem in optimization, now a problem of the calculus of
variations. The main aim was to find the shape of a symmetrical revolution
body so as to minimize the resistance to motion in a fluid. Subsequently
Newton derived the resistance law of the body. Interestingly, Galileo Galilei
independently suggested a similar problem in 1638 in his Discursi.
In June 1696, J. Bernoulli made some significant progress in calculus. In
an article in Acta Eruditorum, he challenged all the mathematicians in the
world to find the shape or curve connecting two points at different heights
so that a body will fall along the curve in the shortest time due to gravity
- the line of quickest descent, though Bernoulli already knew the solution.
On January 29, 1697 the challenge was received by Newton when he come
home at four in the afternoon and he did not sleep until he had solved it by
about four the next morning and on the same day he sent out his solution.
Though Newton managed to solve it in less than 12 hours as he became the
Warden of the Royal Mint on March 19, 1696, some suggested that he, as
such a genius, should have been able to solve it in half an hour. Some said
this was the first hint or evidence that too much administrative work will slow
down one's progress. The solution as we now know is a part of a cycloid. This
steepest descent is now called Brachistochrone problem, which inspired Euler
and Lagrange to formulate the general theory of calculus of variations.
In 1746, the principle of least action was proposed by P. L. de Maupertuis
to unify various laws of physical motion and its application to explain all
phenomena. In modern terminology, it is a variational principle of stationary
action in terms of an integral equation of a functional in the framework of
calculus of variations, which plays a central role in the Lagrangian and Hamiltonian
classical mechanics. It is also an important principle in mathematics
and physics.
In 1781, Gaspard Monge, a French civil engineer, investigated the transportation
problem for optimal transportation and allocation of resources, if
the initial and final spatial distribution are known. In 1942, Leonid Kantorovich
showed that this combinatorial optimization problem is in fact a
case of a linear programming problem.
Around 1801, Frederich Gauss claimed that he used the method of leastsquares
to predict the orbital location of the asteroid Ceres, though his version
of the least squares with more rigorous mathematical foundation was published
later in 1809. In 1805, Adrien Legendre was the first to describe the
method of least squares in an appendix of his book Nouvelle meethodes pour
la determination des orbites des cometes, and in 1806 he used the principle
of least squares for curve fitting. Gauss later claimed that he had been using
this method for more than 20 years, and laid the foundation for least-squares
analysis in 1795. This led to some bitter disputes with Legendre. In 1808,
Robert Adrain, unaware of Legendre's work, published the method of least
squares studying the uncertainty and errors in making observations, not using
the same terminology as those by Legendre.
In 1815, D. Ricardo proposed the law of diminishing returns for land cultivation,
which can be applied in many activities. For example, the productivity
of a piece of a land or a factory will only increase marginally with additional
increase of inputs. This law is called law of increasing opportunity cost.
1.3 ENGINEERING APPLICATIONS OF OPTIMIZATION
Optimization, in its broadest sense, can be applied to solve any engineering problem.
Some typical applications from different engineering disciplines indicate the wide scope
of the subject:
1. Design of aircraft and aerospace structures for minimum weight
2. Finding the optimal trajectories of space vehicles
3. Design of civil engineering structures such as frames, foundations, bridges,
towers, chimneys, and dams for minimum cost
4. Minimum-weight design of structures for earthquake, wind, and other types of
random loading
5. Design of water resources systems for maximum benefit
6. Optimal plastic design of structures
7. Optimum design of linkages, cams, gears, machine tools, and other mechanical
components
8. Selection of machining conditions in metal-cutting processes for minimum production
cost
9. Design of material handling equipment, such as conveyors, trucks, and cranes,
for minimum cost
10. Design of pumps, turbines, and heat transfer equipment for maximum efficiency
11. Optimum design of electrical machinery such as motors, generators, and transformers
12. Optimum design of electrical networks
13. Shortest route taken by a salesperson visiting various cities during one tour
14. Optimal production planning, controlling, and scheduling
15. Analysis of statistical data and building empirical models from experimental
results to obtain the most accurate representation of the physical phenomenon
16. Optimum design of chemical processing equipment and plants
17. Design of optimum pipeline networks for process industries
18. Selection of a site for an industry
19. Planning of maintenance and replacement of equipment to reduce operating
costs
20. Inventory control
21. Allocation of resources or services among several activities to maximize the
benefit
22. Controlling the waiting and idle times and queueing in production lines to reduce
the costs
23. Planning the best strategy to obtain maximum profit in the presence of a competitor
24. Optimum design of control systems
6 Introduction to Optimization
where X is an n-dimensional vector called the design vector, f (X) is termed the objective
Introduction
Throughout the ages, man has continuously been involved with the process of
optimization. In its earliest form, optimization consisted of unscientific rituals
and prejudices like pouring libations and sacrificing animals to the gods, consulting
the oracles, observing the positions of the stars, and watching the flight
of birds. When the circumstances were appropriate, the timing was thought to
be auspicious (or optimum) for planting the crops or embarking on a war.
As the ages advanced and the age of reason prevailed, unscientific rituals
were replaced by rules of thumb and later, with the development of mathematics,
mathematical calculations began to be applied.
Interest in the process of optimization has taken a giant leap with the advent of
the digital computer in the early fifties. In recent years, optimization techniques
advanced rapidly and considerable progress has been achieved. At the same
time, digital computers became faster, more versatile, and more efficient. As a
consequence, it is now possible to solve complex optimization problems which
were thought intractable only a few years ago.
The process of optimization is the process of obtaining the ‘best’, if it is possible
to measure and change what is ‘good’ or ‘bad’. In practice, one wishes the
‘most’ or ‘maximum’ (e.g., salary) or the ‘least’ or ‘minimum’ (e.g., expenses).
Therefore, the word ‘optimum’ is taken to mean ‘maximum’ or ‘minimum’ depending
on the circumstances; ‘optimum’ is a technical term which implies
quantitative measurement and is a stronger word than ‘best’ which is more
appropriate for everyday use. Likewise, the word ‘optimize’, which means to
achieve an optimum, is a stronger word than ‘improve’. Optimization theory
is the branch of mathematics encompassing the quantitative study of optima
and methods for finding them. Optimization practice, on the other hand, is the
2
collection of techniques, methods, procedures, and algorithms that can be used
to find the optima.
Optimization problems occur in most disciplines like engineering, physics,
mathematics, economics, administration, commerce, social sciences, and even
politics. Optimization problems abound in the various fields of engineering like
electrical, mechanical, civil, chemical, and building engineering. Typical areas
of application are modeling, characterization, and design of devices, circuits,
and systems; design of tools, instruments, and equipment; design of structures
and buildings; process control; approximation theory, curve fitting, solution
of systems of equations; forecasting, production scheduling, quality control;
maintenance and repair; inventory control, accounting, budgeting, etc. Some
recent innovations rely almost entirely on optimization theory, for example,
neural networks and adaptive systems.
Most real-life problems have several solutions and occasionally an infinite
number of solutions may be possible. Assuming that the problem at hand
admits more than one solution, optimization can be achieved by finding the
best solution of the problem in terms of some performance criterion. If the
problem admits only one solution, that is, only a unique set of parameter values
is acceptable, then optimization cannot be applied.
Several general approaches to optimization are available, as follows:
1. Analytical methods
2. Graphical methods
3. Experimental methods
4. Numerical methods
Analytical methods are based on the classical techniques of differential calculus.
In these methods the maximum or minimum of a performance criterion
is determined by finding the values of parameters x1, x2, . . . , xn that cause the
derivatives of f(x1, x2, . . . , xn) with respect to x1, x2, . . . , xn to assume zero
values. The problem to be solved must obviously be described in mathematical
terms before the rules of calculus can be applied. The method need not entail
the use of a digital computer. However, it cannot be applied to highly nonlinear
problems or to problems where the number of independent parameters exceeds
two or three.
A graphical method can be used to plot the function to be maximized or minimized
if the number of variables does not exceed two. If the function depends
on only one variable, say, x1, a plot of f(x1) versus x1 will immediately reveal
the maxima and/or minima of the function. Similarly, if the function depends
on only two variables, say, x1 and x2, a set of contours can be constructed. A
contour is a set of points in the (x1, x2) plane for which f(x1, x2) is constant,
and so a contour plot, like a topographical map of a specific region, will reveal
readily the peaks and valleys of the function. For example, the contour plot of
f(x1, x2) depicted in Fig. 1.1 shows that the function has a minimum at point
The Optimization Problem 3
A. Unfortunately, the graphical method is of limited usefulness since in most
practical applications the function to be optimized depends on several variables,
usually in excess of four.
The optimum performance of a system can sometimes be achieved by direct
experimentation. In this method, the system is set up and the process variables
are adjusted one by one and the performance criterion is measured in each
case. This method may lead to optimum or near optimum operating conditions.
However, it can lead to unreliable results since in certain systems, two or more
variables interact with each other, and must be adjusted simultaneously to yield
the optimum performance criterion.
The most important general approach to optimization is based on numerical
methods. In this approach, iterative numerical procedures are used to generate a
series of progressively improved solutions to the optimization problem, starting
with an initial estimate for the solution. The process is terminated when some
convergence criterion is satisfied. For example, when changes in the independent
variables or the performance criterion from iteration to iteration become
insignificant.
Numerical methods can be used to solve highly complex optimization problems
of the type that cannot be solved analytically. Furthermore, they can be
readily programmed on the digital computer. Consequently, they have all but
replaced most other approaches to optimization.
What is Optimization?
The term of “optimization” refers to the process of searching for the optimum solution from a set of candidates to the problem of interest based on certain performance criteria, which has found broad applications in manufacturing, engineering, finance and logistics etc. Generally speaking, all problems to be optimized should be able to be formulated as a system with its status controlled by one or more input variables and its performance specified by a well defined objective function. The goal of optimization is to find the best value for each variable in order to achieve satisfactory performance. In practice, it could mean to accomplish a predefined task in the most efficient way or the highest quality or to produce maximum yields given limited resources.
1.1 INTRODUCTION
Optimization is the act of obtaining the best result under given circumstances. In design,
construction, and maintenance of any engineering system, engineers have to take many
technological and managerial decisions at several stages. The ultimate goal of all such
decisions is either to minimize the effort required or to maximize the desired benefit.
Since the effort required or the benefit desired in any practical situation can be expressed
as a function of certain decision variables, optimization can be defined as the process
of finding the conditions that give the maximum or minimum value of a function. It can
be seen from Fig. 1.1 that if a point x∗ corresponds to the minimum value of function
f (x), the same point also corresponds to the maximum value of the negative of the
function, −f (x). Thus without loss of generality, optimization can be taken to mean
minimization since the maximum of a function can be found by seeking the minimum
of the negative of the same function.
In addition, the following operations on the objective function will not change the
optimum solution x∗ (see Fig. 1.2):
1. Multiplication (or division) of f (x) by a positive constant c.
2. Addition (or subtraction) of a positive constant c to (or from) f (x).
There is no single method available for solving all optimization problems efficiently.
Hence a number of optimization methods have been developed for solving
different types of optimization problems. The optimum seeking methods are also known
as mathematical programming techniques and are generally studied as a part of operations
research. Operations research is a branch of mathematics concerned with the
application of scientific methods and techniques to decision making problems and with
establishing the best or optimal solutions. The beginnings of the subject of operations
research can be traced to the early period of World War II. During the war, the British
military faced the problem of allocating very scarce and limited resources (such as
fighter airplanes, radars, and submarines) to several activities (deployment to numerous
targets and destinations). Because there were no systematic methods available to
solve resource allocation problems, the military called upon a team of mathematicians
to develop methods for solving the problem in a scientific manner. The methods developed
by the team were instrumental in the winning of the Air Battle by Britain. These
methods, such as linear programming, which were developed as a result of research
on (military) operations, subsequently became known as the methods of operations
research.
II. Real World Problems
Optimization problems are ubiquitous in our everyday life and may come in a variety of forms. For example, a fund manager may need to decide an appropriate investment portfolio according to the specific investment objective, which is often represented by the trade-off between profit and volatility. Usually, funds mainly invested in assets such as cash and property are likely to yield stable but relatively low return while an aggressive portfolio could be made up of a significant portion of high-risk assets such as shares, which may experience large fluctuations in value especially in short term. In this scenario, the variables to be optimized are the percentages of each class of asset, which of course should add up to one.
|[pic] |[pic] |
On the other hand, if this manager needs to visit his clients in different locations, he may be interested in planning his journey in advance in order to visit all clients at the minimum cost in terms of time and petrol, which often implies choosing the shortest route. Suppose there are totally n clients, all possible routes could be encoded by n variables with each one indicating the order of a certain client to be visited. If he is reluctant to drive by locations that he has already visited, there would be totally n! possible routes to choose from. In this problem, the number of candidates could grow very quickly as the increase of the number of locations. For instance, there are 3,628,800 and 2,432,902,008,176,640,000 possible routes for n=10 and n=20 respectively.
|[pic] |[pic] |
In the mean time, people have long been enthusiastic on discovering the underling principles behind data in the hope to, for example, better understand the movement of market price or help the diagnosis of illness based on patient symptoms. These problems are generally specified as regression problems in which one wants to approximate the distribution of the data or classification problems in which data points are to be given different labels and a variety of learning systems have been developed to model the important features embedded in the data. Since most systems have multiple parameters to be adjusted and their performance depends heavily on choosing the right parameter values, optimization techniques could also play a significant role in these areas.
|[pic] |[pic] |
III. How to Solve Them?
While the best solutions may be worked out manually or through exhaustive search in some simple situations, computerized optimization techniques are required to handle most non-trivial problems mainly due to the size and multimodality of the search space. Furthermore, many problems have inherent constraints that must be satisfied and multiple criteria to be met. As a result, good optimization techniques should not only be able to evaluate candidate solutions hundreds of thousands times faster than human thanks to the power of modern computer systems but also employ intelligent mechanism to guide the searching in order to solve challenging problems in practical time.
Despite of the existence of a wide variety of optimization problems that may look quite different from each other, the good news is that many of them could be tackled using techniques under a unified framework. This means that it is not compulsory to invent brand new approaches for each new problem, although certain level of customization may be helpful. The reason is that, during optimization, each problem is transformed into a landscape in the mathematical space similar to its counterpart in the physical world with each dimension representing a variable and an additional dimension indicating the performance. Consequently, the process of optimization is like wondering on the landscape to look for the highest peak, without worrying about the realistic meaning of the problem.
|[pic] |[pic] |
However, landscape walking is not necessarily an easy task as the search space will often grow exponentially with regard to the number of variables. Furthermore, for landscapes with a large number of peaks, locating the best one could also be very challenging. Just image the difficulty of finding a way to the top of the highest hill in a mountain extending hundreds of miles with numerous peaks, valleys and plateaus. In fact, even deciding whether you are on the top of the highest hill could sometimes be difficult. Note that you DO NOT have the big picture of the landscape except the performance of each single point or solution. Unfortunately, based on the current computing technology, it is nearly impossible to guarantee finding the optimum solution in polynomial time.
In order to find as good as possible solutions to these hard optimization problems, a number of meta-heuristic algorithms have been developed since 1970s many of which are loosely based on the fundamental principles of the nature such as population, selection and mutation etc. Some famous ones are Genetic Algorithms,Evolution Strategies, Genetic Programming, Ant Colony Optimization, Estimation of Distribution Algorithms, Particle Swarm Optimizers, Memetic Algorithms andDifferential Evolution, to name a few. The basic idea behind all these algorithms is to assume that there exists some general structure in the landscape, which could be exploited to efficiently explore the search space. Despite of the different heuristics used by these algorithms, the major advantage is that they are usually population-based and have inherent parallel mechanism, which make them less likely to get stuck on local optima. Also, many of them could be implemented relatively easily and could also be modified to better suit different problems.
IV Summary
Optimization is an active and fast growing research area and has a great impact on the real world. Despite of the enormous amount of work that has been conducted both theoretically and empirically and the huge success that has been achieved in different aspects, it is still an ongoing and long-term task to develop competent techniques, which could effectively solve large-scale optimization problems. After all, solving challenging optimization problems is not as simple as plugging in an off-the-shelf optimization routine and hoping it will do the job. Instead, it still requires a significant involvement of human expertise in the analysis, specification and decomposition of the problem as well as choosing and customizing the right technique.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- interval analysis and its applications to
- dynamic workflow optimization on virtual clusters for
- ap calculus ab
- structural shape optimization considering both performance
- polynomials word problems wasatch
- some remedies for some intractable optimization problems
- 6 optimization strategies for client education and report
- optimization tredyffrin easttown school district
- graphical method of solution of a linear programming problem
- a brief history of optimization
Related searches
- a brief history of surgery
- a brief history of philosophy
- a brief history of education
- a brief history of computer
- a brief history of china
- a brief history of time review
- a brief history of india
- a brief history of english
- a brief history of time quotes
- a brief history of time film
- a brief history of time summary
- a brief history of time book