Resumen de Teoremes de No Free Lunch en el continu i el model del Pont Brownià en optimització
Ricard Josep Caballero Monteso
Aquesta tesi consta principalment de dues parts. A la primera part, es generalitza a variable contínua un famós teorema en l'àmbit tèoric de l'optimització: El No-Free-Lunch Theorem, el qual diu que tots els algorismes són igual de bons quan es fa la mitjana de la seva eficiència sobre totes les possibles funcions a optimitzar. Aquesta generalització utilitza de manera molt natural la teoria de processos estocàstics, i arriba a la conclusió que no hi ha teoremes de No-Free-Lunch en el continu, excepte en determinats casos extrems de poca importància pràctica. A la segona part, s'ha considerat el Pont Brownià com un model probabilístic per a problemes d'optimització tipus “caixa negra”, en què no es té cap forma analítica de la funció, sinó que aquesta només pot ser avaluada en un nombre determinat de punts, i a més a més, considerant que cadascuna d'aquestes avaluacions és molt costosa de fer, i per tant només se'n faran unes quantes. El model probabilístic considera que la funció a optimitzar és una trajectòria d'un procés amb una determinada llei. Des del punt de vista de la complexitat computacional, això correspon a estudiar el “average performance” d'algorismes, en front de l'habitual “worst-case performance”. Però això es fa sempre des del punt de vista asimptòtic, quan el nombre d'avaluacions tendeix a infinit, i un dels objectius d'aquesta tesi se centra en la millora de l'estimació del valor òptim quan només es pot avaluar la funció en pocs punts. En aquest sentit, i en un estudi que mancava a la literatura, es comparen i analitzen diverses heurístiques adaptatives i no-adaptatives, arribant a la conclusió de quina és més eficient. D'altra banda, el treball amb el Pont Brownià, ha donat lloc a dues fórmules no explicitades anteriorment, la densitat de l'argument del mínim del Pont Brownià i la densitat conjunta del Pont Brownià i del seu mínim. A més, en aquesta tesi es realitzen molts experiments de simulació per calcular quantitats que són molt difícils, costoses o impossibles d'obtenir analíticament. Seguint una filosofia de practicitat, s'han programat rutines, com per exemple l'histograma de l'argument del mínim d'un Pont Brownià condicionat a n punts, que obtenen una estimació probabilística raonable de l'error comès.
