×

An exponential-function reduction method for block-angular convex programs. (English) Zbl 0856.90089

Summary: 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 \(\varepsilon\)-approximate solution in \(O(K(\ln M)(\varepsilon^{- 2}+ \ln 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.

MSC:

90C25 Convex programming
90B10 Deterministic network models in operations research
90C06 Large-scale problems in mathematical programming

Software:

OSL; DIMACS; tn
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Carolan, Oper. Res. 38 pp 240– (1990)
[2] and , Solving multicommodity network flow problems by an interior point method. Proceedings of the SIAM Workshop on Large-Scale Numerical Optimization ( and , Eds). SIAM, Philadelphia, PA (1990) 58–69.
[3] Dantzig, Econometrica 29 pp 767– (1961)
[4] Grigoriadis, Math. Program. Study 26 pp 83– (1986) · Zbl 0594.90025 · doi:10.1007/BFb0121089
[5] Grigoriadis, SIAM J. Optim. 4 pp 86– (1994)
[6] Grigoriadis, Math. Program. 3 pp 157– (1972)
[7] IBM Optimization Subroutine Library (OSL)–Guide and Reference. Release 2. Publication SC23-0519-02, IBM Corporation, Kingston, NY (July 1991).
[8] and , Approximating concurrent flow with uniform demands and capacities: An implementation. Technical Report 92-4, DIMACS Implementation Challenge Workshop (D. S. Johnson and C. C. McGeoch, Eds.) (1992) 225–240.
[9] Optimization Theory for Large Systems. Macmillan. New York (1970).
[10] Leighton, J. Computer and Syst Sciences 50 pp 228– (1995)
[11] and , Implementation of a combinatorial multicommodity flow algorithm. Technical Report 92-4, DIMACS Implementation Challenge Workshop (D. S. Johnson and C. C. McGeoch, Eds.) (1992) 202–224.
[12] Nonlinear Programming. McGraw Hill, New York (1969).
[13] Marsten, Interfaces 20-4 pp 105– (1990)
[14] Nonlinear Programming–Theory and Algorithms. Wiley, New York (1983).
[15] ”New technique for linear inequalities and optimization”, in Project SCOOP Symp. on Linear Inequalities and Programming, Planning Research Division, U. S. Air Force, Washington, DC, 1952.
[16] and , MINOS 5.4 User’s Guide. Technical Report SOL-83-20R. Department of Operations Research, Stanford University, Stanford, CA (December 1983) (Rev. March 1993).
[17] Nash, SIAM J. Numer. Anal. 21 pp 770– (1984)
[18] and , Fast approximation algorithms for fractional packing and covering problems. Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (1991) 495–504.
[19] Pinar, ORSA J Comput. 4 pp 235– (1992) · Zbl 0759.90028 · doi:10.1287/ijoc.4.3.235
[20] Rosen, Numer. Math. 6 pp 250– (1964)
[21] Schultz, SIAM J. Optim. 1 pp 583– (1991)
[22] Shahrokhi, ORSA J Comput. 1 pp 62– (1989) · Zbl 0753.90030 · doi:10.1287/ijoc.1.2.62
[23] Shahrokhi, J. ACM 37 pp 318– (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.