Optimización de funciones en varias variables mediante desigualdades lineales matriciales

Abstract

En este documento se presenta el trabajo titulado Optimización de funciones en varias variables mediante Desigualdades Lineales Matriciales desarrollado dentro del grupo de matemática computacional, en la línea de reconocimiento de formas, exigido como requisito parcial para la obtención del título de Matemático otorgado por la Universidad del Cauca. En él analizaremos la aplicación de un método de optimización que utiliza la teoría de momentos probabilísticos para optimizar polinomios en varias variables, convirtiendo el problema en una sucesión de problemas de optimización por Desigualdades Lineales Matriciales. En el trabajo además se estudia su aplicación en la estimación de los parámetros de una Gramática Incontextual Probabilística. En el primer capítulo se hará un breve repaso de los conceptos básicos de: gramáticas, gramáticas libres de contexto (GLC), gramáticas libres de contexto probabilísticas (GLP), modelos de lenguaje probabilísticos y estimación de parámetros. Veremos que la función de verosimilitud asociada a las reglas de una gramática incontextual probabilística es un polinomio en varias variables. En el segundo capítulo se estudia un concepto útil para el desarrollo del método de optimización de polinomios en varias variables basado en la teoría de momentos; las Desigualdades Lineales Matriciales, de las cuales se darán algunos conceptos básicos. Este tema se da como un preámbulo de la aplicación de la teoría de momentos en la optimización de polinomios en varias variables. En el tercer capítulo se estudiará el método de optimización de polinomios en varias variables mediante desigualdades lineales matriciales basado en la teoría de momentos presentado por Didier Henrion y Jean Lasserre en su art´ıculo Global Optimization with polynomials and the Problem of Moments. Aquí se mostrará como la teoría de momentos nos ofrece un método no convencional para calcular los valores óptimos de un polinomio en varias variables con o sin restricciones. El capítulo 4 corresponde a la experimentación computacional del método, utilizando una herramienta diseñada por los franceses Didier Henrion y Jean Lasserre para implementar el método. Se harán pruebas con diferentes problemas de optimización y con Gramáticas generadas por una herramienta de simulación y por último se analizarán los resultados obtenidos.