Dual multilevel optimization |
| |
Authors: | Timothy A Davis William W Hager |
| |
Institution: | (1) Department of Computer and Information Science and Engineering, University of Florida, PO Box 116120, Gainesville, FL 32611-6120, USA;(2) Department of Mathematics, University of Florida, Gainesville, PO Box 118105, FL 32611-8105, USA |
| |
Abstract: | We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable
cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations.
As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose
a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel
implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming
test problems.
|
| |
Keywords: | Multilevel optimization Dual optimization Dual separability Dual active set algorithm Parallel algorithms |
本文献已被 SpringerLink 等数据库收录! |
|