Aspectos computacionales en la bisección de un n-simplex regular.

Abstract

En el ambito de la optimizacion global basada en tecnicas de ramificacion y acotacion, cuando el espacio de busqueda es un n-simplex regular es habitual utilizar como regla de division la biseccion por el lado mayor. Este modo de divisi´on evita que los subproblemas generados tengan una forma degenerada o poco redondeada y ademas da lugar a un muestreo mas uniforme del espacio de busqueda ya que la funcion objetivo es normalmente evaluada en los vertices de los sub-problemas o sımplices. En este trabajo se muestra como la division por el lado mayor puede afectar a parametros tales como el numero total de sub-problemas generados, el numero de formas similares que estos pueden tener o el grado de redondez de los sub-problemas. La dificultad de determinar estos parametros se incrementa con el valor de n. En este trabajo se presentan los resultados de los estudios realizados para n ≤ 3, es decir, hasta un espacio 4-dimensional. Debido al crecimiento exponencial del ´arbol binario de busqueda generado, se hace necesario el uso de computacion paralela cuando se usan criterios de terminacion mas precisos y/o n-sımplices con n ≥ 3. Aquı se presenta un modelo paralelo que hace uso de las posibilidades de paralelizacion de MATLAB.