mathematical optimization

Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems of sorts 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. More generally, optimization includes finding "best available" values of some objective function given a defined domain (or input), including a variety of different types of objective functions and different types of domains.

Optimization problems

Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete:
* An optimization problem with discrete variables is known as a '' discrete optimization'', in which an object such as an integer, permutation or graph must be found from a countable set.
* A problem with continuous variables is known as a '' continuous optimization'', in which an optimal value from a continuous function must be found. They can include constrained problems and multimodal problems.

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(\mathbf_)\geq f(\mathbf) \Leftrightarrow -f(\mathbf_)\leq -f(\mathbf),$
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 (lowest) 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 called, variously, an ''objective function'', a ''loss function'' or ''cost function'' (minimization), a ''utility function'' or ''fitness function'' (maximization), or, in certain fields, an ''energy function'' or ''energy functional''. A feasible solution that minimizes (or maximizes, if that is the goal) 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

:$\forall\mathbf\in A \; \text \;\left\Vert\mathbf-\mathbf^\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.

Notation

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

Minimum and maximum value of a function

Consider the following notation:
:$\min_\; \left(x^2 + 1\right)$

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

:$\max_\; 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".

Optimal input arguments

Consider the following notation:
:$\underset \; x^2 + 1,$
or equivalently
:$\underset \; x^2 + 1, \; \text \; x\in(-\infty,-1].$

This represents the value (or values) of the Argument of a function, 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\cos y,$
or equivalently
:\underset \; x\cos y, \; \text \; x\in 5,5 \; y\in\mathbb R,

represents the pair (or pairs) that maximizes (or maximize) the value of the objective function , with the added constraint that lie in the interval (again, the actual maximum value of the expression does not matter). 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

Fermat and Lagrange