Variational Methods in Optimization

VARIATIONAL METHODS IN OPTIMIZATION Abstract. After a review of some well-known optimization problems, properties of vector spaces, and a close examination of functionals, a familiar approach to solving max and min problems is generalized from elementary calculus in order to find solutions to more difficult extremum problems. Using the Gateaux variation, a fundamental necessary condition for an extremum is established and applied. Optimization problems with one constraint are explored along with weak continuity of variations. Following a statement of the Euler-Lagrange Multiplier Theorem, more extremum problems are solved and then applications of the Euler-Lagrange Multiplier Theorem in the Calculus of Variations end the work. 1. Introduction Since the seventeenth century, scientists have been concerned with finding the largest or smallest values of different quantities. For example, Isaac Newton, Christian Huygens, and Leonhard Euler all worked at solving the problem of finding the greatest range of a projectile. In order to find a solution to this problem, one must deduce the optimal initial launch angle of motion for a projectile, taking into account air resistance, so that its range is maximized when the object is hurled from the earth’s surface. In 1687, Newton studied another problem where an object was propelled through water; the goal was to find the least water resistance that can be achieved by changing the object’s shape. The most favorable choice is a smooth, aerodynamic shape that minimizes drag and leaves less turbulence in its wake. A problem that may be familiar to those who have taken a Classical Mechanics course involves finding the shortest time of descent for a bead on a wire. The wire can be molded into many distinct contours and the bead slides under gravity from a high point to a lower point. At first thought, one may think that the quickest motion of the bead lies on a straight line between the two points. In practice, a curved path that John Bernoulli named the brachistochrone 1 gives the quickest descent. In this case, the brachistochrone is part of an inverted cycloid. 1 Brachistochrone derives from brachistos (= shortest) and chronos (= time). 1 2 For another problem, the path of quickest descent (brachistochrone) could be much different. Other optimization problems include finding the shortest transit time between two points on the earth’s surface by tunnelling through the earth from one point to the other; the minimum time for a rocket to reach a certain elevation with a fixed amount of fuel under atmospheric resistance; and the minimum amount of fuel required for a rocket to achieve a certain altitude where the time of flight is unimportant. In this paper, our starting point leads naturally from the preceding questions of maxima and minima. We begin by considering functionals defined on subsets of vector spaces. Most of the functionals arising in applications are continuous, but many are not linear. After Section 3 where continuous and linear functionals are considered, we transition into developing a fundamental necessary condition for an extremum and then introduce the Gateaux Variation. The central focus of Section 6 is the Euler-Lagrange necessary condition for an extremum with constraints culminating with a statement of the Euler-Lagrange multiplier theorem for many constraints. Ending the work, the last two sections involve applications of the Euler-Lagrange multiplier theorem in the calculus of variations. 2. Functionals 2.1. Vector Spaces. Many problems encountered later require consideration of real-valued functions defined on sets of objects other than numbers. Bernoulli’s brachistochrone problem is of this type. Here, the time of descent is presumably a function of the shape of the entire path followed by the bead, and a full description of this shape cannot be given by any single number. Generally, all of our functions are defined on subsets of vector spaces (also called linear spaces). We are familiar with the most common vector space, R, known as the set of all real numbers. A vector space over the set of real numbers R denotes a set A of elements x, y, z, ... called vectors for which the operations of addition of elements and multiplication of elements by real numbers a, b, c, ... are defined and obey the following ten rules2: (1) Given any x, y ∈ A, the sum x + y ∈ A. (2) For every x ∈ A and any real scalar a ∈ R, ax ∈ A. (3) x + y = y + x ∀ two vectors x and y ∈ A. (4) (x + y) + z = x + (y + z) ∀ vectors x, y, and z ∈ A. (5) x + 0 = x, where 0, an element of A, is called the zero vector. 2Covered in a typical linear algebra course. VARIATIONAL METHODS IN OPTIMIZATION 3 (6) A contains, ∀ vector x ∈ A, a vector −x such that x+(−x) = 0. (7) a(bx) = (ab)x ∀ a, b ∈ R and ∀ x ∈ A. (8) a(x + y) = ax + ay ∀ a ∈ R and ∀ x, y ∈ A. (9) (a + b)x = ax + bx ∀ a, b ∈ R and ∀ x ∈ A. (10) 1x = x ∀ x ∈ X. Examples of vector spaces that satisfy the aforementioned ten axioms include the n-dimensional Euclidean space Rn and the set X of all realvalued functions defined on some fixed interval I of numbers. For the latter vector space, consider arbitrary functions φ and ψ. Then we can define addition by (φ + ψ)(x) = φ(x) + ψ(x) for any x in I, while for any number a the product aφ is given by (aφ)(x) = aφ(x) for any x in I. The zero element is the zero function in this vector space X. If A is any fixed vector space and B is a subset of A such that x + y (addition of elements) and ax (scalar multiplication) are in B for every x and y in B and for every real number a, then B is itself a vector space with the same operations of addition and multiplication by numbers as inherited from A. In this case, B is called a subspace of A. The set of all n-tuples of numbers x = (x1 , x2 , ..., xn ) with x1 = 0 is an example of a subspace of n-dimensional Euclidean space Rn . 2.2. Introduction to Functionals. A functional is a real-valued function J whose domain D(J) is a subset of a vector space. As an example, let D be the set of all positive-valued continuous functions φ = φ(x) on the interval 0 ≤ x ≤ π2 . Define the functional J by Z πp 2 φ(x) sin(x)dx J(φ) = 0 for any φ in D. Here the domain D is a subset of the vector space C 0 [0, π2 ] of all continuous functions φ on [0, π2 ]. Note: An important subspace of the vector space of all real-valued functions on some fixed interval I is given by the set of all such functions which have continuous derivatives of all orders up to and including kth order, where k may be any fixed nonnegative integer. This subspace is denoted as C k (I) or C k [a, b] and sometimes said to be the functions of class C k on the underlying interval I = [a, b]. 4 A Brachistochrone Functional. As another example, consider the time it takes for a bead on a wire to descend between two nearby fixed points. We can represent the wire as a smooth curve γ in the (x, y)plane joining the two points P0 = (x0 , y0 ) and P1 = (x1 , y1 ). Then the time T needed for the bead to move from P0 down to P1 along γ is given by the line integral Z T Z ds (1) T = dt = , 0 γ v where s measures the arc length along γ, ds/dt is the rate of change of arc length with respect to time t, and the speed of motion for the bead is v = ds/dt. We assume that the force of gravity due to the earth remains constant and acts downward on the bead in the negative y-direction. Thus, the x-component of the gravitational force is zero and the y-component is given by −g, where g is the constant acceleration due to gravity. The mass of the bead is denoted by the variable m. Applying conservation of energy3, we know that the sum of kinetic and potential energy remains constant throughout the motion (neglecting friction). The kinetic energy of an object in motion is 12 mv 2 and its potential energy relative to an arbitrarily chosen point of reference of zero potential (where y = 0) is represented by mgy. If the bead starts from rest at P0 with zero initial kinetic energy and initial potential energy equal to mgy0 , the relation (2) 1 2 mv + mgy = mgy0 2 must hold during its motion. The curve γ can be represented parametrically as γ : y = Y (x), x0 ≤ x ≤ x1 for some acceptable function Y (x) relating x and y along γ. Then Equation 2 can be solved for speed v along γ and the differential element of arc length along γ is given by p ds = 1 + Y 0 (x)2 dx. 3Conservation of energy for this kind of motion derives from Newton’s law of motion and the definitions of kinetic and potential energy. Consult an introductory level physics textbook for more details. VARIATIONAL METHODS IN OPTIMIZATION 5 Therefore, the integral appearing in Equation 1 that yields the time of descent can be re-written as Z (3) x1 T (Y ) = x0 s 1 + Y 0 (x)2 dx, 2g[y0 − Y (x)] which may be considered to be a functional with domain D given by the set of all continuously differentiable functions Y = Y (x) on the interval [x0 , x1 ] satisfying the constraints Y (x0 ) = y0 and Y (x1 ) = y1 . Thus, Equation 3 gives the value of this brachistochrone functional, denoted T = T (Y ) for any Y in D = D(T ). Note that the domain D(T ) is a subset of the vector space C 1 [x0 , x1 ] of all continuously differentiable functions on [x0 , x1 ]. There are many other types of functionals. For example, an area functional is used to determine the greatest area that can be encircled in a given time T by varying the closed path γ flown by an airplane at constant natural speed v0 while a constant wind blows. An additional example is a transit time functional which is given by the transit time of a boat crossing a river from a fixed initial point on one bank to a specified final point on the other bank. A downstream current speed w is assumed to depend only on the horizontal distance x from the initial point on the riverbank and the boat travels at a constant natural speed v0 relative to the water. Keep in mind that all functionals, including the two examples above, are real-valued with domains that are subsets of vector spaces. 2.3. Normed Vector Spaces. Maximizing or minimizing the values of functionals defined on subsets of vector spaces will be of great interest as we move forward and explore different optimization problems. The special case where the vector space is the set of real numbers is studied in elementary differential calculus. There the absolute value function plays an important role in defining the notion of distance between numbers. It is defined for any number x by  (4) |x| = x if x ≥ 0 −x if x < 0 and the distance between any two numbers x and y is given by the absolute value of their difference |x − y|. We need a similar notion of distance between vectors in a more general vector space in order to solve the optimization problems we encounter later. This concept can be defined in terms of a norm defined 6 on the vector space, which replaces the absolute value function of Equation 4. The notation k·k denotes such a norm, which can be considered a length, similar to the absolute value function | · | on R. A vector space X is said to be a normed vector space whenever there is a real-valued norm function k · k defined on X which assigns the real number kxk (called the norm of x, or the length of x) to the vector x in X such that 1. kxk ≥ 0 for all vectors x in X, and kxk = 0 if and only if x is the zero vector in X. 2. kaxk = |a| kxk for every x in X and every real scalar a in R. 3. kx + yk ≤ kxk + kyk for every pair of vectors x and y in X (known as the triangle inequality4). [S19] To recap, the first condition tells us that the norm of every vector in X is positive except for the zero vector. One main thing that the second condition ensures is that the length of the vector −x is the same as the length of x. The final condition stipulates that the length of the sum x + y cannot exceed the sum of the separate lengths x and y. Now we can define the distance between any two vectors x and y of a normed vector space X to be the length of their difference kx − yk. One can quickly check that the set of all real numbers R is a normed vector space with norm given by the absolute value function of Equation 4, i.e., kxk = |x| for any number x. In addition, n-dimensional Euclidean space Rn is a normed vector space with norm function defined by kxk = q x21 + x22 + ... + x2n for any vector x = (x1 , x2 , ..., xn ) in Rn . In this case, the triangle inequality is established by utilizing Cauchy’s inequality5 X n i=1 4In 2 xi y i ≤ X n i=1 x2i  X n yj2  , i=1 words, the length of any one side of a triangle is always less than or equal to the sum of the lengths of the other two remaining sides. 5A proof of Cauchy’s inequality can be found in the Appendix, Section A1 of Donald R. Smith, Variational Methods in Optimization (Mineola, New York: Dover Publications, Inc.). VARIATIONAL METHODS IN OPTIMIZATION 7 which holds for all n-tuples x = (x1 , x2 , ..., xn ) and y = (y1 , y2 , ..., yn ) in Rn . The vector space C 0 (I) consisting of all continuous real-valued functions φ defined on a fixed interval I = [a, b] can be made into a normed vector space with norm defined by the L2 norm s Z b |φ(x)|2 dx kφk = (5) a for any vector φ in C 0 (I). Here Schwarz’s inequality6  Z b Z b Z b 2 φ(x)ψ(x)dx ≤ φ(x) dx ψ(x)2 dx a a a helps with proving the triangle inequality. [S20] Another possible choice for a norm function on C 0 (I) = C 0 [a, b] is (6) kφk = maxa≤x≤b |φ(x)| for any φ, referred to as the uniform norm on C 0 . One can check that Equations 5 and 6 satisfy all of the conditions required of a norm; therefore, they give two distinct norms for the vector space C 0 [a, b]. Upon closer inspection, one finds that the normed vector spaces induced by Equations 5 and 6 are different. Thus, it is worth noting that a given vector space X may lead to more than one distinct normed vector space since there may be more than one norm on X. We also note in general that any subspace Y of a normed vector space X is itself a normed vector space with the same norm as used on X. At this point, it is convenient to introduce the notion of a ball in a normed vector space. A ball provides a general normed vector space with something similar to the notion of an interval in the set of real numbers, which is a special case of a vector space. For any positive number ρ and any vector x in a normed vector space X, the ball of radius ρ centered at x is the set of all vectors y in X having distance from x less than ρ, i.e., Bρ (x) = {set of all vectors y in X satisfying ky − xk < ρ}. 6Schwarz’s inequality is also proved in Section A1 of the Appendix in Donald R. Smith’s Variational Methods in Optimization. 8 A subset D of a normed vector space X is said to be open if for each x in X there is some positive ρ so that Bρ (x) is contained in X. 3. Continuous and Linear Functionals 3.1. Continuous Functionals. Let D be a fixed open set in a normed vector space X, and let J be a functional defined on D. J has the limit L at x if for every positive number  there is a ball Bρ (x) contained in D (with radius ρ) such that |L − J(y)| <  for all vectors y (excluding x) in Bρ (x). Symbolically we can write lim J(y) = L y→x whenever J has limit L at x. This notion of the limit for functionals agrees with the standard notation for ordinary functions in elementary calculus except that the norm function is used to measure distance in X (replacing the absolute value function). [S23] The functional J is said to be continuous at x in D if J has the limit J(x) at x, or, symbolically: lim J(y) = J(x) y→x J is continuous on D (or some subset of D) if J is continuous at each vector in D (or at each vector in the subset of D). [S23] Even though we have defined the notions of limit and continuity for functionals only at points in open sets, a simple modification allows the definitions to be extended to points on the boundary of an open set D in X. This modification will not be given because the present definitions are adequate for our needs. 3.2. Linear Functionals. An important class of functionals for which continuity is often easy to prove is the class of linear functionals. A functional J is said to be linear if the domain of J consists of an entire vector space X and if J satisfies the linearity relation J(ax + by) = aJ(x) + bJ(y) for all numbers a and b in R and for all vectors x and y in X. [S28] As an example, the functional K = K(f ) defined on C 0 [0, 1] by K(f ) = R1 0 f (t)dt for any continuous function f = f (t) satisfies the linearity relation for all numbers a and b and for all continuous functions f and g on the interval [0, 1]. Thus, the functional K is linear. One can also use the linearity relation to quickly check that VARIATIONAL METHODS IN OPTIMIZATION 9 every linear functional J vanishes at the zero vector in its domain X, that is, that J(0) = 0. We can now verify the useful result that a linear functional is continuous on its domain X if and only if it is continuous at the zero vector in X. If a linear functional J is continuous on X, then by definition J is continuous at each vector in X and therefore at the zero vector. Conversely, suppose that J is continuous at the zero vector in X. The limit definition implies that (recall J(0) = 0) lim J(y) = 0. y→0 Now, given any  > 0 there is a number ρ > 0 such that |J(y)| <  for all vectors y satisfying ||y|| < ρ. If x is any fixed vector in X, then application of the linearity relation gives J(z) = J(z − x + x) = J(z − x) + J(x) for all vectors z in X and so |J(z) − J(x)| = |J(z − x)|. If we take y = z − x in the inequality above, then |J(z) − J(x)| <  for all vectors z satisfying ||z − x|| < ρ. Thus, J is continuous at x and since x was an arbitrary vector, we have shown that J is continuous everywhere on X. The last conclusion completes the proof. Another useful result is that a linear functional J is continuous at the zero vector in its domain X if and only if an estimate |J(x)| ≤ k||x|| holds for all vectors x in X and for some fixed constant k depending only on J but not on x. Therefore, we only need to find such a k for a linear functional J on a normed vector space X in order to conclude that J is continuous everywhere on X. Suppose that the functional J : X → R is linear. We can show (in one direction) that f is continuous on X if and only if there exists a constant k such that |J(x)| ≤ k||x|| holds for all x in X. We begin by supposing that there exists k > 0 such that |J(x)| ≤ k||x|| 10 for every x in X. To prove the continuity of J on X, it suffices to prove continuity at the zero vector. So let  > 0 and choose ρ = k . Then if ||x − 0|| = ||x|| < ρ, |J(x) − J(0)| = |J(x) − 0| = |J(x)| ≤ k||x|| < kρ = k ∗  = . k By definition, J is continuous at the zero vector. 3.3. A Fundamental Necessary Condition for an Extremum: Introduction. In a forthcoming section, we shall introduce the Gateaux variation of a functional. This variation must vanish at a local maximum or minimum vector and this result helps us solve certain extremum problems. We wish to generalize the approach in calculus where we find maximizers or minimizers of a function f by examining points in the domain of f where f 0 is zero or nonexistent. Given a real valued function f , the derivative is the limit f (x + ) − f (x) lim = f 0 (x). →0  If f has a local maximum or minimum value at a point x∗ in D, then f 0 (x∗ ) = 0 will hold at any interior local maximum or minimum point x∗ . In an elementary calculus course, one learns how to use this condition to solve many minimum and maximum problems. We want to obtain a similar method which can be applied in solving the optimization and extremum problems that concern us. 4. A Fundamental Necessary Condition for an Extremum Let D be a fixed nonempty subset of a normed vector space X and let the functional J be defined on D. We define a vector x∗ to be a maximum vector in D for J if J(x) ≤ J(x∗ ) for all vectors x in D. The vector x∗ in D is a local maximum vector in D for J if there is some ball Bp (x∗ ) in X centered at x∗ such that J(x) ≤ J(x∗ ) for all vectors x that are simultaneously in D and in Bp (x∗ ). Similarly, we define a local minimum vector using J(x) ≥ J(x∗ ). For conciseness, we say that x∗ is a local extremum vector in D for J if x∗ is either a local maximum vector or a local minimum vector. In this case, we say that J has a local extremum at x∗ . [S33] We now consider a functional J defined on an open subset D of the normed vector space X. If we have a local minimum vector x∗ in D for J and if h is any fixed vector in X, then J(x∗ + h) − J(x∗ ) ≥ 0 VARIATIONAL METHODS IN OPTIMIZATION 11 holds for all sufficiently small numbers . Note that the vector x∗ + h is in the domain of J for all small . This is because the vector x∗ lies in the open set D. It follows that J(x∗ + h) − J(x∗ ) ≥0  for all small positive numbers , while J(x∗ + h) − J(x∗ ) ≤0  for all small negative numbers  < 0. Letting  approach zero in both inequalities, we can conclude that the nonnegative and nonpositive condition J(x∗ + h) − J(x∗ ) lim =0 →0  must hold at any local minimum vector x∗ in D for the functional J provided that this limit exists. It can be similarly proven that this same condition must hold at any maximum vector in D for J. This condition is the generalization of f 0 (x∗ ) = 0 from elementary calculus that we desired. Formally, a functional J defined on an open subset D of a normed vector space X has a Gateaux variation at a vector x in D whenever there is a functional δJ(x) with values δJ(x; h) defined for all vectors h in X and such that J(x + h) − J(x) lim = δJ(x; h) →0  holds for every vector h in X; compare to f (x + ) − f (x) = f 0 (x) →0  from elementary calculus. The functional δJ(x) is called the Gateaux variation of J at x or just the variation of J at x. [S35] We can also summarize the result of our earlier calculation involving the determination of any local extremum. lim Theorem: If a functional J defined on an open set D contained in a normed vector space X has a local extremum at a vector x∗ in D, and if J has a variation at x∗ , then the variation of J at x∗ must vanish; i.e., δJ(x∗ ; h) = 0 f or all vectors h in X. In other words, vanishing of the variation is a necessary condition for 12 any local extremum vector x∗ . This necessary condition helps solve a wide array of extremum problems. Often, we can eliminate the arbitrary vector h from the equation above in order to obtain a simpler equation involving only x∗ which can be solved for the desired extremum vector. The elimination of the vector h hinges on the equation above having to hold for every vector h in X and thus involves making some suitable choice(s) of h. A word of caution is needed because even if we find a vector x∗ in D that satisfies the necessary condition above, we must still check whether or not J(x∗ ) is actually a local extreme value for J in D. The necessary condition may hold at nonextremum vectors x∗ such as saddle points or inflection points of J in D. Consider the function J defined on R = R1 by J(x) = x3 f or any number x in R. This function has a vanishing derivative at x = 0 and so the variation of J also vanishes at the point x∗ = 0. However, the point x∗ = 0 is not a local extremum vector in R for J but is rather a horizontal inflection point. Another example is provided by examining the function K defined on R2 by K(x) = x22 − x21 for any point x = (x1 , x2 ) in R2 . This function has a variation given as ∂K(x) ∂K(x) h1 + h2 = −2x1 h1 + 2x2 h2 ∂x1 ∂x2 for any vector h = (h1 , h2 ) in R2 . The variation vanishes at the point x∗ = (0, 0), but x∗ is not a local extremum point for K in R2 because it is a saddle point. The variation obtained in the last example utilized the following: δK(x; h) = Let J = J(x) be a real-valued function defined for all n-tuples x = (x1 , x2 , ..., xn ) in a given open region D in Rn , and assume that J has continuous first-order partial derivatives at x denoted as Jxi = ∂J(x) ∂xi for i = 1, 2, ..., n. Then J has a variation at x given by: n X δJ(x; h) = Jxi (x)hi i=1 for any vector h = (h1 , h2 , ..., hn ) in Rn . [S37] We need the notion of open set. A set S in a normed vector space X is open if every point in S has a neighborhood lying within the set. Generally, a neighborhood of a point x in Rn is the set of points VARIATIONAL METHODS IN OPTIMIZATION 13 inside an n -ball with the point x as the center and radius  > 0. A set containing an open neighborhood is also called a neighborhood. Some examples of open sets are the open interval in one-space, a disk in twospace, and a ball in three-space. Additionally, the complement of an open set is a closed set, and it is possible for a set to be neither open nor closed. As an example, let us calculate the Gateaux variation of the functional JR = J(φ) which is defined on the vector space C 0 [0, 1] by 1 J(φ) = 0 [φ(x)2 +φ(x)3 ]dx for any function φ of class C 0 on 0 ≤ x ≤ 1. We can show that the variation of J, δJ(φ; ψ), at an arbitrary fixed vector φ = φ(x) in C 0 [0, 1] is represented by Z 1 δJ(φ; ψ) = [(2φ(x) + 3φ(x)2 )ψ(x)]dx. 0 We begin with J(φ + ψ) − J(φ) →0  and using the expression for the functional J we get R1 R1 [ (φ(x) + ψ(x))2 + (φ(x) + ψ(x))3 ]dx − 0 [φ(x)2 + φ(x)3 ]dx 0 δJ(φ; ψ) = lim . →0  Now writing the numerator as one integral Z 1 [φ(x)2 +2ψ(x)φ(x)+2 ψ(x)2 +φ(x)3 +3φ(x)2 ψ(x)+3φ(x)2 ψ(x)2 +3 ψ(x)3 δJ(φ; ψ) = lim 0 −φ(x)2 − φ(x)3 ]dx then collecting terms we have Z 1 [ 3 (ψ(x)3 ) + 2 (ψ(x)2 + 3φ(x)ψ(x)2 ) + (2ψ(x)φ(x) + 3φ(x)2 ψ(x)) 0 +(φ(x)2 + φ(x)3 − φ(x)2 − φ(x)3 ]dx After canceling terms and dividing by  we now have Z 1 δJ(φ; ψ) = lim [ 2 (ψ(x)3 ) + (ψ(x)2 + 3φ(x)ψ(x)2 )+ →0 0 (2ψ(x)φ(x) + 3φ(x)2 ψ(x)) ]dx Bringing the limit inside of the integral7 and letting  → 0 Z 1 [2ψ(x)φ(x) + 3ψ(x)φ(x)2 ]dx δJ(φ; ψ) = 0 7This involves uniform convergence of R F (, x) to R F (x) on 0 ≤ x ≤ 1. 14 and thus Z δJ(φ; ψ) = 1 [(2φ(x) + 3φ(x)2 )ψ(x)]dx 0 and this is true for any vector ψ(x) in C 0 [0, 1]. Therefore, we have obtained the desired result. 5. Some Remarks on the Gateaux Variation We now expand upon the introduction to the Gateaux variation of a functional. If we refer back to the limit definition of the variation at x, we can see that since the limit of a function is unique if it exists, then it follows that a functional can have at most one variation at x. The value of the variation δJ(x; h) can be thought of as a generalization of the directional derivative of multivariable calculus. It is a directional derivative of J at x in the direction of the vector h. Now if we compare the limit definition of the variation to the derivative of f at x, we see that the value of the variation is just the ordinary derivative of the function J(x + h) considered as a function of the real number  and evaluated at  = 0; i.e., d J(x + h)|=0 . d Therefore, the result we already obtained concerning the vanishing of the variation of J at a local extremum vector x∗ is actually a corollary of the corresponding result in elementary calculus. According to elementary calculus, the derivative of the function f () = J(x∗ + h) must vanish at  = 0 if zero is a local extremum point for f (). If J has a variation at x, then δJ(x; 0) = 0 must hold. Moreover, the variation must satisfy the homogeneity relation: (7) δJ(x; h) = δJ(x; ah) = aδJ(x; h) for any number a. [S39] We can verify this by starting with d J(x + ah)|=0 d and now using σ = a along with the chain rule of differentiation ( dJ = a dJ ) we finish the verification with d dσ δJ(x; ah) = d J(x + σh)|σ=0 = aδJ(x; h). dσ It is worth mentioning that the symbol ∆x may be used often in place of h to denote the second argument in the expression for the δJ(x; ah) = a VARIATIONAL METHODS IN OPTIMIZATION 15 variation δJ(x; ∆x). In that case, J(x + ∆x) − J(x) d = J(x + ∆x)|=0 →0  d will hold for any vector x in the domain of J and for any vector ∆x in X. This is only a matter of notation; the symbol ∆x still represents an arbitrary vector in X. The change assists in bookkeeping later on and possesses no fundamental significance. We now consider an example of a variation calculation using Equation 7. Let the functional J = J(φ) be defined on the vector space C 0 [0, 1] by Z 1 [φ(x)2 + 2(x − 1)φ(x) − 2ex φ(x)]dx J(φ) = δJ(x; ∆x) = lim 0 for any function φ of class C 0 on 0 ≤ x ≤ 1. We can show that the variation of J at an arbitrary fixed vector φ = φ(x) in C 0 [0, 1] is given by Z 1 [φ(x) + x − 1 − ex ]∆φ(x) dx δJ(φ; ∆φ) = 2 0 0 for any vector ∆φ in C [0, 1]. We begin by calculating J(φ + ∆φ): J(φ + ∆φ) = Z 1 [(φ(x)+∆φ(x))2 +2(x−1)(φ(x)+∆φ(x)−2ex (φ(x)+∆φ(x))]dx. 0 Using the earlier result shown in Equation 7 that d J(x + h)|=0 d we can find the variation of J. In our case, this looks like δJ(x; h) = d J(φ + ∆φ)|=0 d and thus, after taking the derivative with respect to  of our expression for J(φ + ∆φ) we get Z 1 d J(φ+∆φ) = [2(φ(x)+∆φ(x))∆φ(x)+2(x−1)∆φ(x)−2ex ∆φ(x)]dx. d 0 δJ(φ; ∆φ) = Then, evaluating at  = 0, we have Z 1 d J(x + h)|=0 = [2φ(x)∆φ(x) + 2(x − 1)∆φ(x) − 2ex ∆φ(x)]dx. d 0 16 Rearranging terms yields d J(x + h)|=0 = 2 d 1 Z [φ(x) + x − 1 − ex ]∆φ(x) dx 0 which is the variation of J that we sought. We can now use a theorem from Section 4 to find a minimum vector ∗ φ in C 0 [0, 1] for the functional J whose variation we just found. Adjusting terms to fit our current situation, recall that if a functional J defined on an open set D contained in a normed vector space X has a local extremum at a vector φ∗ in D, and if J has a variation at φ∗ , then the variation of J at φ∗ must vanish. This means δJ(φ∗ ; ∆φ) = 0 must hold for all vectors ∆φ in the vector space X. Setting our calculated variation equal to zero and making the special choice ∆φ(x) = φ∗ (x) + x − 1 − ex , we obtain Z 1 2 [φ∗ (x) + x − 1 − ex ](φ∗ (x) + x − 1 − ex ) dx = 0 0 thus we have Z 2 1 [φ∗ (x) + x − 1 − ex ]2 dx = 0 0 and our special choice of ∆φ(x) has made it possible for us to deduce that the only way that the integral will equal zero is if the integrand equals zero. Otherwise, the integral will always be positive since the integrand is squared. Therefore, [φ∗ (x) + x − 1 − ex ]2 = 0 and so a minimum vector for J is φ∗ (x) = 1 − x + ex . 5.1. More Examples of the Calculation of Gateaux Variations. A wide class of functionals have the general form Z (8) x1 J(Y ) = F (x, Y (x), Y 0 (x))dx x0 where the function F = F (x, y, z) is a function defined for all points (x, y, z) in some open set in three-dimensional Euclidean space R3 . In order to obtain the variation of the functional J at any fixed vector Y in its domain D, we use Equation 8 to calculate Z x1 J(Y + ∆Y ) = F (x, Y (x) + ∆Y (x), Y 0 (x) + ∆Y 0 (x)) dx x0 VARIATIONAL METHODS IN OPTIMIZATION 17 for any vector ∆Y in the vector space C 1 [x0 , x1 ] and for any small number . We will assume that the function F = F (x, y, z) is continuous with respect to all of its variables and also has continuous first-order parital derivatives with respect to y and z. Applying an oft-used theorem from an earlier section, we can find a general expression of δJ(Y ; ∆Y ) for the wide class of functionals denoted in Equation 8 by taking the derivative of J(Y + ∆Y ) with respect to  and then evaluating the expression at  = 0. Leaving out most of the technical details, this process gives us the variation of J as (9) Z x1 δJ(Y ; ∆Y ) = [FY (x, Y (x), Y 0 (x))∆Y (x)+FY 0 (x, Y (x), Y 0 (x))∆Y 0 (x)] dx x0 for any vector Y = Y (x) in the domain D of J and for any vector ∆Y = ∆Y (x) in the vector space C 1 [x0 , x1 ]. This result comes in very handy in the following example. Consider the functional J defined on the normed vector space C 1 [x0 , x1 ] by Z x1 J(Y ) = [Y (x)2 + Y 0 (x)2 − 2Y (x) sin(x)] dx. x0 We can calculate the variation of J using Equation 9. In this case, F = [Y (x)2 + Y 0 (x)2 − 2Y (x) sin(x)] and the expression we seek for the variation is given by Z x1 δJ(Y ; ∆Y ) = [FY (x, Y (x), Y 0 (x))∆Y (x)+FY 0 (x, Y (x), Y 0 (x))∆Y 0 (x)] dx x0 so the first partial derivative of F with respect to Y (x) is FY = 2Y (x) − 2 sin(x) and the first partial of F with respect to Y 0 (x) is FY 0 = 2Y 0 (x). Thus, the variation of J is Z x1 δJ(Y ; ∆Y ) = [(2Y (x) − 2 sin(x))∆Y (x) + (2Y 0 (x))∆Y 0 (x)] dx x0 and simplifying we get Z x1 δJ(Y ; ∆Y ) = 2 [(Y (x) − sin(x))∆Y (x) + Y 0 (x)∆Y 0 (x)] dx. x0 18 6. The Euler-Lagrange Necessary Condition for an Extremum with Constraints Now we introduce Euler-Lagrange multipliers and their use in solving extremum problems involving equality and inequality constraints. We begin by examining extremum problems with a single constraint. Let X be a normed vector space with D an open subset of X, and let J and K be any two functionals defined and having variations on D. Consider the problem of finding extremum vectors x∗ for J among all vectors x in D satisfying the constraint K(x) = k0 where k0 is some fixed number. The notation D[K = k0 ] represents the subset of D consisting of all vectors x in D which satisfy K(x) = k0 . We always assume that there is at least one vector x in D satisfying the constraint, so that the set D[K = k0 ] is not empty. Therefore, the extremum problem that we consider is to find local extremum vectors in D[K = k0 ] for J. Note that the definition of local extremum vectors for J as given in an earlier section also applies to the set D[K = k0 ] if this set is not open in X. However, the variation of J will not necessarily vanish at a local extremum vector x∗ in this set. The following example shows that the equation resulting from the main theorem of Section 4 can fail to hold for constrained extremum vectors x∗ in D[K = k0 ]. Let J and K be the real-valued functions defined on R by 3 J(x) = x2 , K(x) = x2 + 2x + 4 for any number x in D = R. The set D[K = 0] consists of the two numbers x = − 12 and x = − 32 , i.e., 1 3 D[K = 0] = − , − . 2 2 This set is not open in D = R. Thus, a minimum for J in D[K = 0] is given by x = − 12 and a maximum is given by x = − 32 . Nevertheless, the variation of J fails to vanish at each of these points in D[K = 0] and neither point gives a local extremum for J in D = R. Unlike the preceding example, in many other extremum problems involving a constraint of form K(x) = k0 , it is not possible to determine the set D[K = k0 ] explicitly. The Euler-Lagrange multipliers method allows us to solve many such extremum problems without direct consideration of the set D[K = k0 ]. In order to state this method, we first need to explore the notion of weak continuity of variations. 6.1. Weak Continuity of Variaions. If J is any functional which has a variation on an open set D contained in a normed vector space VARIATIONAL METHODS IN OPTIMIZATION 19 X, and if for some vector x in D lim y→x in X δJ(y; ∆x) = δJ(x; ∆x) holds for every vector ∆x in X, we say that the variation of J is weakly continuous at x. [S60] In other words, if we recall the definition of continuity of functionals, we can state that the variation of J is weakly continuous at x in D whenever each fixed vector ∆x in X with variation δJ(y; ∆x) considered as a functional of y is continuous at y = x. It is sufficient to show that for each fixed ∆x the difference δJ(y; ∆x) − δJ(x; ∆x) can be made arbitrarily small for all vectors y which are sufficiently close to the vector x. The variation of J is weakly continuous near x if the variation of J is weakly continuous at y for every vector y in some ball Bp (x) centered at x. The idea of weak continuity of variations is a generalization to functionals of the notion of continuity of the first-order partial derivatives of real-valued functions of several real variables. As an example, consider a real-valued function F = F (x) defined for all vectors x = (x1 , x2 , ..., xn ) in a fixed open set D. The open set D lies in n-dimensional Euclidean space Rn and the variation δF (x) is defined by n X δF (x; ∆x) = [∂F (x)/∂xi ]∆xi i=1 for any vector ∆x = (∆x1 , ∆x2 , ..., ∆xn ) in Rn . We can show that the variation of F is weakly continuous at x if and only if the function F has continuous first-order partial derivatives ∂F (x)/∂xi at x for i = 1, 2, ..., n. We begin by assuming that ∂F (x)/∂xi is continuous at x for all i. Then n X ∂F (y) lim δF (y; ∆x) = lim ∆xi y→x y→x ∂x i i=1 = n  X i=1 = ∂F (y)  lim ∆xi y→x ∂xi n  X ∂F (x)  i=1 ∂xi ∆xi 20 and now we invoke an earlier result where the variation of a functional was given as the sum of the respective partial derivatives of the functional multiplied by their respective directional vectors to finish the proof in one direction lim δF (y; ∆x) = δF (x; ∆x). y→x Going the other way, we first assume that δF (x; ∆x) is weakly continuous at x. Now we fix j and let ∆xi = 1 only if i = j, otherwise ∆xi = 0. Then n  X ∂F (y) ∂F (y)  lim = lim ∆xi y→x ∂xj y→x ∂xj i=1 = lim δF (y; ∆x) = δF (x; ∆x) y→x n X ∂F (x) = [ ] ∆xi ∂xi i=1 = ∂F (x) . ∂xj 6.2. Euler-Lagrange Multiplier Theorem for a Single Constraint. We are now able to state the multiplier theorem for an extremum problem with a constraint of the form described earlier. Recall that D[K = k0 ] denotes the subset of D consisting of all vectors x in D which satisfy K(x) = k0 . Euler-Lagrange Multiplier Theorem. Let J and K be functionals which are defined and have variations on an open subset D of a normed vector space X, and let x∗ be a local extremum vector in D[K = k0 ] for J, where k0 is any given fixed number for which the set D[K = k0 ] is nonempty. Assume that both the variation of J and the variation of K are weakly continuous near x∗ . Then at least one of the following two possibilities must hold: 1. The variation of K at x∗ vanishes identically, i.e., (10) δK(x∗ ; ∆x) = 0 for every vector ∆x in X; or 2. The variation of J at x∗ is a constant multiple of the variation of K at x∗ , i.e., there is a constant λ such that (11) δJ(x∗ ; ∆x) = λδK(x∗ ; ∆x) VARIATIONAL METHODS IN OPTIMIZATION 21 for every vector ∆x in X. [S62] Note that the theorem guarantees that all possible local extremum vectors in D[K = k0 ] for J must be contained in the collection of those vectors in D[K = k0 ] which satisfy either Equation 10 or Equation 11. However, there may also be other vectors in D[K = k0 ] which satisfy either Equation 10 or Equation 11 that are not local extremum vectors in D[K = k0 ] for J. In practice, our method is to first find all vectors x∗ in D which satisfy the first condition, Equation 10, and then keep for further consideration only those vectors which also satisfy the constraint K(x∗ ) = k0 . Next, we find all vectors x∗ which satisfy the second condition, Equation 11, where the solutions x∗ of this condition generally depend on the value of the parameter λ. Again we only retain for further consideration only those solutions x∗ which also satisfy the constraint K(x∗ ) = k0 . This requirement that x∗ must satisfy the given constraint in addition to the second condition determines a fixed value (or values) for λ in terms of the given constant k0 appearing in the constraint. Any such special value of λ for which both the second condition and the constraint hold is called an Euler-Lagrange multiplier for the given extremum problem. To find the desired maximum or minimum vector in D[K = k0 ] for J, we have to search through the collection of vectors x∗ that we have been accumulating for further consideration. It is sometimes preferable to combine Equations 10 and 11 into one more symmetrical equation µ0 δJ(x∗ ; ∆x) + µ1 δK(x∗ ; ∆x) = 0 for suitable constants µ0 and µ1 . It can be seen that this equation follows from our statement of the Euler-Lagrange multiplier theorem since Equation 10 corresponds to the choices µ0 = 0, µ1 = 1 in the new equation, while Equation 11 corresponds to the choices µ0 = 1, µ1 = −λ. 6.3. Using the E-L Multiplier Theorem. Consider again an extremum problem posed earlier that involves the real-valued functions J and K defined on R by J(x) = x2 and K(x) = x2 + 2x + 43 . We wish to find extremum vectors (numbers) in D[K = 0] for J, where in this case D = R. The variations of J and K are found to be δJ(x; ∆x) = 2x∆x δK(x; ∆x) = 2(x + 1)∆x 22 for any number ∆x. These were obtained using Equation 7 from Section 5. Exploring the first possibility of the Euler-Lagrange multiplier theorem, the only number x∗ which satisfies δK(x; ∆x) = 0 is x∗ = −1. Unfortunately, this number is omitted from further consideration because it does not satisfy the constraint K = 0. Then we must move on and consider the second possibility of the Euler-Lagrange multiplier theorem where the variation of J at x∗ is a constant multiple of the variation of K at x∗ . Thus, we have 2x∗ ∆x = λ2(x∗ + 1)∆x or, equivalently, 2[x∗ − λ(x∗ + 1)]∆x = 0 which must hold for some constant λ and for every number ∆x if x∗ is a local extremum vector in D[K = 0] for J. Making the special choice of ∆x = 1 in the last equation, we can now conclude that any possible local extremum vector x∗ in D[K = 0] for J must satisfy the condition x∗ − λ(x∗ + 1) = 0 for some constant λ. Solving this equation for x∗ , we find that it has solutions depending on the parameter λ: x∗ = λ . 1−λ Substituting our latest result into the constraint K(x∗ ) = 0, we end up with the following equation in quadratic form for λ λ2 − 2λ − 3 = 0 with solutions λ = −1 and λ = 3. Inserting these back into the expression for x∗ in terms of λ, we again come up with the familiar solutions x∗ = − 12 and x∗ = − 32 . A quick check determines which is a minimum or maximum. Let us try to minimize the function x21 + x22 on R2 subject to the constraint x21 −(x2 −1)3 = 0. We can use the Euler-Lagrange multiplier theorem to solve this problem. We begin by denoting J(x) = x21 + x22 and K(x) = x21 − (x2 − 1)3 = 0. The variation of J in D can be found by using n n X X d δJ(x; ∆x) = J(x + ∆x)|=0 = Jxi (x)hi = Jxi (x)∆xi . d i=1 i=1 Thus, δJ(x; ∆x) = 2x1 ∆x1 + 2x2 ∆x2 VARIATIONAL METHODS IN OPTIMIZATION 23 and similarly δK(x; ∆x) = 2x1 ∆x1 − 3(x2 − 1)2 ∆x2 where both are valid for any ∆x = (∆x1 , ∆x2 ) in R2 . Hence if x = (x1 , x2 ) is any fixed vector in D, we see that the variation of K does not vanish identically at any vector x in D. Therefore, the first possibility of the Euler-Lagrange multiplier theorem is eliminated and thus the second possibility must hold at any local extremum vector x∗ in D[K = 0] for J. If x∗ = (x∗1 , x∗2 ) is a minimum point in D[K = 0] for J, then 2x∗1 ∆x1 + 2x∗2 ∆x2 = λ[2x∗1 ∆x1 − 3(x∗2 − 1)2 ∆x2 ] must hold, or, regrouping, (2x∗1 − λ2x∗1 )∆x1 + (2x∗2 + 3λ(x∗2 − 1)2 )∆x2 = 0 for some constant λ and for all numbers ∆x1 and ∆x2 . Making the special choices ∆x1 = 2x∗1 − λ2x∗1 and ∆x2 = 2x∗2 + 3λ(x∗2 − 1)2 in the last equation, we conclude that 2x∗1 − λ2x∗1 = 2x∗1 (1 − λ) = 0 and 2x∗2 + 3λ(x∗2 − 1)2 = 0. This follows from our special choices of ∆x1 and ∆x2 where we end up with two squared terms whose sum can only be zero if both individual terms are zero. The first equation yields either x∗1 = 0 or λ = 1, with the latter possibility being thrown out because it leads to imaginary solutions. Proceeding with x∗1 = 0, we manipulate the constraint equation x21 − (x2 − 1)3 = 0 to get x∗2 = 1. Hence any local extremum vector x∗ in D[K = 0] for J must satisfy x∗ = (x∗1 , x∗2 ) = (0, 1). 6.4. The Euler-Lagrange Multiplier Theorem for Many Constraints. The Euler-Lagrange multiplier theorem for one constraint can be extended to handle extremum problems involving any finite number of constraints of the form K(x) = k. Let K1 , K2 , ..., Km be any collection of functionals which are defined and possess variations on an open subset D of a normed vector space X. Let D[Ki = ki for i = 1, 2, ..., m] denote the subset of D which consists of all vectors x in D that simultaneously satisfy all of the following constraints: K1 (x) = k1 , K2 (x) = k2 , ..., Km (x) = km where k1 , k2 , ..., km may be any given numbers. We always assume that there is at least one vector in D which satisfies all the constraints previously given so that the set D[Ki = ki f or i = 1, 2, ..., m] is not empty. In this case we have the following multiplier theorem. 24 Theorem. Let J, K1 , K2 , ..., Km be functionals which are defined and have variations on an open subset D of a normed vector space X, and let x∗ be a local extremum vector in D[Ki = ki f or i = 1, 2, ..., m] for J, where k1 , k2 , ..., km are any given fixed numbers for which the set D[Ki = ki f or i = 1, 2, ..., m] is nonempty. Assume that the variation of J and the variation of each Ki are weakly continuous near x∗ . Then at least one of the following two possibilities must hold: 1. The following determinant vanishes identically,   δK1 (x∗ ; ∆x1 ) δK1 (x∗ ; ∆x2 ) . . . δK1 (x∗ ; ∆xm )  δK2 (x∗ ; ∆x1 ) δK2 (x∗ ; ∆x2 ) . . . δK2 (x∗ ; ∆xm )  =0 det  .. .. ..   . . . δKm (x∗ ; ∆x1 ) δKm (x∗ ; ∆x2 ) . . . δKm (x∗ ; ∆xm ) for all vectors ∆x1 , ∆x2 , ..., ∆xm in X; or 2. The variation of J at x∗ is a linear combination of the variations of K1 , K2 , ..., Km at x∗ , i.e., there are constants λ1 , λ2 , ..., λm such that ∆J(x∗ ; ∆x) = λ1 δK1 (x∗ ; ∆x) + ... + λm δKm (x∗ ; ∆x) = m X λi δKi (x∗ ; ∆x) i=1 holds for every vector ∆x in X. [S78] 7. An Optimum Consumption Policy with Terminal Savings Constraint During a Period of Inflation Now we consider an investment planning problem involving a person with a known annual income (e.g., salary). Additionally, this person has some accumulated savings which have been invested and earn him a known annual return (e.g., dividends or interest). We assume that the savings can be easily liquidated and converted into consumable goods; this allows the person’s total available annual resources for consumption to consist of current annual income, previous savings, and current annual return on invested savings. The person wants to have accumulated a certain level of savings at the end of T years. In the meantime, he wishes to plan his savings program so that maximum satisfaction is derived from consuming what remains of his available annual resources which is not invested. Then, the problem has to do with deciding how much of the total available annual resources should be consumed and how much should be reinvested annually so as to maximize the satisfaction received from consumption while taking into account the terminal constraint which has been specified for the savings level at the end of T years. VARIATIONAL METHODS IN OPTIMIZATION 25 We let S = S(t) denote the savings which are accumulated and invested at time t. Three factors may affect the savings level S. The known annual income I may be used to increase the savings level; the current annual return R earned on the savings may be reinvested to increase the savings level; and, the current annual consumption C acts to decrease the savings. For simplicity, we assume that the quantities involved may change continuously throughout each year. For example, the savings may be on deposit in a savings bank which compounds interest at a continuous rate, and the individual’s annual consumption rate C is allowed to change from day to day. It is natural to relate the variables S, I, R, and C through the differential equation (see Figure 1) (12) Ṡ = I + R − C which states that the instantaneous rate of change of savings (Ṡ = dS ) dt is given by the difference of the total rate of income (I +R) and the total rate of expenditure (C). [S81] The initial level of savings is assumed to be known (13) S(t) = S0 at t = 0 for a nonnegative constant S0 . Figure 1 We assume that the return R earned on the savings is proportional to the savings level, so that R = αS, where α is a positive constant. Substituting for R in Equation 12, we obtain Ṡ − αS = I − C 26 which can be integrated with Equation 13 to give the savings at time t as Z t αt αt (14) S(t) = e S0 + e e−ατ [I(τ ) − C(τ )]dτ. 0 The income function I = I(t) is assumed to be known over a fixed time period 0 ≤ t ≤ T . In order to solve the optimization problem, we must make a suitable choice for the unknown consumption function C = C(t). We also assume that another requirement is to have a specified level of savings at the end of the time period 0 ≤ t ≤ T , such that (15) S(t) = ST at t = T where ST is a nonnegative constant. Evaluating Equation 14 at t = T and using Equation 15, we find that Z T Z T −αt −αT (16) e C(t)dt = S0 − e ST + e−αt I(t)dt 0 0 must be satisfied by any admissible consumption rate C.8 If we define a functional K on the vector space C 0 [0, T ] by Z T K(C) = e−αt C(t)dt 0 for any function C = C(t) of class C 0 on the interval 0 ≤ t ≤ T , then the constraint given by Equation 16 can be written in the form Z T −αT (17) K(C) = S0 − e ST + e−αt I(t)dt. 0 Thus, the optimization problem we consider is to maximize the satisfaction derived from consumption subject to the constraint given by Equation 17. We need an appropriate measure of the satisfaction derived from any possible consumption rate C = C(t) over the time interval [0, T ]. Such a measure might take the form of an integral such as Z T (18) F (t, C(t))dt 0 where F = F (t, C) would be a suitable function of t and C. For Equation 18 to be a reasonable measure of the satisfaction derived from the consumption rate C, the function F appearing there must satisfy certain natural conditions. For example, the function 8It must be emphasized that the income function I = I(T ) is assumed to be known so that the right-hand side of Equation 16 represents a specified constant. VARIATIONAL METHODS IN OPTIMIZATION 27 F = F (t, C(t)) should be an increasing function of its second argument C. This ensures that the satisfaction measured by Equation 18 increases whenever consumption increases. In this case, the maximization of Equation 18 places a premium on selecting a large consumption rate. For the sake of definitiveness, we consider in detail only the case where F is defined by F (t, C) = e−βt log(1 + C) for any t ≥ 0 and for any C > 0.9 The quantity β is a discount rate which allows for the change in true value (at different times) of a unit of income used in consumption. We assume β > 0, so that the term e−βt decays as t increases and represents the effects of inflation. Finally, we can define a satisfaction functional S by Z T (19) S(C) = e−βt log[1 + C(t)]dt 0 for any suitable consumption function C = C(t). We take the domain of S to be a subset D of the vector space C 0 [0, T ] which consists of all continuous functions C = C(t) on [0, T ] satisfying C(t) > 0. We now want to maximize the functional S on D subject to the constraint given by Equation 17. If we define a constant k0 by Z T −αT e−αt I(t)dt k0 = S 0 − e ST + 0 then the problem is to find a maximum vector C ∗ in the set D[K = k0 ] for the functional S. Utilizing the Euler-Lagrange multiplier theorem of Section 6, we can search for such an extremum vector. Omitting many of the technical details, the variations of K and S are calculated and the Euler-Lagrange multiplier theorem is applied to yield 1 (20) C ∗ (t) = −1 + e(α−β)t λ for 0 ≤ t ≤ T . Inserting Equation 20 back into the constraint given by Equation 16, we find an equation for λ Z T  1  1 − e−αT  β −αT (21) = S0 − e ST + e−αt I(t)dt + . λ α 1 − e−βT 0 To find a unique candidate for the desired extremum vector C ∗ in D[K = k0 ], we may insert the value of λ obtained from Equation 21 back into Equation 20. 9We only consider positive consumption rates. 28 As an example, we can find the optimum consumption rate if both the inflation rate and the investment return rate are .05 (i.e., 5% per year), if an individual has an annual income of $10,000 per year with no initial savings, and if the individual wishes to accumulate $15,000 over a 5-year period while maximizing the satisfaction from consumption as measured by Equation 19. This means α = β = .05, I = 10,000, S0 = 0, ST = 15,000, and T = 5. Putting values these values into Equation 21, we get λ ≈ 0.000135888. Then, substituting this value of λ into Equation 20, we get C ∗ ≈ 7358. Thus, $7358 is the optimum yearly consumption rate for this problem. 8. Applications of the Euler-Lagrange Multiplier Theorem in the Calculus of Variations 8.1. Problems with Fixed End Points. We now consider the problem of maximizing or minimizing the value of a functional J = J(Y ) defined by Z x1 (22) J(Y ) = F (x, Y (x), Y 0 (x))dx x0 in terms of a known function F as in Equation 8 found in Section 5. Here Y = Y (x) is required to be a function of class C 1 on the fixed interval [x0 , x1 ] and we assume that the values of Y at the end points are Y (x0 ) = y0 , Y (x1 ) = y1 for constants y0 and y1 . An example of a functional with the form of Equation 22 is the brachistochrone functional T = T (Y ) of Equation 3 from Section 2. Equation 3 gives the time of descent of a bead sliding down a wire joining two points and the constants y0 and y1 represent the y-coordinates of the two end points of the wire. If we define functionals K0 and K1 by (23) K0 (Y ) = Y (x0 ), K1 (Y ) = Y (x1 ) for any function Y = Y (x) in the vector space C 1 [x0 , x1 ], then the problem we consider is to find extremum vectors in D[K0 = y0 , K1 = y1 ] for the functional J of Equation 22. The open set D is taken to be the entire normed vector space C 1 [x0 , x1 ] with any suitable norm. Using Equation 23 and the definition of the variation10, we see that (24) 10See δK0 (Y ; ∆Y ) = ∆Y (x0 ), Equation 7 in Section 5. δK1 (Y ; ∆Y ) = ∆Y (x1 ) VARIATIONAL METHODS IN OPTIMIZATION 29 for any function ∆Y in C 1 [x0 , x1 ]. The variation of J, according to Equation 9, is given by (25) Z x1 δJ(Y ; ∆Y ) = [FY (x, Y (x), Y 0 (x))∆Y (x)+FY 0 (x, Y (x), Y 0 (x))∆Y 0 (x)]dx x0 for any continuously differentiable function ∆Y = ∆Y (x) on[x0 , x1 ]. The hypotheses of the Euler-Lagrange multiplier theorem of Section 6 are all satisfied, provided that the given function F is ”nice.” At least one of the two possibilities concluded in that theorem must hold for any local extremum vector Y in D[K0 = y0 , K1 = y1 ]. We can eliminate the first possibility since application of the determinant in Section 6.4 using Equation 24 yields a nonzero determinant that does not vanish identically for all functions ∆Y0 and ∆Y1 in C 1 [x0 , x1 ]. Hence, the second possibility of the multiplier theorem must hold. If Y = Y (x) is a local extremum vector in D[K0 = y0 , K1 = y1 ] for J, there exist constants λ0 and λ1 such that δJ(Y ; ∆Y ) = λ0 δK0 (Y ; ∆Y ) + λ1 δK1 (Y ; ∆Y ) holds for all vectors ∆Y in C 1 [x0 , x1 ]. If we use Equations 24 and 25, we can rewrite this condition as R x1 [F (x, Y (x), Y 0 (x))∆Y (x) + FY 0 (x, Y (x), Y 0 (x))∆Y 0 (x)]dx (26) x0 Y = λ0 ∆Y (x0 ) + λ1 ∆Y (x1 ) which must hold for all continuously differentiable functions ∆Y = ∆Y (x). We now want to eliminate the arbitrary vector ∆Y (x) and the derivative ∆Y 0 (x) from Equation 26 so that we can obtain a simpler equation which involves only the extremum vector and may be solved to give Y = Y (x). A method first shown by Joseph Lagrange11 removes the derivative ∆Y 0 from Equation 26 provided that FY 0 (x, Y (x), Y 0 (x)) is continuously differentiable with respect to x. In this case, the product rule of differentiation yields d [FY 0 (x, Y dx 11In 0 0 (x),Y 0 (x))∆Y (x)] = FY 0 (x,  Y (x), Y (x))∆Y (x)+ d F 0 (x, Y (x), Y 0 (x)) ∆Y (x). dx Y 1755, at the age of 19, Lagrange wrote a letter to Leonhard Euler illustrating his method. 30 Integrating the equation above gives R x1 d Rx [FY 0 (x, Y (x),RY 0 (x))∆Y (x)]dx = x01 FY 0 (x, Y (x), Y 0 (x))∆Y 0 (x)dx+ x0 dx x1 d [ F 0 (x, Y (x), Y 0 (x))]∆Y (x)dx, x0 dx Y but the fundamental theorem of calculus implies that R x1 d [FY 0 (x, Y (x), Y 0 (x))∆Y (x)]dx = x0 dx FY 0 (x1 , Y (x1 ), Y 0 (x1 ))∆Y (x1 )dx − FY 0 (x0 , Y (x0 ), Y 0 (x0 ))∆Y (x0 ). Thus, applying the product rule of differentiation again, we find that R x1 [FY 0 (x, Y (x), Y 0 (x))∆Y 0 (x)]dxR= FY 0 (x1 , Y (x1 ), Y 0 (x1 ))∆Y (x1 )dx− x0 x d FY 0 (x0 , Y (x0 ), Y 0 (x0 ))∆Y (x0 ) − x01 [ dx FY 0 (x, Y (x), Y 0 (x))]∆Y (x)dx, which is actually a special case of the general formula for integration by parts. Using this result, we eliminate the term involving ∆Y 0 in Equation 26 and get (27) R x1 d 0 0 [FY (x, Y (x), Y 0 (x)) x0   − dx FY (x, Y (x), Y (x))]∆Y (x)dx = λ0 + FY 0 (x0 , y0 , Y 0 (x0 )) ∆Y (x0 ) + λ1 − FY 0 (x1 , y1 , Y 0 (x1 )) ∆Y (x1 ), which must hold for all vectors ∆Y in the vector space C 1 [x0 , x1 ]. We have used the constraints Y (x0 ) = y0 , Y (x1 ) = y1 in obtaining Equation 27. The constraints are satisfied by any extremum vector Y in D[K0 = y0 , K1 = y1 ]. If we consider only functions ∆Y which vanish at the end points x = x0 and x = x1 , we obtain the following condition from Equation 27 Z x1 d (28) [FY (x, Y (x), Y 0 (x)) − FY 0 (x, Y (x), Y 0 (x))]∆Y (x)dx = 0 dx x0 which must hold for all functions ∆Y of class C 1 on [x0 , x1 ] that satisfy the additional requirements ∆Y (x0 ) = 0 and ∆Y (x1 ) = 0. Since the function in square brackets in Equation 28 is itself a continuous function of x, it follows from Equation 28 and a fundamental lemma12 of the calculus of variations that the extremum function Y (x) must satisfy the second-order differential equation (29) 12See FY (x, Y (x), Y 0 (x)) − d FY 0 (x, Y (x), Y 0 (x)) dx Section A4 of the Appendix in Smith’s Variational Methods in Optimization. VARIATIONAL METHODS IN OPTIMIZATION 31 for all x in [x0 , x1 ]. We finally have the simplified equation13 that we desired. The Euler-Lagrange equation can be simplified in some special cases. Suppose that the given function F = F (x, y, z) does not depend on x so that F = F (y, z). We next differentiate the expression F (Y (x), Y 0 (x)) − Y 0 (x)FY 0 (Y (x), Y 0 (x)) with respect to x utilizing the chain rule of differentiation to find for any smooth function Y (x) that (30) d [F (Y (x), Y 0 (x)) − Y 0 (x)FY 0 (Y (x), Y 0 (x))] dx = FY (Y (x), Y 0 (x))Y 0 (x) + FY 0 (Y (x), Y 0 (x))Y 00 (x) d −Y 00 (x)FY 0 (Y (x), Y 0 (x)) − Y 0 (x) dx FY 0 (Y (x), Y 0 (x)) d 0 0 = Y (x)[FY (Y (x), Y (x)) − dx FY 0 (Y (x), Y 0 (x))]. Thus, if Y (x) is any solution of the Euler-Lagrange equation, we find that d [F (Y (x), Y 0 (x)) − Y 0 (x)FY 0 (Y (x), Y 0 (x))] = 0 dx which can be integrated to give (31) F (Y (x), Y 0 (x)) − Y 0 (x)FY 0 (Y (x), Y 0 (x)) = C for some constant of integration C. In this special case, we may replace the Euler-Lagrange equation with the simpler form of Equation 31. We now have a first-order differential equation for Y (x) which is easier to solve compared to the original second-order differential equation. Consider another special case where the given function F = F (x, y, z) does not depend on y. With F = F (x, z), we have ∂F = 0 and thus ∂y the Euler-Lagrange equation can be reduced to d FY 0 (x, Y 0 (x)) = 0. dx Integrating this equation gives (32) FY 0 (x, Y 0 (x)) = C for some constant of integration C. For this special case, Equation 32 replaces the Euler-Lagrange equation. As an illustrative example of the latter special case, we consider the problem of finding the minimum transit time for a boat to cross a river of length l from an initial point P0 to a terminal point P1 . We assume that the boat travels at a constant speed v0 and that the river is devoid of any cross currents. Taking P0 = (x0 , y0 ) = (0, 0) and 13Equation 29 is known as the Euler-Lagrange equation. 32 P1 = (x1 , y1 ) = (l, y1 ), we seek a curve γ connecting the two points given as γ : y = Y (x), 0 ≤ x ≤ l along which the boat can travel in minimum time. The transit time is given by Z p 1 l 1 − e(x)2 + Y 0 (x)2 − e(x)Y 0 (x) T (Y ) = dx v0 0 1 − e(x)2 where e(x) is defined as the downstream current speed w(x) divided by v0 . The functional T is of the form given by Equation 22 with F given by p 1 − e(x)2 + z 2 − e(x)z F (x, z) = v0 [1 − e(x)2 ] which is independent of y. Therefore, the minimum transit time is attained along a curve γ that satisfies Equation 32. With some calculation we find that p Y 0 (x) − e(x) 1 − e(x)2 + Y 0 (x)2 0 p FY 0 (x, Y (x)) = v0 [1 − e(x)2 ] 1 − e(x)2 + Y 0 (x)2 and Equation 32 implies that p Y 0 (x) − e(x) 1 − e(x)2 + Y 0 (x)2 p = C, v0 [1 − e(x)2 ] 1 − e(x)2 + Y 0 (x)2 which can be simplified to give (33) Y 0 (x)2 = (e(x) + A[1 − e(x)2 ])2 1 − 2Ae(x) − A2 [1 − e(x)2 ] for some constant A = v0 C. We are left with a differential equation that we wish to solve for the extremum function Y (x). Taking the square root of both sides of Equation 33 and integrating the result, we find that Z x e(τ ) + A[1 − e(τ )2 ] p Y (x) = dτ 1 − 2Ae(τ ) − A2 [1 − e(τ )2 ] 0 for 0 ≤ x ≤ l, where the constraint Y (0) = 0 has been imposed.14 The other constraint Y (l) = y1 determines the constant A in terms of the given data l, y1 , and e(x) through Z l e(x) + A[1 − e(x)2 ] p (34) y1 = dx. 1 − 2Ae(x) − A2 [1 − e(x)2 ] 0 14We also assumed that Y (x) ≥ 0 in taking the postive square root. VARIATIONAL METHODS IN OPTIMIZATION 33 Generally, Equation 34 cannot be solved in closed form for A so numerical methods must be utilized to find an approximate value of A. Using the original transit time equation for T (Y ) and Equation 33, we can find the minimum transit time T = Tmin given by Z 1 l 1 − Ae(x) p dx, (35) Tmin = v0 0 1 − 2Ae(x) − A2 [1 − e(x)2 ] where the constant A is determined by Equation 34. Consider a problem where a boat is to cross a uniformly flowing √ feet stream 300 feet wide from an initial point to a terminal point 300 3 downstream on the oppisite bank. The boat travels at a constant speed of 88 feet per minute (or 1 mile per hour) and the stream current has a constant uniform speed of √883 feet per minute. We can find the minimum transit time of the boat by first using Equation 34 to √ , l = 300, and determine the value of A. In this case, we have y1 = 300 3 1 e(x) = √3 so that Equation 34 becomes 300 √ = 3 Z 0 300 ( √13 ) + A[1 − ( √13 )2 ] q dx 1 − 2A( √13 ) − A2 [1 − ( √13 )2 ] and then after integration with respect to x we obtain √1 + 2 A 1 3 3 √ =q . 2 2 2 3 √ −3A − 3A + 1 Since the left side of the last equation is positive, the constant A is required to be positive. Solving this equation for A yields either A = 0 or A = − √33 . The latter value for A is thrown out because it is negative and we see that using A = 0 means Equation 35 becomes Z 300 1 Tmin = dx, 88 0 where integration and simplification give Tmin = 75 . Thus, the mini22 mum transit time for the boat is about 3.41 minutes. 8.2. John Bernoulli’s Brachistochrone Problem. We now consider the problem of finding the shortest time of descent achievable by varying the shape of a wire down which a bead slides under gravity from a higher point to a lower point. As in Section 2, we assume that the force of gravity due to the earth is constant near the earth’s surface 34 and the motion of the bead is frictionless. The wire is represented as a curve γ given as γ : y = Y (x), x0 ≤ x ≤ x1 and thus the problem reduces to minimizing the time functional T = T (Y ) of Equation 3 among all continuously differentiable functions Y = Y (x) satisfying the constraints (36) Y (x0 ) = y0 , Y (x1 ) = y1 . The two end points of the wire are located at P0 = (x0 , y0 ) and P1 (x1 , y1 ). Using the notation of Section 8.1, the problem is to find a minimum vector in D[K0 = y0 , K1 = y1 ] for the functional T of Equation 3. The domain D is the entire vector space C 1 [x0 , x1 ] and the functionals K0 and K1 are defined for any Y = Y (x) by K0 (Y ) = Y (x0 ) and K1 (Y ) = Y (x1 ). Thus, we only need to solve the Euler-Lagrange equation given by Equation 29 subject to the constraints of Equation 36. In this case, the function F is independent of x and is given by s 1 + Y 0 (x)2 F = 2g[y0 − Y (x)] so we may use the simpler Equation 31 instead of Equation 29. We find that Equation 31 implies that s p 1 + Y 0 (x)2 Y 0 (x)2 −p = 2gC y0 − Y (x) [y0 − Y (x)][1 + Y 0 (x)2 ] and after some simplification we obtain s A − [y0 − Y (x)] (37) Y 0 (x) = − y0 − Y (x) where A−1 = 2gC. The differential equation furnished by the Euler-Lagrange equation can be most easily solved with the introduction of a new function θ = θ(x) through the relation θ(x) 2 ]. 2 Inserting Equation 38 into Equation 37 and simplifying, we find that (38) y0 − Y (x) = A [sin θ dθ A [sin ]2 = 1. 2 dx VARIATIONAL METHODS IN OPTIMIZATION 35 Integration using a trigonometric identity15 yields (39) x = x0 + A (θ − sin θ) 2 where x0 is a constant of integration that we have taken to be the xcoordinate of the left end point of the wire. If we use the representation of the curve γ and the previously applied trigonometric identity along with Equations 38 and 39, we obtain another equation given by y = y0 − (40) A (1 − cos θ). 2 Together, Equations 39 and 40 are the parametric equations of a cycloid defined for θ0 ≤ θ ≤ θ1 , where θ0 and θ1 correspond to the end points P0 = (x0 , y0 ) and P1 = (x1 , y1 ) of the wire. The cycloid is generated by the motion of a fixed point on the rim of a wheel of diameter A that is rolling on the underside of the line y = y0 . The parameter θ increases from θ0 to θ1 as the point P = (x, y) travels along the cycloid from P0 = (x0 , y0 ) to P1 = (x1 , y1 ). Taking the initial value of the parameter to be θ0 = 0, at θ = θ1 the parametric Equations 39 and 40 give (41) A(θ1 − sin θ1 ) = 2(x1 − x0 ) A(1 − cos θ1 ) = −2(y1 − y0 ). Therefore, we can adjust the constants A and θ1 so that the resulting cycloid of Equations 39 and 40 connects the two given points P0 and P1 . Using the representation of the curve γ and the derived parametric Equations 39 and 40, we find the value of the minimum descent time of the bead to be Z x1 s Z θ1 s 0 2 1 + Y (x) (dx/dθ)2 + (dy/dθ)2 Tminimum = dx = dθ 2g[y0 − Y (x)] 2g(y0 − y) x0 0 and simplifying we obtain Tminimum = A 2 Z 0 θ1 s 2(1 − cos θ) dθ = gA(1 − cos θ) s A θ1 . 2g The constants A and θ1 are determined by Equation 41. This completes our analysis of John Bernoulli’s brachistochrone problem. 15The trigonometric identity is given by 2[sin θ2 ]2 = 1 − cos θ. 36 9. Conclusion Looking back on the topics covered in this paper, we now have the tools to solve a wider range of more difficult extremum problems. This development came about following our forays into properties of vector spaces, functionals, and generalizing a familiar approach from early calculus. We established and employed a fundamental necessary condition for an extremum using the Gateaux variation, then we explored one constraint optimization problems. A short time learning about the weak continuity of variations preceded a statement of the EulerLagrange Multiplier Theorem and some of its applicationss. The interested reader is encouraged to continue on exploring topics in Smith’s text16 and to search for other challenging optimization problems online and in texts covering similar material. References [1] Smith, Donald R. Variational Methods in Optimization. Mineola, N.Y.: Dover Publications, Inc., 1998. 16See references.