Insights into Conic Optimization Bridging Theory and Applications

Abstract

La presente disertación explora nuevas perspectivas sobre la optimización cónica, abarcando una amplia gama de temas que van desde la optimización lineal sobre secciones de conos hasta aplicaciones en diseño de redes complejas, localización de servicios, detección de fugas o geometría algebraica real. El concepto central del trabajo es la noción matemática de cono, que se explora desde sus orígenes geométricos hasta su uso en la teoría moderna de la optimización. El trabajo se basa, máxime, en el estudio de problemas de optimización cónica, donde se minimiza una función lineal sobre la sección de un cono. Esto generaliza la programación lineal e incluye una amplia gama de problemas de optimización. Uno de los principales propósitos de esta tesis es introducir una nueva familia de conos, los conos de potencia generalizados, y estudiar el problema de minimizar una función lineal sobre ellos. Se realiza un análisis detallado sobre las representaciones minimales de estos conos, proporcionando un procedimiento para construir representaciones minimales utilizando conos de segundo orden cuando los parámetros definitorios son racionales. La construcción se basa en el concepto de grafos mediados, una estructura combinatoria que desempeña un papel crucial en la derivación de estas representaciones minimales. La metodología utilizada supone el desarrollo de resultados teóricos sobre las propiedades de los conos de potencia generalizados, el análisis de grafos mediados y la exploración de resultados de complejidad para el problema de factibilidad sobre conos de orden p. Se derivan nuevas cotas de complejidad, mejorando los resultados existentes y llevando a una mejor comprensión de los desafíos computacionales de la optimización cónica. Los hallazgos tienen aplicaciones directas en varios dominios. Una aplicación importante se encuentra en los problemas de ubicación de instalaciones, donde se aplica la geometría de los conos de potencia generalizados para desarrollar un modelo de optimización basado en la ley de la gravitación universal de Newton. Además, se presenta un enfoque novedoso para la detección de fugas en redes de tuberías, formulado como un problema entero mixto sobre conos de orden p. Las soluciones a estos problemas son computacionalmente eficientes y demuestran la utilidad práctica de los enfoques propuestos. En conclusión, la disertación contribuye tanto a los avances teóricos en optimización cónica como a metodologías prácticas para aplicaciones en el mundo real, ofreciendo una perspectiva unificada sobre la optimización, la geometría algebraica y la combinatoria.

This dissertation explores novel insights into conic optimization, bridging a diverse set of topics ranging from linear optimization over slices of cones to applications in complex network design, facility location, leak detection, or real algebraic geometry. The central concept of the work is the mathematical notion of cone, which is explored from its geometric origins to its use in modern optimization theory. The work is grounded in the study of conic optimization problems, where a linear function is minimized over a slice of a cone. This generalizes linear programming and encompasses a broad range of optimization problems. One of the main purposes of this thesis is to introduce a new family of cones, generalized power cones, and study the conic optimization problem of minimizing a linear function over these cones. A detailed analysis is conducted on the minimal representations of these cones, providing a procedure for constructing minimal representations using second–order cones when the defining parameters are rational. The construction is grounded in the concept of mediated graphs, a combinatorial structure that plays a crucial role in deriving the minimal representations. The methodology involves the development of theoretical results on the properties of generalized power cones, the analysis of mediated graphs, and the exploration of complexity results for the feasibility problem over p– order cones. New complexity bounds are derived, improving upon existing results and leading to a better understanding of the computational challenges in conic optimization. The findings have direct applications in several domains. A significant application is found in facility location problems, where the geometry of generalized power cones is applied to devise an optimization model based on Newton’s universal law of gravitation. Additionally, a novel approach to leak detection in pipeline networks is presented, formulated as a mixed integer p–order cone program. The solutions to these problems are computationally efficient and demonstrate the practical utility of the proposed approaches. In conclusion, the dissertation contributes to both theoretical advancements in conic optimization and practical methodologies for real-world applications, offering a unified perspective on optimization, algebraic geometry, and combinatorics.