Teoremes de No Free Lunch en el continu i el model del Pont Brownià en optimització

Autor/a

Caballero Monteso, Ricard Josep

Director/a

Alabert Romero, Aureli

Data de defensa

2016-02-03

ISBN

9788449060069

Pàgines

138 p.



Departament/Institut

Universitat Autònoma de Barcelona. Departament de Matemàtiques

Resum

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.


This Ph.D. thesis consists mainly of two parts. In the first part, a famous theorem in the field of theoretical optimisation is generalised to continuous variable: The No-Free-Lunch Theorem, which states that all algorithms are equally good when one averages its efficiency over all possible functions to optimise. This generalisation uses in a very natural way the theory of stochastic processes, and concludes that there are no No-Free-Lunch theorems in the continuum, except for certain extreme cases of little practical significance. In the second part, the Brownian Bridge has been considered as a probabilistic model for optimisation problems of the "black box" type, in which we do not have an analytical form of the function, but that the latter can only be evaluated in a certain number of points. Moreover, we consider that each of these evaluations are very expensive, so that only a few of them will be made. The probabilistic model considers that the function to optimise is a path of a stochastic process with a given probability law. From the point of view of computational complexity, this study corresponds to the "average performance" of algorithms, versus the usual "worst-case performance". But this has always been done before from the asymptotic standpoint, when the number of evaluations tends to infinity, and one of the goals of this thesis focuses on improving the estimation of the optimal value when the function can only be evaluated in a few points. In this regard, in a study that was missing in the literature, we compare and analyze several heuristics, adaptive and non-adaptive, concluding which one is most efficient. Moreover, in working with Brownian bridge, we found two formulae not given explicitly before, namely the density of the argument of the Brownian bridge (in the general setting) and the joint density of a bridge and its minimum. In addition, in this thesis many simulation experiments have been performed to calculate quantiites that are difficult, expensive or impossible to obtain analytically. Following a philosophy of practicality, some routines have been programmed, such as the histogram of the argument of the minimum of the Brownian Bridge conditioned to n points, that get a reasonable probabilistic estimate of the error incurred.

Paraules clau

Teoremes de No Free Lunch; No Free Lunch Theorems; Pont Brownià; Brownian Bridge; Optimització Black-Box; Black-Box Optimisation

Matèries

519.1 - Teoria general de l'anàlisi combinatòria. Teoria de grafs

Àrea de coneixement

Ciències Experimentals

Documents

rjcm1de1.pdf

748.7Kb

 

Drets

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/

Aquest element apareix en la col·lecció o col·leccions següent(s)