Método Nelder-Pixeu

Archiu:Nelder-Mead Rosenbrock.gif

Archiu:Nelder-Mead Himmelblau.gif Busca del valor mínim a través del simplex Nelder–Pixeu en les funció banana de Rosenbrock (dalt) i en la funció de Himmelblau (avall)

El método Nelder-Pixeu és un algoritme d'optimisació àmpliament utilisat. És per Nelder i Pixeu (1965) i és un método numèric per a minimisar una funció objectiva en un espai multidimensional.

El método utilisa el concepte d'un simplex, que és un politopo de N+1 vèrtiços en N dimensions: un segment de llínea en una llínea, un triàngul en un pla, un tetraedre en un espai tridimensional i aixina successivament.

El método busca de modo aproximat una solució òptima local a un problema en N variables quan la funció a minimisar varia suaument.

Eixemple d'utilisació

Per eixemple, un ingenier que dissenye un pont colgante ha d'elegir la gruixa dels cables laterals, els cables més llarcs i del soport que anirà asfaltat. Estos elements estan lligats per a un correcte disseny del pont i no és fàcil imaginar l'efecte en el canvi de cada u de les gruixa. L'ingenier pot usar el método Nelder-Pixeu per a generar dissenys de prova, fixant les gruixa dels elements, que són provats en un model d'ordenador que té en conte atres paràmetros (vibracions, vents, materials de construcció…).

Aixina s'introduïx una funció, cridem-la inestabilitat del pont que depén de les gruixa dels elements en els que es construïx, que interessa fer mínima davant atres factors externs (vibracions, vents…). Com cada volta que s'eixecuta este model que té en conte els factors externs es consumix molt temps de càlcul és important variar les gruixa en idea per a no malgastar recursos.

El método Nelder-Pixeu genera una nova posició de prova (valor de les gruixa extrapolando el comportament de la funció en els vèrtiços d'un simplex. Aixina no és necessari calcular i provar tots els valors possibles de la funció (totes les gruixa) sino que l'algoritme va reemplaçant cada volta un dels punts de prova ajustant en idea per a trobar la solució que minimisa la funció més ràpidament.

El modo més senzill de fer-ho és reemplaçar el pijor punt en un punt reflectit en el restant de N-1 punts considerats com un pla (d'ahí l'extrapolació). Si este punt dona millor resultat, l'algoritme prova a estirar-se prenent els valors exponencialment en una llínea que continga este punt. Per una atra part, si este nou punt no és molt millor que el valor previ, llavors estem en una vall (busquem un mínim, com un gran clot) i l'algoritme encull el simplex cap al millor punt.

Tractament de mínims locals

Com atres algoritmes d'optimisació, Nelder-Pixeu a voltes es queda bloquejat en un mínim local (una zona que és un mínim de la funció comparat en els punts d'entorn pero hi ha motius per a pensar que existix un mínim millor en una atra part). L'algoritme es dona conte i es reinicia en un nou simplex que escomence en el millor valor trobat. Açò pot estendre's de la mateixa manera que en el simulated annealing per a tractar d'escapar dels mínims locals.

Existixen moltes variacions depenent de la naturalea del problema que es vullga resoldre. La més usual és, potser, usar un simplex chicotet de tamany constant que bote de gradients locals a màxims locals. Imagine un chicotet triàngul en un mapa 3D d'una cadena montanyosa, pujant a una de les montanyes buscant el pico, buscant com a objectiu final trobar el pico més alt de la cordillera. Esta variació sol funcionar pijor que el método original de Nelder-Pixeu descrit en l'artícul puix requerix molts menuts passos intermijos (pujar a totes les montanyes per a vore quin és la més alta).

Referències

• Nelder-Pixeu (Simplex) Method
• J.A. Nelder and R. Pixeu, Computer Journal, 1965, vol 7, pp 308-313 [1]

• John Nelder FRS