An exponential-function reduction method for block-angular convex programs

✍ Scribed by Michael D. Grigoriadis; Leonid G. Khachiyan

• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 769 KB
• Volume: 26
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230260202

✦ Synopsis

Abstract

An exponential potential‐function reduction algorithm for convex block‐angular optimization problems is described. These problems are characterized by K disjoint convex compact sets called blocks and M non‐negative‐valued convex block‐separable coupling inequalities with a nonempty interior. A given convex block‐separable function is to be minimized. Concurrent, minimum‐cost, and generalized multicommodity network flow problems are important special cases of this model. The method reduces the optimization problem to two resource‐sharing problems. The first of these problems is solved to obtain a feasible solution interior to the coupling constraints. Starting from this solution, The algorithm proceeds to solve the second problem on the original constraints, but with a modified exponential potential function. The method is shown to produce an ϵ‐approximate solution in O(K(In M)(ϵ^−2^ + in K)) iterations, provided that there is a feasible solution sufficiently interior to the coupling inequalities. Each iteration consists of solving a subset of independent block problems, followed by a simple coordination step. Computational experiments with a set of large linear concurrent and minimum‐cost multicommodity network flow problems suggest that the method can be practical for computing fast approximations to large instances.