Optimització convexa

L'optimització convexa és un subcamp de l'optimització matemàtica que estudia el problema de minimitzar les funcions convexes sobre conjunts convexos (o, de manera equivalent, maximitzar les funcions còncaves sobre conjunts convexos). Moltes classes de problemes d'optimització convex admeten algorismes de temps polinomial, mentre que l'optimització matemàtica és en general NP-difícil.^[1]

L'optimització convexa té aplicacions en una àmplia gamma de disciplines, com ara sistemes de control automàtic, estimació i processament de senyals, comunicacions i xarxes, disseny de circuits electrònics, anàlisi i modelització de dades, finances, estadístiques (disseny experimental òptim), i optimització estructural, on el concepte d'aproximació ha demostrat ser eficient. Amb els recents avenços en la informàtica i els algorismes d'optimització, la programació convexa és gairebé tan senzilla com la programació lineal.

Definició

Un problema d'optimització convex és un problema d'optimització en què la funció objectiu és una funció convexa i el conjunt factible és un conjunt convex. Una funció ${\displaystyle f}$ mapatge d'algun subconjunt de ${\displaystyle \mathbb {R} ^{n}}$ a ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$ és convex si el seu domini és convex i per a tots ${\displaystyle \theta \in [0,1]}$ i tot ${\displaystyle x,y}$ en el seu domini, es compleix la següent condició: ${\displaystyle f(\theta x+(1-\theta )y)\leq \theta f(x)+(1-\theta )f(y)}$. Un conjunt S és convex si per a tots els membres ${\displaystyle x,y\in S}$ i tot ${\displaystyle \theta \in [0,1]}$, això ho tenim ${\displaystyle \theta x+(1-\theta )y\in S}$.

Concretament, un problema d'optimització convex és el problema de trobar-ne ${\displaystyle \mathbf {x^{\ast }} \in C}$ aconseguint

${\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}$

on la funció objectiu ${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$ és convex, igual que el conjunt factible ${\displaystyle C}$.^[2][3] Si aquest punt existeix, es coneix com a punt o solució òptima; el conjunt de tots els punts òptims s'anomena conjunt òptim. Si ${\displaystyle f}$ és il·limitat per sota sobre ${\displaystyle C}$ o no s'aconsegueix l'ínfim, llavors es diu que el problema d'optimització és il·limitat. En cas contrari, si ${\displaystyle C}$ és el conjunt buit, llavors es diu que el problema és inviable.

Forma estàndard

Un problema d'optimització convex està en forma estàndard si s'escriu com ${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}$

on:

• ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ és la variable d'optimització;
• La funció objectiu ${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$ és una funció convexa;
• Funcions de restricció de desigualtat ${\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$, ${\displaystyle i=1,\ldots ,m}$, són funcions convexes;
• Les funcions de restricció d'igualtat ${\displaystyle h_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$, ${\displaystyle i=1,\ldots ,p}$, són transformacions afins, és a dir, de la forma: ${\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}}$, on ${\displaystyle \mathbf {a_{i}} }$ és un vector i ${\displaystyle b_{i}}$ és un escalar.

Aplicacions

Una jerarquia de problemes d'optimització convex. (LP: programa lineal, QP: programa quadràtic, SOCP programa de con de segon ordre, SDP: programa semidefinit, CP: programa de con. )

Les següents classes de problemes són tots problemes d'optimització convexes, o es poden reduir a problemes d'optimització convexes mitjançant transformacions simples: ^[4]

• Mínims quadrats.
• Programació lineal.
• Minimització quadràtica convexa amb restriccions lineals.
• Minimització quadràtica amb restriccions quadràtiques convexes.
• Optimització cònica.
• Programació geomètrica.
• Programació de con de segon ordre.
• Programació semidefinida.
• Maximització de l'entropia amb les restriccions adequades.

L'optimització convexa té aplicacions pràctiques per al següent:

• Optimització de la cartera.^[5]
• Anàlisi de risc del pitjor cas.^[5]
• Publicitat òptima.^[5]
• Variacions de la regressió estadística (incloent la regularització i la regressió quantil).^[5]
• Adaptació del model ^[5] (en particular classificació multiclasse ^[6]).
• Optimització de la generació elèctrica.^[6]
• Optimització combinatòria.^[6]
• Modelització no probabilística de la incertesa.
• Localització mitjançant senyals sense fil.

Referències

1. Murty, Katta; Kabadi, Santosh Mathematical Programming, 39, 2, 1987, pàg. 117–129. DOI: 10.1007/BF02592948.
2. Hiriart-Urruty, Jean-Baptiste. Convex analysis and minimization algorithms: Fundamentals (en anglès), 1996, p. 291. ISBN 9783540568506. 
3. Ben-Tal, Aharon. Lectures on modern convex optimization: analysis, algorithms, and engineering applications (en anglès), 2001, p. 335–336. ISBN 9780898714913. 
4. Agrawal, Akshay; Verschueren, Robin; Diamond, Steven; Boyd, Stephen Control and Decision, 5, 1, 2018, pàg. 42–60. arXiv: 1709.04494. DOI: 10.1080/23307706.2017.1397554.
5. Boyd, Stephen. «Convex Optimization Applications» (en anglès). Arxivat de l'original el 2015-10-01. [Consulta: 12 abril 2021].
6. Malick, Jérôme. «Convex optimization: applications, formulations, relaxations» (en anglès), 28-09-2011. Arxivat de l'original el 2021-04-12. [Consulta: 12 abril 2021].