Propuesta evolutiva para encontrar una extensión cordal adecuada en problemas de optimización semidefinida.

Ponente(s): Fernando Ignacio Becerra López, Edgar Fuentes Figueroa

Un enfoque que ha resultado eficiente para resolver problemas de optimización semidefinida es, aprovechando el patrón de esparcidad, reducir la matriz del sistema en varias más pequeñas. Para que esta descomposición sea consistente, se requiere que el grafo asociado a la matriz sea cordal lo cuál rara vez ocurre. Extender el grafo a uno que cumpla la cordalidad es posible pero aumenta el costo computacional. Por ello, encontrar una extensión cordal mínima es clave en el proceso. Desafortunadamente, encontrarla es un problema NP-duro. Debido a esto, se han utilizado heurísticas para lograr una, sino mínimo, si adecuada en términos del problema y tiempo disponible. Dado que revisar la cordalidad se realiza en tiempo lineal, proponemos una estrategia evolutiva basada en un algoritmo genético que flexibiliza la búsqueda e involucra no sólo el tamaño de la extensión sino tanto la cordalidad como el tamaño de la extensión.