Optimization problem

In the case of an optimization problem , a solution space (set of possible solutions) and an evaluation function (also goal or fitness function) are given. One wants to find a solution with the greatest possible value , or make statements about the values ​​of the solutions. ${\displaystyle \Omega }$ ${\displaystyle f\colon \Omega \rightarrow \mathbb {R} }$ ${\displaystyle x\in \Omega }$ ${\displaystyle f(x)}$

In this case there would be a maximization problem , with a minimization problem solutions with as small as possible are sought, but this case can be reduced to the previous one by simply negating . ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle f}$

A distinction is made between three problems:

• Decision problems for which a limit value is alsogiven and it should be determined whether there is awith. ${\displaystyle g\in \mathbb {R} }$ ${\displaystyle x\in \Omega }$ ${\displaystyle f(x)\geq g}$
• actual optimization problems for which you want to know the value of the best solution, that is . ${\displaystyle \max\{f(x)\mid x\in \Omega \}}$
• Search problems for which an optimal solution issought (), or a solution with a given minimum quality, i.e. onewith. Or you just want to find the best possible solution (approximation). ${\displaystyle o\in \Omega }$ ${\displaystyle f(o)=\max\{f(x)\mid x\in \Omega \}}$ ${\displaystyle o}$ ${\displaystyle f(o)\geq g}$

In theoretical computer science , an optimization problem usually means an actual optimization problem, in which only the best possible value and no solution itself is sought. The special case of a discrete evaluation function is also usually considered, since this usually makes no significant difference and real numbers are less easy to handle, e.g. B. approximately as floating point numbers . ${\displaystyle f\colon \Omega \rightarrow \mathbb {N} }$

Mostly, however, one considers decision problems in theoretical computer science. A decision problem can easily be generated for an optimization problem by adding the limit value or to the problem . Conversely, for most practically interesting problems, one can show that a solution path for the decision problem can be modified to a solution of the corresponding search or optimization problem that does not require significantly more computing time or storage space. ${\displaystyle g\in \mathbb {R} }$ ${\displaystyle g\in \mathbb {N} }$

In practical use, you usually have to deal with search problems, because the value of an optimal solution is usually of no use to you without knowledge of this solution. An algorithm that solves an optimization problem is called an optimization algorithm . Similarly, the minimization and maximization problem are more precisely referred to as the minimization or maximization algorithm. An algorithm that approximately solves an optimization problem is called an approximation algorithm , but often also somewhat imprecise as an optimization algorithm.

See also

• Optimization (math)
• Evolutionary Algorithm

Web links

• Literature on the optimization problem in the catalog of the German National Library