16.323 Lecture 5: Calculus of Variations

16.323 Lecture 5 Calculus of Variations • Calculus of Variations • Most books cover this material well, but Kirk Chapter 4 does a particularly nice job. • See here for online reference. x(t) x*+ αδx(1) x*- αδx(1) x* αδx(1) −αδx(1) t t0 tf Figure by MIT OpenCourseWare. Calculus of Variations 16.323 5–1 • Goal: Develop alternative approach to solve general optimization problems for continuous systems – variational calculus – Formal approach will provide new insights for constrained solutions, and a more direct path to the solution for other problems. • Main issue – General control problem, the cost is a function of functions x(t) and u(t). � tf min J = h(x(tf )) + g(x(t), u(t), t)) dt t0 subject to ẋ = f (x, u, t) x(t0), t0 given m(x(tf ), tf ) = 0 – Call J(x(t), u(t)) a functional. • Need to investigate how to find the optimal values of a functional. – For a function, we found the gradient, and set it to zero to find the stationary points, and then investigated the higher order derivatives to determine if it is a maximum or minimum. – Will investigate something similar for functionals. 16.323 5–2 • Maximum and Minimum of a Function – A function f (x) has a local minimum at x� if f (x) ≥ f (x�) for all admissible x in �x − x�� ≤ � – Minimum can occur at (i) stationary point, (ii) at a boundary, or (iii) a point of discontinuous derivative. – If only consider stationary points of the differentiable function f (x), then statement equivalent to requiring that differential of f satisfy: ∂f dx = 0 ∂x for all small dx, which gives the same necessary condition from Lecture 1 ∂f =0 ∂x df = • Note that this definition used norms to compare two vectors. Can do the same thing with functions ⇒ distance between two functions d = �x2(t) − x1(t)� where 1. �x(t)� ≥ 0 for all x(t), and �x(t)� = 0 only if x(t) = 0 for all t in the interval of definition. 2. �ax(t)� = |a|�x(t)� for all real scalars a. 3. �x1(t) + x2(t)� ≤ �x1(t)� + �x2(t)� • Common function norm: �� tf �x(t)�2 = t0 �1/2 x(t)T x(t)dt 16.323 5–3 • Maximum and Minimum of a Functional – A functional J(x(t)) has a local minimum at x�(t) if J(x(t)) ≥ J(x�(t)) for all admissible x(t) in �x(t) − x�(t)� ≤ � • Now define something equivalent to the differential of a function ­ called a variation of a functional. – An increment of a functional ΔJ(x(t), δx(t)) = J(x(t) + δx(t)) − J(x(t)) – A variation of the functional is a linear approximation of this increment: ΔJ(x(t), δx(t)) = δJ(x(t), δx(t)) + H.O.T. i.e. δJ(x(t), δx(t)) is linear in δx(t). Figure by MIT OpenCourseWare. Figure 5.1: Differential df versus increment Δf shown for a function, but the same difference holds for a functional. 16.323 5–4 x(t) x*+ αδx(1) x*- αδx(1) x* αδx(1) −αδx(1) t t0 tf Figure by MIT OpenCourseWare. Figure 5.2: Visualization of perturbations to function x(t) by δx(t) – it is a potential change in the value of x over the entire time period of interest. Typically require that if x(t) is in some class (i.e., continuous), that x(t) + δx(t) is also in that class. • Fundamental Theorem of the Calculus of Variations – Let x be a function of t in the class Ω, and J(x) be a differentiable functional of x. Assume that the functions in Ω are not constrained by any boundaries. – If x� is an extremal function, then the variation of J must vanish on x�, i.e. for all admissible δx, δJ(x(t), δx(t)) = 0 – Proof is in Kirk, page 121, but it is relatively straightforward. � tf • How compute the variation? If J(x(t)) = t0 f (x(t))dt where f has cts first and second derivatives with respect to x, then � � tf � ∂f (x(t)) δJ(x(t), δx) = δxdt + f (x(tf ))δtf − f (x(t0))δt0 ∂x(t) t0 � tf = fx(x(t))δxdt + f (x(tf ))δtf − f (x(t0))δt0 t0 Variation Examples: Scalar 16.323 5–5 • For more general problems, first consider the cost evaluated on a scalar function x(t) with t0, tf and the curve endpoints fixed. � tf J(x(t)) = g(x(t), ẋ(t), t)dt t0 � tf ⇒ δJ(x(t), δx) = [ gx(x(t), ẋ(t), t)δx + gẋ(x(t), ẋ(t), t)δẋ] dt t0 – Note that d δx dt so δx and δẋ are not independent. δẋ = • Integrate by parts: � � udv ≡ uv − vdu with u = gẋ and dv = δ ẋdt to get: � tf t δJ(x(t), δx) = gx(x(t), ẋ(t), t)δxdt + [gẋ(x(t), ẋ(t), t)δx]tf0 t0 � tf d − gẋ(x(t), ẋ(t), t)δxdt dt t � � tf 0� d = gx(x(t), ẋ(t), t) − gẋ(x(t), ẋ(t), t) δx(t)dt dt t0 t + [gẋ(x(t), ẋ(t), t)δx]tf0 • Since x(t0), x(tf ) given, then δx(t0) = δx(tf ) = 0, yielding � � tf � d δJ(x(t), δx) = gx(x(t), ẋ(t), t) − gẋ(x(t), ẋ(t), t) δx(t)dt dt t0 16.323 5–6 • Recall need δJ = 0 for all admissible δx(t), which are arbitrary within (t0, tf ) ⇒ the (first order) necessary condition for a maximum or minimum is called Euler Equation: ∂g(x(t), ẋ(t), t) d − ∂x dt � ∂g(x(t), ẋ(t), t) ∂ ẋ � =0 • Example: Find the curve that gives the shortest distance between 2 points in a plane (x0, y0) and (xf , yf ). – Cost function – sum of differential arc lengths: � xf � xf � J = ds = (dx)2 + (dy)2 x0 x0 � � �2 � xf dy = 1+ dx dx x0 – Take y as dependent variable, and x as independent one dy → ẏ dx – New form of the cost: � xf � � J= 1 + ẏ 2 dx → x0 xf g(ẏ)dx x0 – Take partials: ∂g/∂y = 0, and � � � � d ∂g d ∂g dẏ = dx ∂ẏ dẏ ∂ẏ dx � � d ẏ ÿ = ÿ = =0 dẏ (1 + ẏ 2)1/2 (1 + ẏ 2)3/2 which implies that ÿ = 0 – Most general curve with ÿ = 0 is a line y = c1x + c2 Vector Functions 16.323 5–7 • Can generalize the problem by including several (N ) functions xi(t) and possibly free endpoints � tf J(x(t)) = g(x(t), ẋ(t), t)dt t0 with t0, tf , x(t0) fixed. • Then (drop the arguments for brevity) � tf δJ(x(t), δx) = [ gxδx(t) + gẋδẋ(t)] dt t0 – Integrate by parts to get: � � tf � d δJ(x(t), δx) = gx − gẋ δx(t)dt + gẋ(x(tf ), ẋ(tf ), tf )δx(tf ) dt t0 • The requirement then is that for t ∈ (t0, tf ), x(t) must satisfy ∂g d ∂g =0 − ∂x dt ∂ẋ where x(t0) = x0 which are the given N boundary conditions, and the remaining N more BC follow from: – x(tf ) = xf if xf is given as fixed, – If x(tf ) are free, then ∂g(x(t), ẋ(t), t) =0 ∂ẋ(tf ) • Note that we could also have a mixture, where parts of x(tf ) are given as fixed, and other parts are free – just use the rules above on each component of xi(tf ) Free Terminal Time 16.323 5–8 • Now consider a slight variation: the goal is to minimize � tf J(x(t)) = g(x(t), ẋ(t), t)dt t0 with t0, x(t0) fixed, tf free, and various constraints on x(tf ) • Compute variation of the functional considering 2 candidate solutions: – x(t), which we consider to be a perturbation of the optimal x�(t) (that we need to find) � tf δJ(x�(t), δx) = [ gxδx(t) + gẋδẋ(t)] dt + g(x�(tf ), ẋ�(tf ), tf )δtf t0 – Integrate by parts to get: tf � d δJ(x�(t), δx) = gx − gẋ δx(t)dt dt t0 + gẋ(x�(tf ), ẋ�(tf ), tf )δx(tf ) + g(x�(tf ), ẋ�(tf ), tf )δtf � � • Looks standard so far, but we have to be careful how we handle the terminal conditions 16.323 5–9 Figure by MIT OpenCourseWare. Figure 5.3: Comparison of possible changes to function at end time when tf is free. • By definition, δx(tf ) is the difference between two admissible func­ tions at time tf (in this case the optimal solution x� and another candidate x). – But in this case, must also account for possible changes to δtf . – Define δxf as being the difference between the ends of the two possible functions – total possible change in the final state: δxf ≈ δx(tf ) + ẋ�(tf )δtf so δx(tf ) �= δxf in general. • Substitute to get � � tf � d δJ(x�(t), δx) = gx − gẋ δx(t)dt + gẋ(x�(tf ), ẋ�(tf ), tf )δxf dt t0 + [g(x�(tf ), ẋ�(tf ), tf ) − gẋ(x�(tf ), ẋ�(tf ), tf )ẋ�(tf )] δtf 16.323 5–10 • Independent of the terminal constraint, the conditions on the solution x�(t) to be an extremal for this case are that it satisfy the Euler equations gx(x�(t), ẋ�(t), t) − d gẋ(x�(t), ẋ�(t), t) = 0 dt – Now consider the additional constraints on the individual elements of x�(tf ) and tf to find the other boundary conditions • Type of terminal constraints determines how we treat δxf and δtf 1. Unrelated 2. Related by a simple function x(tf ) = Θ(tf ) 3. Specified by a more complex constraint m(x(tf ), tf ) = 0 • Type 1: If tf and x(tf ) are free but unrelated, then δxf and δtf are independent and arbitrary ⇒ their coefficients must both be zero. gx(x�(t), ẋ�(t), t) − d gẋ(x�(t), ẋ�(t), t) = 0 dt g(x�(tf ), ẋ�(tf ), tf ) − gẋ(x�(tf ), ẋ�(tf ), tf )ẋ�(tf ) = 0 gẋ(x�(tf ), ẋ�(tf ), tf ) = 0 – Which makes it clear that this is a two-point boundary value problem, as we now have conditions at both t0 and tf 16.323 5–11 • Type 2: If tf and x(tf ) are free but related as x(tf ) = Θ(tf ), then δxf = dΘ (tf )δtf dt – Substitute and collect terms gives � � � tf � d dΘ δJ = gx − gẋ δxdt + gẋ(x�(tf ), ẋ�(tf ), tf ) (tf ) dt dt t0 � + g(x�(tf ), ẋ�(tf ), tf ) − gẋ(x�(tf ), ẋ�(tf ), tf )ẋ�(tf ) δtf – Set coefficient of δtf to zero (it is arbitrary) ⇒ full conditions gx(x�(t), ẋ�(t), t) − gẋ(x�(tf ), ẋ�(tf ), tf ) � d gẋ(x�(t), ẋ�(t), t) = 0 dt � dΘ (tf ) − ẋ�(tf ) + g(x�(tf ), ẋ�(tf ), tf ) = 0 dt – Last equation called the Transversality Condition • To handle third type of terminal condition, must address solution of constrained problems. 16.323 5–12 Image removed due to copyright restrictions. Figure 5.4: Summary of possible terminal constraints (Kirk, page 151) Example: 5–1 16.323 5–13 • Find the shortest curve from the origin to a specified line. • Goal: minimize the cost functional (See page 5–6) � tf � J= 1 + ẋ2(t) dt t0 given that t0 = 0, x(0) = 0, and tf and x(tf ) are free, but x(tf ) must line on the line θ(t) = −5t + 15 • Since g(x, x, ˙ t) is only a function of x, ˙ Euler equation reduces to � � d ẋ�(t) =0 dt [1 + ẋ�(t)2]1/2 which after differentiating and simplifying, gives ẍ�(t) = 0 ⇒ answer is a straight line x�(t) = c1t + c0 but since x(0) = 0, then c0 = 0 • Transversality condition gives � � x˙ �(tf ) � � 2 1/2 [−5 − ẋ (t )] + [1 + ẋ (t ) ] =0 f f [1 + x˙ �(tf )2]1/2 that simplifies to [ẋ�(tf )] [−5 − ẋ�(tf )] + [1 + ẋ�(tf )2] = −5ẋ�(tf ) + 1 = 0 so that ẋ�(tf ) = c1 = 1/5 – Not a surprise, as this gives the slope of a line orthogonal to the constraint line. • To find final time: x(tf ) = −5tf + 15 = tf /5 which gives tf ≈ 2.88 Example: 5–2 16.323 5–14 • Had the terminal constraint been a bit more challenging, such as 1 dΘ Θ(t) = ([t − 5]2 − 1) ⇒ =t−5 2 dt • Then the transversality condition gives � � ẋ�(tf ) [tf − 5 − ẋ�(tf )] + [1 + ẋ�(tf )2]1/2 = 0 � 2 1/2 [1 + ẋ (tf ) ] [ẋ�(tf )] [tf − 5 − ẋ�(tf )] + [1 + ẋ�(tf )2] = 0 c1 [tf − 5] + 1 = 0 • Now look at x�(t) and Θ(t) at tf x�(tf ) = − tf 1 = ([tf − 5]2 − 1) (tf − 5) 2 which gives tf = 3, c1 = 1/2 and x�(tf ) = t/2 Figure 5.5: Quadratic terminal constraint. Corner Conditions 16.323 5–15 • Key generalization of the preceding is to allow the possibility that the solutions not be as smooth – Assume that x(t) cts, but allow discontinuities in ẋ(t), which occur at corners. – Naturally occur when intermediate state constraints imposed, or with jumps in the control signal. • Goal: with t0, tf , x(t0), and x(tf ) fixed, minimize cost functional � tf J(x(t), t) = g(x(t), ẋ(t), t)dt t0 – Assume g has cts first/second derivatives wrt all arguments – Even so, ẋ discontinuity could lead to a discontinuity in g. • Assume that ẋ has a discontinuity at some time t1 ∈ (t0, tf ), which is not fixed (or typically known). Divide cost into 2 regions: � t1 � tf J(x(t), t) = g(x(t), ẋ(t), t)dt + g(x(t), ẋ(t), t)dt t0 t1 • Expand as before – note that t1 is not fixed � � t1 � ∂g ∂g δJ = δx + δẋ dt + g(t− 1 )δt1 ∂x ∂ẋ t0 � � tf � ∂g ∂g + δx + δẋ dt − g(t+ 1 )δt1 ∂x ∂ẋ t1 16.323 5–16 • Now IBP t1 � d − − δJ = gx − (gx˙ ) δxdt + g(t− 1 )δt1 + gẋ (t1 )δx(t1 ) dt t0 � � tf � d + + + gx − (gẋ) δxdt − g(t+ 1 )δt1 − gẋ (t1 )δx(t1 ) dt t1 � � • As on 5–9, must constrain δx1, which is the total variation in the solution at time t1 from lefthand side from righthand side − δx1 = δx(t− 1 ) + ẋ(t1 )δt1 + δx1 = δx(t+ 1 ) + ẋ(t1 )δt1 – Continuity requires that these two expressions for δx1 be equal + – Already know that it is possible that ẋ(t− 1 ) �= ẋ(t1 ), so possible + that δx(t− 1 ) �= δx(t1 ) as well. • Substitute: � � t1 � � � d − − δJ = gx − (gẋ) δxdt + g(t− ) − g (t )ẋ(t ) δt1 + gẋ(t− ẋ 1 1 1 1 )δx1 dt t � � 0tf � � � d + + + gx − (gẋ) δxdt − g(t+ ) − g (t )ẋ(t ) δt1 − gẋ(t+ ẋ 1 1 1 1 )δx1 dt t1 • Necessary conditions are then: gx − d (gẋ) = 0 t ∈ (t0, tf ) dt + gẋ(t− 1 ) = gẋ (t1 ) − − + + + g(t− 1 ) − gẋ (t1 )ẋ(t1 ) = g(t1 ) − gẋ (t1 )ẋ(t1 ) – Last two are the Weierstrass-Erdmann conditions 16.323 5–17 • Necessary conditions given for a special set of the terminal conditions, but the form of the internal conditions unchanged by different terminal constraints – With several corners, there are a set of constraints for each – Can be used to demonstrate that there isn’t a corner • Typical instance that induces corners is intermediate time constraints of the form x(t1) = θ(t1). – i.e., the solution must touch a specified curve at some point in time during the solution. • Slightly complicated in this case, because the constraint couples the allowable variations in δx1 and δt since dθ δx1 = δt1 = θ̇δt1 dt – But can eliminate δx1 in favor of δt1 in the expression for δJ to get new corner condition: � � � � − − − − + + + + g(t1 )+gẋ(t1 ) θ̇(t1 ) − ẋ(t1 ) = g(t1 )+gẋ(t1 ) θ̇(t1 ) − ẋ(t1 ) + – So now gẋ(t− 1 ) = gẋ (t1 ) no longer needed, but have x(t1 ) = θ(t1 ) Corner Example 16.323 5–18 • Find shortest length path joining the points x = 0, t = −2 and x = 0, t = 1 that touches the curve x = t2 + 3 at some point �1 √ • In this case, J = −2 and x(t1) = t21 + 3 1 + ẋ2dt with x(1) = x(−2) = 0 • Note that since g is only a function of ẋ, then solution x(t) will only be linear in each segment (see 5–13) segment 1 x(t) = a + bt segment 2 x(t) = c + dt – Terminal conditions: x(−2) = a − 2b = 0 and x(1) = c + d = 0 • Apply corner condition: � � − � ẋ(t− 1) − − 2 1 + ẋ(t1 ) + � 2t − ẋ(t ) 1 1 2 1 + ẋ(t− 1) − + 1 + 2t− 1 + 2t+ 1 ẋ(t1 ) 1 ẋ(t1 ) =� =� 2 2 1 + ẋ(t+ 1 + ẋ(t− ) 1) 1 which gives: 1 + 2bt1 1 + 2dt1 √ =√ 2 1+b 1 + d2 • Solve using fsolve to get: a = 3.0947, b = 1.5474, c = 2.8362, d = −2.8362, t1 = −0.0590 function F=myfunc(x); % % x=[a b c d t1]; % F=[x(1)-2*x(2); x(3)+x(4); (1+2*x(2)*x(5))/(1+x(2)^2)^(1/2) - (1+2*x(4)*x(5))/(1+x(4)^2)^(1/2); x(1)+x(2)*x(5) - (x(5)^2+3); x(3)+x(4)*x(5) - (x(5)^2+3)]; return % x = fsolve(’myfunc’,[2 1 2 -2 0]’) Constrained Solutions 16.323 5–19 • Now consider variations of the basic problem that include constraints. • For example, if the goal is to find the extremal function x� that minimizes � tf J(x(t), t) = g(x(t), ẋ(t), t)dt t0 subject to the constraint that a given set of n differential equations be satisfied f (x(t), ẋ(t), t) = 0 where we assume that x ∈ Rn+m (take tf and x(tf ) to be fixed) • As with the basic optimization problems in Lecture 2, proceed by augmenting cost with the constraints using Lagrange multipliers – Since the constraints must be satisfied at all time, these multipliers are also assumed to be functions of time. � tf � � T Ja(x(t), t) = g(x, ẋ, t) + p(t) f (x, ẋ, t) dt t0 – Does not change the cost if the constraints are satisfied. – Time varying Lagrange multipliers give more degrees of freedom in specifying how the constraints are added. • Take variation of augmented functional considering perturbations to both x(t) and p(t) δJ(x(t), δx(t), p(t), δp(t)) � tf �� � � � � = gx + pT fx δx(t) + gẋ + pT fẋ δẋ(t) + f T δp(t) dt t0 16.323 5–20 • As before, integrate by parts to get: δJ(x(t), δx(t), p(t), δp(t)) � � � tf �� � � � � d = gx + pT fx − gẋ + pT fẋ δx(t) + f T δp(t) dt dt t0 • To simplify things a bit, define ga(x(t), ẋ(t), t) ≡ g(x(t), ẋ(t), t) + p(t)T f (x(t), ẋ(t), t) • On the extremal, the variation must be zero, but since δx(t) and δp(t) can be arbitrary, can only occur if � � ∂ga(x(t), ẋ(t), t) d ∂ga(x(t), ẋ(t), t) − = 0 ∂x dt ∂ ẋ f (x(t), ẋ(t), t) = 0 – which are obviously a generalized version of the Euler equations obtained before. • Note similarity of the definition of ga here with the Hamiltonian on page 4–4. • Will find that this generalization carries over to future optimizations as well. 16.323 5–21 General Terminal Conditions • Now consider Type 3 constraints on 5–10, which are a very general form with tf free and x(tf ) given by a condition: m(x(tf ), tf ) = 0 • Constrained optimization, so as before, augment the cost functional � tf J(x(t), t) = h(x(tf ), tf ) + g(x(t), ẋ(t), t)dt t0 with the constraint using Lagrange multipliers: T � tf Ja(x(t), ν, t) = h(x(tf ), tf )+ν m(x(tf ), tf )+ g(x(t), ẋ(t), t)dt t0 • Considering changes to x(t), tf , x(tf ) and ν, the variation for Ja is � � T T δJa = hx(tf )δxf + htf δtf + m (tf )δν + ν mx(tf )δxf + mtf (tf )δtf � tf + [gxδx + gẋδẋ] dt + g(tf )δtf t0 � � � T = hx(tf ) + ν mx(tf ) δxf + htf + ν mtf (tf ) + g(tf ) δtf � � tf � d +mT (tf )δν + gx − gẋ δxdt + gẋ(tf )δx(tf ) dt t0 � T – Now use that δxf = δx(tf ) + ẋ(tf )δtf as before to get � � T δJa = hx(tf ) + ν mx(tf ) + gẋ(tf ) δxf � � T + htf + ν mtf (tf ) + g(tf ) − gẋ(tf )ẋ(tf ) δtf + mT (tf )δν � � tf � d + gx − gẋ δxdt dt t0 16.323 5–22 • Looks like a bit of a mess, but we can clean it up a bit using w(x(tf ), ν, tf ) = h(x(tf ), tf ) + ν T m(x(tf ), tf ) to get δJa = [wx(tf ) + gx˙ (tf )] δxf � � + wtf + g(tf ) − gẋ(tf )ẋ(tf ) δtf + mT (tf )δν � � tf � d + gx − gẋ δxdt dt t0 – Given the extra degrees of freedom in the multipliers, can treat all of the variations as independent ⇒ all coefficients must be zero to achieve δJa = 0 • So the necessary conditions are d gẋ = 0 dt wx(tf ) + gẋ(tf ) = 0 wtf + g(tf ) − gẋ(tf )ẋ(tf ) = 0 gx − (dim n) (dim n) (dim 1) – With x(t0) = x0 (dim n) and m(x(tf ), tf ) = 0 (dim m) combined with last 2 conditions ⇒ 2n + m + 1 constraints – Solution of Eulers equation has 2n constants of integration for x(t), and must find ν (dim m) and tf ⇒ 2n + m + 1 unknowns • Some special cases: – If tf is fixed, h = h(x(tf )), m → m(x(tf )) and we lose the last condition in box – others remain unchanged – If tf is fixed, x(tf ) free, then there is no m, no ν and w reduces to h. • Kirk’s book also considers several other type of constraints.