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.

Un altre problema d'optimització típic, excepte que es requereix una calculadora per resoldre el problema. Maximitzar és el que volem determinar.

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 $${\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.

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ó.