Software de programación cuadrática general y generalizada para MATLAB: teoría y práctica

Abstract

ABSTRACT: The objective of this work is the study and the implementation in MATLAB of an active set numerical method to solve general quadratic optimization problems (GQP), that is to say, problems that include the nonconvex case. Given any symmetric matrix, we study how to calculate a Cholesky factorization, total or partial. This factorization allows to calculate descent directions for any Hessian of the objective function whether positive definite or not. Furthermore, we address the resolution of quadratic problems with l1 terms in the objective function (generalized general quadratic programming, GGQP). This is a procedure to relax some constraints in some applications and also control the violation of this constraints in order to obtain an initial feasible vector, which is necessary to start the iterative process of the active-set methods. For the programming part of this work, we start with an implementation of the algorithm already done in FORTRAN (6600 lines of code, approximately), we have studied each routine (except the update of the Cholesky factors) and we have carried out a new implementation in MATLAB. Our code has been compared with the quadratic programming codes of MATLAB and OCTAVE. Our code was superior to them in the nonconvex case (solving some problems that they do not) and all three performed similarly when solving convex quadratic problems.

RESUMEN: El objetivo de este trabajo es el estudio y la implementación en MATLAB de un método numérico de conjunto activo para resolver problemas de optimización cuadrática general (GQP), es decir, problemas que incluyen el caso no convexo. Dada cualquier matriz simétrica, estudiamos la forma de calcular una factorización de Cholesky, total o parcial. Dicha factorización nos permite obtener direcciones de descenso para cualquier matriz Hessiana de la función objetivo, sea definida positiva o no. Además, abordamos la resolución de problemas cuadráticos con términos l₁ en la función objetivo (programación cuadrática general y generalizada, GGQP). Esto permite relajar algunas restricciones (útil para muchas aplicaciones) y controlar su violación para la obtención de un vector inicial admisible, necesario para comenzar el proceso iterativo de los métodos de conjunto activo. En cuanto a la parte de programación en MATLAB, a partir de una implementación del algoritmo ya realizada en FORTRAN (6600 líneas de código, aproximadamente), hemos estudiado cada rutina (a excepción de las readaptaciones de los factores de Cholesky) y hemos llevado a cabo una nueva programación en MATLAB. Nuestro código ha sido comparado con los de programación cuadrática de MATLAB y OCTAVE (por ser dos paquetes científicos de amplia difusión), mostrándose superior a ellos en la resolución de problemas no convexos (resolviendo problemas que ellos no resuelven),y teniendo un comportamiento muy similar a estos en la resolución de problemas convexos.