LOGARITHMIC BARRIER DECOMPOSITION METHODS FOR SEMI-INFINITE PROGRAMMING

D.Haglin, J. Kaliski, C. Roos, T. Terlaky

A computational study of some logarithmic barrier decomposition algorithms for semi--infinite programming is presented in this paper. The conceptual algorithm is a straightforward adaptation of the logarithmic barrier cutting plane algorithm which was presented recently by den Hertog et al., to solve semi-infinite programming problems. Usually decomposition (cutting plane methods) use cutting planes to improve the localization of the given problem. In this paper we propose an extension which uses linear cuts to solve large scale, difficult real world problems. This algorithm uses both static and (doubly) dynamic enumeration of the parameter space and allows for multiple cuts to be simultaneously added for larger/difficult problems. The algorithm is implemented both on sequential and parallel computers. Implementation issues and parallelization strategies are discussed and encouraging computational results are presented. Key Words: column generation, convex programming, cutting plane methods, linear programming, quadratic programming, interior point method, logarithmic barrier function, semi--infinite programming.

TR-1996-51 Delft University of Technology, P.O.Box 5031, 2600 GA, Delft, The Netherlands

Contact: t.terlaky@twi.tudelft.nl


 [PS]  [IP PAGE]  [SEARCH AGAIN]