Optimització convexa i condicions KKT: de local a global

La convexitat és la propietat que converteix l'optimització en un problema tractable. Sense ella, trobar un punt crític no et diu gairebé res sobre el global; amb ella, un mínim local ja és global i les condicions de primer ordre es converteixen en un certificat complet. Per això, en optimització aplicada, la primera pregunta sempre és si el problema és convex.

Conjunts i funcions convexes

Un conjunt és convex si conté el segment que uneix qualsevol parell dels seus punts. Una funció definida sobre un conjunt convex és convexa si el seu valor en un punt intermedi no supera la corresponent combinació dels valors extrems:

$$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y).$$

Geomètricament: la corda queda per sobre de la gràfica.

Per a funcions diferenciables en un obert convex, hi ha dues caracteritzacions molt més pràctiques. La de primer ordre diu que la funció queda sempre per sobre de qualsevol dels seus plans tangents:

$$f(y) \geq f(x) + \nabla f(x)^{T}(y-x).$$

I la de segon ordre diu que la hessiana és semidefinida positiva a tot el domini.

Un avís que s'oblida sovint: la convexitat estricta garanteix unicitat si el mínim existeix, però no garanteix existència. L'exponencial a tota la recta és estrictament convexa i no assoleix mai el seu ínfim, que és zero.

Lagrangià i funció dual

Per a un problema de minimització amb desigualtats i igualtats afins, el lagrangià és

$$\mathcal{L}(x,\mu,\lambda) = f(x) + \sum_i \mu_i g_i(x) + \lambda^{T}(Ax-b), \qquad \mu\geq 0,$$

i la funció dual és el seu ínfim en $x$. Per a qualsevol punt factible del primal, la funció dual queda per sota del valor objectiu: el dual dona cotes inferiors.

Dos fets notables. Primer, maximitzar la funció dual és sempre un problema còncau, encara que el primal no sigui convex, perquè un ínfim de funcions afins en els multiplicadors és còncau. Segon, la igualtat de valors òptims (dualitat forta) pot fallar si el primal no és convex: la diferència s'anomena salt de dualitat.

Les condicions KKT

Per a funcions diferenciables, les condicions de Karush, Kuhn i Tucker són quatre blocs:

• Factibilitat primal: el punt compleix totes les restriccions.
• Factibilitat dual: els multiplicadors de les desigualtats són no negatius.
• Complementarietat: cada multiplicador multiplicat per la seva restricció dona zero, és a dir, si la restricció no és activa el seu multiplicador és zero.
• Estacionarietat: el gradient del lagrangià respecte de les variables s'anul·la.

Convexitat forta

Una funció és fortament convexa amb paràmetre $m$ si queda per sobre dels seus plans tangents per un marge quadràtic, és a dir si la desigualtat de primer ordre val amb un terme addicional proporcional a la distància al quadrat. En termes de segon ordre, equival que la hessiana menys $m$ vegades la identitat sigui semidefinida positiva.

L'interès és quantitatiu: si hi ha un mínim interior, aleshores

$$f(x)-f(x_*) \geq \frac{m}{2}\lVert x - x_*\rVert^{2},$$

cosa que permet convertir una cota sobre el valor objectiu en una cota sobre la distància a l'òptim. És també la hipòtesi que dona taxes de convergència geomètriques als mètodes de descens.

Exercici resolt: mínim amb una desigualtat

Minimitza $x^{2}+y^{2}$ amb la condició $x+y\geq 2$.

Plantejament. Escrivim la restricció en forma estàndard: $g(x,y) = 2-x-y\leq 0$. L'objectiu és convex i la restricció també, de manera que les KKT seran suficients.

Estacionarietat. $2x - \mu = 0$ i $2y - \mu = 0$, d'on $x = y = \mu/2$.

Cas inactiu ($\mu = 0$): dona l'origen, que no compleix la restricció. Descartat.

Cas actiu: $x+y = 2$ amb $x = y$, o sigui $x = y = 1$ i $\mu = 2 \geq 0$. Totes les condicions es compleixen.

Conclusió. L'òptim és $(1,1)$ amb valor $2$, i la convexitat en certifica la globalitat. Geomètricament és el punt de la recta més proper a l'origen, cosa que confirma el resultat sense cap càlcul.

Exercici resolt: decidir si un problema és convex

És convexa la funció $f(x,y) = x^{2} + 4y^{2} - 2xy$?

Hessiana. Les segones derivades donen una matriu constant amb files $(2,-2)$ i $(-2,8)$.

Comprovació amb Sylvester. El primer menor líder és $2 > 0$. El determinant és $2\cdot 8 - (-2)^{2} = 12 > 0$. Tots dos positius: la hessiana és definida positiva.

Conclusió. Com que la hessiana és constant i definida positiva a tot el pla, la funció és estrictament convexa a tot arreu. Per tant qualsevol mínim local seria global i únic.

I existeix? Sí: una forma quadràtica definida positiva és coerciva. L'únic punt crític és l'origen, i per tant és el mínim global, amb valor zero.

El contrast. Si el terme creuat hagués estat $-6xy$, el determinant seria $16 - 36 < 0$ i la forma seria indefinida: l'origen seria una sella i no hi hauria cap mínim. Un sol coeficient decideix si el problema és tractable o no.