Introduction to nonlinear optimization : theory, algorithms, and applications with MATLAB

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. 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 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. Readers will find more than 170 theoretical, algorithmic, and numerical exercises that deepen and enhance the reader's understanding of the topics. The author includes several subjects not typically found in optimization books-for example, optimality conditions in sparsity-constrained optimization, hidden convexity, and total least squares. The book also offers 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. Contents : Chapter 1: Mathematical Preliminaries; Chapter 2: Optimality Conditions for Unconstrained Optimization; Chapter 3: Least Squares; Chapter 4: The Gradient Method; Chapter 5: Newton s Method; Chapter 6: Convex Sets; Chapter 7: Convex Functions; Chapter 8: Convex Optimization; Chapter 9: Optimization Over a Convex Set; Chapter 10: Optimality Conditions for Linearly Constrained Problems; Chapter 11: The KKT Conditions; Chapter 12: Duality 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. 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. Readers Will Find More Than 170 Theoretical, Algorithmic, And Numerical Exercises That Deepen And Enhance The Reader's Understanding Of The Topics. The Author Includes Offers Several Subjects Not Typically Found In Optimization Books?for Example, Optimality Conditions In Sparsity-constrained Optimization, Hidden Convexity, And Total Least Squares. The Book Also Offers 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.