Andreas Grothey (University of Edinburgh)

Decomposition methods for nonlinear nonconvex optimization problems
Monday 18 June 2001 at 14.15, JCMB 6324


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.

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.

Seminars by year

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