Problema d'optimització

En matemàtiques, informàtica i economia, un problema d'optimització és el problema de trobar la millor solució entre totes les solucions factibles.^[1]

Els problemes d'optimització es poden dividir en dues categories, depenent de si les variables són contínues o discretes:

• Un problema d'optimització amb variables discretes es coneix com a optimització discreta, en la qual un objecte com un nombre enter, una permutació o un gràfic s'ha de trobar a partir d'un conjunt comptable.
• Un problema amb variables contínues es coneix com a optimització contínua, en la qual s'ha de trobar un valor òptim d'una funció contínua. Poden incloure problemes restringits i problemes multimodals.

La forma estàndard d'un problema d'optimització contínua és^[2]$${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimitzar} }}&&f(x)\\&\operatorname {subjecte\;a} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}}$$on

• f : ℝⁿ → ℝ és la funció de pèrdues a optimitzar el vector x d'n variables.
• g_i(x) ≤ 0 són les restriccions en forma de desigualtats.
• h_j(x) = 0 són les restriccions en forma de desigualtats, i
• m ≥ 0 i p ≥ 0.

Si m = p = 0, el problema és un problema d'optimització sense restriccions. Per convenció, la forma estàndard defineix un problema de minimització. Un problema de maximització es pot tractar negant la funció objectiu.^[3]

En el camp dels algorismes d'aproximació, els algorismes estan dissenyats per trobar solucions gairebé òptimes a problemes difícils. La versió de decisió habitual és llavors una definició inadequada del problema, ja que només especifica solucions acceptables. Tot i que podríem introduir problemes de decisió adequats, el problema es caracteritza de manera més natural com un problema d'optimització.^[4]