A proposition to exploit the partially linear structure of the nonlinear multicommodity flow optimization problem
DOI:
https://doi.org/10.26636/jtit.2002.3.133Keywords:
multicommodity flow problem, projection methods, large nonlinear problemsAbstract
Optimization problems arising in telecommunications are often large-scale nonlinear problems. Usually their big size is generated mainly by their linear parts but the existence of small or medium nonlinear parts prevents us from directly tackling them with linear solvers, which are efficient. Instead, the author has proposed a method to decompose big nonlinear problems into nonlinear and linear parts. Its coordination procedure uses two auxiliary solvers: quadratic and pure nonlinear. The procedure falls in the class of projection methods. Special cuts proposed by the author allow to avoid an excessive zigzagging while not enormously increasing the complexity of both the parts. The validity of these cuts can be analyzed within the framework of obtuse cone model. Here the author summarizes the method and analyses its applicability to nonlinear multicommodity flow problems. The structure and particular sizes of this problem make the method useful. The considerations are illustrated by a numerical example with a multicommodity flow problem.
Downloads
References
[1] A. Altman and J. Gondzio, "Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization", Optim. Meth. Softw., vol. 11-12, pp. 275-302, 2000.
View in Google Scholar
[2] H. Bauschke and J. Borwein, "On projection algorithms for solving convex feasibility problems", SIAM Rev., vol. 38, no. 3, pp. 367-426, 1996.
View in Google Scholar
[3] P. Białoń, "Large-scale nonlinear projection algorithm using projection methods", Discus. Math. Differ. Inclus., Contr. Optim., vol. 20, no. 2, pp. 171-194, 1999.
View in Google Scholar
[4] A. Cegielski, "A method of projection onto an acute cone with level control in convex minimization", Math. Progr., vol. 85, pp. 469-490, 1999.
View in Google Scholar
[5] A. Cegielski, Relaxation Methods in Convex Optimization Problems, Higher College of Engineering. Series Monographies, no. 67. Zielona Góra, Poland (in Polish).
View in Google Scholar
[6] R. Dylewski, "Numerical behavior of the method of projection onto an acute cone with level control in convex optimization", Discus. Math. Differ. Inclus., Contr. Optim., vol. 20, 1999.
View in Google Scholar
[7] S. Flam and J. Zowe, "Relaxed outer projections, weighted averages and convex feasibility", BIT, vol. 30, pp. 289-300, 1999.
View in Google Scholar
[8] S. Kim, A. Hyunsil, and C. Seong-Cheol, "Variable target value subgradient method", Math. Progr., vol. 49, pp. 356-369, 1991.
View in Google Scholar
[9] K. Kiwiel, "Monotone Gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems", Linear Algeb. Appl., vol. 215, pp. 27-33, 1997.
View in Google Scholar
[10] K. Kiwiel, "The efficiency of subgradient projection methods for convex optimization", Part I: "General level methods", SIAM Contr. Optim., vol. 34, no. 2, pp. 660-676, 1996.
View in Google Scholar
[11] K. Kiwiel, "Block-iterative surrogate projection methods for convex feasibility problems", Linear Algeb. Appl., vol. 15, pp. 225-259, 1995.
View in Google Scholar
[12] T. Kręglewski, J. Granat, and A. Wierzbicki, IAC-DIDAS-N - A Dynamic Interactive Decision Analysis and Support System for Multicriteria Analysis of Nonlinear Models, v. 4.0. Laxenburg (Austria): International Institute for Applied Systems Analysis, June 1991, collabor. paper, CP-91-101.
View in Google Scholar
[13] C. Lemaréchal, A. S. Nemirovskii, and Yu. Nesterov, "New variants of bundle methods", Math. Progr., vol. 69, pp. 111-147, 1995.
View in Google Scholar
[14] M. Makowski, LP-DIT Data Interchange Tool for Linear Programming Problems (Version 1.20). Laxenburg (Austria): International Institute for Applied Systems Analysis, 1994, work. paper, WP-94-36.
View in Google Scholar
[15] M. Minoux, "Network synthesis and optimum network design problems: models, solution methods and applications", Network, vol. 19, pp. 313-360, 1989.
View in Google Scholar
[16] M. Shchepakin, "On a modification of a class of algorithms for mathematical programming", Zh. Vychisl. Mat. i Mat. Fiz., vol. 19, pp. 1387-1395, 1979 (in Russian).
View in Google Scholar
Downloads
Published
Issue
Section
License
Copyright (c) 2002 Journal of Telecommunications and Information Technology

This work is licensed under a Creative Commons Attribution 4.0 International License.