Exercicis d'algorismes d'optimització

El càlcul.

$x_1 = \frac{1}{2}\left(3 + \frac{7}{3}\right) = \frac{1}{2}\left(3 + 2.333333\right) = 2.666667$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-7$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{7} \approx 2.645751$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.

La iteració.

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

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

$|1-16\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{8} \approx 0.1250$

Coincideix amb la teoria general. La constant de Lipschitz del gradient és $L = 16$, i la condició general era $\alpha < 2/L$, que dona exactament aquest valor.

El pas òptim. Amb $\alpha = \frac{1}{16}$ la raó val zero i s'arriba al mínim en un sol pas. No és casualitat: aquest és l'invers de la segona derivada, és a dir el pas de Newton, que per a una quadràtica encerta sempre a la primera.

Les dues cotes. Tota solució entera també és factible per a la relaxació, de manera que l'òptim enter no pot baixar de $61.2$. I la solució trobada demostra que no passa de $65$.

$\text{gap} = 65 - 61.2 = 3.8000$

Què demostra i què no. Encara no està demostrat que $65$ sigui òptim. Per tancar-ho caldria o bé trobar una solució millor, o bé pujar la cota inferior ramificant i comprovant que cap branca no hi arriba.

El que passa a la pràctica. Molt sovint la solució òptima es troba 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 petit és acceptable, pots aturar-te abans; però llavors has de dir que és una bona solució, no que és l'òptima.

El càlcul.

$x_1 = \frac{1}{2}\left(3 + \frac{10}{3}\right) = \frac{1}{2}\left(3 + 3.333333\right) = 3.166667$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-10$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{10} \approx 3.162278$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.

La iteració.

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

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

$|1-40\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{20} \approx 0.0500$

Coincideix amb la teoria general. La constant de Lipschitz del gradient és $L = 40$, i la condició general era $\alpha < 2/L$, que dona exactament aquest valor.

El pas òptim. Amb $\alpha = \frac{1}{40}$ la raó val zero i s'arriba al mínim en un sol pas. No és casualitat: aquest és l'invers de la segona derivada, és a dir el pas de Newton, que per a una quadràtica encerta sempre a la primera.

Les dues cotes. Tota solució entera també és factible per a la relaxació, de manera que l'òptim enter no pot baixar de $19.8$. I la solució trobada demostra que no passa de $20$.

$\text{gap} = 20 - 19.8 = 0.2000$

Què demostra i què no. Encara no està demostrat que $20$ sigui òptim. Per tancar-ho caldria o bé trobar una solució millor, o bé pujar la cota inferior ramificant i comprovant que cap branca no hi arriba.

El que passa a la pràctica. Molt sovint la solució òptima es troba 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 petit és acceptable, pots aturar-te abans; però llavors has de dir que és una bona solució, no que és l'òptima.

El càlcul.

$x_1 = \frac{1}{2}\left(4 + \frac{17}{4}\right) = \frac{1}{2}\left(4 + 4.250000\right) = 4.125000$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-17$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{17} \approx 4.123106$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.

La iteració.

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

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

$|1-50\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{25} \approx 0.0400$

Coincideix amb la teoria general. La constant de Lipschitz del gradient és $L = 50$, i la condició general era $\alpha < 2/L$, que dona exactament aquest valor.

El pas òptim. Amb $\alpha = \frac{1}{50}$ la raó val zero i s'arriba al mínim en un sol pas. No és casualitat: aquest és l'invers de la segona derivada, és a dir el pas de Newton, que per a una quadràtica encerta sempre a la primera.

Les dues cotes. Tota solució entera també és factible per a la relaxació, de manera que l'òptim enter no pot baixar de $77.7$. I la solució trobada demostra que no passa de $80$.

$\text{gap} = 80 - 77.7 = 2.3000$

Què demostra i què no. Encara no està demostrat que $80$ sigui òptim. Per tancar-ho caldria o bé trobar una solució millor, o bé pujar la cota inferior ramificant i comprovant que cap branca no hi arriba.

El que passa a la pràctica. Molt sovint la solució òptima es troba 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 petit és acceptable, pots aturar-te abans; però llavors has de dir que és una bona solució, no que és l'òptima.

El càlcul.

$x_1 = \frac{1}{2}\left(1.5 + \frac{2}{1.5}\right) = \frac{1}{2}\left(1.5 + 1.333333\right) = 1.416667$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-2$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{2} \approx 1.414214$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.