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

✍ Scribed by Amir Beck

• Publisher: SIAM
• Year: 2014
• Tongue: English
• Leaves: 290
• Series: MOS-Siam Series on Optimization
• Category: Library

✦ Synopsis

This book provides the foundations of the theory of nonlinear optimization as well as some related algorithms and presents a variety of applications from diverse areas of applied sciences. The author combines three pillars of optimization—theoretical and algorithmic foundation, familiarity with various applications, and the ability to apply the theory and algorithms on actual problems—and rigorously and gradually builds the connection between theory, algorithms, applications, and implementation.

more than 170 theoretical, algorithmic, and numerical exercises that deepen and enhance the reader's understanding of the topics;
several subjects not typically found in optimization books—for example, optimality conditions in sparsity-constrained optimization, hidden convexity, and total least squares;
a large number of applications discussed theoretically and algorithmically, such as circle fitting, Chebyshev center, the Fermat–Weber problem, denoising, clustering, total least squares, and orthogonal regression; and
theoretical and algorithmic topics demonstrated by the MATLAB® toolbox CVX and a package of m-files that is posted on the book’s web site.

Audience
This book is intended for graduate or advanced undergraduate students of mathematics, computer science, and electrical engineering as well as other engineering departments. The book will also be of interest to researchers.

About the Author
Amir Beck is an Associate Professor in the Department of Industrial Engineering at The Technion—Israel Institute of Technology. He has published numerous papers, has given invited lectures at international conferences, and was awarded the Salomon Simon Mani Award for Excellence in Teaching and the Henry Taub Research Prize. He is on the editorial board of Mathematics of Operations Research, Operations Research, and Journal of Optimization Theory and Applications. His research interests are in continuous optimization, including theory, algorithmic analysis, and applications.

✦ Table of Contents

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

✦ Subjects

Математика;Методы оптимизации;