Exercicis d'algorismes d'optimització

El càlcul.

$x_1 = \frac{1}{2}\left(4 + \frac{15}{4}\right) = \frac{1}{2}\left(4 + 3.750000\right) = 3.875000$

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

Quantes xifres guanyes. El valor exacte és $\sqrt{15} \approx 3.872983$, 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 3x_k = (1-3\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-3\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{2}{3} \approx 0.6667$

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

El pas òptim. Amb $\alpha = \frac{1}{3}$ 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 $29.5$. I la solució trobada demostra que no passa de $31$.

$\text{gap} = 31 - 29.5 = 1.5000$

Què demostra i què no. Encara no està demostrat que $31$ 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{20}{4}\right) = \frac{1}{2}\left(4 + 5.000000\right) = 4.500000$

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

Quantes xifres guanyes. El valor exacte és $\sqrt{20} \approx 4.472136$, 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 18x_k = (1-18\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-18\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{9} \approx 0.1111$

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

El pas òptim. Amb $\alpha = \frac{1}{18}$ 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 $55.6$. I la solució trobada demostra que no passa de $58$.

$\text{gap} = 58 - 55.6 = 2.4000$

Què demostra i què no. Encara no està demostrat que $58$ 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(5 + \frac{23}{5}\right) = \frac{1}{2}\left(5 + 4.600000\right) = 4.800000$

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

Quantes xifres guanyes. El valor exacte és $\sqrt{23} \approx 4.795832$, 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 22x_k = (1-22\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-22\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{11} \approx 0.0909$

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

El pas òptim. Amb $\alpha = \frac{1}{22}$ 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 $110.3$. I la solució trobada demostra que no passa de $115$.

$\text{gap} = 115 - 110.3 = 4.7000$

Què demostra i què no. Encara no està demostrat que $115$ 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(5 + \frac{29}{5}\right) = \frac{1}{2}\left(5 + 5.800000\right) = 5.400000$

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

Quantes xifres guanyes. El valor exacte és $\sqrt{29} \approx 5.385165$, 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.