Data e ora inizio evento:
Data e ora fine evento:
Sede:
Dipartimento di Matematica Guido Castelnuovo, Università Sapienza Roma
Aula:
Sala di Consiglio
Speaker:
Gerardo Toraldo, Dipartimento di Matematica e Applicazioni "Renato Caccioppoli", Università di Napoli Federico II
We propose a two-phase gradient-based method for general Quadratic Programming (QP) problems. Such kind of problems arise in many real-world applications, such as Support Vector Machines, multicommodity network flow and logistics or in variational approaches to image deblurring. Moreover, an effective QP solver is the basic building block in many algorithms for the solution of nonlinear constrained problems. The proposed approach alternates between two phases: an identification phase, which performs Gradient Projection iterations until either a candidate active set is identified or no reasonable progress is made, and an unconstrained minimization phase, which reduces the objective function in a suitable space defined by the identification phase, by applying either the conjugate gradient method or any spectral gradient method. A critical issue about a two-phase method stands in the design of an effective way to switch from phase 1 to phase 2. In our method, this is based on a comparison between a measure of optimality in the reduced space and a measure of bindingness of the active variables, defined by extending the concept of proportional iterate, which was proposed by some authors for box-constrained problems. If the objective function is bounded, the algorithm converges to a stationary point. For strictly convex problems, the algorithm converges to the optimal solution in a finite number of steps even in the case of degeneracy. Extensive numerical experiments show the effectiveness of the proposed approach. This talk is based on joint work with Daniela di Serafino (Dipartimento di Matematica e Fisica dell’Università della Campania “Luigi Vanvitelli”) and Marco Viola (Dipartimento di Ingegneria Informatica Automatica e Gestionale “Antonio Ruberti” della Sapienza Università di Roma). References Diening, L., Harjulehto, P., Hästö, P., Ruzicka, M., Lebesgue and Sobolev spaces with variable exponents. Lecture Notes in Mathematics. vol. 2017, Springer, 2011. Schuster, T., Kaltenbacher, B., Hofmann, B., and Kazimierski, K. S., Regularization Methods in Banach Spaces. Radon Series on Computational and Applied Mathematics, vol. 10, De Gruyter, 2012 C. Estatico, S. Gratton, F. Lenti, D. Titley-Peloquin, “A conjugate gradient like method for p-norm minimization in functional spaces”, Numerische Mathematik,