Decomposition Strategies for Nonconvex Problems, a Parametric Approach

This thesis deals with the development of numerical methods for solving nonconvex optimisation problems by means of decomposition and continuation techniques. We first introduce a novel decomposition algorithm based on alternating gradient projections and augmented Lagrangian relaxations. A proof of local convergence is given under standard assumptions. The effect of different stopping criteria on the convergence of the augmented Lagrangian loop is investigated. As a second step, a trust region algorithm for distributed nonlinear programs, named TRAP, is introduced. Its salient ingredient is an alternating gradient projection for computing a set of active constraints in a distributed manner, which is a novelty for trust region techniques. Global convergence as well as local almost superlinear convergence are proven. The numerical performance of the algorithm is assessed on nonconvex optimal power flow problems. The core of this thesis is the development and analysis of an augmented Lagrangian algorithm for tracking parameter-dependent optima. Despite their interesting features for large-scale and distributed optimisation, augmented Lagrangian methods have not been designed and fully analysed in a parametric setting. Therefore, we propose a novel optimality-tracking scheme that consists of fixed number of descent steps computed on an augmented Lagrangian subproblem and one dual update per parameter change. It is shown that the descent steps can be performed by means of first-order as well as trust region methods. Using the Kurdyka-Lojasiewicz property, an analysis of the local convergence rate of a class of trust region Newton methods is provided without relying on the finite detection of an optimal active set. This allows us to establish a contraction inequality for the parametric augmented Lagrangian algorithm. Hence, stability of the continuation scheme can be proven under mild assumptions. The effect of the number of primal iterations and the penalty is analysed by means of numerical examples. Finally, the efficacy of the augmented Lagrangian continuation scheme is successfully demonstrated on three examples in the field of optimal control. The first two examples consists of a real-time NMPC algorithm based on a multiple-shooting discretisation. In particular, it is shown that our C++ software package is competitive with the state-of-the-art codes on NMPC problems with long prediction horizons, and can address a more general class of real-time NMPC problems. The third case study is the distributed computation of solutions to multi-stage nonconvex optimal power flow problems in a real-time setting.