ITEM METADATA RECORD
Title: Sequential Convex Programming and Decomposition Approaches for Nonlinear Optimization (Sequentiële convex programmeren en ontbindingsmethoden voor niet-lineaire optimalisering)
Other Titles: Sequential Convex Programming and Decomposition Approaches for Nonlinear Optimization
Authors: Tran Dinh, Quoc
Issue Date: 7-Nov-2012
Abstract: This thesis is devoted to studying numerical solution methods for some classes of nonlinear optimization problems. These methods are motivated from the fact that many optimization problems in practice possess certain structures such as convexity, separability and sparsity. Moreover, solving a convex optimization problem is more efficient and reliable than a nonconvex one by using the state-of-the-art of convex optimization algorithms. Exploiting such specific structures and convex optimization techniques can lead to more efficient and reliable solution methods than conventional approaches.The content of the thesis is divided into two parts. Part I studies the sequential convex programming approach for solving nonconvex optimization problems, both parametric nonlinear programming and nonconvex semidefinite programming. Ageneric algorithmic framework which we call adjoint-based predictor-corrector sequential convex programming is proposed to treat parametric nonconvex optimization problems with general convex constraints. The algorithm is based on three ingredients, namely sequential convex programming, predictor-corrector path-following and adjoint-based optimization. The stability of the tracking errorsbetween approximation solutions and the true ones is proved. Without parameters, the algorithm collapses to the one which we call the sequential convex programming (SCP) method for solving nonconvex optimization problems. As a special case of SCP, we develop a generalized inner convex approximation method and a generalized convex-concave decomposition algorithm for solving a class of nonconvex semidefinite programming problems. We also show applications of these algorithms in static state/output feedback controller design. Numerical results are benchmarked via several standard numerical examples.Part II deals with decomposition approaches for separable optimization, both in the convex and nonconvex case. We develop several decomposition methods for solving separable convex optimization problems. The first class of algorithms is based on two main ingredients, namely smoothing via prox-functions and the excessive gap technique. The convergence of these algorithms is proved and the convergence rate is estimated. Extensions to the strongly convex case and inexact cases are also considered. The second class of algorithms makes use of smoothing techniques via self-concordant barrier functions and a path-following method.The algorithms developed in this part can be implemented in a parallel or distributed fashion. Several algorithmic variants are tested in numerical examples. We also show an application of these algorithms to the nonconvex case. This leads to a two- level decomposition algorithm for solving a class of separable nonconvex optimization problems.
Table of Contents: Contents v
List of acronyms and notations ix
1 Introduction 1
1.1 Motivation and objectives . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Three main concepts . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Contributions of the thesis and overview . . . . . . . . . . . . . 8
I Sequential Convex Programming 13
2 Predictor-corrector sequential convex programming 15
2.1 Problem statement and contribution . . . . . . . . . . . . . . . 15
2.2 Three ingredients of the algorithm . . . . . . . . . . . . . . . . 17
2.3 Adjoint-based predictor-corrector SCP algorithm . . . . . . . . 22
2.4 Contraction estimate . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Applications in nonlinear programming . . . . . . . . . . . . . 39
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 SCP applications in optimal control 43
3.1 NMPC of a hydro power plant . . . . . . . . . . . . . . . . . . 43
3.2 Time optimal trajectory planning problem . . . . . . . . . . . . 52
4 Inner convex approximation methods for nonconvex SDP 63
4.1 A short literature review and contribution . . . . . . . . . . . . 63
4.2 Problem statement and optimality condition . . . . . . . . . . . 65
4.3 Generalized inner convex approximation algorithms . . . . . . . 69
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5 BMI optimization in robust controller design 81
5.1 BMI optimization in static feedback control . . . . . . . . . . . . 81
5.2 Implementation details . . . . . . . . . . . . . . . . . . . . . . . 82
5.3 Linear output-feedback controller design . . . . . . . . . . . . . 85
5.4 H2 control: BMI optimization approach . . . . . . . . . . . . . 90
5.5 H1 control: BMI optimization approach . . . . . . . . . . . . . 94
5.6 Mixed H2/H1 control: BMI optimization approach . . . . . . 95
5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
II Decomposition in Separable Optimization 103
6 Existing approaches in separable optimization 105
6.1 Problem statements . . . . . . . . . . . . . . . . . . . . . . . . 106
6.2 Related existing approaches . . . . . . . . . . . . . . . . . . . . 108
6.3 Lagrangian decomposition in separable convex programming . . . 111
6.4 Parallel algorithms vs distributed algorithms . . . . . . . . . . 112
6.5 Benchmarking algorithms with performance profiles . . . . . . 114
7 Dual decomposition algorithms via the excessive gap technique 117
7.1 Smoothing via proximity functions . . . . . . . . . . . . . . . . 118
7.2 Solution of primal subproblems and excessive gap condition . . 124
7.3 Decomposition algorithm with two primal steps . . . . . . . . . 128
7.4 Decomposition algorithm with two dual steps . . . . . . . . . . 132
7.5 Decomposition algorithms with switching steps . . . . . . . . . 137
7.6 Application to strongly convex case . . . . . . . . . . . . . . . . 142
7.7 Extensions to inexact case . . . . . . . . . . . . . . . . . . . . . 144
7.8 Comparison and implementation aspects . . . . . . . . . . . . . 149
7.9 Numerical tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8 Path-following gradient decomposition algorithms 163
8.1 Smoothing via self-concordant barrier functions . . . . . . . . . 164
8.2 Path-following gradient-based decomposition algorithm . . . . . 174
8.3 Accelerating gradient decomposition algorithm . . . . . . . . . . 181
8.4 Numerical tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
9 An inexact perturbed path-following decomposition algorithm 191
9.1 Self-concordance of smoothed dual function . . . . . . . . . . . 192
9.2 Inexact perturbed path-following decomposition method . . . . 195
9.3 Exact path-following decomposition algorithm . . . . . . . . . . 210
9.4 Discussion on implementation . . . . . . . . . . . . . . . . . . . 213
9.5 Numerical tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
9.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
10 Application to separable nonconvex optimization 219
10.1 SCP approach for separable nonconvex optimization . . . . . . 220
10.2 Two-level decomposition algorithm . . . . . . . . . . . . . . . . 227
10.3 Numerical tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
10.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
11 Conclusion 233
11.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
11.2 Future research directions . . . . . . . . . . . . . . . . . . . . . 236
A The proof of technical statements 239
A.1 The proof of technical statements in Chapter 7 . . . . . . . . . 239
A.2 The proof of technical statements in Chapter 9 . . . . . . . . . . 251
Bibliography 259
Publications by the author contains in the thesis 277
ISBN: 978-94-6018-589-2
Publication status: published
KU Leuven publication type: TH
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics

Files in This Item:
File Status SizeFormat
Tran_PhD_Thesis_onlinever.pdf Published 3078KbAdobe PDFView/Open

These files are only available to some KU Leuven staff members

 


All items in Lirias are protected by copyright, with all rights reserved.