Optimisació convexa

L'optimisació convexa és un subcampo de l'optimisació matemàtica que estudia el problema de minimisar funcions convexas sobre conjunts convexos (o, equivalentement, maximizar funcions cóncaves sobre conjunts convexos). Moltes classes de problemes d'optimisació convexa admeten algoritmes de temps polinomial,[1] mentres que l'optimisació matemàtica és, en general, NP-difícil.[2][3]
Definició
Un problema d'optimisació convexa es definix per mig de dos ingredients: [4][5]
- La funció objectiu, que és una funció convexa de n variables que pren valors reals, ;
- El conjunt factible, que és un subconjunt convexo .
L'objectiu del problema és trobar algun punt a on s'alcance el menor valor de la funció objectiu en el conjunt :
- .
En general, existixen tres situacions possibles: [6] <span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: chpt.4
- Si existix un punt a on s'alcance el valor ínfim de , a este punt se li denomina punt òptim o solució, i el problema es denomina resoluble (té solució). El conjunt de tots els punts òptims es denomina conjunt òptim (conjunt de solucions).
- Si és no acotada inferiorment en , o si no s'alcança l'ínfim, llavors es diu que el problema d'optimisació és no acotat.
- Si és el conjunt buit, llavors es diu que el problema és no factible: no existix .
Forma estàndar
Un problema d'optimisació convexa està en forma estàndar quan s'escriu com:
a on: [6] <span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: chpt.4
- és el vector de variables d'optimisació;
- La funció objectiu és una funció convexa (en particular el domini s'assumix convexo);
- Les funcions de restriccions de desigualtat , , són funcions convexas;
- Les funcions de restriccions d'igualtat , , són funcions afins. És dir, funcions de la forma: , a on és un vector i és un escalar.
El conjunt factible del problema d'optimisació consta de tots els punts que satisfan les restriccions de desigualtat i igualtat. Este conjunt és convex perque: és convexo, els conjunts de nivell de funcions convexas són convexos, els conjunts afins són convexos i l'intersecció de conjunts convexos és convexa.[6] <span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: chpt.2
Molts problemes d'optimisació poden formular-se en esta forma estàndar. Per eixemple, el problema de maximizar una funció cóncava pot reformular-se de forma equivalent com el problema de minimisar la funció convexa . Per açò, el problema de maximizar una funció cóncava sobre un conjunt convex es denomina comunament problema d'optimisació convexa.[7]
Forma epigràfica (forma estàndar en objectiu llineal)
En la forma estàndar és possible assumir, sense pèrdua de generalitat, que la funció objectiu f és una funció llineal. Açò es deu a que qualsevol problema convex en la seua forma estàndar pot transformar-se de forma equivalent en un problema convex en funció objectiu llineal, agregant una variable t i una restricció, com seguix: [8] <span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: 1.4
Forma cònica
Tot programa convex pot presentar-se en forma cònica, lo que significa minimisar una funció objectiu llineal sobre l'intersecció d'un pla afí i un con convexo: [8] <span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: 5.1
a on K és un con convex tancat i puntagut, L és un subespacio llineal de Rn, i b és un vector en Rn. Un problema llineal en forma estàndar és el cas especial en el que K és el ortante no negatiu de Rn.
Eliminació de restriccions d'igualtat llineal
És possible convertir un problema convex en forma estàndar a un problema convex sense restriccions d'igualtat.[6] Denotem les restriccions d'igualtat hi ( x )=0 com Ax = b, a on A és una matriu de n columnes. Si Ax = b és no factible, llavors, per supost, el problema original és no factible. De lo contrari, té alguna solució x0, i el conjunt de totes les solucions es pot escriure com: Fz + x0, a on z està en Rk, k = n -ranc(A), i F és una matriu n × k. Substituint x = Fz + x 0 en el problema original s'obté:
a on les variables són z. Note's que hi ha ranc( A ) menys variables. Açò significa que, en principi, es pot llimitar l'atenció a problemes d'optimisació convexa sense restriccions d'igualtat. No obstant, en la pràctica, sol preferir-se mantindre les restriccions d'igualtat, ya que poden fer que alguns algoritmes siguen més eficients i també faciliten la comprensió i l'anàlisis del problema.
Casos especials
Les següents classes de problemes són tots problemes d'optimisació convexa, o poden reduir-se a problemes d'optimisació convexa per mig de transformacions simples: [6] <span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: chpt.4 [9]

- Els problemes de programació llineal són els problemes convexos més simples. En la programació llineal, tant la funció objectiu com les funcions de restricció són llineals.
- La programació quadràtica és la següent més senzilla. En la programació quadràtica, totes les restriccions són llineals, pero la funció objectiu pot ser una funció quadràtica convexa.
- La programació de cons de segon orde és més general.
- La programació semidefinida és més general.
- L'optimisació cònica és encara més general; vore la figura de la dreta.
Atres casos especials inclouen:
- Mínims quadrats.
- Minimisació quadràtica en restriccions quadràtiques convexas.
- Programació geomètrica.
- Maximisació de la entropía en les restriccions adequades.
Vore també
Notes
- ↑ Nesterov y Nemirovskii, 1994
- ↑ Murty, Katta; Kabadi, Santosh(1987).«Some NP-complete problems in quadratic and nonlinear programming».Mathematical Programming.39(2): 117–129.doi:10.1007/BF02592948.
- ↑ Pardalos, Panos M.; Vavasis, Stephen A.(1991).«Quadratic programming with one negative eigenvalue is NP-hard».Journal of Global Optimization.1: 15–22.doi:10.1007/BF00120662.
- ↑ Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1996). Convex analysis and minimization algorithms: Fundamentals, Springer, p. 291. ISBN 9783540568506.
- ↑ Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications, pp. 335–336. ISBN 9780898714913.
- ↑ 6,0 6,1 6,2 6,3 6,4 Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization, Cambridge University Press. ISBN 978-0-521-83378-3. Consultat el 2021-04-12.
- ↑ «Optimization Problem Types - Convex Optimization» (2011-01-09).
- ↑ 8,0 8,1 Arkadi Nemirovsky (2004). Interior point polynomial-clave methods in convex programming.
- ↑ Agrawal, Akshay; Verschueren, Robin; Diamond, Steven; Boyd, Stephen(2018).«A rewriting system for convex optimization problems».Control and Decision.5(1): 42–60.doi:10.1080/23307706.2017.1397554.
Referències
- Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Assumixquen (2003). Convex Analysis and Optimization, Belmont, MA.: Athena Scientific. ISBN 978-1-886529-45-8.
- Bertsekas, Dimitri P. (2009). Convex Optimization Theory, Belmont, MA.: Athena Scientific. ISBN 978-1-886529-31-1.
- Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms, Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
- Borwein, Jonathan; Lewis, Adrian (2000). Convex Analysis and Nonlinear Optimization: Theory and Examples, Second Edition, Springer. Consultat el 12 Apr 2021.
- Christensen, Peter W.; Anders Klarbring (2008). An introduction to structural optimization (vol. 153), Springer Science & Business Media. ISBN 9781402086663.
- Hiriart-Urruty, Jean-Baptiste i Lemaréchal, Claude . (2004). Fonaments de l'anàlisis convexo. Berlín: Springer.
- Nesterov, Yurii. (2004). Lliçons introductòries sobre optimisació convexa, Kluwer Academic Publishers
- Este artícul conté una traducció derivada de «Optimisació convexa» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.