Optimization in Function Spaces

By Amol Sasane

This highly readable volume on optimization in function spaces is based on author Amol Sasane's lecture notes, which he developed over several years while teaching a course for third-year undergraduates at the London School of Economics. The classroom-tested text is written in an informal but precise style that emphasizes clarity and detail, taking students step by step through each subject.
Numerous examples throughout the text clarify methods, and a substantial number of exercises provide reinforcement. Detailed solutions to all of the exercises make this book ideal for self-study. The topics are relevant to students in engineering and economics as well as mathematics majors. Prerequisites include multivariable calculus and basic linear algebra. The necessary background in differential equations and elementary functional analysis is developed within the text, offering students a self-contained treatment.

• Language: English
• Publisher: Dover Publications
• Release date: Apr 10, 2016
• ISBN: 9780486810966

Book preview

OPTIMIZATION IN FUNCTION SPACES

AMOL SASANE

DEPARTMENT OF MATHEMATICS LONDON SCHOOL OF ECONOMICS

DOVER PUBLICATIONS, INC.

MINEOLA, NEW YORK

Copyright

Copyright © 2016 by Amol Sasane

All rights reserved.

Bibliographical Note

Optimization in Function Spaces is a new work, first published by Dover Publications, Inc., in 2016, as part of the Aurora: Dover Modern Math Originals series.

International Standard Book Number

eISBN-13: 978-0-486-81096-6

Manufactured in the United States by RR Donnelley

78945401 2016

www.doverpublications.com

Contents

Introduction

Part 1. Calculus in Normed Spaces; Euler-Lagrange Equation

Chapter 1. Calculus in Normed Spaces

§1.1. Normed Spaces

§1.2. Continuity, Linear Transformations, and Continuous Linear Transformations

§1.3. Differentiation

§1.4. Fundamental Theorems of Optimization

§1.5. What We Will Do Next

§1.6. A Historical Episode

Chapter 2. Euler-Lagrange Equation

§2.1. Fixed Endpoints

§2.2. Free Endpoints

§2.3. Scalar-Valued Integral Constraint

Part 2. Optimal Control

Chapter 3. Differential Equations

§3.1. High Order to First Order

§3.2. Initial Value Problem. Existence and Uniqueness.

§3.3. Linear Systems

§3.4. Underdetermined ODEs and Control Theory

§3.5. A Useful Perturbation Result

Chapter 4. Pontryagin’s Minimum Principle

§4.1. Unconstrained Control with no Endpoint Condition on the State

§4.2. Constrained Input, Fixed Final State, Autonomous

§4.3. Final State in a Manifold, Autonomous

§4.4. Variable Final Time; Autonomous Case

§4.5. Cost Involving the Final State; Autonomous Case

§4.6. Nonautonomous Case

§4.7. Do Optimal Solutions Always Exist?

Chapter 5. Bellman’s Equation

Solutions

Solutions to the Exercises from the Introduction

Solutions to the Exercises from Chapter 1

Solutions to the Exercises from Chapter 2

Solutions to the Exercises from Chapter 3

Solutions to the Exercises from Chapter 4

Solutions to the Exercises from Chapter 5

Project on Curve Fitting

Bibliography

Index

Introduction

The subject matter of this book is

It is thus natural to begin by explaining what we mean by this.

If we ignore the in function spaces part, we see that the subject matter is a part of optimization. In optimization, we know that the basic object of study is a real-valued function

defined on a set S, and the central problem is that of maximizing or minimizing f:

This is the case of minimizing f. In maximization problems, the inequality above is reversed. There is no real difference between maximization and minimization problems: indeed, if we learn to solve minimization problems, we also know how to solve maximization problems, because we can just look at –f instead of f.

Exercise 0.1. Let f : S → be a given function on a set S, and define –f : S by

Show that x* ∈ S is a maximizer for f if and only if x* is a minimizer for –f.

Why bother with optimization problems? In applications, we are often faced with choices or options, that is, different ways of doing the same thing. Imagine, for example, traveling to a certain place by rail, bus or air. Given the choice, it makes sense that we then choose the best possible option. For example, one might wish to seek the cheapest means of transport. The set S in our optimization problem is thus the set of possible choices. To each choice x ∈ S, we assign a number f(x(measuring how good that choice is), and this gives the cost function f : S to be minimized. In an optimization problem of minimizing f : S , the set S is called the feasible set, and the function f is called the objective function.

Thus, in optimization, one studies the problem

Depending on the nature of S and f, the broad subject of optimization is divided into subdisciplines such as

and so on. In this book, we will study dynamic optimization in continuous-time. Roughly, this is the subject where the set S is the collection of functions on a real interval, for example,

Let us consider a simple example to see that such problems do arise in real life situations.

Example 0.2. Imagine a copper mining company that is mining in a mountain, which has an estimated amount of Q tonnes of copper, over a period of T years. Suppose that x(t) denotes the total amount of copper removed up to time t ∈ [0, T]. Since the operation is over a large time period, we may assume that this x is a function living on the continuous-time interval [0, T]. The company has the freedom to choose its mining operation: x can be any nondecreasing function on [0, T] such that x(0) = 0 (no copper removed initially) and x(T) = Q (all copper removed at the end of the mining operations).

Figure 1. Several possible mining operations: x, ∙ ∙ ∙.

The cost of extracting copper per unit tonne at time t is given by

Here a, b are given positive constants. The expression is reasonable, since the term a ∙ x(t) accounts for the fact that when more and more copper is taken out, it becomes more and more difficult to find the left over copper, while the term b ∙ x′(t) accounts for the fact that if the rate of removal of copper is high, then the costs increase (for example, due to machine replacement costs). We don’t need to follow the exact reasoning behind this formula; this is just a model that the optimizer has been given.

If the company decides on a particular mining operation, say x : [0, T, then the overall cost f(xover the whole mining period [0, T] is given by

Indeed, x′(t)dt is the incremental amount of copper removed at time t, and if we multiply this by c(t), we get the incremental cost at time t. The total cost should be the sum of all these incremental costs over the interval [0, T], and so we obtain the integral expression for f (x) given above.

Hence, the mining company is faced with the following natural problem: Which mining operation x incurs the least cost? In other words,

where S denotes the set of all (continuously differentiable) functions x : [0, Tsuch that x(0) = 0 and x(T)= Q.◊

Exercise 0.3. In Example 0.2, calculate f(x1), f(x2) where:

Which is smaller among f(x1) and f(x2)? Which mining operation among x1 and x2 will be preferred?

In the subject of optimization in function spaces, we will learn to solve optimization problems where the feasible set is a set of functions on an interval [a, b]. This interval is thought of as the continuous-time variable, but one needn’t always have this interpretation with time. We hope that the above example convinces the reader that optimization problems in function spaces do arise in practice, and we will see many more examples from diverse application areas such as economics, engineering, physics, and life sciences.

How do we solve optimization problems in function spaces? Suppose that instead of an optimization problem in a function space, we consider a much simpler problem:

Then we know how to solve this. Indeed, from ordinary calculus, we know the following two facts.

Fact 1. If x* is a minimizer of f, then f′(x*) = 0.

Fact 2. If f″(x) ≥ 0 for all x and f′(x*) = 0, then x* is a minimizer of f.

Figure 2. Fact 1 says that at a minimizer x*, the tangent to the graph of f must be horizontal. Fact 2 says that if f′ is increasing (f″ ≥ 0), and if f′(x*) = 0, then for points x to the left of x*, f′ must be nonpositive, and so f must be decreasing there, and similarly f must be increasing to the right of x*. This has the consequence that x* is a minimizer of f.

Fact 1 allows us to narrow our choice of possible minimizers, since we can calculate

and note that 2x – 2 = 0 if and only if x = 1. So if at all there is a minimizer, then it must be x* = 1. On the other hand,

and so Fact 2 confirms that x* = 1 is a minimizer. Thus using these two facts, we have completely solved the optimization problem: we know that x* = 1 is the only minimizer of f.

or more generally a finite n. Indeed, vector spaces of functions such as C[a, b] are infinite dimensional vector spaces. Nevertheless, it is natural to try solving our optimization problem in function spaces in the same manner. But we immediately run into a problem. We don’t yet know what the derivative f′(x*) at x* is for a real-valued function f whose domain is itself a space of functions like C[a, b]! So we first develop calculus in this setting. Our approach will be to proceed abstractly, where we will first learn about calculus in vector spaces (which are possibly infinite dimensional, like C[a, b], or the set C¹[a, b] of all continuously differentiable functions on [a, b]), and we will also learn the analogues of Facts 1 and 2 in this more general setting. We will then be in a position to apply these general results to more specialized problems, and see what they give there. The initial abstract approach we follow allows us to solve many problems in one go, that is, seemingly different problems are considered as one basic problem in a unified setting by the removal of inessential details. In the second part of the course, we will also learn about more complicated optimization problems in function spaces, namely optimal control problems, in which one has an objective function given by an integral, where the integrand involves functions that satisfy a differential equation constraint. The broad outline of the content in this book is as follows:

(1) Calculus in Normed Spaces.

(2) The Euler-Lagrange Equation.

(3) Preliminaries on Ordinary Differential Equations (ODEs).

(4) The Pontryagin Minimum Principle.

(5) The Hamilton-Jacobi-Bellman Equation.

-δ arguments), and so it should be accessible to a wide spectrum of students. Preliminary versions of the book were used for a course with the same title as that of the book, for the students in the third year of the BSc in Mathematics and/with Economics programs at the London School of Economics. The book contains many exercises, which form an integral part of the text. Detailed solutions appear at the end of the book. Also in the book, a project is outlined, which involves some theoretical exercises, together with a practical component of writing a program in MATLAB to implement the resulting numerical algorithm.

This book relies heavily on some of the sources mentioned in the bibliography. I am thankful to Erik G.F. Thomas, Sara Maad Sasane, and Adam Ostaszewski for several useful discussions.

Amol Sasane

London, 2013.

Part 1

Calculus in Normed Spaces; Euler-Lagrange Equation

Chapter 1

Calculus in Normed Spaces

As we had discussed in the previous chapter, we wish to differentiate functions living on vector spaces (such as C[a, b. In order to talk about the derivative, we need a notion of closeness between points of a vector space so that the derivative can be defined. It turns out that vector spaces such as C[a, b] can be equipped with a norm, and this provides a distance between two vectors. Having done this, we have the familiar setting of calculus, and we can talk about the derivative of a function living on a normed space. We then also have analogues of the two facts from ordinary calculus relevant to optimization that were mentioned in the previous chapter, namely the vanishing of the derivative for minimizers, and the sufficiency of this condition for minimization when the function has an increasing derivative. Thus the outline of this chapter is as follows:

(1) We will learn the notion of a normed space, that is a vector space equipped with a norm, enabling one to measure distances between vectors in the vector space. This makes it possible to talk about concepts from calculus, and in particular the notion of differentiability of functions between normed spaces.

(2) We will define what we mean by the derivative of a function f : X → Y, where X, Y are normed spaces, at a point x0 ∈ X. In other words, we will explain what we mean by "f′(x0)."

(3) We will prove the following two fundamental results in optimization for a real-valued function f on a normed space X:

Fact 1. If x* ∈ X is a minimizer of f, then f′(x*) = 0.

Fact 2. If f is convex and f′(x*) = 0, then x* is a minimizer of f.

1.1. Normed Spaces

We would like to develop calculus in the setting of vector spaces of functions such as C[a, b]. Underlying all the fundamental notions in ordinary calculus is the notion of closeness between points. For example, recall that a sequence (an)nis said to converge with limit L > 0, there exists an N such that whenever n > N, |an – L| < . converges to L if no matter what distance > 0 is given, one can guarantee that all the terms of the sequence beyond a certain index N away from L (this is the inequality |an – L| < . A similar thing happens with continuity and differentiability. For example, recall that a function f is said to be continuous at x> 0, there exists a δ > 0 such that whenever |x – x0| < δ, there holds that |f(x) – f(x0)| < , I can find a distance δ such that whenever I choose an x not farther than a distance δ from x0, I am guaranteed that f(xfrom f(x0). Again, notice the key role played by the distance in this definition. We observe that the distance between two real numbers x, y is given by |x – y|is the absolute value function: for x ,

So in order to generalize the notions from ordinary calculus (where we work with real numbers and where the absolute value is used to