Exercicis d'algorismes d'optimització

La iteració.

$x_{k+1} = x_k - \alpha\cdot 100x_k = (1-100\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-100\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{50} \approx 0.0200$

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

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

$\text{gap} = 152 - 150.1 = 1.9000$

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

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

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

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

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

$\text{gap} = 26 - 24.6 = 1.4000$

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

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

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

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

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

$\text{gap} = 4 - 3.2 = 0.8000$

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

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

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

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

El pas òptim. Amb $\alpha = \frac{1}{14}$ 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.