Lecture Notes on Numerical Optimization
                       ´
                   Miguel A. Carreira-Perpin˜´an
                EECS, University of California, Merced
                      December 30, 2020
      These are notes for a one-semester graduate course on numerical optimisation given by Prof.
        ´
     Miguel A. Carreira-Perpin˜´an at the University of California, Merced. The notes are largely based
     on the book “Numerical Optimization” by Jorge Nocedal and Stephen J. Wright (Springer, 2nd ed.,
     2006), with some additions.
      These notes may be used for educational, non-commercial purposes.
       c        ´
      
2005–2020 Miguel A. Carreira-Perpin˜´an
                 1        Introduction
                      • Goal: describe the basic concepts & main state-of-the-art algorithms for continuous optimiza-
                          tion.
                      • The optimization problem: 
                                                 minf(x) s.t.               ci(x) = 0;         i ∈ E      equality constraints (scalar)
                                                x∈Rn                        ci(x) ≥ 0;         i ∈ I      inequality constraints (scalar)
                          x: variables (vector); f(x): objective function (scalar).
                          Feasible region: set of points satisfying all constraints.
                          maxf ≡−min−f.                                                                 
                                                                                                               2
                                                                                                             x −x ≤0
                      • Ex. (fig. 1.1): min                     (x −2)2+(x −1)2 s.t.                            1       2
                                                       x1;x2       1                  2                      x +x ≤2:
                                                                                                               1       2
                      • Ex.: transportation problem (LP)
                                                                               Px ≤a ∀i (capacityoffactory i)
                                                       X                        j ij                i
                                              min            c x        s.t.        Px ≥b ∀i                        (demand of shop j)
                                              {x }            ij   ij           i ij                j
                                                 ij     i;j                         x ≥0                  ∀i;j      (nonnegative production)
                                                                                      ij
                          c : shipping cost; x : amount of product shipped from factory i to shop j.
                           ij                             ij
                      • Ex.: LSQ problem: fit a parametric model (e.g. line, polynomial, neural net...) to a data set.                                                                  Ex. 2.1
                      • Optimization algorithms are iterative: build sequence of points that converges to the solution.
                          Needs good initial point (often by prior knowledge).
                      • Focus on many-variable problems (but will illustrate in 2D).
                      • Desiderata for algorithms:
                              – Robustness: perform well on wide variety of problems in their class, for any starting point;
                              – Efficiency: little computer time or storage;
                              – Accuracy: identify solution precisely (within the limits of fixed-point arithmetic).
                          They conflict with each other.
                      • General commentaboutoptimization(Fletcher): “fascinating blend of theory and computation,
                          heuristics and rigour”.
                              – No universal algorithm: a given algorithm works well with a given class of problems.
                              – Necessary to adapt a method to the problem at hand (by experimenting).
                              – Not choosing an appropriate algorithm → solution found very slowly or not at all.
                      • Not covered in the Nocedal & Wright book, or in this course:
                              – Discrete optimization (integer programming): the variables are discrete. Ex.: integer
                                  transportation problem, traveling salesman problem.
                                     ∗ Hardertosolve thancontinuous opt(in the latter we can predict the objective function
                                         value at nearby points).
                                                                                                 1
               ∗ Too many solutions to count them.
               ∗ Rounding typically gives very bad solutions.
               ∗ Highly specialized techniques for each problem type.
              Ref: Papadimitriou & Steiglitz 1982.
            – Network opt: shortest paths, max flow, min cost flow, assignments & matchings, MST,
              dynamic programming, graph partitioning...
              Ref: Ahuja, Magnanti & Orlin 1993.
            – Non-smooth opt: discontinuous derivatives, e.g. L -norm.
                                              1
              Ref: Fletcher 1987.
            – Stochastic opt: the model is specified with uncertainty, e.g. x ≤ b where b could be given
              by a probability density function.
            – Global opt: find the global minimum, not just a local one. Very difficult.
              Some heuristics: simulated annealing, genetic algorithms, evolutionary computation.
            – Multiobjective opt: one approach is to transform it to a single objective = linear combi-
              nations of objectives.
            – EMalgorithm(Expectation-Maximization): specialized technique for maximum likelihood
              estimation of probabilistic models.
              Ref: McLachlan & Krishnan 2008; many books on statistics or machine learning.
            – Calculus of variations: stationary point of a functional (= function of functions).
            – Convex optimization: we’ll see some of this.
              Ref: Boyd & Vandenberghe 2003.
            – Modeling: the setup of the opt problem, i.e., the process of identifying objective, variables
              and constraints for a given problem. Very important but application-dependent.
              Ref: Dantzig 1963; Ahuja, Magnanti & Orlin 1993.
         • Course contents: derivative-based methods for continuous optimization (see syllabus).
                                       2
            2     Fundamentals of unconstrained optimization
            Problem: minf(x); x ∈ Rn.
            Conditions for a local minimum x∗ (cf.casen=1)
                                            ∗                   n
                • Global minimizer: f(x ) ≤ f(x) ∀x ∈ R .
                                                                  ∗      ∗
                • Local minimizer: ∃ neighborhood N of x : f(x ) ≤ f(x) ∀x ∈ N.
                                                              ∗                       ∗                              4    ∗
                • Strict (or strong) local minimizer: f(x ) < f(x) ∀x ∈ N\{x }. (Ex. f(x)=3 vs f(x)=(x−2) at x =2.)
                                                        ∗              ∗                                            4   1    4
                • Isolated local minimizer: ∃N of x such that x is the only local min. in N. (Ex.f(x)=x cos x+2x
                  with f(0) = 0 has a strict global minimizer at x∗ = 0 but non-isolated.) All isolated local min. are strict.
                                                                      ∗
                • First-order necessary conditions (Th. 2.2): x local min, f cont. diff. in an open neighborhood
                       ∗           ∗                                        3
                  of x ⇒ ∇f(x ) = 0. (Not sufficient condition, ex: f(x) = x .)
                  (Pf.: by contradiction: if ∇f(x∗) 6= 0 then f decreases along the negative gradient direction.)
                                             ∗
                • Stationary point: ∇f(x ) = 0.
                                                                          ∗
                • Second-order necessary conditions (Th. 2.3): x is local min, f twice cont. diff. in an open
                                       ∗           ∗               2    ∗                                          3
                  neighborhood of x ⇒ ∇f(x ) = 0 and ∇ f(x ) is psd. (Not sufficient condition, ex: f(x)=x .)
                  (Pf.: by contradiction: if ∇2f(x∗) is not psd then f decreases along the direction where ∇2 is not psd.)
                                                                       2                                         ∗        ∗
                • Second-ordersufficient conditions (Th.2.4): ∇ f cont.inanopenneighborhoodofx , ∇f(x ) =
                        2    ∗           ∗                                                                      4    ∗
                  0, ∇ f(x ) pd ⇒ x is a strict local minimizer of f. (Not necessary condition, ex.: f(x) = x at x =0.)
                  (Pf.: Taylor-expand f around x∗.)
            The key for the conditions is that ∇, ∇2 exist and are continuous. The smoothness of f allows us to
            predict approximately the landscape around a point x.
            Convex optimization
                • S ⊂ Rn is a convex set if x;y ∈ S ⇒ αx+(1−α)y ∈ S, ∀α ∈ [0;1].
                • f: S ⊂ Rn → R is a convex function if its domain S is convex and f(αx + (1 − α)y) ≤
                  αf(x)+(1−α)f(y), ∀α ∈ (0;1), ∀x;y ∈ S.
                  Strictly convex: “<” instead of “≤”. f is (strictly) concave if −f is (strictly) convex.
                • Convex optimization problem: the objective function and the feasible set are both convex
                  (⇐the equality constraints are linear and the inequality constraints ci(x) ≥ 0 are concave.)
                  Ex.: linear programming (LP).
                • Easier to solve because every local min is a global min.
                • Th. 2.5:
                     – f convex ⇒ any local min is also global.
                     – f convex and differentiable ⇒ any stationary point is a global min.
                  (Pf.: by contradiction, assume z with f(z) < f(x∗), study the segment x∗z.)
                                                                    3