Anar al contingut

Optimisació convexa

De L'Enciclopèdia, la wikipedia en valencià
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, f:𝒟⊆ℝn→ℝ;
  • El conjunt factible, que és un subconjunt convexo C⊆ℝn.

L'objectiu del problema és trobar algun punt 𝐱∗∈C a on s'alcance el menor valor de la funció objectiu en el conjunt C:

inf⁡{f(𝐱):𝐱∈C}.

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 𝐱∗∈C a on s'alcance el valor ínfim de f, 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 f és no acotada inferiorment en C, o si no s'alcança l'ínfim, llavors es diu que el problema d'optimisació és no acotat.
  • Si C és el conjunt buit, llavors es diu que el problema és no factible: no existix 𝐱∗∈C.

Forma estàndar

Un problema d'optimisació convexa està en forma estàndar quan s'escriu com:

minimizar𝐱f(𝐱)sujeto agi(𝐱)≤0,i=1,…,mhi(𝐱)=0,i=1,…,p,

a on: [6] <span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: chpt.4 

  • 𝐱∈ℝn és el vector de variables d'optimisació;
  • La funció objectiu f:𝒟⊆ℝn→ℝ és una funció convexa (en particular el domini 𝒟 s'assumix convexo);
  • Les funcions de restriccions de desigualtat gi:ℝn→ℝ, i=1,…,m, són funcions convexas;
  • Les funcions de restriccions d'igualtat hi:ℝn→ℝ, i=1,…,p, són funcions afins. És dir, funcions de la forma: hi(𝐱)=𝐚𝐢⋅𝐱−bi, a on 𝐚𝐢 és un vector i bi és un escalar.


El conjunt factible C 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 f pot reformular-se de forma equivalent com el problema de minimisar la funció convexa −f. 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 

minimizar𝐱,ttsujeto af(𝐱)−t≤0gi(𝐱)≤0,i=1,…,mhi(𝐱)=0,i=1,…,p,

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 

minimizar𝐱cTxsujeto ax∈(b+L)∩K

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é:

minimizar𝐳f(𝐅𝐳+𝐱𝟎)sujeto agi(𝐅𝐳+𝐱𝟎)≤0,i=1,…,m

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]

Jerarquia de problemes d'optimisació convexa. (LP: programació llineal, QP: programació quadràtica, SOCP: programa de con de segon orde, SDP: programació semidefinida, CP: optimisació cònica).
  • 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:

Vore també

Notes

  1. ↑ Nesterov y Nemirovskii, 1994
  2. ↑ Murty, Katta; Kabadi, Santosh(1987).«Some NP-complete problems in quadratic and nonlinear programming».Mathematical Programming.39(2): 117–129.doi:10.1007/BF02592948.
  3. ↑ 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.
  4. ↑ Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1996). Convex analysis and minimization algorithms: Fundamentals, Springer, p. 291. ISBN 9783540568506.
  5. ↑ Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications, pp. 335–336. ISBN 9780898714913.
  6. ↑ 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.
  7. ↑ «Optimization Problem Types - Convex Optimization» (2011-01-09).
  8. ↑ 8,0 8,1 Arkadi Nemirovsky (2004). Interior point polynomial-clave methods in convex programming.
  9. ↑ 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