MATHEMATICAL ANALYSIS : Did you say optimize ?

Version française

 

by Claude Lemaréchal

Optimization tackles the most complex problems, planning railway traffic, managing inventory or a portfolio or even predicting tomorrow's weather. The objective is always the same, to find the best solution. Optimization consists in finding values for real variables so that a given function in these variables, let us say f(x), takes the smallest possible value (cost minimization) or the largest possible value (profit maximization). This operation may turn out to be quite complex when the number of variables is large. The so-called linear optimization concerns, roughly speaking, functions that vary proportionally to their variables. This type of problem is by now well under control using algebraic methods that date back to post World War II. On the other hand, nonlinear optimization poses highly specialized problems in analysis and is being significantly researched at INRIA. The main difficulty is that the information available on a given problem is usually very limited. What is available is basically a software that takes as input the numerical values of the vector x and computes the corresponding value of f(x). First derivatives, and more rarely second derivatives, are sometimes also available.

In numerous optimization problems, f is expressed in euros and the goal is to find a solution that corresponds to production at the lowest cost or to the convergence of the set of stocks in a portfolio toward maximum gains. Optimization is however not limited to this and can also be applied to identification problems of determining unknown parameters based on observations. In weather prediction, for example, the evolution of the weather can be simulated by solving the equations that govern the state of the atmosphere (pressure, temperature, winds and so on). These are essentially the Navier-Stokes equations or an appropriately simplified version thereof. Prediction requires the knowledge of the initial conditions of the atmosphere. The problem is to identify these initial conditions in order to improve the model, and thus the prediction, when the only available data concern the past states of the atmosphere. Optimization solves this problem by trying to minimize the distance between today's measurements and a theoretical prediction. Taking the state of the atmosphere yesterday at the same time as the unknown x, f(x) is the distance between the result of the computations starting from x and today's observations. Once the optimization procedure is complete, an initial condition for prediction strictly speaking is obtained, and the actual prediction is computed by a final integration starting from today. This example shows very well the scarcity of available information: the computation of just f(x) is itself a lengthy procedure that involves the resolution of equations that are far from simple. We might say that the first difficulty in meteorology is actually to know what the current weather is, and optimization is also helpful in this respect.

Claude Lemaréchal, researcher at INRIA, Project Numopt at Grenoble Tel.: +33 4 76 61 52 02, Claude.Lemarechal@inria.fr

Contents INedit 27