000216950 001__ 216950
000216950 005__ 20190509132552.0
000216950 0247_ $$2doi$$a10.5075/epfl-thesis-6875
000216950 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis6875-8
000216950 02471 $$2nebis$$a10598840
000216950 037__ $$aTHESIS
000216950 041__ $$aeng
000216950 088__ $$a6875
000216950 245__ $$aDecomposition Strategies for Nonconvex Problems, a Parametric Approach
000216950 269__ $$a2016
000216950 260__ $$bEPFL$$c2016$$aLausanne
000216950 300__ $$a256
000216950 336__ $$aTheses
000216950 502__ $$aProf. Mario Paolone (président) ; Prof. Colin Neil Jones (directeur de thèse) ; Prof. Daniel Kressner, Prof. Moritz Diehl, Prof. Jérôme  Bolte (rapporteurs)
000216950 520__ $$aThis 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.
000216950 6531_ $$aDecomposition
000216950 6531_ $$acontinuation
000216950 6531_ $$anonconvex optimisation
000216950 6531_ $$aparametric optimisation
000216950 6531_ $$aalternating minimisations
000216950 6531_ $$atrust region methods
000216950 6531_ $$aaugmented Lagrangian methods
000216950 6531_ $$aKurdyka-Lojasiewicz property
000216950 6531_ $$aoptimal control
000216950 6531_ $$anonlinear model predictive control
000216950 700__ $$0246475$$g213816$$aHours, Jean-Hubert
000216950 720_2 $$aJones, Colin Neil$$edir.$$g207237$$0246471
000216950 8564_ $$uhttps://infoscience.epfl.ch/record/216950/files/EPFL_TH6875.pdf$$zn/a$$s10552322$$yn/a
000216950 909C0 $$xU12397$$0252490$$pLA3
000216950 909CO $$pthesis$$pthesis-bn2018$$pDOI$$ooai:infoscience.tind.io:216950$$qDOI2$$qGLOBAL_SET$$pSTI
000216950 918__ $$dEDEE$$cIGM$$aSTI
000216950 919__ $$aLA3
000216950 917Z8 $$x108898
000216950 917Z8 $$x108898
000216950 917Z8 $$x108898
000216950 920__ $$b2016$$a2016-2-26
000216950 973__ $$sPUBLISHED$$aEPFL
000216950 970__ $$a6875/THESES
000216950 980__ $$aTHESIS