caa a22 4500 475769147 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000101xx s 000 0 eng 10.1007/s101079900112 doi (NATIONALLICENCE)springer-10.1007/s101079900112 An outer approximate subdifferential method for piecewise affine optimization [Elektronische Daten] [Philip Neame, Natashia Boland, Daniel Ralph] Abstract. : Piecewise affine functions arise from Lagrangian duals of integer programming problems, and optimizing them provides good bounds for use in a branch and bound method. Methods such as the subgradient method and bundle methods assume only one subgradient is available at each point, but in many situations there is more information available. We present a new method for optimizing such functions, which is related to steepest descent, but uses an outer approximation to the subdifferential to avoid some of the numerical problems with the steepest descent approach. We provide convergence results for a class of outer approximations, and then develop a practical algorithm using such an approximation for the compact dual to the linear programming relaxation of the uncapacitated facility location problem. We make a numerical comparison of our outer approximation method with the projection method of Conn and Cornuéjols, and the bundle method of Schramm and Zowe. Springer-Verlag Berlin Heidelberg, 2000 Key words: uncapacitated facility location - approximate subdifferential - bundle method - Lagrangian dual - piecewise affine functions nationallicence Neame Philip Department of Engineering Science, University of Auckland, New Zealand, e-mail: p.neame@auckland.ac.nz, NZ aut Boland Natashia Department of Mathematics and Statistics, University of Melbourne, Australia, AU aut Ralph Daniel Department of Mathematics and Statistics, University of Melbourne, Australia, AU aut https://doi.org/10.1007/s101079900112 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101079900112 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Neame Philip Department of Engineering Science, University of Auckland, New Zealand, e-mail: p.neame@auckland.ac.nz, NZ aut NATIONALLICENCE 700 1- Boland Natashia Department of Mathematics and Statistics, University of Melbourne, Australia, AU aut NATIONALLICENCE 700 1- Ralph Daniel Department of Mathematics and Statistics, University of Melbourne, Australia, AU aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer