Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives.[1] [2] It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering[3] to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.[4]
In the more general approach, an optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics.
See main article: Optimization problem.
Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete:
An optimization problem can be represented in the following way:
Given: a function from some set to the real numbers
Sought: an element such that for all ("minimization") or such that for all ("maximization").
Such a formulation is called an optimization problem or a mathematical programming problem (a term not directly related to computer programming, but still in use for example in linear programming – see History below). Many real-world and theoretical problems may be modeled in this general framework.
Since the following is valid
f(x0)\geqf(x)\Leftrightarrow-f(x0)\leq-f(x),
Problems formulated using this technique in the fields of physics may refer to the technique as energy minimization,[5] speaking of the value of the function as representing the energy of the system being modeled. In machine learning, it is always necessary to continuously evaluate the quality of a data model by using a cost function where a minimum implies a set of possibly optimal parameters with an optimal (lowest) error.
Rn
The function is variously called an objective function, criterion function, loss function, cost function (minimization), utility function or fitness function (maximization), or, in certain fields, an energy function or energy functional. A feasible solution that minimizes (or maximizes) the objective function is called an optimal solution.
In mathematics, conventional optimization problems are usually stated in terms of minimization.
A local minimum is defined as an element for which there exists some such that
\forallx\inA where \left\Vertx-x\ast\right\Vert\leq\delta,
the expression holds;
that is to say, on some region around all of the function values are greater than or equal to the value at that element. Local maxima are defined similarly.
While a local minimum is at least as good as any nearby elements, a global minimum is at least as good as every feasible element.Generally, unless the objective function is convex in a minimization problem, there may be several local minima.In a convex problem, if there is a local minimum that is interior (not on the edge of the set of feasible elements), it is also the global minimum, but a nonconvex problem may have more than one local minimum not all of which need be global minima.
A large number of algorithms proposed for solving the nonconvex problems – including the majority of commercially available solvers – are not capable of making a distinction between locally optimal solutions and globally optimal solutions, and will treat the former as actual solutions to the original problem. Global optimization is the branch of applied mathematics and numerical analysis that is concerned with the development of deterministic algorithms that are capable of guaranteeing convergence in finite time to the actual optimal solution of a nonconvex problem.
Optimization problems are often expressed with special notation. Here are some examples:
Consider the following notation:
minx\inR \left(x2+1\right)
This denotes the minimum value of the objective function, when choosing from the set of real numbers
R
Similarly, the notation
maxx\inR 2x
asks for the maximum value of the objective function, where may be any real number. In this case, there is no such maximum as the objective function is unbounded, so the answer is "infinity" or "undefined".
See main article: Arg max. Consider the following notation:
\underset{x\in(-infty,-1]}{\operatorname{argmin}} x2+1,
\underset{x}{\operatorname{argmin}} x2+1, subjectto: x\in(-infty,-1].
This represents the value (or values) of the argument in the interval that minimizes (or minimize) the objective function (the actual minimum value of that function is not what the problem asks for). In this case, the answer is, since is infeasible, that is, it does not belong to the feasible set.
Similarly,
\underset{x\in[-5,5], y\inR}{\operatorname{argmax}} x\cosy,
\underset{x, y}{\operatorname{argmax}} x\cosy, subjectto: x\in[-5,5], y\inR,
represents the