Exercicis d'algorismes d'optimització

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

$\text{gap} = 17 - 15.9 = 1.1000$

Què demostra i què no. Encara no està demostrat que $17$ 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{8}{3}\right) = \frac{1}{2}\left(3 + 2.666667\right) = 2.833333$

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

Quantes xifres guanyes. El valor exacte és $\sqrt{8} \approx 2.828427$, 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 24x_k = (1-24\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-24\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{12} \approx 0.0833$

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

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

$\text{gap} = 44 - 42.1 = 1.9000$

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

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

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

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

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

$\text{gap} = 92 - 88.8 = 3.2000$

Què demostra i què no. Encara no està demostrat que $92$ 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(6 + \frac{37}{6}\right) = \frac{1}{2}\left(6 + 6.166667\right) = 6.083333$

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

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

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

El pas òptim. Amb $\alpha = 2$ 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 $7.4$. I la solució trobada demostra que no passa de $8$.

$\text{gap} = 8 - 7.4 = 0.6000$

Què demostra i què no. Encara no està demostrat que $8$ 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.