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

Abstract

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.