Riassunto analitico
A causa del sempre più crescente uso dei problemi di minimizzazione in vari campi delle scienze applicate, l'ottimizzazione differenziabile e non differenziabile ha rappresentato negli ultimi decenni un campo di ricerca molto attivo. I problemi di minimizzazione si presentano nella modellizzazione di fenomeni riguardanti applicazioni reali che trattano dati di larga scala e richiedono soluzioni in tempi reali. Per questi motivi, tra i possibili schemi iterativi, i metodi del primo ordine sono spesso utilizzati poiché presentano una semplice implementazione ed evitano calcoli onerosi durante le iterazioni. Inoltre strategie basate su una scelta opportuna dei parametri che intervengono nella loro descrizione permettono di accelerare largamente la loro velocità di convergenza. Obiettivo di questa tesi è stato quello di progettare tecniche convenienti per la selezione del parametro di lunghezza di passo nei metodi del primo ordine utilizzati per la minimizzazione di funzionali che si possono esprimere come la somma di una funzione differenziabile e di una non differenziabile. Il primo caso discusso si presenta quando il termine non differenziabile si riduce alla funzione indicatrice di un insieme. Sotto questa ipotesi, il problema di ottimizzazione iniziale si trasforma in un problema completamente differenziabile ma vincolato. Uno dei metodi che ha guadagnato grande popolarità in letteratura negli ultimi anni e su cui abbiamo soffermato la nostra attenzione è il metodo del gradiente proiettato scalato (SGP). La nostra analisi si concentra sui parametri che definiscono SGP quali la lunghezza di passo e la matrice di scaling. Prima di tutto è stata sviluppata una analisi teorica delle proprietà regolarizzanti di SGP nell'affrontare problemi ai minimi quadrati. In particolare, è stata esaminata la sua capacità di riprodurre correttamente i fattori di filtro della soluzione e smorzare l'influenza del rumore che corrompe i dati. Questo studio ha consentito di dimostrare quale settaggio dei parametri è necessario per ottenere benefici in termini di accuratezza e regolarizzazione. In secondo luogo è stata proposta una strategia di accelerazione per SGP: l'idea adatta una regola di selezione del passo a memoria limitata recentemente introdotta per i metodi del tipo steepest descent per l'ottimizzazione non vincolata. Le problematiche legate alla generalizzazione di questa regola al caso vincolato sono state discusse e i miglioramenti che si possono ottenere grazie a questa strategia di accelerazione sono stati valutati in esperimenti numerici su problemi di deconvoluzione di immagini. Dopo aver investigato la classe dei problemi differenziabili, l'interesse è stato rivolto allo studio di metodi iterativi, detti proximal, nati per la minimizzazione di un funzionale che comprende anche una parte non differenziabile. L'ipotesi principale alla base di questi algoritmi è la continua Lipschitzianità del gradiente della parte differenziabile della funzione obiettivo. Approcci proximal classici sfruttano la conoscenza della costante di Lipschitz per selezionare la lunghezza di passo; talvolta però il valore di tale costante non è calcolabile. Partendo da questa osservazione, sono state analizzate due possibilità per realizzare metodi proximal indipendenti dalla costante di Lipschitz. In particolare sono stati generalizzati al caso non differenziabile due metodi nati per l’ottimizzazione differenziabile vincolata: il metodo extra-gradiente di Khobotov e il metodo del gradiente proiettato lungo le direzioni ammissibili. Nel tentativo di estensione, la sfida principale è consistita nel sostituire l'operatore di proiezione con il più generale operatore proximal della parte non differenziabile del funzionale. La convergenza di entrambi gli algoritmi è stata provata e la loro efficienza è stata valutata nella risoluzione di problemi di ricostruzione di segnali modellizzabili come problemi di ottimizzazione non differenziabile.
|
Abstract
Because of the wide and growing use of minimization problems in various domains of applied science, differentiable and nondifferentiable optimization are very discussed mathematical fields that have experienced several efforts from many researchers in the last decades. Minimization issues often occur in modeling phenomena dealing with real-life applications that nowadays handle large-scale data and require real-time solutions. For these reasons, among all possible iterative schemes, first order methods are frequently exploited since they present a relative simple implementation and avoid onerous computations during the iterations. Moreover, strategies based on a suitable setting of the parameters involved in the description of these methods allow to largely accelerate their convergence rate. The aim of this thesis has been to design convenient techniques to choose the steplength in first order methods employed for the minimization of functionals that can be expressed as the sum of a differentiable term and a nondifferentiable one.
The first case we discussed occurs when the nondifferentiable term reduces to the indicator function of a set. Under this special assumption, the original optimization problem becomes a constrained differentiable minimization problem. The so-called scaled gradient projection (SGP) method earned a great popularity in the last years in the differentiable constrained optimization framework. Therefore, we focused on this algorithm, especially on the parameters involved in its definition such as the steplength and the scaling matrix. First, we developed a theoretical analysis on the regularizing properties of SGP in finding the solution of a linear least-squares problem. The study we carried out has been performed by examining its ability to reproduce correctly the filter factors of the solution and dampen the influence of the noise corrupting the data. Consequently, this study permitted to establish which setting of the SGP parameters needs to be fixed in order to gain some benefits in terms of accuracy and regularizing effects. Secondly, an acceleration strategy for the SGP method has been proposed: the idea is derived by adapting a steplength selection rule, recently introduced for limited-memory steepest descent methods in unconstrained optimization. We described the issues related to the generalization of this rule to the constrained case and we evaluated the improvements due to the acceleration strategy by numerical experiments on image deconvolution problems.
After the investigation of the differentiable problems, we turned to the initial issue of minimizing a functional that includes also a non-smooth part. Proximal methods are a useful tool for addressing the minimization of this type of objective function. The main assumption for proximal algorithms is based on having a Lipschitz continuous gradient for the differentiable part of the objective function. Classical proximal approaches heavily exploit the knowledge of the gradient Lipschitz constant in order to select the steplength. However, for some minimization problems the value of this constant is not available. Starting from this remark, we discussed two possibilities of realizing proximal methods completely independent on the Lipschitz parameter. We generalized two approaches often adopted in the constrained differentiable optimization framework: the Khobotov extra-gradient method and the gradient projection method along the feasible direction. In this extension attempt, the main challenge is taking into account the presence of the proximal operator of the non-smooth function part instead of a projection onto a suitable set. For both the suggested generalized scheme, the convergence has been proved. In order to evaluate the performance of the presented algorithms, we conducted a numerical study on the capabilities of solving signal recovering problems that can be formalized as nondifferentiable problems.
|