Abstract
Nonlinear network flow problems with linear/nonlinear side con- straints can be solved by means of Lagrangian relaxations. The dual problem is the maximization of a dual function whose value is estimated by minimizing approximately a Lagrangian function on the set defined by the network constraints. We study alternative stepsizes in the approximate subgradient methods to solve the dual problem. Some basic convergence results are put forward. Moreover, we compare the quality of the computed solutions and the efficiency of these methods.
Chapter PDF
Similar content being viewed by others
References
Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)
Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)
Correa, R., Lemarechal, C.: Convergence of some algorithms for convex minimization. Mathematical Programming 62, 261–275 (1993)
DIMACS. The first DIMACS international algorithm implementation challenge: The bench-mark experiments. Technical Report, DIMACS, New Brunswick, NJ, USA (1991)
Ermoliev, Y.M.: Methods for solving nonlinear extremal problems. Cybernetics 2, 1–17 (1966)
Kiwiel, K.: Convergence of approximate and incremental subgradient methods for convex optimization. SIAM Journal on Optimization 14(3), 807–840 (2004)
Mijangos, E.: A variant of the constant step rule for approximate subgradient methods over nonlinear networks. In: Gavrilova, M.L., Gervasi, O., Kumar, V., Tan, C.J.K., Taniar, D., Laganá, A., Mun, Y., Choo, H. (eds.) ICCSA 2006. LNCS, vol. 3982, pp. 757–766. Springer, Heidelberg (2006)
Mijangos, E.: Approximate subgradient methods for nonlinearly constrained network flow problems. Journal of Optimization Theory and Applications 128(1), 167–190 (2006)
Mijangos, E., Nabona, N.: The application of the multipliers method in nonlinear network flows with side constraints. Technical Report 96/10, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, Barcelona, Spain (1996), http://www.ehu.es/~mepmifee
Mijangos, E., Nabona, N.: On the first-order estimation of multipliers from Kuhn-Tucker systems. Computers and Operations Research 28, 243–270 (2001)
Murtagh, B.A., Saunders, M.A.: Large-scale linearly constrained optimization. Mathematical Programming 14, 41–72 (1978)
Nedić, A., Bertsekas, D.P.: Incremental subgradient methods for nondifferentiable optimization. SIAM Journal on Optimization 12, 109–138 (2001)
Poljak, B.T.: Introduction to Optimization. Optimization Software Inc., New York (1987)
Shor, N.Z.: Minimization Methods for Nondifferentiable Functions. Springer, Berlin (1985)
Toint, Ph.L., Tuyttens, D.: On large scale nonlinear network optimization. Mathematical Programming 48, 125–159 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 IFIP International Federation for Information Processing
About this paper
Cite this paper
Mijangos, E. (2009). Approximate Subgradient Methods for Lagrangian Relaxations on Networks. In: Korytowski, A., Malanowski, K., Mitkowski, W., Szymkat, M. (eds) System Modeling and Optimization. CSMO 2007. IFIP Advances in Information and Communication Technology, vol 312. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04802-9_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-04802-9_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04801-2
Online ISBN: 978-3-642-04802-9
eBook Packages: Computer ScienceComputer Science (R0)