Algorismes d'optimització: descens del gradient, Newton i variables enteres

Un cop tens el problema ben plantejat, cal resoldre'l. Aquesta pàgina recull els algorismes bàsics i, sobretot, els criteris per triar el pas, per saber quan aturar-se i per no confondre «he trobat una solució» amb «he demostrat que és òptima».

Formular abans de resoldre

Un model especifica variables, domini, objectiu i restriccions. Les variables poden ser contínues, enteres o binàries, i sovint convé afegir-ne d'auxiliars per expressar coses que no són lineals de manera natural.

L'exemple canònic és el valor absolut. Minimitzar $|ax-b|$ no és lineal, però es converteix en lineal introduint una variable $t$ i minimitzant-la amb les dues restriccions

$$ax - b \leq t, \qquad -(ax-b) \leq t.$$

A l'òptim, $t$ pren exactament el valor absolut, perquè la minimització l'empeny cap avall fins que una de les dues restriccions es satura. El mateix truc serveix per a màxims i per a normes.

Descens del gradient

La iteració és moure's en la direcció oposada al gradient:

$$x_{k+1} = x_k - \alpha_k\,\nabla f(x_k).$$

La pregunta important és quant avançar. Si el gradient és Lipschitz amb constant $L$, es compleix la desigualtat de descens

$$f(x+s) \leq f(x) + \nabla f(x)^{T}s + \frac{L}{2}\lVert s\rVert^{2},$$

i substituint-hi el pas del gradient surt que el valor disminueix sempre que el pas estigui entre $0$ i $2/L$. Això explica per què hi ha un límit superior al pas: passat aquest llindar, el terme quadràtic domina i l'algorisme divergeix.

En problemes convexos suaus, passos adequats donen convergència del valor objectiu; amb convexitat forta, la convergència és geomètrica.

A la pràctica no se sol conèixer $L$, i es fa servir una cerca enrere d'Armijo: es prova un pas, i mentre no es compleixi

$$f(x+\alpha d) \leq f(x) + c\,\alpha\,\nabla f(x)^{T}d$$

amb una constant petita, es redueix el pas. La condició demana una fracció de la millora que prediu la linealització, i evita haver de fixar un pas sense mirar l'escala local del problema.

Newton

Newton fa servir la curvatura: resol el sistema

$$H_f(x_k)\,p_k = -\nabla f(x_k)$$

i actualitza amb aquesta direcció, normalment amb una cerca de pas. A prop d'un mínim amb hessiana definida positiva i regularitat suficient, la convergència és quadràtica: el nombre de xifres correctes es duplica a cada iteració.

Lluny de l'òptim, però, la hessiana pot ser indefinida i la direcció resultant pot no ser ni de descens. Per això a la pràctica s'usen variants amb amortiment, regularització de la hessiana o regions de confiança, que limiten la mida del pas al radi on el model quadràtic és fiable.

Per a un conjunt convex tancat, el gradient projectat fa el pas habitual i després projecta el resultat sobre el conjunt. La condició d'optimalitat deixa de ser «gradient nul» i passa a ser que el gradient formi angle no agut amb qualsevol direcció admissible:

$$\nabla f(x_*)^{T}(y-x_*)\geq 0\quad\text{per a tot } y \text{ factible.}$$

En un òptim de frontera, el gradient no s'anul·la, i esperar que ho faci és un error conceptual freqüent.

Variables enteres

Amb integritat, la relaxació contínua (deixar que les variables prenguin valors reals) dona una cota en el sentit favorable: cota inferior per a un problema de minimització. I qualsevol solució entera factible que trobis dona una cota en l'altre sentit.

La ramificació i acotació explota aquesta parella: divideix el domini (per exemple imposant que una variable sigui com a molt un cert enter, o com a mínim el següent), resol la relaxació de cada branca, i poda les branques la cota de les quals ja no pot millorar la millor solució coneguda.

Criteris d'aturada

Aturar-se quan «els valors gairebé no canvien» és insuficient: un canvi petit pot indicar convergència, però també estancament per mal condicionament o per un pas massa curt. Cal comprovar:

• Factibilitat de les restriccions, amb tolerància.
• Estacionarietat o residu de les condicions KKT.
• Gap primal i dual, si està disponible.

I les toleràncies han de combinar escales absolutes i relatives, perquè un residu de $10^{-6}$ vol dir coses molt diferents segons la magnitud de les dades. El resultat final hauria de dir de quina de les tres coses es tracta: òptim certificat, punt estacionari, o simplement la millor solució trobada.

Exercici resolt: rang de passos que convergeix

Per a $f(x) = 5x^{2}$, quins passos constants fan convergir el descens del gradient des de qualsevol punt inicial?

La iteració. El gradient és $10x$, de manera que

$$x_{k+1} = x_k - \alpha\cdot 10 x_k = (1-10\alpha)\,x_k.$$

La condició. És una progressió geomètrica de raó $1-10\alpha$, que tendeix a zero si i només si el mòdul de la raó és menor que $1$:

$$|1-10\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac15.$$

Comprovació amb la teoria. La constant de Lipschitz del gradient és $L = 10$, i la condició general era $0 < \alpha < 2/L = 1/5$. Coincideix exactament.

El cas òptim. Amb $\alpha = 1/10$ la raó val zero i s'arriba al mínim en un sol pas. Això no és casualitat: aquest pas és precisament l'invers de la segona derivada, és a dir el pas de Newton. Per a una funció quadràtica, Newton hi arriba sempre en una iteració.

Exercici resolt: cota de la relaxació

Un problema de minimització enter té relaxació contínua amb valor òptim $47{,}3$, i s'ha trobat una solució entera factible de valor $49$. Què es pot afirmar?

La cota inferior. Com que tota solució entera també és factible per a la relaxació, l'òptim enter no pot ser menor que $47{,}3$. I com que és enter, ha de ser com a mínim $48$.

La cota superior. La solució trobada dona $49$.

Conclusió. L'òptim enter és $48$ o $49$, amb un gap d'una unitat. Encara no està demostrat que $49$ sigui òptim: caldria o bé trobar una solució de valor $48$, o bé millorar la cota inferior per sobre de $48$ (per exemple ramificant i comprovant que cap branca no baixa d'aquest valor).

Per què importa. Moltes vegades, la solució òptima es troba molt aviat i la major part del temps de càlcul es dedica a demostrar que ho és. Si per a la teva aplicació un gap del $2\%$ és acceptable, aturar-se abans estalvia moltíssim temps: però llavors has de dir que és una bona solució, no que és l'òptima.