Editing Mathematical optimization (section)

== Optimization problems ==
{{main|Optimization problem}}

Optimization problems can be divided into two categories, depending on whether the [[Variable (mathematics)|variables]] are [[continuous variable|continuous]] or [[discrete variable|discrete]]: 
* An optimization problem with discrete variables is known as a ''[[discrete optimization]]'', in which an [[Mathematical object|object]] such as an [[integer]], [[permutation]] or [[Graph (discrete mathematics)|graph]] must be found from a [[countable set]]. 
* A problem with continuous variables is known as a ''[[continuous optimization]]'', in which optimal arguments from a continuous set must be found. They can include [[Constrained optimization|constrained problem]]s and multimodal problems.

An optimization problem can be represented in the following way:
:''Given:'' a [[function (mathematics)|function]] {{math|''f'' : ''A'' → <math>\mathbb R</math>}} from some [[Set (mathematics)|set]] {{mvar|A}} to the [[real number]]s
:''Sought:'' an element {{math|'''x'''<sub>0</sub> ∈ ''A''}} such that {{math|''f''('''x'''<sub>0</sub>) ≤ ''f''('''x''')}} for all {{math|'''x''' ∈ ''A''}} ("minimization") or such that {{math|''f''('''x'''<sub>0</sub>) ≥ ''f''('''x''')}} for all {{math|'''x''' ∈ ''A''}} ("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|History]] below). Many real-world and theoretical problems may be modeled in this general framework.

Since the following is valid:

:<math>f(\mathbf{x}_{0})\geq f(\mathbf{x}) \Leftrightarrow -f(\mathbf{x}_{0})\leq -f(\mathbf{x}),</math> 
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'',<ref>{{cite book |title=Optimization algorithms in physics |last1=Hartmann |first1=Alexander K |last2=Rieger |first2=Heiko |date=2002 |publisher=Citeseer}}</ref> speaking of the value of the function {{mvar|f}} as representing the energy of the [[system]] being [[Mathematical model|modeled]]. In [[machine learning]], it is always necessary to continuously evaluate the quality of a data model by using a [[Loss function|cost function]] where a minimum implies a set of possibly optimal parameters with an optimal (lowest) error.

Typically, {{mvar|A}} is some [[subset]] of the [[Euclidean space]] <math>\mathbb R^n</math>, often specified by a set of ''[[constraint (mathematics)|constraints]]'', equalities or inequalities that the members of {{mvar|A}} have to satisfy. The [[domain of a function|domain]] {{mvar|A}} of {{mvar|f}} is called the ''search space'' or the ''choice set'', while the elements of {{mvar|A}} are called ''[[candidate solution]]s'' or ''feasible solutions''.

The function {{mvar|f}} is variously called an ''objective function'', ''criterion function'', ''[[loss function]]'', ''cost function'' (minimization),<ref>{{Citation |last=Erwin Diewert |first=W. |title=Cost Functions |date=2017 |work=The New Palgrave Dictionary of Economics |pages=1–12 |url=https://link.springer.com/referenceworkentry/10.1057/978-1-349-95121-5_659-2 |access-date=2024-08-18 |place=London |publisher=Palgrave Macmillan UK |language=en |doi=10.1057/978-1-349-95121-5_659-2 |isbn=978-1-349-95121-5}}</ref> ''utility function'' or ''fitness function'' (maximization), or, in certain fields, an ''energy function'' or ''energy [[functional (mathematics)|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'' {{math|'''x'''*}} is defined as an element for which there exists some {{math|''δ'' > 0}} such that

:<math>\forall\mathbf{x}\in A \; \text{where} \;\left\Vert\mathbf{x}-\mathbf{x}^{\ast}\right\Vert\leq\delta,\,</math>

the expression {{math|''f''('''x'''*) ≤ ''f''('''x''')}} holds;

that is to say, on some region around {{math|'''x'''*}} 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 function|convex]] in a minimization problem, there may be several local minima.
In a [[convex optimization|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.