×

Mean value cross decomposition for nonlinear convex problems. (English) Zbl 1136.90433

Summary: Mean value cross decomposition is a symmetric primal–dual decomposition method suitable for optimization problems with both primal and dual structures. It uses only easily solvable subproblems and no difficult master problems. Originally developed for linear problems, it is in this paper extended to nonlinear convex optimization problems. Convergence is proved for a somewhat generalized version, allowing more general weights. Computational results are presented for a network routing problem with congestion costs, a large-scale nonlinear problem with structures that enable decomposition both with respect to variables and constraints. The main goals of the tests are to illustrate the procedure and to indicate that this decomposition approach is more efficient than direct solution with a well established general code.

MSC:

90C25 Convex programming
90C30 Nonlinear programming

Software:

AMPL; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/0377-2217(92)90177-B · Zbl 0770.90041 · doi:10.1016/0377-2217(92)90177-B
[2] Holmberg K., Zeitschrift für Operations Research 39 pp 157– (1994)
[3] Brown, G. W. 1949. ”Some notes on computation of games solutions”. The RAND Corporation. Technical Report RAND Report P-78
[4] DOI: 10.2307/1969530 · Zbl 0045.08203 · doi:10.2307/1969530
[5] DOI: 10.2307/1911892 · Zbl 0127.36703 · doi:10.2307/1911892
[6] DOI: 10.1016/S0377-2217(96)00139-7 · Zbl 0923.90119 · doi:10.1016/S0377-2217(96)00139-7
[7] DOI: 10.1007/BF01300860 · Zbl 0844.90060 · doi:10.1007/BF01300860
[8] DOI: 10.1002/(SICI)1520-6750(199608)43:5<673::AID-NAV5>3.0.CO;2-2 · Zbl 0868.90085 · doi:10.1002/(SICI)1520-6750(199608)43:5<673::AID-NAV5>3.0.CO;2-2
[9] Holmberg, K. 1991. ”Nonlinear MVC decomposition: The strictly convex case”. Sweden: Division of Optimization, Department of Mathematics, Linköping Institute of Technology. Working Paper LiTH-MAT/OPT-WP-1991-15
[10] Vlahos, K. 1991. ”Convergence proof for MVC decomposition applied to convex problems”. England: Decision Science Group, London Business School. Research paper
[11] DOI: 10.1007/BF02591718 · Zbl 0505.90057 · doi:10.1007/BF02591718
[12] Geoffrion A. M., Mathematical Programming Study 2 pp 82– (1974) · Zbl 0395.90056
[13] DOI: 10.1016/0377-2217(93)90118-7 · Zbl 0768.90045 · doi:10.1016/0377-2217(93)90118-7
[14] Rockafellar R. T., Convex Analysis (1970) · Zbl 0193.18401
[15] DOI: 10.1007/BF00934810 · Zbl 0229.90024 · doi:10.1007/BF00934810
[16] Belenky V. Z., Computing Equilibria: How and Why (Proc. Internat. Conf., Comput. Centre, Polish Acad. Sci., Toruń, 8–13 July, 1974) pp 225– (1976)
[17] DOI: 10.1002/nav.3800240211 · Zbl 0372.90119 · doi:10.1002/nav.3800240211
[18] DOI: 10.1016/0898-1221(77)90060-8 · Zbl 0364.90048 · doi:10.1016/0898-1221(77)90060-8
[19] DOI: 10.1007/s101070050050 · Zbl 0956.90020 · doi:10.1007/s101070050050
[20] Fourer R., AMPL: A Modeling Language for Mathematical Programming (1993)
[21] Murtagh B. A., MINOS User’s Guide (1998)
[22] ILOG, ILOG CPLEX User’s Manual (1999)
[23] DOI: 10.1080/02331930108844546 · Zbl 0993.90069 · doi:10.1080/02331930108844546
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.