Calculus of Variation on Local Regions of Function Space

[-dove]

I am familiar with basic calculus of variations. For example, how to find a function that makes some integral functional stationary (Euler-Lagrange Equations). Or for example, how to perform that same problem but with some additional holonomic constraint or with some integral constraint. The problem I am interested in, however, is how to find a function that makes some property stationary (let's say an integral functional) subject to inequality constraints. In particular I am interested in solving the usual stationary integral functional problem, but where the solution is confined to some region of function space defined by simple inequalities.

A very simple example:

What is the shortest path f(x) that connects the point (-2,1) to the point (2,1) such that f(x)≤x²?

In this problem, it is as if the standard parabola is a wall that blocks one from taking the usual straight line path. Intuitively, I'd say that the shortest path is the one that starts as a straight line from (-2,1) that is tangent to the parabola, approaches the parabola and then begins following the parabola, then bends back off the parabola on the tangent that carries it to (2,1). However, I have no clue how to prove this mathematically. There are also more complicated functionals than arc length that I am interested in minimizing, but hopefully this example will suffice for me to understand the general principle for attacking these sorts of problems.EDIT: Whoa! I typed this too hastily and originally used the points (-1,1) and (1,1) which are on the parabola itself ::facepalm::. Now it should make sense.

 

[-dove]

150+ views and no leads? Is the question at least clear?

As an addendum: I also wonder how restrictions of smoothness get involved. The Euler–Lagrange approach doesn't specify whether the function space it is optimizing over is the space of all continuous functions, or all differentiable functions, or all analytic functions, etc. In the example I give in the previous post, the answer may be different depending on how smooth the function need be. The "intuitive" answer I give is continuous and differentiable, but is not twice differentiable (the problem spots are the points where the path switches from straight line to parabola and vice versa). I can't think of any intuitive solutions when restricted to twice differentiable functions.

 

[haruspex]

In general, the optimal path may or may not touch the boundary, and if it touches the boundary then it may do so over discontinuous arbitrary intervals. So (fairly) generally could suppose it follows the boundary over a set of intervals (x_1i, x_2i), i = 1..n. Trouble is, there's no limit on n. But in many circumstances you might be able to argue such a limit.
In the specific example, a limit of 1 seems fair. So construct a formula for the path (x_a, y_a), (x₁₁, f(x₁₁)), (x₂₁, f(x₂₁)), (x_b, y_b), where the first and last legs are unconstrained and the middle leg follows the boundary. Next, find the ranges of values for x₁₁ and x₂₁ s.t. the first and last legs do not violate the constraint. Then optimise the total length wrt the two intermediate points.
Clearly this can get very messy as the number of constraints increases.

 

[-dove]

But what if it the optimum solution is one where it doesn't touch at all? More importantly, what if you don't know how many times it touches in the optimal solution? Remember, this approach has to handle general functionals that may not have anything to do with the arc length of the path.

Forcing it to touch exactly once, or any n number of times for that matter, may give you a suboptimal solution. Furthermore, there is nothing in that piecewise approach that specifically prevents the path from violating the inequality. Just because it is forced to ride on the boundary for some interval doesn't mean that the standard Lagrangian approach won't make it break the boundary in the other intervals. You could also have problems with more than one boundary. In fact, the cases I'm interested in have two boundaries.

I feel like there should be some way to directly embed inequality constraints into the usual Lagrangian method, or perhaps there should be some other equally straightforward way of solving a calculus of variations problem that has such constraints.

One way I can think of doing it would be to add a term to the Lagrangian that is 0 in the allowed regions and quickly rises to an extremely high value at all boundaries. However, this is pretty much only useful for numerical simulations. Forget finding a closed-form function that actually gives you that last term. In principle, you could solve the problem with such a term, then take the limit where the boundary value and the slope at the boundary both go to infinity. But like I said, this is far from being practically attainable.

 

[haruspex]

But what if it the optimum solution is one where it doesn't touch at all?

I didn't spell that out, but the idea was that having set a limit of N sections you try 0 to N.

More importantly, what if you don't know how many times it touches in the optimal solution? Remember, this approach has to handle general functionals that may not have anything to do with the arc length of the path.

Quite so, but I couldn't see a way to do it in such generality.

Just because it is forced to ride on the boundary for some interval doesn't mean that the standard Lagrangian approach won't make it break the boundary in the other intervals.

As I said, you have to figure out the ranges for the interval endpoints (which may lead to functional relationships between them) before optimising.

One way I can think of doing it would be to add a term to the Lagrangian that is 0 in the allowed regions and quickly rises to an extremely high value at all boundaries.

Not only at the boundaries, but everywhere the wrong side of the boundary.
Yes, that might work. You'd want some parameter which drives the value in the forbidden region towards infinity as you vary it. Might be hard to dream up such a function though, and you still need to be able to do the calculus on it..

 

[-dove]

I didn't spell that out, but the idea was that having set a limit of N sections you try 0 to N.

So you mean try every value for n that seems reasonable, perform the optimization routine for each one, then calculate the resulting functional for each case, compare all of them by hand, and choose the one that is optimal?

To be honest, the whole thing seems more convoluted than it ought to be. But regardless, there are larger problems with this approach. If you know the answer doesn't touch the boundary at all (n=0), then this procedure just reduces to the standard Lagrangian approach which we know will not respect the boundaries. Furthermore, I still don't see how it will ensure that the boundaries are obeyed for arbitrary n. In the example I gave, if you took n=2, then undoubtedly you'd end up with a path section that cut straight through the unallowed region.

Not only at the boundaries, but everywhere the wrong side of the boundary.

Yep.

Yes, that might work. You'd want some parameter which drives the value in the forbidden region towards infinity as you vary it. Might be hard to dream up such a function though, and you still need to be able to do the calculus on it..

Tell me about it...hence why I'm in no rush to call this a solution. The best I can think of is coming up with the necessary bump function by convoluting the indicator function for the unallowed region with a sufficiently narrow mollifier (not hard to construct) and then multiplying the whole thing by a scaling constant that will be taken to infinity at the end. (For an exact result you'd also have to take the limit where the mollifier is infinitely narrow, i.e. a delta, but this will probably have very little effect on the actual result so isn't necessary for certain approximate applications.) But, as you point out, good luck doing calculus on it. Perhaps it is somewhat feasible for numerical simulations, but even that I am not sure about.


So as to not encourage solutions that are only feasible for overly simple situations, let me state a simple form of the problem I am most interested in studying:

Given a 90 degree circular turn on a flat road of fixed width, find the fastest path around the turn (known as the 'racing line').

The naive answer is to hug the inside of the road. This only correct if you have enough traction available to take that line at the top speed of the vehicle (which is almost never the case), in which case it is the top speed of the vehicle that limits your time. Instead, the usual situation is that you have some fixed amount of traction, and any path around the turn will have to be taken at a speed much lower than the top speed of the vehicle. So, while tighter paths are shorter, they also demand a lower speed to prevent the vehicle from loosing traction.

The popular knowledge is that neither the inside edge nor the outside edge provide the proper balance. The correct 'racing line' for a 90 degree circular fixed width curve is claimed to be the largest circle you can fit in the turn. That is, it starts at a point on the outside edge, curves in and touches the inside edge exactly at the apex, and then curves back out and hits the outside edge at the end of the turn. While it is easy to verify that this path will be faster than the inside or outside edge paths (or any other circular path that shares it's origin with these two paths), I have never found a mathematical proof that it is indeed the optimal path. We know for a fact that it is the 'safest path' in that it minimizes the traction used up by centripetal force (any other path will have at least one instant in time during which it exceeds the curvature of this path). However, I can't give it any more credit than being a pretty damn good sounding guess for the fastest path. Furthermore, no one even has mathematically defined guesses for other types of more complex turns. All I can find are drawings of roughly the line to follow which I assume are just communal knowledge built up over many years in the racing community as a product of guessing, thinking about simpler situations, following intuition, minimizing centripetal force alone, and trial and error on the track.

This problem SCREAMS calculus of variations. The only catch is that you need these sort of inequality constraints/boundaries to keep the paths on the road. Given the already existing, simple techniques for certain type of constraints on such problems (holonomic and functional equality constraints), it feels like the sort of thing that would be 'doable'.

Not only is it a very interesting problem that 1) just interests me and I feel like I should be able to solve and 2) would be a great pedagogical example/exercise when teaching calculus of variations, but 3) it has some serious real world applications that I'd be interesting in working on in my spare time.

 

[haruspex]

So you mean try every value for n that seems reasonable, perform the optimization routine for each one, then calculate the resulting functional for each case, compare all of them by hand, and choose the one that is optimal?

Yes

If you know the answer doesn't touch the boundary at all (n=0), then this procedure just reduces to the standard Lagrangian approach which we know will not respect the boundaries.

If the n=0 solution does not touch a boundary then it doesn't cross one either. I don't see the problem. If it does cross a boundary, discard it; otherwise it will likely be the optimal for any n.

Furthermore, I still don't see how it will ensure that the boundaries are obeyed for arbitrary n. In the example I gave, if you took n=2, then undoubtedly you'd end up with a path section that cut straight through the unallowed region.

You're overlooking what I said about range relationships. With n=2, you have 4 variable points on the boundary, parameterised by p1, .. , p4. The assumption is that you don't have to worry about the boundary on the p2-p3 leg. That imposes a range relationship between p2 and p3. In this case, you quickly discover that every optimal p2-p3 path will violate the boundary unless p2=p3, so you're back to n=1. In more general contexts, the relationship may take a more complicated functional form: α < p1< p2, f(p2) < p3 < p4 < β.

Given a 90 degree circular turn on a flat road of fixed width, find the fastest path around the turn (known as the 'racing line').

If the straight road is long enough each side of the bend, you can start (at infinity) on the side of the road which becomes the outside of the bend. So pick a point on that boundary, distance x from the bend, and we can let x tend to infinity later (if appropriate). Same deal, same x, on the downstream side of the bend.
I assume there'll be constraints on acceleration, so also set the initial and final trajectories as being tangential to the outside boundary.
Equally clearly, we will want to touch the inside boundary, but only either transiently or over a single interval. Again, the limited acceleration implies tangential movement (unless we come to a stop), so looks like we can assume it's a single point of contact.
So that's it: two freeform (non-boundary) legs, with a variable point in common. Because we will insist that it's tangential contact on the inside boundary, there's no danger of getting an invalid solution for the freeform legs either side.
If the inside of the bend is a point (zero radius of curvature) then coming to a stop becomes an option to be considered.

 

[-dove]

Yes

If the n=0 solution does not touch a boundary then it doesn't cross one either. I don't see the problem. If it does cross a boundary, discard it; otherwise it will likely be the optimal for any n.

You're overlooking what I said about range relationships. With n=2, you have 4 variable points on the boundary, parameterised by p1, .. , p4. The assumption is that you don't have to worry about the boundary on the p2-p3 leg. That imposes a range relationship between p2 and p3. In this case, you quickly discover that every optimal p2-p3 path will violate the boundary unless p2=p3, so you're back to n=1. In more general contexts, the relationship may take a more complicated functional form: α < p1< p2, f(p2) < p3 < p4 < β.

Maybe I'm misunderstanding you. But consider the following situation: Imagine we were interested in the classic 'fastest path' problem between two points where we are given some 'speed limit' function (a function of position). In this case we are dealing with two dimensions. This is a classic calculus of variations type problem. Say the speed limit function is relatively low everywhere, except for two fast tracks where the speed limit function is very high. One fast track includes the line y=1 connecting our two endpoints. The other takes a longer route following y=x^2-3. We can imagine that the speed limit function drops off smoothly, but quickly, when off of these two fast tracks.

Now, if we just solve the problem with no boundaries, we'll get the y=1 path. If we enforce an f(x)≤x^2 boundary then we should get an answer that is close to the y=x^2-3 path, but perhaps it rides close to the drop off edge depending on the details of how fast the drop off is. This path is an n=0 type path. But, if we follow your algorithm for n=0 then (unless I'm missing something) we would just get the y=1 path which violates the boundary. Sure, we could observe the second fast track in this scenario, but one can invent other scenarios where the proper path doesn't touch the boundary, is different from the boundary-less optimal path, and isn't obvious.

If the straight road is long enough each side of the bend, you can start (at infinity) on the side of the road which becomes the outside of the bend. So pick a point on that boundary, distance x from the bend, and we can let x tend to infinity later (if appropriate). Same deal, same x, on the downstream side of the bend.
I assume there'll be constraints on acceleration, so also set the initial and final trajectories as being tangential to the outside boundary.
Equally clearly, we will want to touch the inside boundary, but only either transiently or over a single interval. Again, the limited acceleration implies tangential movement (unless we come to a stop), so looks like we can assume it's a single point of contact.
So that's it: two freeform (non-boundary) legs, with a variable point in common. Because we will insist that it's tangential contact on the inside boundary, there's no danger of getting an invalid solution for the freeform legs either side.
If the inside of the bend is a point (zero radius of curvature) then coming to a stop becomes an option to be considered.

How are you sure that the fastest path touches the boundary at all? What if the path that correctly balances traction and arc length is a path that remains entirely in the road? We have no way a priori of knowing whether or not this is the case besides intuition. If it is the case, then this method cannot work, because the only single segment path (n=0) it would give is the straight line connecting the beginning and ending of the turn. We have no way of forcing a solution that doesn't touch the boundary. Unless I'm misunderstanding your approach.

 

[haruspex]

Imagine we were interested in the classic 'fastest path' problem between two points where we are given some 'speed limit' function (a function of position). In this case we are dealing with two dimensions. This is a classic calculus of variations type problem. Say the speed limit function is relatively low everywhere, except for two fast tracks where the speed limit function is very high. One fast track includes the line y=1 connecting our two endpoints. The other takes a longer route following y=x^2-3. We can imagine that the speed limit function drops off smoothly, but quickly, when off of these two fast tracks.

Now, if we just solve the problem with no boundaries, we'll get the y=1 path. If we enforce an f(x)≤x^2 boundary then we should get an answer that is close to the y=x^2-3 path, but perhaps it rides close to the drop off edge depending on the details of how fast the drop off is. This path is an n=0 type path. But, if we follow your algorithm for n=0 then (unless I'm missing something) we would just get the y=1 path which violates the boundary.

Since the n = 0, y = 1 solution violates the boundary you would discard it and look for other solutions. That would include both an n=1 solution, etc., and other local minima at n=0. (I'm not aware that calc of var has any magic bullets for this - you always need to consider local minima and compare by hand.) That would find the other fast path, no?

Sure, we could observe the second fast track in this scenario, but one can invent other scenarios where the proper path doesn't touch the boundary, is different from the boundary-less optimal path, and isn't obvious.

If it doesn't touch a boundary it will be a local minimum under n = 0.

How are you sure that the fastest path touches the boundary at all? What if the path that correctly balances traction and arc length is a path that remains entirely in the road?

You can rule that out quickly and convincingly in this inbstance. As my x increases, it costs less and less to arrange to be closer to the inside of the bend on the turn. The extra time taken to migrate across from outside of bend to inside on the approach tends to zero. The trajectory is the 'same', just migrated closer to the inside of the bend with effectively straight bits added at the ends for the increase in x.
More generally, such a solution would have been a local minimum in the n = 0 case.

 

[-dove]

If it doesn't touch a boundary it will be a local minimum under n = 0.

Gah! Of course! Sorry for the stupidity. I'm just so use to dealing with Lagrangians with a single extremum for given endpoints that I entirely forgot about the Euler-Lagrange equations' ability to deal with local extrema. (I blame undergrad physics.)

I see your point now, and agree that it is the way to go about it. It's completely analogous to standard calculus.

Here's an interesting piece of info on the subject:
http://en.wikipedia.org/wiki/Calculus_of_variations#Lavrentiev_phenomenon