Optimización Convexa
La optimización convexa es el estudio de la minimización de funciones convexas sobre conjuntos convexos, una clase de problemas para los cuales los óptimos locales son globales y existen algoritmos eficientes.
Definition
Un problema de optimización convexa minimiza un objetivo convexo sujeto a restricciones de desigualdad convexas y restricciones de igualdad afines; el conjunto factible es convexo, lo que asegura que cualquier mínimo local es también un mínimo global.
Scope
Este tema abarca conjuntos y funciones convexas, reconocimiento y modelado de problemas convexos, programas lineales, cuadráticos, de cono de segundo orden y semidefinidos, dualidad lagrangiana y las condiciones de Karush-Kuhn-Tucker para problemas convexos, y algoritmos de punto interior y de primer orden con sus garantías de complejidad.
Core questions
- ¿Cómo se puede reconocer o reformular un problema como convexo?
- ¿Por qué la convexidad garantiza que los óptimos locales son globales?
- ¿Qué revela la dualidad sobre un problema convexo y su solución?
- ¿Qué algoritmos resuelven problemas convexos de manera eficiente y con qué garantías?
Key theories
- Optimalidad global de problemas convexos
- Debido a que una función convexa sobre un conjunto convexo no tiene mínimos locales espurios, cualquier punto localmente óptimo es globalmente óptimo, lo que hace que los problemas convexos sean resolubles de manera fiable.
- Dualidad lagrangiana y condiciones KKT
- Todo problema convexo tiene un problema dual asociado que proporciona certificados de optimalidad, y bajo calificaciones de restricción, las condiciones de Karush-Kuhn-Tucker son necesarias y suficientes para la optimalidad.
- Métodos de punto interior
- Los métodos de punto interior siguen una trayectoria central a través del interior de la región factible, resolviendo problemas convexos, incluidos los programas semidefinidos, en tiempo polinomial demostrable.
Clinical relevance
La optimización convexa es omnipresente en el aprendizaje automático, el procesamiento de señales e imágenes, el control, las finanzas y el diseño de ingeniería, porque muchos problemas de estimación y decisión pueden plantearse como programas convexos y resolverse de manera fiable a escala.
History
El campo se basa en el análisis convexo sistematizado por Rockafellar alrededor de 1970. El método de punto interior de Karmarkar de 1984 y la subsiguiente teoría de Nesterov y Nemirovski demostraron que amplias clases de problemas convexos son resolubles en tiempo polinomial, lo que impulsó el enfoque moderno y basado en modelos de la optimización convexa.
Key figures
- R. Tyrrell Rockafellar
- Stephen Boyd
- Yurii Nesterov
- Narendra Karmarkar
Related topics
Seminal works
- boyd2004
- rockafellar1970
Frequently asked questions
- ¿Por qué preferir modelos convexos cuando sea posible?
- Los problemas convexos vienen con la garantía de que cualquier solución encontrada es globalmente óptima y con algoritmos maduros y eficientes. Los modelos no convexos pueden atrapar a los solucionadores en óptimos locales inferiores, por lo que una gran parte del trabajo aplicado se dedica a reformular problemas de manera convexa.
- ¿Es la programación lineal un tipo de optimización convexa?
- Sí. Un programa lineal minimiza un objetivo lineal sobre un poliedro, y tanto las funciones lineales como los poliedros son convexos, por lo que la programación lineal es un caso especial, particularmente bien comprendido, de optimización convexa.