Brief History of Optimization

What is Optimization?

Optimization is a word that tends to get misunderstood as each person seems to have their own interpretation of what optimization means. Engineers and technicians instinctively think of optimization as “trial and error.” Others believe that the optimization process is exhaustively listing the design possibilities and picking the best one. Then there are those who perceive that optimization is simply making qualitative suggestions that lead to a better product design.

However, are these methods optimization? They are optimization methods in a broad sense, but they are not proper ones if you follow the definition of optimization as a quantitative and systematic methodology to search for the best design among numerous possibilities while satisfying given constraints.

Optimization as a Quantitative and Systematic Methodology

By this formal definition, optimization has three essential elements: variables, objectives, and constraints.

Variables: Variables are entities and parameters that a designer can change, such as material choice, shape of the product, geometric dimensions, operating parameters, settings, and so on.

Objectives: Objectives are the goals that a designer wants a product or process to achieve, such as the lowest cost, highest performance, least mass, highest efficiency, or minimum deviation from ideal values.

Constraints: Constraints represent the safety regulations, standards and codes, and technical specifications that a product or process must satisfy. For example, a car designer must consider numerous design standards and codes so that the car is safe, comfortable, and environmentally friendly. Simultaneously, a car must perform as well as its competitors and preferably with lower costs to produce. All these can be defined as constraints.

It goes without saying that adjusting variables will impact objectives and/or constraints; otherwise, such variables should not be included in the optimization study.

A Look at Intentional and Subconscious Optimization

You might have noticed that I refer to both product and process design optimization. Yes, optimization can currently be applied to both product design and process design. You apply optimization to design the best cars, airplanes, cell phones, and everything in between. You also apply optimization to design the best manufacturing process, the ideal patient treatment process in hospitals, the best logistic process, the best delivery process, and so on.

As a matter of fact, any rational human behavior could be modelled as an optimization problem because we do such optimization intentionally or subconsciously almost all the time. The following examples illustrate how you use optimization in your everyday life.

When you buy a home: You pick the home/accommodation (variable) to reach the best possible lifestyle (objective) that you can afford (constraint).

When you buy a car: You buy the car (variable) that you like the most (objective) and that you can afford (constraint).

When you attend school: You attend the school (variable) to get the best education (objective) as far as your grades can reach (constraint). The list goes on!

Technological Advances Improve Optimization

Helicopter Design.jpg

Having said that, not all optimization problems can be quantitatively modelled and solved with current technologies. In engineering, however, as human beings develop more advanced mathematics and computational tools, we can model and simulate more sophisticated product and process behaviors, and that makes the application of optimization practical, significant, and worthwhile.

History of Optimization Methods

Calculus: The Earliest Optimization Approach

You can find the earliest optimization approach in calculus where a point on a one-variable function with its first derivative equal to zero gives either a maximum or minimum of the function. Pierre De Fermat and Joseph-Louis Lagrange first found calculus-based formulae for identifying optima. Isaac Newton and Johann C.F. Gauss first proposed iterative methods to search for an optimum.

Early Classic Optimization Approaches

Formal optimization on “linear programming” was started by Leonid Kantorovich in 1939. The first well-known approach, the Simplex Method, was published in 1947 by George Dantzig, and in the same year, the Theory of Duality was published by John von Neumann.

Since then, many optimization methods have been developed. Among the numerous methods, the following methods became well known and widely accepted:

·         The steepest descent method (rooted in unpublished notes of Riemann in 1863)

·         Newton’s method

·         Quasi-Newton methods

·         The penalty method

·         The feasible direction method

·         Quadratic programming

The Karush-Kuhn-Tucker (KKT) condition was found in 1939 and 1951 by two separate groups to test the necessary condition for a constrained optimum. Over the period from the 1940s to the 1970s, the classic optimization approaches were developed rapidly and peaked in the 1970s.

Optimization was also known as mathematical programming or mathematical optimization. Optimization quickly became a large research area with many branches, including those listed here:

·         Linear programming

·         Nonlinear programming

·         Unconstrained optimization

·         Constrained optimization

·         Single-objective and multi-objective optimization

·         Goal programming

·         Dynamic programming

Linear programming matured well and can be found applied in logistics, banking, and economics due to its simplicity.

When it comes to nonlinear optimization, meaning that there is at least one nonlinear objective or constraint function, the known approaches faced more difficulties. Unfortunately, in engineering design, nearly all problems are nonlinear. I will focus my discussion on nonlinear optimization problems for the following sections.

First Generation Optimization: Local, Sequential, and Reliant

The first wave of optimization approaches is characterized with the following three features:

1.       Local optimization: Most of these approaches consider a local optimal, i.e., the lowest point or a valley. A global optimal is defined as the lowest point of all valleys, which is beyond the capabilities of these methods.

2.       Sequential/Iterative search: The idea of iterative search is based on the location of the previously explored point. Its analogy resembles a blind person climbing a hill. This person must know their current position, a direction of movement, and a distance to move in order to determine the next position. The search iterates itself until reaching the top of a hill. This method faces difficulties when each step takes a long time as the total time for optimization equals the multiplication of the time elapsed for each step and the number of steps taken.

3.       Reliance on gradients or higher order derivatives: The calculation of gradients or even higher order derivatives needs more computing resources and is more error-prone than other methods. Earlier optimization code often had problems of non-convergence, float-point error, and other robustness issues.

In application, practitioners complained about these methods because they could not provide enough information about the problems at hand. These methods could not enable practitioners to explain why the optimal is optimal and where to find the next optimal design in case the current solution is not usable for any reason. Also, due to limited computing power, these methods did not get widely applied in engineering. These are some commercial software tools that found success: CPLEX, LINDO, GAMS, SNOPT, and MATLAB.

There are also numerous open source projects that can be downloaded from the internet. This group of approaches can be considered as the first generation of optimization methods.

Second Generation Optimization: The Metaheuristic Approach

The 1980s is when metaheuristic approaches attracted the attention of engineers, and one of the most popular approaches was Genetic Algorithms, invented by John Holland in 1960. Genetic Algorithms work on the principle of “survival of the fittest.” Following that, Simulated Annealing was published in 1983 in the Science journal, which was unusual for an algorithm article to appear in the journal. Simulated Annealing was inspired by the heat treatment process of annealing and became a global optimization algorithm.

More algorithms were developed later, such as Particle Swarm Optimization, Ant Colony Optimization, Tabu Search, and Artificial Bee Colony. This group of approaches is inspired by nature or other heuristics and have the following benefits:

·         They are global optimization approaches in essence.

·         They do not require gradients or higher derivatives.

·         They support parallel computation.

Even today there are new methods being developed as new heuristics are invented. This group represents the second generation of optimization methods.

Despite many benefits, the major problem with metaheuristic approaches is the need for an enormous amount of trial points before reaching the global optimum. These methods work very well for problems consisting of just equations or those that need little computation to evaluate each trial. However, in engineering, as computer aided engineering (CAE) tools are widely adopted and applied, the computation time for evaluating each design could be hours or days. Even with parallel computation, the total time for evaluating thousands of design trials would still be impractical. The question then becomes, “How do you find the global optimal with the minimum number of design trials?”

Third Generation Optimization: The Al-Based Approach

In this context, the AI-based approaches started to emerge in the late 1990s as the third generation of optimization methods and have matured in recent years. This group of approaches is also called surrogate-based optimization or metamodel-based optimization. The idea is to use a limited number of design trials (called sample points) to construct a machine-learning model between the design variables and objectives/constraints. Sample points can be generated following traditional Design of Experiments (DOE), but the community realized that for computer experiments DOE methods were no longer applicable as they tend to go beyond the design space and have little information about the space itself. This is because DOE schemes were developed to reduce the variance caused by random errors in physical experimentation.

For computer simulations, space-filling samples are needed in order to address the possible system error between the machine-learning model and the CAE model. In the beginning, this machine-learning model replaced the original CAE model to participate in visualization, design exploration, and optimization. This is how the name “surrogate” originated. Then it was discovered that simply replacing the original model is insufficient as the machine-learning model may not be accurate, and in fact, it is not feasible to build a globally accurate machine-learning model over a high-dimensional space.

The community chose to use “metamodel” instead of simply indicating this machine-learning model is a “model of a model.” The modeling approach and mathematics are essentially the same as those for machine learning. By iteratively constructing the machine-learning model, optimization can be carried out along with the learning and knowledge mining from a growing number of sample points. The AI-based approaches are global optimization methods with the following advantages:

·         They support parallel computation.

·         They do not need gradients.

·         They use fewer design trials than before.

·         They offer insight and knowledge about the design problem.

 These advantages make this group of approaches practical. Many algorithms were developed, and among them were the Efficient Global Optimization (EGO) and Mode Pursuing Sampling (MPS), which are both widely cited in the research community. Commercial software tools adopted this group of methods.

One big obstacle for AI-based approaches is the so-called “curse-of-dimensionality.” As sample points are needed in order to learn a space, assuming you only use three points per dimension, for a 10-dimensional problem the number of design trial points becomes 59,049 (i.e., 3^10). The growth of the design trial count is exponential and thus becomes a curse. For this very reason, early AI-based methods can only solve problems of 10 dimensions or less and have difficulty for higher dimensional problems. Both EGO and MPS suffer from this problem.

Integrating the Approaches Can Lead to State-of-the-Art in Optimization

My classification of the different generations of optimization approaches is simply based on the developmental timeline. It does not mean that the new generation of approaches will outdate the previous generation of approaches. On the contrary, AI-based approaches often call a local search from the first-generation approaches, and some recent research integrates metaheuristics and AI-based approaches to develop new algorithms. Such integration or idea fusion is healthy and justifiable as long as it is pushing the boundary of what is considered to be cutting-edge today and satisfies the need of engineering practice.

Challenges of Handling Constraints

Constraint handling is a challenge, and that is a topic I started to tackle in 2007 and about which I published a series of important works. Most algorithms assume constraints are cheap to evaluate and thus users can generate numerous design trials and check them against constraints. The reality is that many constraints come from expensive simulations as well.

For example, when designing a car, its crashworthiness needs to be simulated and tested. Using a modern high-performance computer one reasonable crash simulation took 17 hours to complete. When crashworthiness is specified as a constraint, as often it is, algorithms that assume that constraints are fast to evaluate (i.e., that the 17-hour simulation is “fast”) are simply not applicable. In other cases, constraints are often evaluated together with the objective. For instance, if we design a desk to have great strength (objective) and want its maximum deformation to be smaller than a certain value to prevent apparent sag under a given load (constraint). The strength and deformation are usually computed from one solid mechanics simulation. These challenges represent the tasks that state-of-the-art systems must overcome.



About the Author

Dr. Gary Wang is a Co-Founder of Empower Operations. He is recognized as one of the world leaders in engineering design and optimization and has more than 20 years of research and development experience in the field. He is the recipient of the 2005 National I. W. Smith award for creative engineering from the Canadian Society of Mechanical Engineering (CSME,) as well as the 2007 Rh Award from University of Manitoba for outstanding research contribution. Being an ASME Fellow, Dr. Wang is currently serving as an associate editor for field top journals Engineering Optimization and ASME Transactions, Journal of Mechanical Design.