Premium
An exponential‐function reduction method for block‐angular convex programs
Author(s) -
Grigoriadis Michael D.,
Khachiyan Leonid G.
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230260202
Subject(s) - mathematics , block (permutation group theory) , mathematical optimization , reduction (mathematics) , disjoint sets , convex function , convex optimization , exponential function , separable space , function (biology) , solution set , optimization problem , linear programming , regular polygon , set (abstract data type) , computer science , combinatorics , mathematical analysis , geometry , evolutionary biology , biology , programming language
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.