This book emerged from the idea that an optimization training should include three
basic components: a strong theoretical and algorithmic foundation, familiarity with
various applications, and the ability to apply the theory and algorithms on actual “real-life”
problems. The book is intended to be the basis of such an extensive training. The
mathematical development of the main concepts in nonlinear optimization is done rigorously,
where a special effort was made to keep the proofs as simple as possible. The results
are presented gradually and accompanied with many illustrative examples. Since the aim
is not to give an encyclopedic overview, the focus is on the most useful and important
concepts. The theory is complemented by numerous discussions on applications from
various scientific fields such as signal processing, economics and localization. Some basic
algorithms are also presented and studied to provide some flavor of this important aspect
of optimization. Many topics are demonstrated by MATLAB programs, and ideally, the
interested reader will find satisfaction in the ability of actually solving problems on his or
her own. The book contains several topics that, compared to other classical textbooks,
are treated differently. The following are some examples of the less common issues.
Author(s): Amir Beck
Publisher: SIAM
Year: 2014
Language: English
Pages: 294
Beck, Amir .Introduction to nonlinear optimization_theory, algorithms, and applications with MATLAB 2014 ......Page 4
Copyright ......Page 5
Contents ......Page 7
Preface xi ......Page 10
1.1 The Space Rn 1 ......Page 12
1.3 Inner Products and Norms 2 ......Page 13
1.4 Eigenvalues and Eigenvectors 5 ......Page 16
1.5 Basic Topological Concepts 6 ......Page 17
Exercises 10 ......Page 21
2.1 Global and Local Optima 13 ......Page 24
2.2 Classification of Matrices 17 ......Page 28
2.3 Second Order Optimality Conditions 23 ......Page 34
2.4 Global Optimality Conditions 30 ......Page 41
2.5 Quadratic Functions 32 ......Page 43
Exercises 34 ......Page 45
3.1 “Solution” of Overdetermined Systems 37 ......Page 48
3.2 Data Fitting 39 ......Page 50
3.3 Regularized Least Squares 41 ......Page 52
3.4 Denoising 42 ......Page 53
3.6 Circle Fitting 45 ......Page 56
Exercises 47 ......Page 58
4.1 Descent Directions Methods 49 ......Page 60
4.2 The Gradient Method 52 ......Page 63
4.3 The Condition Number 58 ......Page 69
4.4 Diagonal Scaling 63 ......Page 74
4.5 The Gauss-Newton Method 67 ......Page 78
4.6 The Fermat-Weber Problem 68 ......Page 79
4.7 Convergence Analysis of the Gradient Method 73 ......Page 84
Exercises 79 ......Page 90
5.1 Pure Newton’s Method 83 ......Page 94
5.2 Damped Newton’s Method 88 ......Page 99
5.3 The Cholesky Factorization 90 ......Page 101
Exercises 94 ......Page 105
6.1 Definition and Examples 97 ......Page 108
6.2 Algebraic Operations with Convex Sets 100 ......Page 111
6.3 The Convex Hull 101 ......Page 112
6.4 Convex Cones 104 ......Page 115
6.5 Topological Properties of Convex Sets 108 ......Page 119
6.6 Extreme Points 111......Page 122
Exercises 113 ......Page 124
7.1 Definition and Examples 117 ......Page 128
7.2 First Order Characterizations of Convex Functions 119 ......Page 130
7.3 Second Order Characterization of Convex Functions 123 ......Page 134
7.4 Operations Preserving Convexity 125 ......Page 136
7.5 Level Sets of Convex Functions 130 ......Page 141
7.6 Continuity and Differentiability of Convex Functions 132 ......Page 143
7.7 Extended Real-Valued Functions 135 ......Page 146
7.8 Maxima of Convex Functions 137 ......Page 148
7.9 Convexity and Inequalities 139 ......Page 150
Exercises 141 ......Page 152
8.1 Definition 147 ......Page 158
8.2 Examples 149 ......Page 160
8.3 The Orthogonal Projection Operator 156 ......Page 167
8.4 CVX 158 ......Page 169
Exercises 166 ......Page 177
9.1 Stationarity 169 ......Page 180
9.3 The Orthogonal Projection Revisited 173 ......Page 184
9.4 The Gradient Projection Method 175 ......Page 186
9.5 Sparsity Constrained Problems 183 ......Page 194
Exercises 189 ......Page 200
10.1 Separation and Alternative Theorems 191 ......Page 202
10.2 The KKT conditions 195 ......Page 206
10.3 Orthogonal Regression 203 ......Page 214
Exercises 205 ......Page 216
11.1 Inequality Constrained Problems 207 ......Page 218
11.2 Inequality and Equality Constrained Problems 210 ......Page 221
11.3 The Convex Case 213 ......Page 224
11.4 Constrained Least Squares 218......Page 229
11.5 Second Order Optimality Conditions 222 ......Page 233
11.6 Optimality Conditions for the Trust Region Subproblem 227 ......Page 238
11.7 Total Least Squares 230 ......Page 241
Exercises 233 ......Page 244
12.1 Motivation and Definition 237 ......Page 248
12.2 Strong Duality in the Convex Case 241 ......Page 252
12.3 Examples 247 ......Page 258
Exercises 270 ......Page 281
Bibliographic Notes 275 ......Page 286
Bibliography 277 ......Page 288
Index 281 ......Page 292
cover......Page 1
