Content deleted Content added
Fgnievinski (talk | contribs) No edit summary |
Linkify terms |
||
Line 1:
{{Broader|Mathematical optimization}}
In [[mathematics]] and [[computer science]], an '''optimization problem''' is the [[Computational_problem|problem]] of finding the ''best'' solution from all [[feasible solution]]s. 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 mathematics|discrete]] variables is known as a [[Combinatorial Optimization|combinatorial optimization problem]]. In a combinatorial optimization problem, we are looking for an object such as an [[integer]], [[permutation]] or [[Graph (discrete mathematics)|graph]] from a [[Finite set|finite]] (or possibly [[Countable set|countable infinite]]) set. Problems with continuous variables include constrained problems and multimodal problems.
==Continuous optimization problem==
The ''[[Canonical form|standard form]]'' of a ([[Continuity (mathematics)|continuous]]) optimization problem is<ref>{{cite book|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|page=129|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|format=pdf}}</ref>
: <math>\begin{align}
&\underset{x}{\operatorname{minimize}}& & f(x) \\
Line 12:
\end{align}</math>
where
* <math>f(x): \mathbb{R}^n \to \mathbb{R}</math> is the '''[[Loss function|objective function]]''' to be minimized over the variable <math>x</math>,
* <math>g_i(x) \leq 0</math> are called '''inequality [[Constraint (mathematics)|constraints]]''', and
* <math>h_i(x) = 0</math> are called '''equality constraints'''.
By convention, the standard form defines a '''minimization problem'''. A '''maximization problem''' can be treated by [[Additive inverse|negating]] the objective function.
==Combinatorial optimization problem==
Formally, a [[combinatorial optimization]] problem <math>A</math> is a quadruple <math>(I, f, m, g)</math>, where
* <math>I</math> is a [[Set (mathematics)|set]] of instances;
* given an instance <math>x \in I</math>, <math>f(x)</math> is the set of feasible solutions;
* given an instance <math>x</math> and a feasible solution <math>y</math> of <math>x</math>, <math>m(x, y)</math> denotes the [[Measure (mathematics)|measure]] of <math>y</math>, which is usually a [[Positive (mathematics)|positive]] [[Real number|real]].
* <math>g</math> is the goal function, and is either <math>\min</math> or <math>\max</math>.
Line 52:
| publisher = Springer
| isbn = 978-3-540-44134-2
}}</ref> Note that the below referred [[Polynomial|polynomials]] are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances.
* the size of every feasible solution <math>\scriptstyle y\in f(x)</math> is polynomially [[Bounded set|bounded]] in the size of the given instance <math>x</math>,
* the languages <math>\scriptstyle \{\,x\,\mid\, x \in I \,\}</math> and <math>\scriptstyle \{\,(x,y)\, \mid\, y \in f(x) \,\}</math> can be [[decidable language|recognized]] in [[polynomial time]], and
* ''m'' is [[polynomial time|polynomial-time computable]].
| |||