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.

Google Online Preview   Download