Lagrangian Relaxation via Ballstep Subgradient Methods

References

• Anstreicher K. M., Wolsey L. On dual solutions in subgradient optimization. (1993) . Technical report, Department of Management Sciences, University of Iowa, Iowa City, IAGoogle Scholar
• Bahiense L., Maculan N., Sagastizábal C. A. The volume algorithm revisited: Relation with bundle methods. Math. Programming (2002) 94:41–69Crossref, Google Scholar
• Balas E., Carrera M. C. A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. (1996) 44(6):875–890Link, Google Scholar
• Barahona F., Anbil R. The volume algorithm: Producing primal solutions with a subgradient method. Math. Programming (2000) 87(3):385–399Crossref, Google Scholar
• Barahona F., Anbil R. On some difficult linear programs coming from set partitioning. Discrete Appl. Math. (2002) 118(1-2):3–11Crossref, Google Scholar
• Barahona F., Chudak D., Pardalos P. M. Solving large scale uncapacitated facility location problems. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems (2000) (Kluwer, Dordrecht, The Netherlands) 48–62Crossref, Google Scholar
• Ben-Tal A., Margalit T., Nemirovski A. The ordered subsets mirror descent optimization method with applications to tomography. SIAM J. Optim. (2001) 12(1):79–108Crossref, Google Scholar
• Bertsekas D. P.Network Optimization: Continuous and Discrete Models (1998) (Athena Scientific, Belmont, MA) Google Scholar
• Bertsekas D. P.Nonlinear Programming (1999) 2nd ed.(Athena Scientific, Belmont, MA) Google Scholar
• Burke J. V., Ferris M. C. Characterization of solutions sets of convex programs. Oper. Res. Lett. (1991) 10:57–60Crossref, Google Scholar
• Ceria S., Nobili P., Sassano A. A Lagrangian-based heuristic for large-scale set covering problems. Math. Programming (1998) 81(2):215–228Crossref, Google Scholar
• Feltenmark S., Kiwiel K. C. Dual applications of proximal bundle methods, including Lagrangian relaxation of nonconvex problems. SIAM J. Optim. (2000) 10(3):697–721Crossref, Google Scholar
• Fukushima M. A nonsmooth optimization approach to nonlinear multicommodity network flow problems. J. Oper. Res. Soc. Japan (1984) 27(2):151–176Google Scholar
• Fukushima M. On a dual approach to the traffic assignment problem. Transportation Res. (1984) 18:235–245Crossref, Google Scholar
• Gallo G., Pallotino S. Shortest path algorithms. Ann. Oper. Res. (1988) 13:3–79Crossref, Google Scholar
• Goffin J.-L., Contesse L., Correa R., Weintraub A. The ellipsoid method and its predecessors. Recent Advances in System Modelling and Optimization. Lecture Notes in Control and Information Sciences (1987) 87(Springer-Verlag, Berlin, Germany) 127–141Google Scholar
• Goffin J.-L., Gondzio J., Sarkissian R., Vial J.-Ph. Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Math. Programming (1996) 76(1):131–154Crossref, Google Scholar
• Gondzio J., Sarkissian R., Vial J.-Ph. Using an interior point method for the master problem in a decomposition approach. Eur. J. Oper. Res. (1997) 101:577–587Crossref, Google Scholar
• Hiriart-Urruty J.-B., Lemaréchal C.Convex Analysis and Minimization Algorithms (1993) (Springer, Berlin, Germany) Crossref, Google Scholar
• Kiwiel K. C. Proximity control in bundle methods for convex nondifferentiable minimization. Math. Programming (1990) 46:105–122Crossref, Google Scholar
• Kiwiel K. C. Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. Math. Programming (1995) 69:89–109Crossref, Google Scholar
• Kiwiel K. C. The efficiency of subgradient projection methods for convex optimization. Part II: Implementations and extensions. SIAM J. Control Optim. (1996) 34(2):677–697Crossref, Google Scholar
• Kiwiel K. C. Efficiency of proximal bundle methods. J. Optim. Theory Appl. (2000) 104(3):589–603Crossref, Google Scholar
• Kiwiel K. C. Convergence of approximate and incremental subgradient methods for convex optimization. SIAM J. Optim. (2004) 14(3):807–840Crossref, Google Scholar
• Kiwiel K. C., Lindberg P. O., Butnariu D., Censor Y., Reich S. Parallel subgradient methods for convex optimization. Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications. Studies in Computational Mathematics (2001) 8(Elsevier, Amsterdam, The Netherlands) 335–344Crossref, Google Scholar
• Kiwiel K. C., Larsson T., Lindberg P. O. Dual properties of ballstep subgradient methods, with applications to Lagrangian relaxation. (1999) . Technical Report LiTH-MAT-R-1999-24, Department of Mathematics, Linköping University, Linköping, Sweden. Revised October 2002, and December 2005Google Scholar
• Kiwiel K. C., Larsson T., Lindberg P. O. The efficiency of ballstep subgradient level methods for convex optimization. Math. Oper. Res. (1999) 24(1):237–254Link, Google Scholar
• Larsson T., Liu Z. A Lagrangean relaxation scheme for structured linear programs with application to multicommodity network flows. Optimization (1997) 40:247–284Crossref, Google Scholar
• Larsson T., Liu Z., Patriksson M. A dual scheme for traffic assignment problems. Optimization (1997) 42:323–358Crossref, Google Scholar
• Larsson T., Patriksson M., Rydergren C., Pardalos P. M., Hearn D. W., Hager W. W. Applications of simplicial decomposition with nonlinear column generation to nonlinear network flows. Network Optimization. Lecture Notes in Economics and Mathematical Systems (1997) 450(Springer-Verlag, Berlin, Germany) 346–373Crossref, Google Scholar
• Larsson T., Patriksson M., Strömberg A.-B. Ergodic convergence in subgradient optimization. Optim. Methods Software (1998) 9(1-3):93–120Crossref, Google Scholar
• Larsson T., Patriksson M., Strömberg A.-B. Ergodic, primal convergence in dual subgradient schemes for convex programming. Math. Programming (1999) 86(2):283–312Crossref, Google Scholar
• Lemaréchal C., Nemirovskii A. S., Nesterov Yu. E. New variants of bundle methods. Math. Programming (1995) 69(1):111–147Crossref, Google Scholar
• Nedić A., Bertsekas D. P. Incremental subgradient methods for nondifferentiable optimization. SIAM J. Optim. (2001) 12(1):109–138Crossref, Google Scholar
• Nedić A., Bertsekas D. P., Borkar V. S. Distributed asynchronous incremental subgradient methods. Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications. Studies in Computational Mathematics (2001) 8(Elsevier, Amsterdam, The Netherlands) 381–407Crossref, Google Scholar
• Ouorou A., Mahey P., Vial J.-Ph. A survey of algorithms for convex multicommodity flow problems. Management Sci. (2000) 46(1):126–147Link, Google Scholar
• Polyak B. T. Minimization of unsmooth functionals. Zh. Vychisl. Mat. i Mat. Fiz. (1969) 9:509–521(Russian). English transl. (1969) in U.S.S.R. Comput. Math. Math. Phys. 9(3) 14–29Google Scholar
• Polyak B. T.Introduction to Optimization (1983) (Nauka, Moscow USSR) . English transl. 1987. Optimization Software Inc., New YorkGoogle Scholar
• Rockafellar R. T.Convex Analysis (1970) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Sen S., Sherali H. D. A class of convergent primal-dual subgradient algorithms for decomposable convex programs. Math. Programming (1986) 35(3):279–297Crossref, Google Scholar
• Sherali H. D., Choi G. Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs. Oper. Res. Lett. (1996) 19:105–113Crossref, Google Scholar
• Shor N. Z.Minimization Methods for Non-Differentiable Functions (1979) (Naukova Dumka, Kiev (Russian)) . English transl., Springer-Verlag, Berlin, Germany (1985)Google Scholar
• Tatineni M., Edwards H., Boyce D. Comparison of disaggregate simplicial decomposition and Frank-Wolfe algorithms for user-optimal route choice. Transportation Res. Record (1998) 1617:157–162Crossref, Google Scholar
• Zhurbenko N. G. Investigation of a class of algorithms for minimizing nonsmooth functions and their application to the solution of large-scale problems. (1977) . Dissertation, Cybernetics Institute, Academy of Sciences of the Ukrainian SSR, Kiev, USSRGoogle Scholar