Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB

Preface xi

1 Mathematical Preliminaries 1
1.1 The Space n  1
1.2 The Space m×n  2
1.3 Inner Products and Norms  2
1.4 Eigenvalues and Eigenvectors  5
1.5 Basic Topological Concepts  6
Exercises  10

2 Optimality Conditions for Unconstrained Optimization 13
2.1 Global and Local Optima  13
2.2 Classification of Matrices  17
2.3 Second Order Optimality Conditions  23
2.4 Global Optimality Conditions  30
2.5 Quadratic Functions  32
Exercises  34

3 Least Squares 37
3.1 “Solution” of Overdetermined Systems  37
3.2 Data Fitting  39
3.3 Regularized Least Squares  41
3.4 Denoising  42
3.5 Nonlinear Least Squares  45
3.6 Circle Fitting  45
Exercises  47

4 The Gradient Method 49
4.1 Descent Directions Methods  49
4.2 The Gradient Method  52
4.3 The Condition Number  58
4.4 Diagonal Scaling  63
4.5 The Gauss–Newton Method  67
4.6 The Fermat–Weber Problem  68
4.7 Convergence Analysis of the Gradient Method  73
Exercises  79

5 Newton’s Method 83
5.1 Pure Newton’s Method  83
5.2 Damped Newton’s Method  88
5.3 The Cholesky Factorization  90
Exercises  94

6 Convex Sets 97
6.1 Definition and Examples  97
6.2 Algebraic Operations with Convex Sets  100
6.3 The Convex Hull  101
6.4 Convex Cones  104
6.5 Topological Properties of Convex Sets  108
6.6 Extreme Points  111
Exercises  113

7 Convex Functions 117
7.1 Definition and Examples  117
7.2 First Order Characterizations of Convex Functions  119
7.3 Second Order Characterization of Convex Functions  123
7.4 Operations Preserving Convexity  125
7.5 Level Sets of Convex Functions  130
7.6 Continuity and Differentiability of Convex Functions  132
7.7 Extended Real-Valued Functions  135
7.8 Maxima of Convex Functions  137
7.9 Convexity and Inequalities  139
Exercises  141

8 Convex Optimization 147
8.1 Definition  147
8.2 Examples  149
8.3 The Orthogonal Projection Operator  156
8.4 CVX  158
Exercises  166

9 Optimization over a Convex Set 169
9.1 Stationarity  169
9.2 Stationarity in Convex Problems  173
9.3 The Orthogonal Projection Revisited  173
9.4 The Gradient Projection Method  175
9.5 Sparsity Constrained Problems  183
Exercises  189

10 Optimality Conditions for Linearly Constrained Problems 191
10.1 Separation and Alternative Theorems  191
10.2 The KKT conditions  195
10.3 Orthogonal Regression  203
Exercises  205

11 The KKT Conditions 207
11.1 Inequality Constrained Problems  207
11.2 Inequality and Equality Constrained Problems  210
11.3 The Convex Case  213
11.4 Constrained Least Squares  218
11.5 Second Order Optimality Conditions  222
11.6 Optimality Conditions for the Trust Region Subproblem  227
11.7 Total Least Squares  230
Exercises  233

12 Duality 237
12.1 Motivation and Definition  237
12.2 Strong Duality in the Convex Case  241
12.3 Examples  247
Exercises  270

Bibliographic Notes 275

Bibliography 277

Index 281