Mathematical optimization


Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.
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.

Optimization problems

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:
Such a formulation is called an optimization problem or a mathematical programming problem. Many real-world and theoretical problems may be modeled in this general framework.
Since the following is valid:
it suffices to solve only minimization problems. However, the opposite perspective of considering only maximization problems would be valid, too.
Problems formulated using this technique in the fields of physics may refer to the technique as energy minimization, 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 error.
Typically, is some subset of the Euclidean space, often specified by a set of constraints, equalities or inequalities that the members of have to satisfy. The domain of is called the search space or the choice set, while the elements of are called candidate solutions or feasible solutions.
The function is variously called an objective function, criterion function, loss function, cost function, utility function or fitness function, or, in certain fields, an energy function or energy functional. A feasible solution that minimizes 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
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, 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.

Notation

Optimization problems are often expressed with special notation. Here are some examples:

Minimum and maximum value of a function

Consider the following notation:
This denotes the minimum value of the objective function, when choosing from the set of real numbers. The minimum value in this case is 1, occurring at.
Similarly, the notation
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".

Optimal input arguments

Consider the following notation:
or equivalently
This represents the value of the argument in the interval that minimizes the objective function . In this case, the answer is, since is infeasible, that is, it does not belong to the feasible set.
Similarly,
or equivalently
represents the pair that maximizes the value of the objective function, with the added constraint that lie in the interval . In this case, the solutions are the pairs of the form and, where ranges over all integers.
Operators and are sometimes also written as and, and stand for argument of the minimum and argument of the maximum.

History

and Lagrange found calculus-based formulae for identifying optima, while Newton and Gauss proposed iterative methods for moving towards an optimum.
The term "linear programming" for certain optimization cases was due to George B. Dantzig, although much of the theory had been introduced by Leonid Kantorovich in 1939. Dantzig published the Simplex algorithm in 1947, and also John von Neumann and other researchers worked on the theoretical aspects of linear programming around the same time.
Other notable researchers in mathematical optimization include the following:
In a number of subfields, the techniques are designed primarily for optimization in dynamic contexts :