Multigrid methods in network optimization : overview and appraisal

Abstract

Multigrid methods have been traditionally applied to the solution of certain Partial Differential Equations. However, applications in control theory, optimization, pattern recognition, computational tomography and particle physics are beginning to appear. This thesis analyzes the application of multigrid methodology to optimization problems. The work is centered on networks. Transportation problems are chosen frequently as reference because they have been the object of some multigrid research. The goal is to establish a basis for development of multigrid-based algorithms. Optimality conditions in linear programming and networks are reviewed, and a compilation of various multilevel approaches in optimization is presented. Emphasis is on the recent scaling techniques; they add some special insights into solving large network problems efficiently using progressive level of detail. An analysis of the difficulties that these problems present to the multigrid approach reveals that perhaps some abstraction is appropriate when interpreting multigrid components applied to optimization problems (in particular, the concept of grid itself). The idea of implicit ordering is developed and associated with the effectiveness of the multigrid method. These concepts are applied to identify problems that can be solved using multigrid. Finally, suggestions for the development of future multigrid-based algorithms are provided