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 $8.7$. I la solució trobada demostra que no passa de $9$.

$\text{gap} = 9 - 8.7 = 0.3000$

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

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

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

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

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

$\text{gap} = 35 - 33.4 = 1.6000$

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

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

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

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

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

$\text{gap} = 210 - 200.9 = 9.1000$

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

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

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

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

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

$\text{gap} = 6 - 5.5 = 0.5000$

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