Optimalidad y mínimos cuadrados · Definición

Problema de optimización

optimización continuaoptimalidad y mínimos cuadrados

Antes de empezar necesitas conocer

Muchos problemas de ingeniería, economía y aprendizaje automático se formulan como encontrar el mejor valor de una cantidad bajo límites. Esta forma general permite estudiar todos ellos con las mismas herramientas.

Definición

Un problema de optimización consiste en minimizar o maximizar una función objetivo \(f\) sobre un conjunto de puntos que cumplen ciertas restricciones.

\[\min_{x \in \mathbb{R}^n} f(x) \quad \text{sujeto a} \quad g_i(x) \le 0\]

Si \(f\) es convexa y el conjunto factible es convexo, todo mínimo local es también global, y las condiciones KKT son necesarias y suficientes bajo condiciones de regularidad. Los métodos de descenso de gradiente, de Newton y de punto interior permiten resolverlos numéricamente.

Considera minimizar \(f(x,y)=x^2+y^2\) sujeto a \(x+y=2\). Al sustituir \(y=2-x\) se obtiene \(h(x)=x^2+(2-x)^2\), cuyo punto crítico \(x=1\) da el mínimo \(f(1,1)=2\).

Un error típico es buscar puntos donde \(\nabla f=0\) sin revisar las restricciones, lo que puede dar un punto fuera del conjunto factible. Además, confundir un mínimo local con el global lleva a conclusiones incorrectas en problemas no convexos.

Para pensar

¿Qué pasaría con un mínimo local si la función objetivo dejara de ser convexa?

Podría existir otro punto factible con un valor menor, así que el mínimo local ya no garantiza ser global.

Ejercicios 10

  1. ¿Cuál es la forma general de un problema de optimización con restricciones de desigualdad?
  2. ¿Qué nombre recibe la función que se minimiza en un problema de optimización?
  3. ¿Cómo se llama el conjunto de puntos que cumplen todas las restricciones?
  4. ¿Qué significa minimizar una función sobre un conjunto?
  5. ¿Qué tipo de problema es minimizar \(f(x)=x^2\) sin restricciones?
  6. Minimiza \(f(x,y)=x^2+y^2\) sujeto a \(x+y=4\). ¿Cuál es el valor mínimo?
  7. Calcula el mínimo de \(f(x)=x^2-4x+7\) sobre todos los reales.
  8. Maximiza \(f(x,y)=xy\) sujeto a \(x+y=10\). ¿Cuál es el valor máximo?
  9. Minimiza \(f(x,y)=(x-1)^2+(y-2)^2\) sujeto a \(x+y\le 1\). ¿Cuál es el punto óptimo?
  10. Minimiza \(f(x,y)=x^2+2y^2\) sujeto a \(x+y=3\). Indica el valor mínimo y verifica que es global.

Referencias

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.