Permutation-based enhancement of factorization methods for the fast solution of KKT systems

Abstract

Esta tesis explora las posibles mejoras en el tiempo de procesamiento para la resolu- ción de problemas de control óptimo mediante el uso de las condiciones de Karush- Kuhn-Tucker (KKT)que dan lugar a una serie de ecuaciones lineales. El objetivo principal de este trabajo era desarrollar y probar métodos que redujeran el esfuerzo computacional y el tiempo necesario para resolver estos sistemas, lo cual es crítico en aplicaciones en tiempo real como el Control Predictivo de Modelos(MPC). Se pro- pusieron dos enfoques para abordar el problema: el primero se centra en el uso de un algoritmo de Grado Mínimo Aproximado (AMD) calculado fuera de línea para reducir los rellenos al factorizar la matriz de coeficientes, y el segundo aprovecha la información relacionada con cómo cambian las entradas de la matriz a través de la iteración de los solvers para identificar los sectores constantes que no es necesario calcular en cada paso del solver. Ambos enfoques muestran resultados prometedores en la resolución del problema, con el de AMD mostrando una mejora más concreta en comparación con otros métodos similares, mientras que el segundo mostró potencial para sistemas más grandes, aunque son necesarias más optimizaciones en la codificación. En gen- eral, la investigación proporciona valiosos conocimientos para mejorar la eficiencia de la resolución de problemas de control óptimo y contribuir a estrategias de control en tiempo real más eficaces.

This thesis explores the potential improvements in processing time for solving optimal control problems by using the Karush-Kuhn-Tucker (KKT) conditions which result in a series of linear equations. The primary objective of this work was to develop and test methods that would reduce the computational effort and time needed for solving these systems, which is critical in real-time applications such as Model Predictive Control (MPC). Two approaches were proposed to tackle the problem: the first focuses on the use of an offline calculated Approximate Minimum Degree (AMD) algorithm to reduce the fill-ins when factorizing the coefficient matrix, and the second takes advantage of information related to how the entries of the matrix change through the solvers iteration to identify the constant sectors that do not need to be calculated at each solver step. Both approachess how promising results in solving the problem, with the AMD one showing a more concrete improvement compared to other similar methods, while the second one showed potential for larger systems, though further optimizations on the coding are necessary. In general, the research provides valuable insight into improving the efficiency of solving optimal control problems and contributing to more effective real- time control strategies.