From Monge Transport to Skorokhod Embeddings
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Palmer, Aaron Zeff
We explore a dynamic formulation of the optimal transportation problem with the additional freedom to choose the end-time of each trajectory. The dual problem is then posed with a Hamilton-Jacobi variational inequality, which we analyze with the method of viscosity solutions. We find properties that imply the optimal stopping-time is the hitting-time of the free boundary to the variational inequality.
 And he's titled this ultimate transportation with free end times. Thank you. But your time is free end time because lunch is waiting. Thank you. I'll try not to keep you too long. And I'd like to thank all the organizers for inviting me and to Naseef. Nice to meet you, Naseef. And I'll be talking about work that's with Naseef Kaseub and Yohan Kim at UBC, where I'm a postdoc. And it's all fairly new. So I apologize for my mistakes like in the first slide that gave today's approach to 10. But the topic will be relating these two classical problems. Where the first problem is familiar to all of us, the lunch of transportation problem. The one just considering how to move a big pile of snow, which is piled according to distribution U, into a snow fort, for example, new, and do it in an optimal way to minimize the transportation cost. Whereas the scrollpot embedding problem starts with a Brownian motion, which begins according to a fixed distribution U. And you have to construct a stopping time tau, which such that the Brownian motion at the stopping time tau has distribution nu, the target distribution. So the metaphor here is a pollination of strawberries by dangling. And there are some real models, real applications for this problem that there's a metaphor. But one of the main questions to ask is when the transportation problem consider when the optimal transportation is given by a map. Here we're really considering when the optimal stopping time is given by the hitting time of a barrier. So the first time the Brownian motion enters some close up. So the barriers are? Oh, yeah. I won't use R later. So here's a little bit of a tour to connect these two problems, these two seemingly different problems. And the first step is something that's come up a few times in this conference so far, which is the dynamic formulation for optimal transportation with the fixed end time. So here we look at optimal transportation costs that can be written as the infimum of a Lagrangian over curves connecting the initial point y and the target z. And so the first sort of consider maybe for the quadratic Lagrangian, which which builds the quadratic cost function is considered by Venemo and Brenier, kind of relating it to fluid mechanics. And later, Bernardo Bufoni with applications to matter theory, as he mentioned yesterday, and Fatiha Tagali also extended that work. And I apologize right now that I'm a hazard of new system in these fields and if I miss some important references, please forgive me. So our main project will be focusing on a variation of this problem where the, instead of the fixed end time at one, we consider the optimization problem where we're not only optimizing over curves gamma, but also with a free end time tab. And so it shows up both as the integral sign should probably be inside brackets, the integral of over the integral of the running cost or Lagrangian and the end position is now the curve at time. But in this formulation still use a transportation cost or an optimal transportation problem. And it's natural now to kind of generalize this to a control theory perspective, which is some of my, my background's been studying control theory. And this has been done in the fixed end time case by Leon Agriche, the difference, the things we change here are instead of optimizing over all curves with a Lagrangian that depends on the derivative of the curve. We now are optimizing over control policies and end times and the dynamics, the curve is determined by the differential equation with some prescribed velocity function. So this was considered a fixed end time developing the theory of using a Pontiac and maximum principle, but now we can consider it with the free end time as well. But the next step is actually a big leap and also has to do with my background in stochastic optimal control theory, where now we want to look at the stochastic version of the problem. So we replace the deterministic differential equation for the control, for the trajectory gamut with a stochastic differential equation for a process xt with a new diffusion term. And the big leap here is that now the optimization problem can no longer be formulated as an optimal transportation problem. But what we want to do is use the techniques that we can, or use the analog of the techniques for optimal transportation to also study this problem. And this has already been had important contributions at least for fixed end time in optimal transportation related literature, starting with Mikami Ikulin who looked at the limit as the diffusion goes to zero and how this recovers the optimal transportation maps. And then Shinti Yanargin-Rapani and as a young Shintian earlier Chen Pavone in Georgia looking at the linear quadratic case and how this relates to a minimization of the attribute. But so the actual problem we'll be discussing in this talk is both this free end time deterministic control and then we'll just simplify and look at the scroll card and then a problem where there's no control. We have the Brownian motion but we keep the minimization of a running cost or the ground gain and the freedom to choose the end time tau. And this has had a large and very large and important literature starting in probability even more recently because of applications to mathematical points. And I'll discuss. We lost the XT here. So I replaced XT so XT had a stochastic differential equation but now we're just working directly with the Brownian motion. So here WT is just the Brownian motion that we assume is beginning with the distribution mu but then we're constrained to have it stop with the distribution mu using the stop time machine. So this is a subset of this problem where this stochastic differential equation is just XT equals WT. F is 0 sigma 1. Yeah. So next I want to kind of give an overview of the type of problems we're going to consider. And so to begin with just the general problem is just the classical existence in this theory. And so here I first am referring to the results of Gingbo and McCann because this gives a sort of direct analogy to the way they resolved the problem for the optimal transportation is kind of a direct analogy to our approach for this problem. But the history of course is a lot longer and includes many contributions. But a important thing to consider for the uniqueness aspect is whether or not the optimal transport can be given by a transportation map. And so in our case this adds a not so classical element which is considering whether the end time can be recovered as the hitting time of a barrier. And so one of the tools we use is the Pontiagin maximum principle in particular the transfer sality condition for the optimal control problems with free end time. But then also in the scrollcott and vetting literature this has been considered by these authors, Brute and Roast. And the other tool that we'll make use of in particular to translate the techniques from the deterministic version to the stochastic version is the Eulerian formulation of the optimal transportation problem. The mentioned four has been considered by Bernoulli and Bernard DeFony. And the important thing is that this relates the problem to fluid mechanics, to kinetic theory, you'll see the formulation of our problem is closely related to kinetic theory. The interesting aspect of that is when we consider the Cantorovic duality, we find that the Cantorovic duality can be expressed using as a reboundary PDE. In particular an optimization over a variational inequality or quasi-variational inequality of the type that's been considered for example by Vincent Sain and Jons as the equations that determine the value functions for optimal stopping problems in stochastic deterministic optimal control. But then the free boundary PDE is also a reason in the scrollcott and vetting problem. There are some of the authors that have considered it. But the new part that we'll bring to this is how we consider this as part of the dual optimization problem to our free end time optimization. And this all leads to a lot of questions involving how to understand the solutions to these differential equations, whether weak solutions or viscosity solutions and understanding regularity. And this is a topic that I think affects pretty much everyone. Everyone here, lots of contributions from everyone. So the literature is too big to summarize. But in particular one thing that's been very helpful for me is reading the great book on the introduction of variational inequality as a professor, Kindler, and Stapakia. Which is available in the book online. So part one. Is this available at Ectronik, man? Yes. Okay, so here's the problem the first problem we'll consider, which is the occult transportation with the cost function defined by the occult control problem with free end time. And the first thing I want to discuss is what is the Eulerian formulation for this problem. So the theorem is under certain conditions, the mu is nice and everything else is nice. The infamon value over the transportation problem is equal to the infamon value over an Eulerian formulation where we work with Eta, which is a time dependent density on base space as in kinetic theory. So we're satisfying that the initial condition, at least the spatial marginal, is given by the source distribution mu. And then we have a stopping measure, which is just the ordinary probability measure on space and time, satisfying that the spatial marginal is the target distribution mu. So instead of the free end time case where you're transporting from the density from time 0 to time 1, which gives the sort of interpolation of auto transportation from the con. Now we have a sort of smearing of the transport plan as a space time density, which has as its spatial marginal the target distribution. And so the continuity equation takes this form where this is an equation for each t and x. In the weak form this also will include the source constraint. And so you notice this is immediately indetermined on the velocity space. So either it could be any measure on velocity space, which you can think of as corresponding to some generalized trajectories for our optimal control problem. But the one dimension, one direction of this theorem is sort of obvious that if you have a transportation map and nice enough trajectories, you can embed them into a density in stopping measure and get a weak selection to this continuity equation showing that the E is less than or equal to B. That the equivalent we have to consider the dual picture. So to begin with, I want to review how the duality shows up for the optimal transportation problem given by Lagrangians with a fixed end time. So this is the standard Cantorovic duality using this sign conventions. You have the constraint is that the n potential psi minus the initial potential phi should be less than or equal to the cost. And so the standard duality theorem states that this is equal to the initial value function. And then here, you can always assume the potentials are optimized in this sense. So since we're maximizing this, we want phi to be as small as possible. So we can always choose it to be the supremum over those that satisfy the constraint. But then when you see that when you have this supremum, you can actually replace this with the infimum over the trajectories to get this is just the supremum over all trajectories where we have the n potential now evaluated at the terminal position and the integral of Lagrangian. So this correspondence really relates the potential to the value function j psi, which is the solution to Hamilton-Jakobi equation. And this Hamilton-Jakobi equation runs backwards in time starting at time one equal to psi and giving phi at time zero. And really, the solution is you could determine as just the supremum over the trajectories starting at time t and at position y. And that shows the equivalence between the phi and the Scotty solution, Hamilton-Jakobi equation. Which can also be expressed then more classically in terms of the Hamiltonian flow where you have the gamma, the trajectory and its momentum satisfying Hamiltonian equations in the relationship being the momentum should be the greater value of the function j. So now I want to go into the free end time problem and show the relationship with the duality. But now I take a different perspective and do it directly from the Eulerian formulation. So if you remember in the Eulerian formation there are really two constraints. There's the target constraint that the spatial marginal of the stopping measure mu is equal to nu and the continuity equation. And so those have dual functions. But I don't know if I emphasize this, but the Eulerian formulation we had before was a linear optimization problem. They had a linear, Eulerian equation that was linear in eta and a linear cost in eta and only linear constraints. So we can formulate the dual as a linear optimization problem with the dual function psi corresponding to the target distribution constraint and the dual function j corresponding to the continuity equation constraint. And because we had the condition eta and rho were non-negative in Eulerian formulation which is a very significant condition we only get inequalities. And so the two inequalities say that psi should always be less than or equal to j and that j should always be a super solution. Well, okay. So this solution holds now for each t, each x and each v. But we could do the same thing of optimizing over the potentials, particularly optimizing over j. And a well-known result in viscosity solutions is that the viscosity solution to, in this case, a quasi-variational inequality can be expressed as the minimum, point-wise minimum over all super solutions. So what we see here is these equations here are the equivalent to being a super solution to this quasi-variational inequality where we see if this, the max of this being equal to zero implies each one of these individually is less than or equal to zero, but also implies at each point one of these should hold. And so this is given, the viscosity solution by Perron's method is given by the point-wise minimum over all j satisfying this equation, which is necessarily satisfied by the, or we can assume satisfied by the optimum of j. Here. Now this is just the equation in T and x because we've used the Hamiltonian where we've also taken the soup over, and we're showing that in this equation. And the proof that these two are equivalent problems just happens from the dynamic programming principle, essentially the same as I mentioned on the previous slide where now that you have a representation of an optimized potential phi as the supremum over all trajectories gamma, n times tau of the integral of the cost and the n potential at the end position. So why does this help us characterize the solution? Well here's just a simple proposition, you can state using improvement, a lot of generality that is the only time dependence on the equation occurs in the Hamiltonian, which comes from the time dependence of the cost function L. So if L is increasing that implies the Hamiltonian is decreasing and can show that that implies the unique discussed solution j psi is not increasing, by decreasing I mean not increasing. And the same occurs if L is decreasing. So in both of these cases you have an explicit expression for the free boundary which separates the points where this is an inequality and this is an inequality just given by taking the infimum over times for the first case or the second case. And so then the analog to optimizing over the n potential psi is then given by having psi satisfy this transversality condition along this free boundary. So a couple of pictures, see these pictures, psi is on the support of the target distribution nu is in blue and here's the case of A so j is in red and it's decreasing until it begins to hit psi. And this position psi again is in red and here's a double snapshot in time as psi increases and separates from j. So those points where j, transversality condition, so I don't know, in the Pontiagin maximum principle terminology, transversality condition is used to, to describe the terminal conditions for the generalized momentum. And when you have a free n time problem, you get an additional constraint on the, or the Pontiagin maximum principle which is that the Hamiltonian should be zero at the n position and n time. And that's really what's showing up here. In fact, it doesn't imply that there's any sort of transverse intersection. So, okay. So, so under these, under these, under these conditions, particularly with L, strictly increasing or strictly decreasing and a nice enough Hamiltonian like strictly convex and smooth and nu and nu have indensity, for example, you get a unique optimal transport map. And this is a transport plan which is given by a transportation map, which is just the optimal introductory gamma x evaluated at the optimal n times tau, which satisfy this transversality condition at the, which, so, and this condition is the Hamiltonian now is strictly increasing or strictly decreasing, this uniquely determines n time tau. And particularly it determines it as the pre-downing on gamma. And then for previous times, you have the same sort of Hamiltonian flow for the trajectory symbol. And the Eulerian point of view, the Eulerian point of view has nice compactness properties. It's easy to show attainment of optimizers. And then given, given the characterization of the dual problem, the support of the target, the support of the stopping measure should be in the graph of the free boundary. Also, it turns out that the value function is C1, then you can see that it determines the momentum part of the equation and you just get that the support of eta in the velocity space is always at the derivative of the Hamiltonian. And the density is uniquely determined by this continuity equation, just a nice transport equation, but now nonlinear because it involves both J and eta. And what's sort of unresolved is in the case even if everything is nice, the solutions J might not be C1. And the case that they're elliptous, kind of, in general you could have like discontinuities in the gradient along shocks. And so there's still a bit of a question in the Eulerian formulation of whether the optimal eta is uniquely determined in that case, in the case that J is on the ellipticians. And so in this slide I just want to make a little relationship with the classical transportation problems, which is what when you get, you choose this Lagrangian where, so it's infinite if the speed is greater than 1 and it's the derivative of some time dependent function. The speed is less than or equal to 1, whereas function is increasing, it's zero. So the optimal trajectories connecting any point Y and Z is the straight line with speed 1. And so in this case the transportation cost has this familiar form of a convex or concave function of the distance of Y and Z. So this of course has been studied by Gamebo and Necan, showed that existence of a transfer map. So now here we have this sort of picture of the difference of the solutions in these two regimes, which is that if E is convex, that corresponds to our case where the cost is strictly increasing. And in this case the free boundary is hit from below by the trajectories, so the time goes in the, is increasing in the vertical direction. So the trajectories have slope zero and are hitting the free boundary from above, and in this case the G is concave, they hit it. Or hit the free boundary from above in the case G is concave, which corresponds to orientation preserving or rotation reversing the object. Okay, so now I'd like to move on to the scroll cut problem. So the techniques are basically going to be the same. So in history, 28 constructions by problem lists and one view, so maybe a few of these. But then recently in the mathematical finance literature, it's been related to important problems in the options pricing, and there's been a nice review by Avaloch considering all the different constructions and relating them to optimization problems, which is generally not how they're constructed in the first place. So our optimization problem we're going to consider here is just this minimizing over stopping times tau that satisfies this target constraint, the transport embed, the Brownian motion, beginning at view, and the distribution. So earlier in formulation is a bit simpler now. But we have to use it because we don't have an optimal transportation formulation anymore. And so now we have non-negative density eta and stopping measure rho satisfying this heat equation, which is really like a substitution of the heat equation since rho is non-negative, starting at mu and transporting, stopping along mu. And the dual problem has the same form where we just are maximizing over the difference of the potentials. And the potentials are a solution to something that looks like a parabolic equation going backwards in time. This is the sign, so on. And inequality. So similar to before, the system of inequality is when we minimize over J is given by the quasi-variational inequality, where one of these conditions should hold at this point. But to prove the dual problems actually attained, we have a couple remaining problems to deal with. So here, one thing, whenever psi is always less than J, you could subtract a positive function. But clearly that doesn't maximize the cost, so you can just always assume psi is the largest function below it. But then a little harder to deal with is you can subtract a subharmonic function from both psi and J, which still results in a super solution to this equation. And this shows unless the measures mu and nu are in subharmonic order, that would imply that the dual problem is unbattered, that the dual value is actually infinity. So a necessary condition for the primal problem to be feasible is then that the measures mu and nu are in subharmonic order, which is a stand. Easy to show just properties of Marni-Gales as well. This is harder to handle, but you got some ways to do it. It's a bit of a work in progress. And then to conclude that the dual problem is attained, and not only attained, it's attained at sufficiently regular psi and J. So that means twice-weekly, differentiable, and continuous in particular. And psi, yeah. And so the point of having them sufficiently regular is to make sense of these conditions. So to check optimality, you really just have to prove that there's no duality gap between the optimizers. That's just saying that if you have admissible eta and rho and admissible psi and J psi, then if the costs are equal, they must be optimal. And then given the equations, you can see that this immediately yields the sort of complementary slackness conditions, which is saying psi is equal to J, anywhere where rho, everywhere on the support of rho, rho almost everywhere. And the backwards parabolic equation is satisfied almost everywhere on the support of eta. But then we have this exact same proposition that we had in the deterministic case, which determines the, which describes the dual functions J psi and psi. And so once again, the monotonyst E and psi of J psi only depends on whether L is increasing or decreasing. The free boundary can then be described explicitly. And sort of important for the proof of dual attainment is that in fact, you can choose psi so that the, it satisfies this sort of transversality condition where there's a plastic size given by the free boundary. And as a result from the previous slide, you can conclude that eta has support in the set where, in the set of x where t is less than the free boundary. This follows from the L being strictly increasing that if this condition, this condition is satisfied at S, it cannot, the inequality can't, it can't be satisfied for t greater than s for psi, which was must in constant. So, so we get this condition on the support of eta, which uniquely determines eta. And if you assume extra regularity, then you can see that, okay, well, actually it's just the equation that's relating the rate of particles stopping on the free boundary, which is given by the gradient of eta dotted with the gradient of the free boundary with the target distribution. So in fact, everything, all the dependence now goes away besides the free boundary. So eta doesn't depend on J and psi at all, as it did in the first part of the talk. It did depend on J and psi in the first part. Now it just depends on the free boundary. And one of the consequences of this is that in fact, there's a, there's a rigidity which says that if you have a free boundary S, which determines the optimal stopping time for some increasing L, then it's optimal for any increasing L. And then it is unique. So, so the reason is, well, once you have a free boundary, then you cannot just use this equation to redetermine psi. And then given this equation, you can just solve the backwards parabolic equation to get J psi that's equal to psi on the free boundary. And by the comparison principle, that will be a super solution to the equation. So it's optimal. And the case A and B are really the same. You just have to replace the domains with either the hypergraph or the hypergraph of the free boundary S. And this, this equation for the case B would reverse the orientation in a sense, so you replace new with new. And finally, I want to like relate it to the work of these three authors who go about Cox and Houston got an influential paper relating the scrollcard embedding problem with optimal transportation. But they, and they took a different perspective, which was the perspective on pass space. And what, how they expressed the duality of the dual problem as the maximizing over all martingales on the probabilities case, maximizing the difference of psi and the expectation at time zero with the constraint that the martingale is always greater than equal to some continuous function psi. So what we've done is kind of reduce this problem to just something that's on the, on the space time. And, and can see given the optimal J and tau, you can explicitly construct this martingale just as the evaluation of the function J along a Brownian motion with the expectation of the remaining cost. And, but one of the important aspects of our work is now using the PDE method. We have sort of new ways to prove the dual attainment, which they didn't have. So they did have a similar characterization of the stopping time as hitting of a barrier using something, something like the cyclic monotensity principle on pass space. So just to end, I want to kind of go back and talk about this sort of general case, which I skipped over. So in the general case, we have some stochastic differential equation with a control variable A, and we want to choose both the control variable A and the n time tau to minimize the expected cost subject to the, to the stopping constraint. And you can write it in this or in that way. Before we had the integration over the velocity space, it's almost as natural just having a general control space. And it's a well continuity equation or a factor plane equation. With row, row is still non-negative. Stopping measure, eta takes values as measures on this control space. And then immediately as of any optimization problem, you have some duality where the dual problem is posed over, over the same, same potentials. In fact, the same proposition holds that when you have the solutions, you have the same monotonicity properties to characterize the tau. Although, okay, there's some details when you have the diffusion depending on X and A, there's some technical details you get fully nonlinear equations. But even in the case where sigma is just constant, there's a lot of interesting things to be done here. And so I think there's a case where sigma is constant and as we had in the first part, that was just the velocity. And then L was the Hamiltonian, the grandian. You get some interesting, interesting problems depending on the growth conditions for the Hamiltonians. So in particular, it's sort of, you get these three sort of distinct cases where if the Hamiltonian grows super quadratically, quadratically, or sub-quadratically, well, when it's growing super quadratically, you can sort of immediately get some quarter space estimates. And actually, that's nice. This ship sort of shows you can really control the processes. When it's sub-quadratic, you can sort of show that the density always has finite entropy. So you can never control it beyond at least having finite entropy. And then for the quadratic case, this is sort of what's been considered by Leonard and Gentian and others and having really nice relationships with the problem of minimization of entropy on path space. So I think I'll leave it there. Thank you everyone. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Questions? Let's look at it. So the role, when the role is optimal, when you get the role and can you say more about the role or can you? How about row? About the structure of row. So the easy thing to show is based on this condition. Without any, with only, okay, just assuming that this psi and j are continuous, this immediately implies that row, that the support would grow is in the set where j psi is equal to psi. So what we're really doing is in the case where the dual problem has a solution that has this sort of monotensity property so that j psi is equal to psi on the epigraph of a function and the cost is increasing, then you can show that row is actually supported on the boundary. And the reason being that, so for the square root of the writing problem, if it enters into the set where j psi is equal to psi, we have the second condition that says that the parabolic equation should be satisfied, but now j psi is equal to psi so that says that one, that the positive of psi should be equal to L, but L is strictly increasing and it's L is strictly increasing in time in this case. And so this is not, and so it's satisfied along the free boundary but not satisfied at later times. So we have to get a strict inequality for psi, which leads to a strict inequality here, which implies that, well, in this case it implies there's no support for eta but then from the conjugate equation you can apply there's no possibility you have row. So the row, the row needs to be supported on the free boundary. Answering question about regularity of the free boundary is a very difficult problem, but of course it's not applied by anything I've discussed. In the stochastic case, if you thought of applying the kind of techniques you're using to another kind of problem, the problem is state constraints. It's across the infinite, or many of my settings makes sense. Yes, so certainly there's a connection with a lot of these problems. A lot of the literature, at least I've seen on these problems, takes the perspective of backwards stochastic differential equations and they pose the backwards stochastic equations as some sort of transversality condition for the state constraint. And it's closely related in some ways, but to draw the connection with the stochastic differential equations is pretty clear, but using these methods for state constraints, I haven't really considered yet. But you think there's an unrivaled practical combination, this one is right today, stopping time. Right, so actually it's probably the same just because the condition in state constraints is generally, I would say, I think that you just restrict to the row that are properly measured. Some set O, right, so just restricting to the property is the same. But I haven't really thought about how it really relates. Any other question? Everybody's hungry? Thank you.
 And he's titled this ultimate transportation with free end times.  Thank you.  But your time is free end time because lunch is waiting.  Thank you.  I'll try not to keep you too long.  And I'd like to thank all the organizers for inviting me and to Naseef.  Nice to meet you, Naseef.  And I'll be talking about work that's with Naseef Kaseub and Yohan Kim at UBC, where I'm a postdoc.  And it's all fairly new.  So I apologize for my mistakes like in the first slide that gave today's approach to 10.  But the topic will be relating these two classical problems.  Where the first problem is familiar to all of us, the lunch of transportation problem.  The one just considering how to move a big pile of snow, which is piled according to distribution U,  into a snow fort, for example, new, and do it in an optimal way to minimize the transportation cost.  Whereas the scrollpot embedding problem starts with a Brownian motion,  which begins according to a fixed distribution U.  And you have to construct a stopping time tau, which such that the Brownian motion at the stopping time tau  has distribution nu, the target distribution.  So the metaphor here is a pollination of strawberries by dangling.  And there are some real models, real applications for this problem that there's a metaphor.  But one of the main questions to ask is when the transportation problem consider when the optimal transportation is given by a map.  Here we're really considering when the optimal stopping time is given by the hitting time of a barrier.  So the first time the Brownian motion enters some close up.  So the barriers are?  Oh, yeah. I won't use R later.  So here's a little bit of a tour to connect these two problems, these two seemingly different problems.  And the first step is something that's come up a few times in this conference so far,  which is the dynamic formulation for optimal transportation with the fixed end time.  So here we look at optimal transportation costs that can be written as the infimum of a Lagrangian over curves connecting the initial point y and the target z.  And so the first sort of consider maybe for the quadratic Lagrangian, which which builds the quadratic cost function is considered by Venemo and Brenier,  kind of relating it to fluid mechanics.  And later, Bernardo Bufoni with applications to matter theory, as he mentioned yesterday, and Fatiha Tagali also extended that work.  And I apologize right now that I'm a hazard of new system in these fields and if I miss some important references, please forgive me.  So our main project will be focusing on a variation of this problem where the, instead of the fixed end time at one, we consider the optimization problem where we're not only optimizing over curves gamma,  but also with a free end time tab.  And so it shows up both as the integral sign should probably be inside brackets, the integral of over the integral of the running cost or Lagrangian and the end position is now the curve at time.  But in this formulation still use a transportation cost or an optimal transportation problem.  And it's natural now to kind of generalize this to a control theory perspective, which is some of my, my background's been studying control theory.  And this has been done in the fixed end time case by Leon Agriche, the difference, the things we change here are instead of optimizing over all curves with a Lagrangian that depends on the derivative of the curve.  We now are optimizing over control policies and end times and the dynamics, the curve is determined by the differential equation with some prescribed velocity function.  So this was considered a fixed end time developing the theory of using a Pontiac and maximum principle, but now we can consider it with the free end time as well.  But the next step is actually a big leap and also has to do with my background in stochastic optimal control theory, where now we want to look at the stochastic version of the problem.  So we replace the deterministic differential equation for the control, for the trajectory gamut with a stochastic differential equation for a process xt with a new diffusion term.  And the big leap here is that now the optimization problem can no longer be formulated as an optimal transportation problem.  But what we want to do is use the techniques that we can, or use the analog of the techniques for optimal transportation to also study this problem.  And this has already been had important contributions at least for fixed end time in optimal transportation related literature, starting with Mikami Ikulin who looked at the limit as the diffusion goes to zero and how this recovers the optimal transportation maps.  And then Shinti Yanargin-Rapani and as a young Shintian earlier Chen Pavone in Georgia looking at the linear quadratic case and how this relates to a minimization of the attribute.  But so the actual problem we'll be discussing in this talk is both this free end time deterministic control and then we'll just simplify and look at the scroll card and then a problem where there's no control.  We have the Brownian motion but we keep the minimization of a running cost or the ground gain and the freedom to choose the end time tau.  And this has had a large and very large and important literature starting in probability even more recently because of applications to mathematical points.  And I'll discuss.  We lost the XT here.  So I replaced XT so XT had a stochastic differential equation but now we're just working directly with the Brownian motion. So here WT is just the Brownian motion that we assume is beginning with the distribution mu but then we're constrained to have it stop with the distribution mu using the stop time machine.  So this is a subset of this problem where this stochastic differential equation is just XT equals WT.  F is 0 sigma 1.  Yeah.  So next I want to kind of give an overview of the type of problems we're going to consider.  And so to begin with just the general problem is just the classical existence in this theory. And so here I first am referring to the results of Gingbo and McCann because this gives a sort of direct analogy to the way they resolved the problem for the optimal transportation is kind of a direct analogy to our approach for this problem.  But the history of course is a lot longer and includes many contributions.  But a important thing to consider for the uniqueness aspect is whether or not the optimal transport can be given by a transportation map.  And so in our case this adds a not so classical element which is considering whether the end time can be recovered as the hitting time of a barrier.  And so one of the tools we use is the Pontiagin maximum principle in particular the transfer sality condition for the optimal control problems with free end time.  But then also in the scrollcott and vetting literature this has been considered by these authors, Brute and Roast.  And the other tool that we'll make use of in particular to translate the techniques from the deterministic version to the stochastic version is the Eulerian formulation of the optimal transportation problem.  The mentioned four has been considered by Bernoulli and Bernard DeFony. And the important thing is that this relates the problem to fluid mechanics, to kinetic theory, you'll see the formulation of our problem is closely related to kinetic theory.  The interesting aspect of that is when we consider the Cantorovic duality, we find that the Cantorovic duality can be expressed using as a reboundary PDE.  In particular an optimization over a variational inequality or quasi-variational inequality of the type that's been considered for example by Vincent Sain and Jons as the equations that determine the value functions for optimal stopping problems in stochastic deterministic optimal control.  But then the free boundary PDE is also a reason in the scrollcott and vetting problem.  There are some of the authors that have considered it. But the new part that we'll bring to this is how we consider this as part of the dual optimization problem to our free end time optimization.  And this all leads to a lot of questions involving how to understand the solutions to these differential equations, whether weak solutions or viscosity solutions and understanding regularity.  And this is a topic that I think affects pretty much everyone. Everyone here, lots of contributions from everyone. So the literature is too big to summarize.  But in particular one thing that's been very helpful for me is reading the great book on the introduction of variational inequality as a professor, Kindler, and Stapakia.  Which is available in the book online.  So part one.  Is this available at Ectronik, man?  Yes.  Okay, so here's the problem the first problem we'll consider, which is the occult transportation with the cost function defined by the occult control problem with free end time.  And the first thing I want to discuss is what is the Eulerian formulation for this problem.  So the theorem is under certain conditions, the mu is nice and everything else is nice.  The infamon value over the transportation problem is equal to the infamon value over an Eulerian formulation where we work with Eta, which is a time dependent density on base space as in kinetic theory.  So we're satisfying that the initial condition, at least the spatial marginal, is given by the source distribution mu.  And then we have a stopping measure, which is just the ordinary probability measure on space and time, satisfying that the spatial marginal is the target distribution mu.  So instead of the free end time case where you're transporting from the density from time 0 to time 1, which gives the sort of interpolation of auto transportation from the con.  Now we have a sort of smearing of the transport plan as a space time density, which has as its spatial marginal the target distribution.  And so the continuity equation takes this form where this is an equation for each t and x. In the weak form this also will include the source constraint.  And so you notice this is immediately indetermined on the velocity space.  So either it could be any measure on velocity space, which you can think of as corresponding to some generalized trajectories for our optimal control problem.  But the one dimension, one direction of this theorem is sort of obvious that if you have a transportation map and nice enough trajectories, you can embed them into a density in stopping measure and get a weak selection to this continuity equation showing that the E is less than or equal to B.  That the equivalent we have to consider the dual picture.  So to begin with, I want to review how the duality shows up for the optimal transportation problem given by Lagrangians with a fixed end time.  So this is the standard Cantorovic duality using this sign conventions. You have the constraint is that the n potential psi minus the initial potential phi should be less than or equal to the cost.  And so the standard duality theorem states that this is equal to the initial value function. And then here, you can always assume the potentials are optimized in this sense.  So since we're maximizing this, we want phi to be as small as possible. So we can always choose it to be the supremum over those that satisfy the constraint.  But then when you see that when you have this supremum, you can actually replace this with the infimum over the trajectories to get this is just the supremum over all trajectories where we have the n potential now evaluated at the terminal position and the integral of Lagrangian.  So this correspondence really relates the potential to the value function j psi, which is the solution to Hamilton-Jakobi equation.  And this Hamilton-Jakobi equation runs backwards in time starting at time one equal to psi and giving phi at time zero.  And really, the solution is you could determine as just the supremum over the trajectories starting at time t and at position y.  And that shows the equivalence between the phi and the Scotty solution, Hamilton-Jakobi equation.  Which can also be expressed then more classically in terms of the Hamiltonian flow where you have the gamma, the trajectory and its momentum satisfying Hamiltonian equations in the relationship being the momentum should be the greater value of the function j.  So now I want to go into the free end time problem and show the relationship with the duality. But now I take a different perspective and do it directly from the Eulerian formulation.  So if you remember in the Eulerian formation there are really two constraints. There's the target constraint that the spatial marginal of the stopping measure mu is equal to nu and the continuity equation.  And so those have dual functions. But I don't know if I emphasize this, but the Eulerian formulation we had before was a linear optimization problem.  They had a linear, Eulerian equation that was linear in eta and a linear cost in eta and only linear constraints. So we can formulate the dual as a linear optimization problem with the dual function psi corresponding to the target distribution constraint  and the dual function j corresponding to the continuity equation constraint.  And because we had the condition eta and rho were non-negative in Eulerian formulation which is a very significant condition we only get inequalities.  And so the two inequalities say that psi should always be less than or equal to j and that j should always be a super solution. Well, okay.  So this solution holds now for each t, each x and each v.  But we could do the same thing of optimizing over the potentials, particularly optimizing over j.  And a well-known result in viscosity solutions is that the viscosity solution to, in this case, a quasi-variational inequality can be expressed as the minimum, point-wise minimum over all super solutions.  So what we see here is these equations here are the equivalent to being a super solution to this quasi-variational inequality where we see if this, the max of this being equal to zero implies each one of these individually is less than or equal to zero,  but also implies at each point one of these should hold.  And so this is given, the viscosity solution by Perron's method is given by the point-wise minimum over all j satisfying this equation, which is necessarily satisfied by the, or we can assume satisfied by the optimum of j.  Here.  Now this is just the equation in T and x because we've used the Hamiltonian where we've also taken the soup over, and we're showing that in this equation.  And the proof that these two are equivalent problems just happens from the dynamic programming principle, essentially the same as I mentioned on the previous slide where now that you have a representation of an optimized potential phi as the supremum over all  trajectories gamma, n times tau of the integral of the cost and the n potential at the end position.  So why does this help us characterize the solution? Well here's just a simple proposition, you can state using improvement, a lot of generality that is the only time dependence on the equation occurs in the Hamiltonian, which comes from the time dependence of the cost function L.  So if L is increasing that implies the Hamiltonian is decreasing and can show that that implies the unique discussed solution j psi is not increasing, by decreasing I mean not increasing.  And the same occurs if L is decreasing.  So in both of these cases you have an explicit expression for the free boundary which separates the points where this is an inequality and this is an inequality just given by taking the infimum over times for the first case or the second case.  And so then the analog to optimizing over the n potential psi is then given by having psi satisfy this transversality condition along this free boundary.  So a couple of pictures, see these pictures, psi is on the support of the target distribution nu is in blue and here's the case of A so j is in red and it's decreasing until it begins to hit psi.  And this position psi again is in red and here's a double snapshot in time as psi increases and separates from j.  So those points where j, transversality condition, so I don't know, in the Pontiagin maximum principle terminology, transversality condition is used to,  to describe the terminal conditions for the generalized momentum.  And when you have a free n time problem, you get an additional constraint on the, or the Pontiagin maximum principle which is that the Hamiltonian should be zero at the n position and n time.  And that's really what's showing up here.  In fact, it doesn't imply that there's any sort of transverse intersection.  So, okay.  So, so under these, under these, under these conditions, particularly with L, strictly increasing or strictly decreasing and a nice enough Hamiltonian like strictly convex and smooth and nu and nu have indensity, for example, you get a unique optimal transport map.  And this is a transport plan which is given by a transportation map, which is just the optimal introductory gamma x evaluated at the optimal n times tau, which satisfy this transversality condition at the, which, so, and this condition is the Hamiltonian now is strictly increasing or strictly decreasing,  this uniquely determines n time tau.  And particularly it determines it as the pre-downing on gamma.  And then for previous times, you have the same sort of Hamiltonian flow for the trajectory symbol.  And the Eulerian point of view, the Eulerian point of view has nice compactness properties. It's easy to show attainment of optimizers. And then given, given the characterization of the dual problem, the support of the target, the support of the stopping measure should be in the graph of the free boundary.  Also, it turns out that the value function is C1, then you can see that it determines the momentum part of the equation and you just get that the support of eta in the velocity space is always at the derivative of the Hamiltonian.  And the density is uniquely determined by this continuity equation, just a nice transport equation, but now nonlinear because it involves both J and eta.  And what's sort of unresolved is in the case even if everything is nice, the solutions J might not be C1.  And the case that they're elliptous, kind of, in general you could have like discontinuities in the gradient along shocks.  And so there's still a bit of a question in the Eulerian formulation of whether the optimal eta is uniquely determined in that case, in the case that J is on the ellipticians.  And so in this slide I just want to make a little relationship with the classical transportation problems, which is what when you get, you choose this Lagrangian where, so it's infinite if the speed is greater than 1 and it's the derivative of some time dependent function.  The speed is less than or equal to 1, whereas function is increasing, it's zero.  So the optimal trajectories connecting any point Y and Z is the straight line with speed 1.  And so in this case the transportation cost has this familiar form of a convex or concave function of the distance of Y and Z.  So this of course has been studied by Gamebo and Necan, showed that existence of a transfer map.  So now here we have this sort of picture of the difference of the solutions in these two regimes, which is that if E is convex, that corresponds to our case where the cost is strictly increasing.  And in this case the free boundary is hit from below by the trajectories, so the time goes in the, is increasing in the vertical direction.  So the trajectories have slope zero and are hitting the free boundary from above, and in this case the G is concave, they hit it.  Or hit the free boundary from above in the case G is concave, which corresponds to orientation preserving or rotation reversing the object.  Okay, so now I'd like to move on to the scroll cut problem.  So the techniques are basically going to be the same.  So in history, 28 constructions by problem lists and one view, so maybe a few of these.  But then recently in the mathematical finance literature, it's been related to important problems in the options pricing,  and there's been a nice review by Avaloch considering all the different constructions and relating them to optimization problems,  which is generally not how they're constructed in the first place.  So our optimization problem we're going to consider here is just this minimizing over stopping times tau that satisfies this target constraint,  the transport embed, the Brownian motion, beginning at view, and the distribution.  So earlier in formulation is a bit simpler now.  But we have to use it because we don't have an optimal transportation formulation anymore.  And so now we have non-negative density eta and stopping measure rho satisfying this heat equation,  which is really like a substitution of the heat equation since rho is non-negative,  starting at mu and transporting, stopping along mu.  And the dual problem has the same form where we just are maximizing over the difference of the potentials.  And the potentials are a solution to something that looks like a parabolic equation going backwards in time.  This is the sign, so on.  And inequality.  So similar to before, the system of inequality is when we minimize over J is given by the quasi-variational inequality,  where one of these conditions should hold at this point.  But to prove the dual problems actually attained, we have a couple remaining problems to deal with.  So here, one thing, whenever psi is always less than J, you could subtract a positive function.  But clearly that doesn't maximize the cost, so you can just always assume psi is the largest function below it.  But then a little harder to deal with is you can subtract a subharmonic function from both psi and J,  which still results in a super solution to this equation.  And this shows unless the measures mu and nu are in subharmonic order,  that would imply that the dual problem is unbattered, that the dual value is actually infinity.  So a necessary condition for the primal problem to be feasible is then that the measures mu and nu are in subharmonic order,  which is a stand. Easy to show just properties of Marni-Gales as well.  This is harder to handle, but you got some ways to do it. It's a bit of a work in progress.  And then to conclude that the dual problem is attained, and not only attained,  it's attained at sufficiently regular psi and J.  So that means twice-weekly, differentiable, and continuous in particular.  And psi, yeah.  And so the point of having them sufficiently regular is to make sense of these conditions.  So to check optimality, you really just have to prove that there's no duality gap between the optimizers.  That's just saying that if you have admissible eta and rho and admissible psi and J psi,  then if the costs are equal, they must be optimal.  And then given the equations, you can see that this immediately yields the sort of complementary slackness conditions,  which is saying psi is equal to J, anywhere where rho, everywhere on the support of rho,  rho almost everywhere.  And the backwards parabolic equation is satisfied almost everywhere on the support of eta.  But then we have this exact same proposition that we had in the deterministic case,  which determines the, which describes the dual functions J psi and psi.  And so once again, the monotonyst E and psi of J psi only depends on whether L is increasing or decreasing.  The free boundary can then be described explicitly.  And sort of important for the proof of dual attainment is that in fact,  you can choose psi so that the, it satisfies this sort of transversality condition where there's a plastic size given by the free boundary.  And as a result from the previous slide, you can conclude that eta has support in the set where,  in the set of x where t is less than the free boundary.  This follows from the L being strictly increasing that if this condition, this condition is satisfied at S,  it cannot, the inequality can't, it can't be satisfied for t greater than s for psi, which was must in constant.  So, so we get this condition on the support of eta, which uniquely determines eta.  And if you assume extra regularity, then you can see that, okay, well, actually it's just the equation that's relating the rate of particles stopping on the free boundary,  which is given by the gradient of eta dotted with the gradient of the free boundary with the target distribution.  So in fact, everything, all the dependence now goes away besides the free boundary.  So eta doesn't depend on J and psi at all, as it did in the first part of the talk.  It did depend on J and psi in the first part. Now it just depends on the free boundary.  And one of the consequences of this is that in fact, there's a, there's a rigidity which says that if you have a free boundary S,  which determines the optimal stopping time for some increasing L, then it's optimal for any increasing L.  And then it is unique.  So, so the reason is, well, once you have a free boundary, then you cannot just use this equation to redetermine psi.  And then given this equation, you can just solve the backwards parabolic equation to get J psi that's equal to psi on the free boundary.  And by the comparison principle, that will be a super solution to the equation.  So it's optimal.  And the case A and B are really the same. You just have to replace the domains with either the hypergraph or the hypergraph of the free boundary S.  And this, this equation for the case B would reverse the orientation in a sense, so you replace new with new.  And finally, I want to like relate it to the work of these three authors who go about Cox and Houston got an influential paper relating the scrollcard embedding problem with optimal transportation.  But they, and they took a different perspective, which was the perspective on pass space.  And what, how they expressed the duality of the dual problem as the maximizing over all martingales on the probabilities case,  maximizing the difference of psi and the expectation at time zero with the constraint that the martingale is always greater than equal to some continuous function psi.  So what we've done is kind of reduce this problem to just something that's on the, on the space time.  And, and can see given the optimal J and tau, you can explicitly construct this martingale just as the evaluation of the function J along a Brownian motion with the expectation of the remaining cost.  And, but one of the important aspects of our work is now using the PDE method. We have sort of new ways to prove the dual attainment, which they didn't have.  So they did have a similar characterization of the stopping time as hitting of a barrier using something, something like the cyclic monotensity principle on pass space.  So just to end, I want to kind of go back and talk about this sort of general case, which I skipped over.  So in the general case, we have some stochastic differential equation with a control variable A, and we want to choose both the control variable A and the n time tau to minimize the expected cost subject to the, to the stopping constraint.  And you can write it in this or in that way. Before we had the integration over the velocity space, it's almost as natural just having a general control space.  And it's a well continuity equation or a factor plane equation.  With row, row is still non-negative. Stopping measure, eta takes values as measures on this control space.  And then immediately as of any optimization problem, you have some duality where the dual problem is posed over, over the same, same potentials.  In fact, the same proposition holds that when you have the solutions, you have the same monotonicity properties to characterize the tau.  Although, okay, there's some details when you have the diffusion depending on X and A, there's some technical details you get fully nonlinear equations.  But even in the case where sigma is just constant, there's a lot of interesting things to be done here.  And so I think there's a case where sigma is constant and as we had in the first part, that was just the velocity.  And then L was the Hamiltonian, the grandian. You get some interesting, interesting problems depending on the growth conditions for the Hamiltonians.  So in particular, it's sort of, you get these three sort of distinct cases where if the Hamiltonian grows super quadratically, quadratically, or sub-quadratically,  well, when it's growing super quadratically, you can sort of immediately get some quarter space estimates.  And actually, that's nice. This ship sort of shows you can really control the processes.  When it's sub-quadratic, you can sort of show that the density always has finite entropy. So you can never control it beyond at least having finite entropy.  And then for the quadratic case, this is sort of what's been considered by Leonard and Gentian and others and having really nice relationships with the problem of minimization of entropy on path space.  So I think I'll leave it there. Thank you everyone.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Questions?  Let's look at it.  So the role, when the role is optimal, when you get the role and can you say more about the role or can you?  How about row?  About the structure of row.  So the easy thing to show is based on this condition.  Without any, with only, okay, just assuming that this psi and j are continuous, this immediately implies that row, that the support would grow is in the set where j psi is equal to psi.  So what we're really doing is in the case where the dual problem has a solution that has this sort of monotensity property so that j psi is equal to psi on the epigraph of a function and the cost is increasing,  then you can show that row is actually supported on the boundary.  And the reason being that, so for the square root of the writing problem, if it enters into the set where j psi is equal to psi, we have the second condition that says that the parabolic equation should be satisfied,  but now j psi is equal to psi so that says that one, that the positive of psi should be equal to L, but L is strictly increasing and it's L is strictly increasing in time in this case.  And so this is not, and so it's satisfied along the free boundary but not satisfied at later times.  So we have to get a strict inequality for psi, which leads to a strict inequality here, which implies that, well, in this case it implies there's no support for eta but then from the conjugate equation you can apply there's no possibility you have row.  So the row, the row needs to be supported on the free boundary.  Answering question about regularity of the free boundary is a very difficult problem, but of course it's not applied by anything I've discussed.  In the stochastic case, if you thought of applying the kind of techniques you're using to another kind of problem, the problem is state constraints.  It's across the infinite, or many of my settings makes sense.  Yes, so certainly there's a connection with a lot of these problems.  A lot of the literature, at least I've seen on these problems, takes the perspective of backwards stochastic differential equations and they pose the backwards stochastic equations as some sort of transversality condition for the state constraint.  And it's closely related in some ways, but to draw the connection with the stochastic differential equations is pretty clear, but using these methods for state constraints, I haven't really considered yet.  But you think there's an unrivaled practical combination, this one is right today, stopping time.  Right, so actually it's probably the same just because the condition in state constraints is generally, I would say, I think that you just restrict to the row that are properly measured.  Some set O, right, so just restricting to the property is the same.  But I haven't really thought about how it really relates.  Any other question? Everybody's hungry?  Thank you.
201804101120-Palmer_lrv_0_707.png 201804101120-Palmer_lrv_708_887.png 201804101120-Palmer_lrv_888_2855.png 201804101120-Palmer_lrv_2856_3023.png 201804101120-Palmer_lrv_3024_3347.png 201804101120-Palmer_lrv_3348_3767.png 201804101120-Palmer_lrv_3768_4127.png 201804101120-Palmer_lrv_4128_4247.png 201804101120-Palmer_lrv_4248_4391.png 201804101120-Palmer_lrv_4392_4691.png 201804101120-Palmer_lrv_4692_4979.png 201804101120-Palmer_lrv_4980_5219.png 201804101120-Palmer_lrv_5220_5975.png 201804101120-Palmer_lrv_5976_11375.png 201804101120-Palmer_lrv_11376_11783.png 201804101120-Palmer_lrv_11784_11891.png 201804101120-Palmer_lrv_11892_16151.png 201804101120-Palmer_lrv_16152_16499.png 201804101120-Palmer_lrv_16500_20387.png 201804101120-Palmer_lrv_20388_21875.png 201804101120-Palmer_lrv_21876_22967.png 201804101120-Palmer_lrv_22968_23591.png 201804101120-Palmer_lrv_23592_23963.png 201804101120-Palmer_lrv_23964_24731.png 201804101120-Palmer_lrv_24732_24887.png 201804101120-Palmer_lrv_24888_26351.png 201804101120-Palmer_lrv_26352_26399.png 201804101120-Palmer_lrv_26400_42755.png 201804101120-Palmer_lrv_42756_43991.png 201804101120-Palmer_lrv_43992_50711.png 201804101120-Palmer_lrv_50712_51419.png 201804101120-Palmer_lrv_51420_56159.png 201804101120-Palmer_lrv_56160_56351.png 201804101120-Palmer_lrv_56352_56603.png 201804101120-Palmer_lrv_56604_56663.png 201804101120-Palmer_lrv_56664_56867.png 201804101120-Palmer_lrv_56868_57179.png 201804101120-Palmer_lrv_57180_57383.png 201804101120-Palmer_lrv_57384_57479.png 201804101120-Palmer_lrv_57480_57611.png 201804101120-Palmer_lrv_57612_60359.png 201804101120-Palmer_lrv_60360_60443.png 201804101120-Palmer_lrv_60444_60707.png 201804101120-Palmer_lrv_60708_60851.png 201804101120-Palmer_lrv_60852_61127.png 201804101120-Palmer_lrv_61128_61235.png 201804101120-Palmer_lrv_61236_61751.png 201804101120-Palmer_lrv_61752_61943.png 201804101120-Palmer_lrv_61944_61993.png