Métodos de segundo orden para la resolución numérica de problemas de optimización dispersos

Abstract

Resumen .- En este trabajo se propone un algoritmo tipo Quasi-Newton para resolver numéricamente problemas de optimización dispersos, inducidos por la norma l1. Por medio de una versión regularizada de dicha norma, el nuevo algoritmo es capaz de calcular direcciones de descenso incorporando información de segundo orden asociada al término no diferenciable en la matriz Hessiana de la función objetivo; adicionalmente, se utiliza información de los subgradientes, los cuales caracterizan los conjuntos activos de manera eficiente y un esquema de búsqueda lineal proyectada que permite obtener un paso de descenso que mantiene el proceso de minimización en las zonas donde las función objetivo es diferenciable. Gracias a la combinación de estas tres estrategias el algoritmo propuesto adquiere características importantes. Presentamos algunas propiedades teóricas y conducimos experimentos numéricos exhaustivos que revelan un mejor desempeño del algoritmo propuesto en este trabajo con respecto a algoritmos similares desarrollados previamente. Para ilustrar la aplicabilidad del algoritmo, resolvemos numéricamente un problema de control óptimo de dinámica poblacional gobernado por la ecuación de Fisher. Abstract .- In this paper we propose a Quasi-Newton type algorithm for the numerical solution of optimization problems with sparsity induced by the l1 norm. By means of a regularized version of this norm, the new algorithm is capable to compute descent directions by including second-order information associated to the non-differentiable term in the Hessian matrix of the objective function; furthermore, we use subgradients in order to characterize the active sets efficiently and a projected line-search procedure, which allows the algorithm to obtain a descent step, keeping the minimization procedure in zones where the objective function is differentiable. Thanks to the combination of this three strategies, the proposed algorithm gains important numerical and theoretical properties. We show some of these theoretical properties and conduct exhaustive numerical experiments which reveal a better performance than other up-to-date algorithms. In order to illustrate the applicability of our algorithm, we solve numerically an optimal control problem of population dynamics governed by the Fisher’s equation.