Anne Marsan: Software for Engineers

Awhile back I wrote part 1 of a series on design optimization. At long last here is Part 2.

As a quick review, design optimization is a mathematical process that we can use to (i) describe a system in terms of mathematical variables, (ii) change the values of the variables in order to explore different system configurations, and (iii) find the values of the variables that give us the "best" system. Design optimization can be applied to many different kinds of systems. If you can model your system with mathematical equations, then most likely you can apply design optimization to it. For instance, mathematical equations can be used to model the flow of a fluid such as water in a series of interconnected pipes. Design optimization can be used to find the best size for each pipe in order to minimize the cost of the pipes, but still move the the fluid through the system without backups or ruptures.

In part 1 of this series, I introduced the key concepts in modeling a system: our system is defined in terms of variables, the system must satisfy certain constraints, and we are trying to minimize an objective function. Usually design optimization problems are written like this:

Note that we group the design variables into a vector x. One thing I didn't mention in Part 1 about the design variables is that they are generally assumed to be real-valued, which is indicated in the last line of figure above.

Once we've described our optimization problem using mathematical equations, the question becomes, "How do we find the value of x that results in the best design?" The basic idea is that we start with some arbitrary value, called x_i, and then we use a systematic way of tweaking that value to get x_i+1. Ideally, our objective function evaluated at x_i+1 will be less than at x_i, or f(x_i+1) < f(x_i). Following the design algorithm, we would have a series of values x₁, x₂, ... , x_n, and corresponding series f(x₁) > f(x₂) > ... > f(x_n), with x_n being the optimal point. Schematically, it would look like this:

At this point, two questions must be answered: (1) What goes on in the "Do some math" box? And (2) how do we know when to stop iterating?

I'll answer the second question first. There are several different stopping criteria that are used in design optimization practice. One of the most common is to stop if the the objective function doesn't change very much between x_i and x_i+1, i.e. if:

This works if as we approach the optimal point we take smaller and smaller steps. Another approach is to stop if we reach some predetermined maximum number of iterations, i.e. if:

n >= max_iterations.

There are other criteria, especially depending on the optimization algorithm that is used, but the ones shown above are fairly common.

But back to question 1, what goes on inside the black box? This is where most of the work in design optimization takes place: designing and tweaking the optimization algorithm. The type of algorithm that is used depends on the type of design variables - whether they are continuous or discrete; the type of constraints - whether they are linear or non-linear; and the objective function - can derivatives be computed or not.

To give you an idea of the variety of optimization algorithms that are available to choose from, take a look at Wikipedia's summary on the topic. It lists 89 different algorithms. Some are fairly exotic and used in highly specialized situations. Others are more general purpose and are the workhorses of the design optimization community. In my next installment, I'll talk about some of the commonly used algorithms, going over the basic idea behind them and in what scenarios they can be applied.