Proprietà spettrali dei metodi del gradiente per problemi di ottimizzazione con vincoli speciali

The role of the steplength selection strategies in gradient methods has been widely investigated in the last decades. Starting from the pioneering paper of Barzilai and Borwein (1988), many efficient steplength rules have been designed, which contributed to make gradient-based approaches an effective tool for addressing large-scale optimization problems arising in many real-world applications. Most of these steplength selection rules have been developed in the unconstrained optimization framework, with the aim of exploiting some second-order information for achieving a fast annihilation of the gradient of the objective function. These steplength rules have been successfully applied also within gradient projection (GP) methods for constrained optimization, though, in this case, a detailed analysis on how the constraints may affect their spectral properties, as well as their formulation, has not been yet carried out. However, the convergence criteria for the GP method do not require restrictive hypothesis on the steplength parameter, provided that it is bounded away from zero and belongs to a predefined interval: this flexibility in the choice of the steplength allows to develop updating strategies aimed at optimizing the numerical behaviour, possibly in an inexpensive way. Motivated by these considerations, we analyse how, for quadratic programs, the original Barzilai-Borwein (BB) schemes are influenced by the presence of the feasible set. To this aim, we analyse their behaviour with respect to the spectrum of the Hessian of the objective function starting from the simpler case of box-constraints, and then moving to inspect the case of a more general feasible region expressed by a Single Linear equality constraint together with lower and upper Bounds (SLB). We propose modified versions of the BB rules (and their extensions), obtaining improvements of the gradient projection methods. Driven by this study on the BB rules, we extend the spectral analysis to the steplength updating strategy proposed by Roger Fletcher (2012) within the so-called Limited Memory Steepest Descent (LMSD) method. In particular, we combine the idea of the limited memory steplength approach with the gradient projection method for quadratic programming problems subject to box-constraints, investigating the possibility of modifying the original updating strategy in order to take into account the lower and the upper bounds in a suitable manner. The practical effectiveness of the proposed strategies has been tested in several numerical experiments on random large scale box-constrained and SLB quadratic problems, on some well known non quadratic problems and on a set of test problems arising from real-life applications.

Il ruolo delle tecniche di scelta del passo nel metodo del gradiente è stato largamente studiato in letteratura. Di fondamentale ispirazione, a tal riguardo, è stato il lavoro di Barzilai e Borwein (1988), a partire dal quale sono state sviluppate nuove ed efficienti tecniche di scelta del passo, che hanno contribuito a rendere gli approcci di tipo gradiente particolarmente efficaci per la risoluzione di problemi di ottimizzazione di grandi dimensioni nell’ambito delle applicazioni reali. Tali tecniche sono state principalmente ideate nel contesto dell’ottimizzazione non vincolata, allo scopo di introdurre informazioni del secondo ordine utili ad accelerare la riduzione del gradiente della funzione obiettivo e sono state poi utilizzate con successo anche nei metodi del gradiente proiettato (GP) per la risoluzione di problemi di ottimizzazione vincolata. Tuttavia nel caso vincolato, a differenza di quanto fatto nel caso non vincolato, manca in letteratura un’accurata analisi delle proprietà spettrali del metodo GP in relazione alle tecniche di scelta del passo e a come queste siano influenzate dalla presenza dei vincoli. Accanto a ciò, è opportuno ricordare che i risultati di convergenza del metodo del gradiente proiettato non richiedono ipotesi particolarmente restrittive per la scelta del passo, a patto che esso sia strettamente positivo ed appartenga ad un intervallo reale limitato: pertanto, questa flessibilità di scelta consente di sviluppare regole di aggiornamento del passo atte ad ottimizzare il comportamento numerico, senza incrementare i costi computazionali. Sulla base di queste considerazioni, intendiamo esaminare, dapprima per il caso quadratico, in che modo le regole di Barzilai-Borwein (BB) sono influenzate dalla presenza della regione ammissibile. A tale scopo, abbiamo analizzato il comportamento dei passi generati da tali regole in relazione allo spettro della matrice Hessiana della funzione obiettivo, partendo dal caso più semplice di vincoli box per poi considerare un caso più generale di regione ammissibile espressa da un vincolo lineare di uguaglianza e vincoli di tipo box (a quest’ultimo caso ci riferiremo con l’acronimo SLB, dalla notazione inglese). Nello specifico, proponiamo versioni modificate delle regole BB (e di alcune loro estensioni), che consentono di migliorare le prestazioni del metodo del gradiente proiettato. Guidati dai risultati ottenuti per le regole di tipo BB, abbiamo esteso l’analisi delle proprietà spettrali anche alla strategia di aggiornamento del passo proposta da Roger Fletcher (2012) nell’ambito del metodo denominato Limited Memory Steepest Descent (LMSD). In particolare, si è proposto di adattare l’approccio di Fletcher al metodo del gradiente proiettato per la risoluzione di problemi di minimizzazione quadratici con vincoli box, introducendo la possibilità di modificare la strategia originale per tenere conto dei vincoli in maniera opportuna. L’efficienza pratica delle strategie proposte è stata verificata attraverso una consistente sperimentazione numerica su problemi quadratici di grande dimensione generati in maniera casuale, su problemi non quadratici ben noti e su un dataset di problemi provenienti da applicazioni reali.