Mètode Nelder-Mead

Cerca del valor mínim a través del símplex Nelder-Mead a les funció banana de Rosenbrock (dalt) i la funció de Himmelblau (a sota)

El mètode Nelder-Mead és un algorisme d'optimització àmpliament utilitzat. És deu a Nelder i Mead (1965) i és un mètode numèric per minimitzar una funció objectiva en un espai multidimensional.

El mètode utilitza el concepte d'un símplex, que és un politop de N+1 vèrtexs en N dimensions: un segment de línia en una línia, un triangle en un pla, un tetraedre en un espai tridimensional i així successivament.

El mètode busca de manera aproximada una solució òptima local a un problema amb N variables quan la funció a minimitzar varia suaument.

Exemple d'utilització

Per exemple, un enginyer que dissenyi un pont penjant ha de triar el gruix dels cables laterals, els cables més llargs i del suport que anirà asfaltat. Aquests elements estan lligats per un correcte disseny del pont i no és fàcil imaginar l'efecte en el canvi de cadascun dels gruixos. L'enginyer pot usar el mètode Nelder-Mead per generar dissenys de prova, fixant els gruixos dels elements, que són provats en un model d'ordinador que té en compte altres paràmetres (vibracions, vents, materials de construcció ...).

Així s'introdueix una funció, diguem inestabilitat del pont que depèn dels gruixos dels elements amb els quals es construeix, que interessa fer mínima davant altres factors externs (vibracions, vents ...). Com cada vegada que s'executa aquest model que té en compte els factors externs es consumeix molt temps de càlcul és important variar els gruixos amb idea per no malbaratar recursos.

El mètode Nelder-Mead genera una nova posició de prova (valor dels gruixos extrapolant el comportament de la funció en els vèrtexs d'un simplex. Així no cal calcular provar tots els valors possibles de la funció (tots els gruixos) sinó que l'algorisme va reemplaçant cada vegada un dels punts de prova ajustant amb idea per trobar la solució que minimitza la funció més ràpidament.

La manera més senzilla de fer-ho és reemplaçar el pitjor punt amb un punt reflectit en la resta de N-1 punts considerats com un plànol (d'aquí l'extrapolació). Si aquest punt dona millor resultat, l'algorisme prova d'"estirar" prenent els valors exponencialment en una línia que contingui aquest punt. D'altra banda, si aquest nou punt no és molt millor que el valor previ, llavors estem en una vall (busquem un mínim, com un gran forat) i l'algorisme encongeix el símplex cap al millor punt.

Com altres algorismes d'optimització, Nelder-Mead de vegades es queda bloquejat en un mínim local (una zona que és un mínim de la funció comparat amb els punts del voltant però hi ha motius per pensar que hi ha un mímino millor en una altra part). L'algorisme es dona compte i es reinicia amb un nou símplex que comenci en el millor valor trobat. Això pot estendre de la mateixa manera que en el simulated annealing per intentar escapar dels mínims locals.

Existeixen moltes variacions depenent de la naturalesa del problema que es vulgui resoldre. La més usual és, potser, usar un símplex petit de mida constant que salti de gradients locals a màxims locals. Imagini un petit triangle en un mapa en 3D d'una cadena muntanyosa, pujant a una de les muntanyes buscant el bec, buscant com a objectiu final trobar el pic més alt de la serralada. Aquesta variació sol funcionar pitjor que l'esquema original de Nelder-Mead descrit en l'article doncs requereix molts petits passos intermedis (pujar a totes les muntanyes per veure quina és la més alta).

Fonts

• Nelder-Mead (Simplex) Method Arxivat 2005-04-24 a Wayback Machine.
• J.A. Nelder and R. Mead, Computer Journal, 1965, vol 7, pp 308-313 «CiteSeerX».
• Nelder FRS