Abstract
We give a bundle method for minimizing the sum of two convex functions, one of them being known only via an oracle of arbitrary accuracy. Each iteration involves solving two subproblems in which the functions are alternately represented by their linearizations. Our approach is motivated by applications to nonlinear multicommodity flow problems. Encouraging numerical experience on large scale problems is reported.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Babonneau F., Vial J.P.: ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems. Math. Program. 120, 179–210 (2009)
Babonneau F., Vial J.P.: ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems: A corrigendum. Math. Program. 120, 211–212 (2009)
Frangioni A.: Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 23, 1099–1118 (1996)
Gallo G., Pallottino S.: Shortest path algorithms. Ann. Oper. Res. 13, 3–79 (1988)
Goffin J.L.: The ellipsoid method and its predecessors. In: Contesse, L., Correa, R., Weintraub, A. (eds) Recent Advances in System Modelling and Optimization, Lecture Notes in Control and Information Sciences 87, pp. 127–141. Springer, Berlin (1987)
Goffin J.L., Gondzio J., Sarkissian R., Vial J.P.: Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Math. Program. 76, 131–154 (1996)
Hiriart-Urruty J.B., Lemaréchal C.: Convex Analysis and Minimization Algorithms. Springer, Berlin (1993)
Kiwiel K.C.: A method for solving certain quadratic programming problems arising in nonsmooth optimization. IMA J. Numer. Anal. 6, 137–152 (1986)
Kiwiel K.C.: Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program. 46, 105–122 (1990)
Kiwiel K.C.: A Cholesky dual method for proximal piecewise linear programming. Numer. Math. 68, 325–340 (1994)
Kiwiel K.C.: A projection-proximal bundle method for convex nondifferentiable minimization. In: Théra, M., Tichatschke, R. (eds) Ill-posed Variational Problems and Regularization Techniques, Lecture Notes in Economics and Mathematical Systems 477, pp. 137–150. Springer, Berlin (1999)
Kiwiel K.C.: A proximal bundle method with approximate subgradient linearizations. SIAM J. Optim. 16, 1007–1023 (2006)
Kiwiel K.C.: A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming. SIAM J. Optim. 17, 1015–1034 (2006)
Kiwiel K.C., Larsson T., Lindberg P.O.: Lagrangian relaxation via ballstep subgradient methods. Math. Oper. Res. 32, 669–686 (2007)
Kiwiel K.C., Lemaréchal C.: An inexact bundle variant suited to column generation. Math. Program. 118, 177–206 (2009)
Kiwiel K.C., Rosa C.H., Ruszczyński A.: Proximal decomposition via alternating linearization. SIAM J. Optim. 9, 668–689 (1999)
Lemaréchal, C., Ouorou, A., Petrou, G.: A bundle-type algorithm for routing in telecommunication data networks. Comput. Optim. Appl. (2007). doi:10.1007/s10589-007-9160-7
Martinet B.: Régularisation d’inéquations variationelles par approximations successives. RAIRO Rech. Opér. 4(R3), 154–158 (1970)
Ouorou A., Mahey P., Vial J.P.: A survey of algorithms for convex multicommodity flow problems. Manag. Sci. 46, 126–147 (2000)
Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Rockafellar R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by the Polish Ministry of Science and Higher Education Grant No. N N514 408736.
Rights and permissions
About this article
Cite this article
Kiwiel, K.C. An alternating linearization bundle method for convex optimization and nonlinear multicommodity flow problems. Math. Program. 130, 59–84 (2011). https://doi.org/10.1007/s10107-009-0327-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-009-0327-0
Keywords
- Nondifferentiable optimization
- Convex programming
- Proximal bundle methods
- Approximate subgradients
- Network flow problem