Adventures in Optimization

I think it's safe to say that optimization is my area of expertise. My dissertation was on the application of an optimization method to a problem arising in geophysics. My boss is putting me on all these proposals as the optimization expert. And the other day, I was asked to serve on a DOE review panel for a couple of proposals involving optimization.

This explains why optimization is always on my mind, then. And it explains why this blog entry is all about optimization! (Well, that and the fact that some people just come here for the math. Gotta know your audience!)

Once again, never fear, non-mathematicians! I'm not going to get all technical on you. Why would I want to relive all the technical details in my off time, after all?

Optimization is the process of finding the best possible configuration or solution to a problem. The best solution is called the optimal solution, or optimum, and the configuration at which we obtain the optimal solution is the optimizer. So, for example, if we want to buy at least three oranges from Kroger at the cheapest possible price, then the optimum might be $1.00, with the optimizer of the oranges that are 3 for a dollar.

Usually when we have an optimization problem, we also have a constraint. That is, we might want to buy no fewer than three oranges, but no more than a dozen, and minimize the price per orange. So maybe there is a bag of a dozen oranges that sells for $3, and a crate of a gross (144) selling for $5, in addition to the 3 for a dollar deal. Well, the crate price is definitely the cheapest per orange (about 3.5 cents per orange!) but it doesn't meet our constraints. So instead we must choose the bag of a dozen oranges for $3, which comes out to a quarter per orange.

Sometimes in an optimization problem, we have two conflicting objectives we wish to satisfy. For example, the other day I had a shopping list that was pretty much evenly divided between food items and drugstore items. If I wanted to minimize the dollar cost of buying everything on my list, I could buy all the drugstore items at Kmart for a pretty good price, and then head over to Kroger and buy all the food items. But I was also kind of tired (it was 6 p.m. on a Friday, after a long day of work!) so another, conflicting objective was to minimize my effort. The drugstore items were also available at Kroger, but they would cost slightly more. Which solution was better: going to two stores, or going to one store but paying more?

It would be nice if I could incorporate these conflicting objectives into a single problem. But how can I quantify "effort?" I could say that time is money, and express the problem like this:

minimize [(cost of shopping) + (my hourly pay rate) × (time spent shopping)].

The trouble with this approach is that the effort of shopping isn't always the same. For example, it takes much more effort to shop when you're hungry or sick with the flu than when you're well-rested and not in a hurry. So "effort" doesn't seem to readily translate into terms of money.

Optimization problems like these, with conflicting objectives that can't readily be combined, are called Pareto optimization problems. They are pervasive in the fields of economics, engineering, and mathematics.

Depending on how important each objective is, there can be a huge continuum of solutions. For example, if my only objective was to minimize the cost of the items on my list, I might hit several stores, compare all the prices, compile a list of the cheapest prices, and buy from a large number of stores. Of course, this process would take hours and I would have expended a great deal of effort. At the other extreme, I could pay someone to go to the store and buy all those items for me. This would require little effort but probably cost more than I would want it to.

Qualitatively, if we were to draw a graph of cost versus effort, it might look something like the following.



The x-axis (left to right) represents cost, and the y-axis (up and down) represents effort. The dotted lines represent the minimum possible cost and effort. The red dot where they intersect represents the (impossible) minimum combination of cost and effort. The blue curve represents all the possible minimum combinations of cost and effort; in other words, at any of the green dots on the curve, any decrease in cost will come at the expense of more effort, and vice versa.

You may be wondering how I could draw such a curve in real life. Well, I do have a means of converting effort to money (pay rate × time). I could quantify effort by weighting that quantity depending on how tired I am. I could set up the problem like this:

minimize (1- w) × (Cost) + w × (Effort),

where 0 < w < 1 is the weight I assign to effort. So on days when I am feeling chipper and adventurous, maybe I will assign w = 0.1, and on days when I am in bed with the flu, maybe w = 0.9. In other words, there are many Pareto optimal solutions to this problem, and I simply select the one that best suits my needs.

I mentioned before that Pareto optimization problems are central to economics and engineering. You can see from my example that the same sort of analysis could be applied to many economic issues.

As for engineering, hydrogeologists might want to determine the configuration of an underground aquifer using data from several different exploration methods, such as seismic data, borehole data, and electromagnetic data. All of these methods give different pictures of the aquifer. How do we combine the data to give us the most accurate picture?

Once we've figured out the configuration of the aquifer, we can now understand how the geology will affect the transport of a contaminant. What is the best way to clean up the contaminant, while minimizing environmental impact, cost, and time?

Suppose we want to route messages through a dynamically changing network where the cost of a path is determined by several non-additive cost functions. How do we find the best path?

Suppose we create a robot that needs to make sequential decisions in a changing environment. How can the robot make those choices?

These are all very difficult problems, and unfortunately, there are no unique solutions. The solutions generally depend on the priorities of the people posing the problems.