Lecture Notes on Numerical Optimization
                    (Preliminary Draft)
                       Moritz Diehl
          Department of Microsystems Engineering and Department of Mathematics,
                   University of Freiburg, Germany
                 moritz.diehl@imtek.uni-freiburg.de
                       March 3, 2016
                                                 1
       Preface
       Thiscourse’s aim is to give an introduction into numerical methods for the solution of optimization
       problems in science and engineering. It is intended for students from two faculties, mathematics
       and physics on the one hand, and engineering and computer science on the other hand. The
       course’s focus is on continuous optimization (rather than discrete optimization) with special em-
       phasis on nonlinear programming. For this reason, the course is in large parts based on the
       excellent text book “Numerical Optimization” by Jorge Nocedal and Steve Wright [4]. This book
       appeared in Springer Verlag and is available at the ACCO book shop as well as at VTK and rec-
       ommended to the students. Besides nonlinear programming, we discuss important and beautiful
       concepts from the field of convex optimization that we believe to be important to all users and
       developers of optimization methods. These contents and much more are covered by the equally
       excellent text book “Convex Optimization” by Stephen Boyd and Lieven Vandenberghe [2], that
       was published by Cambridge University Press (CUP). Fortunately, this book is also freely avail-
       able and can be downloaded from the home page of Stephen Boyd in form of a completely legal
       PDFcopy of the CUP book. An excellent textbook on nonlinear optimization that contains also
       many MATLAB exercises was recently written by Amir Beck [1].
       The course is divided into four major parts:
         • Fundamental Concepts of Optimization
         • Unconstrained Optimization and Newton-Type Algorithms
         • Equality Constrained Optimization
         • Inequality Constrained Optimization
       followed by two appendices, the first containing the description of one student project done during
       the course exercises, and some remarks intended to help with exam preparation (including a list
       of questions and answers).
       Thewriting of this lecture manuscript started at the Optimization in Engineering Center OPTEC
       of KU Leuven in 2007, with major help of Jan Bouckaert (who did, among other, most of the the
       figures), David Ariens, and Laurent Sorber. Dr. Carlo Savorgnan and to many students helped
       with feedback and with spotting errors in the last years. The latest version was compiled at the
       University of Freiburg with the help of Dimitris Kouzoupis.
       Moritz Diehl,
       Leuven and Freiburg,
       October 2015.
       moritz.diehl@imtek.uni-freiburg.de
                  Contents
                     Preface    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    1
                  I   Fundamental Concepts of Optimization                                                                   5
                  1 Fundamental Concepts of Optimization                                                                     6
                     1.1   WhyOptimization? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .            6
                     1.2   What Characterizes an Optimization Problem? . . . . . . . . . . . . . . . . . . . .               6
                     1.3   Mathematical Formulation in Standard Form . . . . . . . . . . . . . . . . . . . . .               7
                     1.4   Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      8
                     1.5   When Do Minimizers Exist? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           9
                     1.6   Mathematical Notation        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    9
                  2 Types of Optimization Problems                                                                          11
                     2.1   Nonlinear Programming (NLP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .            11
                     2.2   Linear Programming (LP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          11
                     2.3   Quadratic Programming (QP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           13
                     2.4   General Convex Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . .             14
                     2.5   Unconstrained Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . .            17
                     2.6   Non-Differentiable Optimization Problems . . . . . . . . . . . . . . . . . . . . . . .            17
                     2.7   Mixed-Integer Programming (MIP) . . . . . . . . . . . . . . . . . . . . . . . . . . .            18
                  3 Convex Optimization                                                                                     20
                     3.1   How to Check Convexity of Functions? . . . . . . . . . . . . . . . . . . . . . . . . .           20
                     3.2   Which Sets are Convex, and which Operations Preserve Convexity? . . . . . . . . .                23
                     3.3   Examples for Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         23
                     3.4   Which Operations Preserve Convexity of Functions? . . . . . . . . . . . . . . . . .              24
                     3.5   Standard Form of a Convex Optimization Problem . . . . . . . . . . . . . . . . . .               24
                     3.6   Semidefinite Programming (SDP) . . . . . . . . . . . . . . . . . . . . . . . . . . . .            25
                     3.7   An Optimality Condition for Convex Problems . . . . . . . . . . . . . . . . . . . .              26
                  4 The Lagrangian Function and Duality                                                                     28
                     4.1   Lagrange Dual Function and Weak Duality . . . . . . . . . . . . . . . . . . . . . .              29
                     4.2   Strong Duality for Convex Problems . . . . . . . . . . . . . . . . . . . . . . . . . .           30
                                                                        2
                  CONTENTS                                                                                                   3
                  II   Unconstrained Optimization and Newton-Type Algorithms                                                36
                  5 Optimality Conditions                                                                                   37
                     5.1   Necessary Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . .          37
                     5.2   Sufficient Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . .           38
                     5.3   Perturbation Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        39
                  6 Estimation and Fitting Problems                                                                         41
                     6.1   Linear Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       42
                     6.2   Ill Posed Linear Least Squares       . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   44
                     6.3   Regularization for Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . .         46
                     6.4   Statistical Derivation of Least Squares . . . . . . . . . . . . . . . . . . . . . . . . .        47
                     6.5   L1-Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      48
                     6.6   Gauss-Newton (GN) Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             49
                     6.7   Levenberg-Marquardt (LM) Method . . . . . . . . . . . . . . . . . . . . . . . . . .              50
                  7 Newton Type Optimization                                                                                51
                     7.1   Exact Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          51
                     7.2   Local Convergence Rates        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   52
                     7.3   Newton Type Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          55
                  8 Local Convergence of General Newton Type Iterations                                                     58
                     8.1   ALocal Contraction Theorem for Newton Type Iterations . . . . . . . . . . . . . .                59
                     8.2   Affine Invariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        60
                     8.3   Local Convergence for Newton Type Optimization Methods . . . . . . . . . . . . .                 61
                     8.4   Necessary and Sufficient Conditions for Local Convergence . . . . . . . . . . . . . .              62
                  9 Globalization Strategies                                                                                65
                     9.1   Line-Search based on Armijo Condition with Backtracking . . . . . . . . . . . . . .              65
                     9.2   Alternative: Line Search based on the Wolfe Conditions . . . . . . . . . . . . . . .             67
                     9.3   Global Convergence of Line Search with Armijo Backtracking . . . . . . . . . . . .               69
                     9.4   Trust-Region Methods (TR) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          70
                     9.5   The Cauchy Point and How to Compute the TR Step . . . . . . . . . . . . . . . .                  71
                  10 Calculating Derivatives                                                                                74
                     10.1 Algorithmic Differentiation (AD) . . . . . . . . . . . . . . . . . . . . . . . . . . . .           75
                     10.2 The Forward Mode of AD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .            77
                     10.3 The Backward Mode of AD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             79
                     10.4 Algorithmic Differentiation Software . . . . . . . . . . . . . . . . . . . . . . . . . .           83
                  III   Equality Constrained Optimization                                                                   84
                  11 Optimality Conditions for Equality Constrained Problems                                                85
                     11.1 Constraint Qualification and Linearized Feasible Cone . . . . . . . . . . . . . . . .              86
                     11.2 Second Order Conditions         . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   90
                     11.3 Perturbation Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         90