A more general dual projected pseudo quasi-Newton method for large network optimization problems

Abstract

One of the major computational steps in the dual projectd pseudo quasi-Newton method for neweork type optimization problems is the projection onto a convex set formed by the linear inequlity constraints of the problem. When the inequlity constraints are coupled, the large-dimension projection problem is a difficult one. In this paper, we propose a graphic-method based decomposition technique to determine a smallest subset of inequality contraints to be converted to equality constraints so that the rest of the inequality constraints become disjoint subsets. Consequently, the large-dimension projection problem can be decomposed into several independent small-dimension projection subproblems, and the computation complexity for the projection step will be largely reduced. Copyright (C) 1998 IFAC.