| In this thesis, we reconsider the class of linear programming problems exhibiting the dual block angular structure. Using a projection over the coupling variables, we can transform any problem of this class into an equivalent convex, but nondifferentiable, optimization problem where the sum of a finite number of polyhedral convex functions is minimized over its domain. Unfortunately, the classical decomposition methods of mathematical programming do not fully exploit the non-differentiability of this equivalent problem.;We firmly believe that the classical approaches can be improved by using the ideas and methods from the field of nondifferentiable optimization, and from the philosophy of the bundle methods in particular. These methods have the basic ingredients of the decomposition algorithms but they are also characterized by special mechanisms to counteract the nondifferentiability's pitfalls.;It is surprising that despite being the main source of nondifferentiable optimization problems, there are only a few reported applications of bundle methods to any kind of decomposition. A goal of this thesis is to fill in the gaps in this area for the case of a primal decomposition approach. In order to do this, it was necessary to develop a new bundle method. Although most of the convergence results remain valid for the more general problem of the minimization of the sum of a finite number of closed convex extended functions over an arbitrary convex set, the method cannot handle this class of problems unless we do some modification to the algorithm and the functions defining the problem were not assumed to take only finite values. We assumed the existence of oracles that generate separating hyperplanes when the solution of the direction finding problem is not feasible for the original problem.;We also consider more general stabilizing terms in the direction finding problem of our method. It is not necessarily a quadratic expression of the euclidean norm. This lead us to determine the more practical dual form of the direction finding problem, expressed in terms of the so called dual norm.;Prior to the definition of the new algorithm, we have considered two different but related approaches to the problem of determining an improvement direction. Both the approaches, trust region and penalization, are based on a norm function whose aim is to restrict the optimization to a region of the space where, hopefully, the approximate descriptions of the functions are reasonably accurate.;Our algorithm is based on the penalization viewpoint, but our numerical tests were done using a trust region adaptation of the method. They allowed us to calibrate the algorithm's parameters and to compare various strategies and options. The method retained the asymptotical convergence properties of the cutting plane methods. (Abstract shortened by UMI.)... |
