Norsk English

# Mathematical optimization

Optimization problems pop up all the time in real-life applications. There are myriads of situations where you want to find the best element among a set of available elements, according to some preference or criteria. If then we represent and solve our problem by means of mathematics, we are in the realm of mathematical optimization.

## Contact person

You are in the center of Oslo and want to get to SINTEF, in Forskningsveien 1, as fast as you can. You know what you can do: you can ask google to find the best way for you. What you maybe do not know is that google is actually representing and solving your query as an optimization problem. Indeed, you want to find the shortest path from your location to a specific location in the city, chosen among the set of all possible paths. This particular optimization problem is called the shortest path problem

In mathematical optimization, both the set of available elements (feasible region) and the quality criteria (objective function) are expressed by means of variables, functions, equations, inequalities, etc.

The feasible region is a subset S Rn, whereas the objective is a function f :  R. The mathematical optimization problem writes as

min f(x): x ∈ S.

The set is the set of vectors ∈ Rsatisfying a finite number of equations or inequalities of the type gi(x) ≤ bi , for = 1, ..., m, with g : Rn  R. These inequalities are called constraints, because the actually limit the range of values that the variables can assume. Back to our shortest path problem, each variable  x(i.e. each component of vector ∈ S) is associated with a specific link or street e. The last street in my path must be Forskningsveien: this is a constraint. Also, for any intermediate street I take in my path, the next must be an adjacent street. This is another constraint.

There are several classifications of mathematical optimization problems, depending on the form of the objectives and of the constraints.  If the feasible set is a polyhedron and the objective function f is linear, then we have a linear programming problem, and if  is quadratic, then we have quadratic programming. If is finite, then we have a combinatorial optimization problem also called discrete optimization problem. The shortest path problem is combinatorial optimization, because we only have a finite (although huge) set of alternative paths.