The subject of this thesis is the development of ways to solve structured nonlinear nonconvex programming problems by a decomposition procedure.

This thesis extends the existing decomposition methods for linear or convex problems to the nonconvex nonlinear case. The algorithms presented are in principle applicable to a general nonlinear problem, although in order to be efficient compared with a nondecomposed method a certain structure is highly advantageous.

Two main ideas are explored. In the first augmented Lagrangians are employed to relax some key constraints of the subproblems, thus guaranteeing that they are feasible for all choices of complicating variables. The resulting formulation is then decomposed by a generalized Benders decomposition scheme, resulting in a three-level problem.

As an alternative a more direct generalization of Benders decomposition is considered. The problem of infeasible subproblems is overcome here by using feasibility cuts that build up a local approximation of the (nonconvex) feasible region in the master problem.

Apart from the issue of infeasible subproblems, there are various differences from the linear/convex case, which are addressed.

**Value functions.**The subproblem value functions are shown to be piecewise differentiable nonconvex functions, whose subgradients can in general be obtained as certain Lagrange multipliers at the solution of the subproblems. Efficient ways of obtaining first and second derivatives of the value function from the subproblems are derived.**Master problem.**A bundle method is used to solve the master problems at the top and middle level of the decomposition. The bundle concept is extended to cope with nonconvex functions and to incorporate second order information of the value function as well as its subgradient. The resulting method is demonstrated to converge superlinearly. The proposed bundle method can also be used outside the decomposition framework to minimize a nonconvex nonsmooth function subject to smooth constraints.

Both algorithms have been coded and applied to a range of problems. Convergence is demonstrated on all problems. The augmented Lagrangian approach is demonstrated to converge superlinearly and also to exhibit a considerable saving of computation time compared with a nondecomposed but sparse SQP code on problems with a favourable structure. All algorithms have been linked to the modelling language AMPL to provide an easy-to-use interface for decomposition. An extension to AMPL to communicate the decomposition information has been written.

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*