Analysis of a Nonhierarchical Decomposition Algorithm

Files
TR Number
TR-92-48
Date
1992
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science, Virginia Polytechnic Institute & State University
Abstract

Large scale optimization problems are tractable only if they are somehow decomposed. Hierarchical decompositions are inappropriate for some types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategy for nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two dimensional quadratic programs. This paper carefully analyzes the algorithm for quadratic programs, and suggests a number of modifications to improve its robustness.

Description
Keywords
Citation