Optimization (mathematics)

In mathematics, the term optimization refers to the study of problems that have the form

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:Given: a function f : A o R from some set A to the real numbers

Related Topics:
Function - Set - Real number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A ("minimization") or such that f(x0) ≥ f(x) for all x in A ("maximization").

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Such a formulation is sometimes called a mathematical program (a term not directly related to computer programming, but still in use for example for linear programming - see history below). Many real-world and theoretical problems may be modeled in this general framework.

Related Topics:
Computer programming - Linear programming

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Typically, A is some subset of the Euclidean space Rn, often specified by a set of constraints, equalities or inequalities that the members of A have to satisfy. The elements of A are called feasible solutions. The function f is called an objective function, or cost function. A feasible solution that minimizes (or maximizes, if that is the goal) the objective function is called an optimal solution.

Related Topics:
Subset - Euclidean space - Constraint

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In general, there will be several local minima and maxima, where a local minimum x* is defined as a point such that for some δ > 0 and all x such that

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:|mathbf{x}-mathbf{x}^*|leqdelta;

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

the formula

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:f(mathbf{x}^*)leq f(mathbf{x})

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

holds; that is to say, on some ball around x* all of the function values are greater than or equal to the value at that point. Local maxima are defined similarly. In general, it is easy to find local minima — additional facts about the problem (e.g. the function being convex) are required to ensure that the solution found is a global minimum.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~