Tecniche di ricerca ad arco per metodi a punti interni

Titolo originale:

Arc-Search Techniques for Interior-Point Methods

Contenuto del libro:

Questo libro tratta un'importante area dell'ottimizzazione numerica, chiamata metodo dei punti interni. Questo argomento è diventato popolare a partire dagli anni '80, quando ci si è gradualmente resi conto che tutti gli algoritmi simplex non convergevano in tempo polinomiale e che molti algoritmi a punti interni potevano essere dimostrati come convergenti in tempo polinomiale.

Tuttavia, per molto tempo è rimasto un notevole divario tra i limiti polinomiali teorici degli algoritmi a punti interni e l'efficienza di questi algoritmi. Le strategie importanti per l'efficienza computazionale sono diventate ostacoli nella dimostrazione di buoni limiti polinomiali. Più le strategie venivano utilizzate negli algoritmi, più i limiti polinomiali peggioravano.

Per aggravare ulteriormente il problema, l'algoritmo predittore-correttore (MPC) di Mehrotra (il più popolare ed efficiente algoritmo a punti interni fino a poco tempo fa) utilizza tutte le strategie buone e non riesce a dimostrare la convergenza.

Pertanto, l'MPC non ha la polinomialità, un problema critico con il metodo simplex. Questo libro analizza i recenti sviluppi che risolvono il dilemma.

Si articola in tre parti principali. La prima, che comprende i capitoli 1, 2, 3 e 4, presenta alcuni degli algoritmi più importanti durante lo sviluppo del metodo dei punti interni intorno agli anni '90, la maggior parte dei quali sono ampiamente conosciuti. Lo scopo principale di questa parte è spiegare il dilemma descritto sopra, analizzando i limiti polinomiali di questi algoritmi e riassumendo l'esperienza computazionale ad essi associata.

La seconda parte, che comprende i capitoli 5, 6, 7 e 8, descrive come risolvere il dilemma passo dopo passo utilizzando le tecniche di ricerca ad arco. Alla fine di questa parte, viene presentato un algoritmo molto efficiente con il limite polinomiale più basso. L'ultima parte, che comprende i capitoli 9, 10, 11 e 12, estende le tecniche di arc-search ad alcuni problemi più generali, come la programmazione quadratica convessa, il problema della complementarità lineare e la programmazione semi-definita.