An inexact infeasible arc-search interior-point method for linear optimization problems

Sintesi Tecnica: Un Metodo Interior-Point ad Arco Inesatto e Inammissibile per Problemi di Ottimizzazione Lineare

Enunciato del Problema
Il documento affronta la risoluzione di Problemi di Ottimizzazione Lineare (LOP) utilizzando i Metodi Interior-Point (IPM). Nello specifico, si concentra sui metodi interior-point inammissibili inesatti (II-IPM), ovvero varianti progettate per risolvere i LOP partendo da un punto iniziale inammissibile e risolvendo i sistemi di Newton in modo inesatto (ad esempio, tramite solver iterativi come il Gradiente Coniugato). Sebbene i solver inesatti riducano il costo computazionale per iterazione per problemi di grande scala, gli esistenti metodi a ricerca di linea inammissibili inesatti soffrono di un significativo svantaggio: l'accumulo di errori di linearizzazione (derivanti dall'approssimazione del percorso centrale) ed errori di inesattezza (dal solver) lungo una direzione di ricerca rettilinea. Questo accumulo costringe l'algoritmo a utilizzare dimensioni del passo molto piccole, risultando in un limite di complessità delle iterazioni nel caso peggiore relativamente debole di $O(n^2 L)$, dove $n$ è il numero di variabili e $L$ è la lunghezza binaria dei dati di input.

Metodologia
Gli autori propongono un nuovo metodo denominato II-arc (un Metodo Interior-Point ad Arco Inammissibile Inesatto). L'innovazione principale risiede nel sostituire la standard ricerca di linea retta con una strategia di ricerca ad arco ellissoidale.

1. Framework di Ricerca ad Arco: Invece di muoversi lungo una linea retta, il metodo approssima il percorso centrale utilizzando un arco ellissoidale definito da un'espansione di Taylor del secondo ordine. Il successivo iterato $(x_{k+1}, y_{k+1}, s_{k+1})$ è calcolato come:
   $$x(\alpha) = x_k - \dot{x} \sin(\alpha) + \ddot{x}(1 - \cos(\alpha))$$
   (e analogamente per $y$ e $s$), dove $\dot{x}, \ddot{x}$ sono la prima e la seconda derivata del percorso centrale.
2. Risoluzione Inesatta: Il metodo risolve i sistemi di Newton per la prima derivata ($\dot{x}, \dot{y}, \dot{s}$) e la seconda derivata ($\ddot{x}, \ddot{y}, \ddot{s}$) in modo inesatto. Gli autori utilizzano la formulazione del Sistema di Equazioni Normali Modificato (MNES) per l'analisi teorica al fine di rilassare i requisiti dei residui, sebbene gli esperimenti numerici utilizzino il sistema di Equazioni Normali (NES) standard con un precondizionatore di Jacobi a causa della instabilità numerica osservata nelle implementazioni MNES per problemi di grande scala.
3. Selezione della Dimensione del Passo: La dimensione del passo $\alpha$ è scelta per soddisfare specifiche condizioni di vicinato (garantendo che l'iterato rimanga all'interno di una specifica regione del percorso centrale) e una condizione di tipo Armijo per garantire un'adeguata riduzione del gap di dualità.
4. Analisi Teorica: Gli autori dimostrano che la traiettoria curva dell'arco sopprime l'errore di linearizzazione più efficacemente rispetto a una linea retta. Ciò consente alla dimensione del passo di rimanere maggiore anche quando i sistemi di Newton sono risolti con una significativa inesattezza.

Contributi Chiave

• Primo IPM ad Arco Inesatto: Per quanto ne sappiano gli autori, questo è il primo articolo che discute un IPM inesatto all'interno del framework di ricerca ad arco.
• Miglioramento del Limite di Complessità: Il documento stabilisce un limite di complessità delle iterazioni polinomiale di $O(n^{1.5} L)$ per il proposto metodo II-arc. Questo rappresenta un miglioramento teorico rispetto al miglior limite noto per gli esistenti metodi inammissibili inesatti a ricerca di linea ($O(n^2 L)$) di un fattore $n^{0.5}$.
• Mitigazione dell'Accumulo di Errore: Gli autori dimostrano che la strategia di ricerca ad arco mitiga l'accumulo di errori di linearizzazione e di inesattezza, che è il principale collo di bottiglia negli esistenti metodi inammissibili inesatti.

Risultati Numerici
Gli autori hanno condotto esperimenti numerici su problemi di grande scala dalla collezione di benchmark NETLIB (inclusi i problemi DFL001, QAP15, STOCFOR3 e Kennington) utilizzando un'implementazione in Python con il Gradiente Coniugato Precondizionato (CG) come solver lineare.

• Confronto: Il metodo II-arc proposto (specificamente la variante che utilizza il punto iniziale euristico di Yang, "II-arc-Yang") è stato confrontato con un esistente metodo inammissibile inesatto a ricerca di linea ("II-line-Yang").
• Performance:
  • Iterazioni: II-arc-Yang ha richiesto costantemente meno iterazioni rispetto a II-line-Yang. Per quasi il 25% dei problemi di test, il metodo a ricerca di linea ha richiesto il doppio o più delle iterazioni rispetto al metodo ad arco.
  • Tempo di Calcolo: II-arc-Yang ha ridotto il tempo totale di calcolo per il 75% dei problemi. La riduzione delle iterazioni ha compensato il costo aggiuntivo della risoluzione del sistema della seconda derivata.
  • Robustezza: Il metodo ha risolto con successo 1 di 18 problemi di test, dimostrando stabilità numerica.
• Punti Iniziali: Lo studio ha anche confrontato un punto iniziale costante contro l'euristica del punto iniziale di Yang, riscontrando che l'approccio euristico (II-arc-Yang) ha generalmente prodotto prestazioni migliori in termini sia di iterazioni che di tempo.

Significatività e Rivendicazioni
Il documento afferma che il metodo II-arc proposto offre un limite di complessità nel caso peggiore provabilmente più stretto rispetto agli esistenti metodi inammissibili inesatti a ricerca di linea. La significatività di questo lavoro risiede nel colmare il divario tra i benefici teorici della ricerca ad arco (migliore approssimazione del percorso centrale) e la necessità pratica di solver inesatti per problemi di grande scala.

Gli autori notano con modestia che, sebbene la complessità teorica sia migliorata, l'obiettivo primario era proporre il framework e discuterne la convergenza. Essi riconoscono che le prestazioni numeriche potrebbero essere ulteriormente migliorate:

• Implementando il metodo in linguaggi più veloci (ad esempio, C++, Julia).
• Investigando solver di sistemi lineari inesatti e precondizionatori più avanzati.
• Esplorando combinazioni con la strategia di riavvio di Nesterov o con IPM ammissibili.

Il documento conclude che l'approssimazione ad arco ellissoidale permette dimensioni del passo maggiori in presenza di inesattezza, portando sia a una riduzione teorica della complessità delle iterazioni che a miglioramenti pratici nella risoluzione di problemi di ottimizzazione lineare di grande scala.