PDE Methods For Optimal Skorokhod Embeddings
Nassif Ghoussoub Young-Heon Kim Aaron Zeff Palmer




	We consider cost minimizing stopping time solutions to Skorokhod embedding problems, which deal with transporting a source probability measure to a given target measure through a stopped Brownian process. PDEs and a free boundary problem approach are used to address the problem in general dimensions with space-time inhomogeneous costs given by Lagrangian integrals along the paths.  We introduce an Eulerian—mass flow—formulation of the problem, whose dual is given by Hamilton-Jacobi-Bellman type variational inequalities.  Our key result is the existence (in a Sobolev class) of optimizers for this new dual problem, which in turn determines a free boundary, where the optimal Skorokhod transport drops the mass in space-time. This complements and provides a constructive PDE alternative to recent results of Beiglböck, Cox, and Huesmann, and is a first step towards developing a general optimal mass transport theory involving mean field interactions and noise.  




Conditional Prior Networks for Optical Flow
    Yanchao Yang    Stefano Soatto
    
===========================================






§ INTRODUCTION
 

	Given two Radon probability measures μ and ν on ^d, the Skorokhod embedding problem consists of constructing a stopping time τ such that ν is realized by the distribution of B_τ (i.e, B_τ∼ν in our notation), where B_t is Brownian motion starting with μ as a source distribution, i.e., B_0∼μ. We shall denote by 𝒯(μ, ν) the set of such –possibly randomized– stopping times with finite expectation. If μ, ν are supported in an open convex subset O ⊂^d, then 𝒯_O(μ, ν) denotes those in 𝒯(μ, ν) such that τ≤τ_O:=inf{t; B_t∉O}. The martingale property of Brownian motion obviously imposes a natural necessary condition on the pair μ, ν for the existence of such a stopping time, namely that they should be in subharmonic order, denoted μ≺ν, which means that 
	
    ∫_ O h  dμ≤∫_ O h   dν  
    	 		for all h smooth and subharmomic on O.
 
	The fact that condition (<ref>) is also sufficient to guarantee that 𝒯_O(μ, ν) is non-empty has been the subject of a large number of papers. Indeed, and as reported by Obłoj <cit.>, one can find more than two dozen constructions of such embeddings in the literature ever since Skorokhod <cit.> gave the original solution in the one-dimensional case. Among those, there are some with additional interesting properties arising from the fact that they optimize various functionals involving stopped Brownian motion. Indeed, Rost  had established in <cit.> that Root's embedding <cit.> minimizes the variance of the stopping time (or equivalently 𝔼[τ^2]), which was conjectured by Kiefer <cit.>.   
	He also established a new embedding that minimizes 𝔼[τ^p] for 0<p<1.   There has been an attempt to relate the Root's embedding problem to obstacle problems by Cox and Wang <cit.> and Gassiat, Oberhauser, and dos Reis <cit.>, but, their works were restricted to one-dimension: see our Remark <ref>.

This led Beiglböck-Cox-Huesmann <cit.> to consider the more general problem of identifying and characterizing solutions of the Skorokhod embedding problem that optimize various functionals of stopped Brownian motion. They also argued that if one thinks of a stopping time τ as “a transport plan" from Wiener measure starting at μ  to the target measure ν, then the analogy with the theory of mass transport –though not directly applicable– could provide a powerful intuition towards developing an analogous theory. They do so in <cit.> by using stochastic analysis to essentially extend the measure theoretic duality methods à la Kantorovich and the monotonicity characteristics of optimal mass transport plans to this setting. 

Our results can be seen as complementary to theirs in several ways: they involve a new important Eulerian formulation, its crucial dual form, which allow us to use PDE methods and the theory of Hamilton-Jacobi-Bellman inequalities. The optimal stopping time we obtain, will be hitting times of corresponding free boundaries. An important part of our approach is our proof of the attainment in the new dual problem, which has been an elusive issue in martingale transport theory, especially in higher dimensions <cit.> (see also the following related results <cit.>, <cit.>). 

	
	We consider two Radon probability measures μ, ν with finite expectations,  whose support lie in a given convex domain O⊂^d, and in subharmonic order on O. Our primal problem will be the following minimization: 
	
    𝒫_0(μ,ν) :=  inf{𝔼[ ∫_0^τ L(t,B_t)dt]; τ∈𝒯_O(μ, ν)
    		}.

	These Lagrangian costs are a special case of the general costs considered in <cit.>, where they prove a general duality theorem, but also give an extension of the result of <cit.>, where it is shown the optimizers are given by the Root and Rost embeddings in the case the Lagrangian L(t, x) is only a (strictly increasing/decreasing) function of time, for which we will handle dependence on the spatial variable.
	We note that costs that depend on the end time and position can be reduced to Lagrangian costs by Itô's formula
	
    𝔼[g(τ,B_τ)]= 𝔼[∫_0^τ L^g(t,B_t)dt],

	where L^g(t,x)=∂_t g(t,x)+1/2Δ g(t,x)).
	In a forthcoming paper <cit.>, we shall deal with Lagrangians defined on phase space (see the end of this introduction). Throughout this article,  the Lagrangian L will be assumed to satisfy:
	 
		
  * 
		 L is non-negative and belongs to C_-γ(^+×O), the latter being the space of continuous functions w on ^+×O with 
		
    -γ t w(t,x) → 0 as t→∞,   uniformly in x.

		Here we fix γ satisfying 0<γ<λ, where λ is the Poincaré constant of O, and we denote ^+ = { t ∈ |  t ≥ 0}. 
	
	 	Note that the set of randomized stopping times 𝒯_O(μ, ν) is non-empty, convex and compact in an appropriate topology, and therefore the existence of a minimum is not really a problem. The challenge is to characterize such solutions and to show when they are natural and unique stopping times, preferably characterized as hitting times of certain barrier sets that can be naturally identified from the Lagrangian as well as the source and target measures. 
	  
 	
	 	
	Duality plays an important role in these problems and Beiglböck et al. had considered in <cit.>  the following dual problem  to (<ref>): 
	
    𝒟_0(μ,ν):=sup_ψ∈ C(O),G∈𝒦^+_-γ{∫_Oψ(z)dν-[G_0]; G_t-ψ(B_t)≥ -∫_0^t L(s,B_s)ds},

	
	where 𝒦^+_-γ denotes the set of continuous supermartingales on the probability space of Brownian motion with γ-exponential growth. In particular, if G∈𝒦^+_-γ, then ω↦ G is continuous with respect to the topology on Ω=C(^+;^d) given by uniform convergence of paths.

	That 𝒫_0(μ,ν)=𝒟_0(μ,ν) was essentially  proven in <cit.> for a slightly different problem. We shall also include a proof in the appendix, Theorem <ref>. 		
	
	

 §.§ Eulerian formulation and its dual

	Our analysis hinges on understanding two other related 
	problems.  One consists of an Eulerian formulation of the primal problem.  We give here a heuristic description leaving the appropriate function spaces to be defined in the next section. For a stopping time τ such that B_τ∼ν, we consider the space-time distribution  of stopped particles ρ, that is (τ,B_τ)∼ρ, where the latter, which we call the stopping measure,  is a probability measure on ^+×O. Note that ρ has a target distribution with  spatial marginal ν, that is
	
    ∫_O u(z) ν(dz) =    ∫_O∫_^+ u(x)ρ(dt,dx)  for all u∈ C(O).

	Let now  η be a non-negative measure on ^+×O that corresponds to the distribution of Brownian motion before it has stopped. It can be expressed by the following   evolution equation in its `very weak' form via smooth test functions w:
	
    -∫_Ow(0,y) μ(dy)=    ∫_O∫_^+[∂/∂ tw(t,x)+1/2Δ w(t,x)]η(dt,dx)
        -∫_O∫_^+ w(t,x)ρ(dt,dx).

	Note that if ρ has the density with respect to η, then dρ/dη(t,x) is the conditional probability to stop given B_t=x. 
	
 	We shall  say that (η,ρ) is an admissible pair, provided they satisfy (<ref>) and (<ref>) as well as an additional condition of exponential decay in time -to be defined in the next section. We shall then consider the following linear problem 
  	
    𝒫_1(μ,ν) = inf_η,ρ{∫_O∫_^+ L(t,x)η(dt,dx); (η,ρ)  is admissible}.

	We shall then prove that it is equivalent to the original primal problem, that is
  	
    𝒫_0(μ, ν)=	𝒫_1(μ,ν).

	This will be proved by means of another dual problem  that is motivated by standard Monge-Kantorovich theory, once applied to a cost given by a Lagrangian function. This was considered -in a deterministic context- by Bernard-Buffoni <cit.> for fixed end-times problems, and by the authors <cit.> in the case when the end-times are free. Here we shall consider the following dual problem:
	
    𝒟_1(μ,ν) := sup_ψ,J{∫_^dψ(z)ν(dz) - ∫_^dJ(0,y)μ(dy); V_ψ[J]≥ 0},

	where ψ:^d→ is continuous, J:^+×^d→ is C^2, and V_ψ is the quasi-variational Hamilton-Jacobi-Bellman operator
	
    V_ψ[J](t,x):=min{[                    J(t,x) -ψ(x); -∂/∂ tJ(t,x)-1/2Δ J(t,x)+L(t,x) ]}.

	For each end-potential ψ:^d→ that is continuous, the value-function, J_ψ:^+×^d→ is defined via the 
	dynamic programming principle
	
    J_ψ(t,x) := sup_τ∈ℛ^t,x{𝔼^t,x[ψ(B_τ)-∫_t^τ L(s,B_s)ds]},

	where the expectation superscripted with t,x is with respect to the Brownian motions satisfying B_t=x, and the minimization is over all finite-expectation stopping times ℛ^t,x on this restricted probability space such that τ≥ t, which will be defined more precisely at the begininng of Section 2. Note τ is not necessarily required to be in 𝒯_O(μ, ν).  
	The value function satisfies the following Hamilton-Jacobi-Bellman variational inequality:
	
    {[                                                                                                   J_ψ(t,x)≥ψ(x);                                                                             ∂/∂ tJ_ψ(t,x)+1/2Δ J_ψ(t,x)≤ L(t,x);                                                         ∂/∂ tJ_ψ(t,x)+1/2Δ J_ψ(t,x)= L(t,x)  if J_ψ(t,x)> ψ(x), ].
	
	or equivalently V_ψ[J_ψ]=0 in the sense of viscosity. 
	Moreover,  
	
    J_ψ (t,x)  = inf{ J (t, x)   ;  V_ψ [J] ≥ 0}.

	
	In Section <ref>, we shall prove that (<ref>) is also dual to the primal problem	  (<ref>), that is  
	
    𝒫_0(μ, ν)=𝒫_1(μ,ν)=𝒟_0(μ, ν)=𝒟_1(μ,ν).
	
	The equivalence of the two dual problems is through a connection with the so-called Snell problem <cit.>. Indeed, if one considers the stochastic process 
	
    Y_t=ψ(B_t)-∫_0^tL(s,B_s)ds,
 then  
	
    G_t = J_ψ(t,B_t)-∫_0^tL(s,B_s)ds

	 is the smallest supermartingale such that G_t≥ Y_t. Moreover, under suitable hypothesis, the “Snell stopping time," that is τ=inf{t   ;   G_t=Y_t}, which renders the process G_t∧τ a martingale, will  
	 coincide with the optimal time we are seeking.  
	 
	



 §.§ Dual attainment and verification

	One of our key results – proved in Section <ref> – is that both  the Eulerian formulation of the primal problem 𝒫_1(μ,ν) and the dual  problem 𝒟_1(μ,ν) are attained  in Sobolev class. For that, we need additional assumptions. 
Indeed, we may restrict the minimization of 𝒟_1(μ,ν) to the pair ψ and its value function J_ψ of (<ref>).
	 Actually, for technical reasons, we shall restrict the problem to the closure of a bounded open convex set O and show that V_ψ[J]=0 may be posed with additional Dirichlet boundary conditions, i.e., ψ(x)=J_ψ(t,x)=0 for x∈∂ O. However, we prove the attainment of the dual problem in a Sobolev class of functions, such that (ψ,J) satisfy V_ψ[J]= 0 in a weak sense. We show that ψ can be taken to be lower semicontinuous, and in this context we can use results in <cit.> that yield that the `minimal weak solution' to V_ψ[J]= 0 coincides with the value function of (<ref>).
	
	
Here are our assumptions on the source and target measures μ, ν:
 	 

		
  *  The closure of the support of both μ and ν is contained in an open, bounded and convex set O⊂^d.  
		
  * 
			  μ and ν are absolutely continuous with respect to Lebesgue measure and have densities in L^2(O). 
		
  *  μ≺ν for the subharmonic order on O.
	
	We shall require that the Lagrangian satisfies the following additional assumption:
	 
	 	
  *  
		L(t,x)≤ D<∞ for all (t,x)∈^+×O.
	
The following result summarizes the linkages between the optimizers of the various primal and dual problems. 	

		Suppose <ref>, <ref>, <ref>, <ref> and <ref>. Then,
		 
		
  * The maximum of the Eulerian dual problem 𝒟_1(μ, ν) is attained at ψ∈  H_0^1(O) and J∈𝒳  (see (<ref>)).

	
  *   The infimum of the primal Eulerian problem 𝒫_1(μ, ν) is attained at an admissible pair (η, ρ)∈ L^2_γ(^+;H_0^1(O))×𝒳^* (see also (<ref>)), which satisfies the following complementary slackness condition:
	
    0=    ∫_O∫_^+[J(t,x)-ψ(x)]ρ(dt,dx)
        + ∫_^+∫_O[-η(t,x)∂/∂ tJ(t,x) +1/2∇ J(t,x)·∇η(t,x)+L(t,x)η(t,x)] dxdt.


	
  *  Furthermore, ψ is lower semicontinuous, and we may take J to be
		
    J(t,x)=J_ψ(t,x):=sup_τ∈ℛ^t,x{𝔼^t,x[ψ(B_τ)-∫_t^τ L(s,B_s)ds]}.

	
	
It is clear from (2) that the optimal process must  stop in the space-time set 

    F:={(t, x); J(t,x)=ψ(x)},

 i.e., the coincidence set of the equation V_ψ[J]=0 viewed as the obstacle problem for J with obstacle ψ.  This enables us in Section <ref> to  
 address  cases where the optimal stopping time is natural and unique. Both properties will follow if the optimal stopping time is given by the hitting time of a barrier, which we establish under strict monotonicity assumptions on L. In this case, the barrier is the coincidence set F. For example, 
 if the Lagrangian L strictly increases in time, then one can define the function 
s(x)=inf{t;J_ψ(t,x)=ψ(x)} 
and the barrier 
F=R_c:= {(t,x); t≥ s(x)}, 
 so that the optimal time is the first hitting-time of R_c, that is τ= inf{t; (t,B_t)∈ R_c}.
	
	
We consider in the final section  more explicit behavior of the free boundary, by deriving another equation for the function s(x). We will also discuss connection of our analysis to a setting involving backward stochastic differential equations (BSDE). A couple of concrete examples are provided for demonstration. 
	Finally, a few additional material are given in  Appendix <ref>, including a proof of weak duality and various notions of solutions to variational inequalities and their properties that are used throughout the paper.
	
The methods in this paper can be extended to other processes, for instance when Brownian motion is replaced by a Markov process generated by a uniformly elliptic operator L.  In this case Laplacian, 1/2Δ, is replaced by L, and the subharmonic functions should be replaced by L-subharmonic; see for example <cit.>.  We deal only with Brownian motion for simplicity and will address the following important extensions of our methods in subsequent work.



 §.§ When cost functions are not induced by a Lagrangian

In a recent paper <cit.>, we show that the methods developed in this paper can be used to deal with other important higher dimensional cases, where the cost is a function of the initial and end points, i.e. c(x,y) = f (|x-y|). In other words, with problems such as 	
	
    𝒫_0(μ,ν) :=  inf{𝔼[c(B_0,B_τ)]; τ∈𝒯_O(μ, ν)
    		}.

	For other related papers in 1 dimension, we refer to <cit.> and <cit.>.



 §.§ Control and mean field extensions


This paper plays an important role in a larger research program on dynamic optimization problems with target constraints.  Deterministic control problems have already been the subject of <cit.> by the authors.  While here we study Brownian motion, we have in mind important more general controlled stochastic differential equations such as, 

    dX_t = α_t dt + dB_t.

The Lagrangian will then be assumed to also depend on the drift. One can also incorporate mean field interactions through the density and stopping distribution.  Such dependence is natural in the Eulerian formulation where we consider the Fokker-Planck equation

    ρ(t,x)+∂_t η(t,x)+∇· a(t,x) η(t,x)=1/2Δη(t,x),

with the cost

    ∫_^d∫_^+[L(t,x,a(t,x))η(t,x)+F(η(t,x))+G(ρ(t,x))]dtdx,

and the target constraint remains ∫_^+dρ = ν.
The resulting Hamilton-Jacobi-Bellman inequality appears as

    J(t,x)-ψ(x)   ≥ -G'(ρ(t,x))     ∀ (t,x)
    
    	J(t,x)-ψ(x)   = -G'(ρ(t,x)),     if ρ(t,x)>0
    
    	-∂_t J(t,x) - A·∇ J(t,x)-1/2Δ J(t,x)   ≥ -L(t,x,A)-F'(η(t,x)),    ∀ (t,x,A)
    
    	-∂_t J(t,x) - A·∇ J(t,x)-1/2Δ J(t,x)   = -L(t,x,A)-F'(η(t,x)),     if (t,x,A) ∈𝒮,

where 

    𝒮:={(t,x,A); 
    η (t, x) >0 and A  maximizes A·∇ J(t,x)-L(t,x,A).

This will be the subject of a forthcoming paper <cit.>. 



Acknowledgment: We are thankful to Martin Barlow and Ed Perkins for helpful comments and references. We also thank A. Cox and M. Huesmann for pointing out several papers related to this work, and an anonymous referee for pertinent comments and pointing out additional related work. 



§ DUALITY, EULERIAN EMBEDDINGS AND VARIATIONAL INEQUALITIES
 

This section is devoted to the proof of the equalities,

    𝒫_0(μ, ν)=𝒫_1(μ,ν)=𝒟_0(μ, ν)=𝒟_1(μ,ν).
		



 §.§ Eulerian embedding of the stopping problem.

Formally, we let B_t be a Brownian motion with  B_0∼μ and we consider the randomized stopping times τ that satisfy B_τ∼ν.  We consider the filtered probability space (Ω,ℱ,{ℱ_t}_t∈^+,ℙ) where Ω =C(^+;^d), ℙ the Wiener measure with initial distribution μ, and {ℱ_t}_t∈^+ the natural filtration of the Brownian motion. We define the space of randomized stopping times with finite expectation as

    ℛ:={α: Ω→ℳ(^+)  ;      α≥ 0,  α(^+)=1,  ∫_^+t   dα<∞ and  α([0,t]) is   ℱ_t-measurable ∀  t}

	
	where ℳ(^+) denotes the space of Radon measures on ^+. 
	We often abbreviate a randomized stopping time by τ∼α such that
	
    𝔼[f(τ)]=𝔼[∫_^+f(t)α(dt)].

	The condition B_τ∼ν is now equivalent to
	
    𝔼[g(B_τ)] = ∫_O g(z)ν(dz), ∀ g∈ C(O).

	We will say that a subset Q⊂^+×Ω is almost sure for a randomized stopping time if
	
    𝔼[∫_^+1{t∈ Q} dα]=0

	where 1 is the indicator function of the set.  Often this will appear instead as an abbreviated form, i.e. 1{t≤η}:=1{t∈ Q_η} where η is a stopping time and Q_η={(t,ω); t≤η(ω)}.


	For each (t,x) we also consider a filtered probability space of Brownian motions beginning at B_t=x, and we use 𝔼^t,x to denote the expectation.  We let ℛ^t,x denote the space of randomized stopping times, larger than or equal to t, with finite expectation on this probability space. 

	We consider C_-γ(^+×O) given as in <ref>, i.e. the continuous functions satisfying
	
    -γ t w(t,x) → 0 as t→∞,   uniformly in x,

		where γ is fixed such that 0<γ<λ for λ the Poincaré constant of O.
		 This is a Banach space with the norm 
	
    w_C_-γ(^+×O):=sup{|-γ tw(t,x)|; (t,x)∈^+×O}<∞,

	 whose dual space ℳ_γ(^+×O) 
	  is the finite (signed) Radon measures with γ-exponential decay.  
	We will also let C_-γ^1,2(^+×O) denote the functions whose first derivative in time and second derivatives in space lie in C_-γ(^+×O).
	
	We consider the `very weak' evolution equation for η,ρ∈ℳ_γ(^+×O), η,ρ≥ 0, that satisfy (<ref>),	which is formally equivalent to 
	
    η≥ 0 and ∂_tη≤1/2Δη with η(0,·)=μ in the sense of distributions.
  
	The stopping measure  ρ 
	 allows us to encode the target constraint as (<ref>), which is formally given by ρ(^+,·)=ν.

	We say that (η,ρ) is admissible if η∈ℳ_γ(^+×O), η≥0, ρ∈ℳ_γ(^+×O), ρ≥0, and  (<ref>) holds and  (<ref>) holds ∀ w ∈ C_-γ^1,2(^+×O).

Note that if L∈ C_-γ(^+×O) any admissible pair has finite cost in (<ref>).
	We recall the two formulations of the primal problem, from (<ref>) we have
	
    𝒫_0(μ,ν) :=  inf{𝔼[ ∫_0^τ L(t,B_t)dt]; τ∈𝒯_O(μ, ν)
    		},

	where τ_O(μ,ν) is the τ∈ℛ, such that B_t∈ O for t<τ almost surely, with B_0∼μ and B_τ∼ν.  The second formulation  is given in (<ref>) as the linear optimization problem over (η,ρ) satisfying (<ref>) and (<ref>),
	
    𝒫_1(μ,ν) = inf_η,ρ{∫_O∫_^+ L(t,x)η(dt,dx); (η,ρ)  is admissible}.



 	We will eventually show that 𝒫_0(μ,ν)=𝒫_1(μ,ν). In the following proposition, we show that one can associate an admissible pair to any randomized stopping time, which will mean that 𝒫_0(μ,ν)≥𝒫_1(μ,ν).
	
 		Given μ and ν satisfying <ref>,
		 if τ is a stopping time in 𝒯(μ, ν), then  	
	there is an admissible pair (η,ρ) such that for every g∈ C_-γ(^+×O),
	
    [g(τ,B_τ)]=∫_O∫_^+g(t,x)ρ(dt,dx),

		and 
 	
    [∫_0^τ g(t,B_t)dt]   
     			= ∫_O∫_^+g(t,x)η(dt,dx).
	
		
	Furthermore, there is an η-measurable map (t,x)→τ^t,x∈ℛ^t,x such that
	
    ∫_O∫_^+𝔼^t,x[A(τ^t,x,B_τ^t,x)]η(dt,dx)= ∫_^+𝔼[1{t≤τ}A(τ,B_τ)]dt

	for all A_-γ∈ C(^+;^d).
 	
 	
 		The expectation [g(τ,B_τ)] defines a continuous linear functional on C_-γ(^+×O) thanks to the continuity of the Brownian paths.  
		Thus [g(τ,B_τ)] is represented by ρ∈ℳ_γ(^+×O) such that for g∈ C_-γ(^+×O),
 		
    [g(τ,B_τ)]=∫_O∫_^+g(t,x)ρ(dt,dx).

 		We immediately have that ρ satisfies (<ref>) if and only if B_τ∼ν.  Similarly, the density of the process η is the representation of the linear functional
 		
    [∫_0^τ g(t,B_t)dt] =∫_O∫_^+ g(t,x)η(dt,dx).

 		Ito's formula shows that if w∈ C_-γ^1,2(^+×O) then
 		
    [w(τ,B_τ)]  =    [∫_0^τ(∂/∂ tw(t,B_t)+ 1/2Δ w(t,B_t)) dt] + [w(0,B_0)]
    
     			=    ∫_O∫_^+(∂/∂ tw(t,x)+ 1/2Δ w(t,x))η(dt,dx)
        +∫_Ow(0,y)μ(dy).

 		Combining this expression with the representation of [w(τ,B_τ)] by ρ shows that (η,ρ) satisfy (<ref>). 
		
		To prove (<ref>), given τ a randomized stopping time representing α:Ω→ℳ(^+), we define a measure ℙ^α on ^+×O×Ω×^+ by dual representation such that
		
    ∫_^+𝔼[1{t≤τ}H^t,B_t_τ]dt = ∫_^+∫_O∫_Ω∫_^+H^t,x_τ(ω)ℙ^α(dt,dx,dω,dτ)

		for all continuous functions H on ^+×O×Ω×^+ with γ-exponential growth in the t and τ variables. For H^t,x_τ(ω)= f(t,x) we have, using the first part of the proposition,
		
    ∫_O∫_^+f(t,x)η(dt,dx)=    [∫_0^τ f(t,B_t)dt]
    
     			 =    ∫_^+𝔼[1{t≤τ}f(t,B_t)]dt
    
     			=    ∫_^+∫_O∫_Ω∫_^+f(t,x)ℙ^α(dt,dx,dω,dτ),

		and thus ℙ^α disintegrates as α̃^t,x(dτ,dω)η(dt,dx).  Furthermore, for H^t,x_τ(ω)=G^t,x(ω), we have
		
    ∫_^+∫_O𝔼^t,x[G^t,x]η(dt,dx) =    ∫_^+𝔼[1{t≤τ}G^t,B_t]dt
    
    			=    ∫_^+∫_O∫_Ω∫_^+G^t,x(ω)α̃^t,x(dτ,dω)η(dt,dx),

		and we have that for η-a.e. (t,x), the measure disintegrates further as 
		
    ℙ^α(dt,dx,dω,dτ)=α^t,x(ω)(dτ)ℙ^t,x(dω)η(dt,dx).
 
		For η-a.e. (t,x) and ℙ^t,x a.e. ω we have that α^t,x(ω)≥ 0, ∫_t^∞α^t,x(ω)(dτ)=1, and for T≥ t, ω↦∫_t^T α^t,x(ω)(dτ) is ℱ_T^t,x measurable.  Thus we have that for η-a.e. (t,x), α^t,x∈ℛ^t,x, measurability follows from the disintegration, and formula (<ref>) follows with H^t,x_τ(ω)=A(τ,B_τ(ω)) completing the proof.
 	
	
	

 §.§ Eulerian dual 𝒟_1(μ, ν) and its weak duality

We now make the dual problem 𝒟_1(μ, ν)  more precise by considering 

    𝒟_1(μ,ν) := sup_ψ,J{∫_^dψ(z)ν(dz) - ∫_^dJ(0,y)μ(dy); V_ψ[J]≥ 0},

where the end-potential, ψ∈ C(O), and the value-function, J∈ C_-γ^1,2(^+×O). The maximization problem is posed over supersolutions V_ψ[J]≥ 0 for the Hamilton-Jacobi quasi-variational operator V_ψ of (<ref>).

	In the remainder of this section we prove the weak duality, 𝒫_1(μ,ν)=𝒟_1(μ,ν), by a method standard to the Monge-Kantorovich duality of optimal transportation.  We will then show that  𝒟_1(μ,ν)=𝒟_0(μ,ν) and conclude (<ref>) via the result  of  <cit.> that shows 𝒟_0(μ,ν)=𝒫_0(μ,ν).  
	 As the latter was proven  for a slightly different but equivalent problem in Theorem 4.2 <cit.> (see also <cit.> for a formulation similar to ours),  we shall 
	sketch  an alternative proof in Theorem <ref>  in the appendix.

	
		Given <ref> and <ref>, 
		 we have 𝒟_1(μ,ν)=𝒫_1(μ,ν).
	
	
		This follows from the general Fenchel-Rockafellar duality <cit.> with Θ,Ξ:C_-γ(^+×O)^2→ by  

    Θ(f,g) := 
         0    if  f≥ -L and g≥ 0, 
    ∞   otherwise.

	and, minimizing over ψ∈ C(O) and J∈ C_-γ^1,2(^+×O),
		
    Ξ(f,g) := -sup_ψ,J{∫_Oψ(z)ν(dz) - ∫_O J(0,y)μ(dy); -∂/∂ t J -1/2Δ J≥ f, J-ψ≥ g}.

		Both Ξ and Θ are convex and lower semicontinuous and by definition we have that 𝒟_1(μ,ν)=-Ξ(-L,0). 

		If there is (f_1,g_1) such that Ξ(f_1,g_1)=-∞, then Ξ(f,g)=-∞ for all f and g, and there cannot be an admissible (η,ρ) with finite cost, thus 𝒟_1(μ,ν)=𝒫_1(μ,ν)=+∞. 

		If Ξ(f,g) is finite for all f and g, then Θ is continuous at f and g if f>-L and g>0 (identically 0 in a neighborhood) and the Fenchel-Rockafellar duality theorem 
		(Theorem 1.9 in <cit.>) states that an optimizer (η,ρ) exists and
		
    max_η,ρ[ - Θ^*(-η,-ρ)-Ξ^*(η,ρ)] = inf_f,g[Θ(f,g)+Ξ(f,g)].

		The infimum on the right side is attained at f=-L and g=0, in which case Θ(f,g)+Ξ(f,g)=-𝒟_1(μ,ν).  The only subtlety in checking continuity of Θ at (f,g) is that for f>-L we require that -γ tf(t,x)≥ --γ tL(t,x)+δ. However, this is not a problem because any admissible (η,ρ) decays faster than γ t and provides a bound showing that Ξ(f,g) is finite.

		The Legendre transform of Θ is
		
    Θ^*(-η,-ρ)=    sup_f,g{ -∫_O∫_^+ f(t,x) η(dt,dx) -∫_O∫_^+ g(t,x) ρ(dt,dx)-Θ(f,g)}
    
    			=    ∫_O∫_^+ L(t,x) η(dt,dx),     (ρ,η)≥ 0,
    ∞,     otherwise,

		whereas the Legendre transform Ξ^*(η,ρ) is 0 if (<ref>) and (<ref>) hold and otherwise +∞:
		
    Ξ^*(η,ρ)    =  sup_ψ,J{∫_O∫_^+[-∂/∂ tJ(t,x)-1/2Δ J(t,x)]η(dt,dx)
       +∫_O∫_^+[J(t,x)-ψ(x)]ρ(dt,dx)
    			+∫_Oψ(z)ν(z)dz-∫_OJ(0,y)μ(y)dy }.

		Thus 𝒫_1(μ,ν)=-max_η,ρ[ - Θ^*(-η,-ρ)-Ξ^*(η,ρ)] and the proof is complete.
	

	We now prove the identity 𝒟_1(μ,ν)=𝒟_0(μ,ν) by using well known relationships between the Snell envelope and viscosity solutions <cit.>.  
	
		The dual problems are equivalent, i.e.,  𝒟_1(μ,ν)=𝒟_0(μ,ν).
	
	 
		One inequality is easy.	Given ψ∈ C(O) and J∈ C_-γ^1,2(^+×O) satisfying V_ψ[J]≥ 0, we may consider the supermartingale G^J∈𝒦_-γ^+ defined by 
		
    G_t^J := J(t,B_t)-∫_0^t L(s,B_s)ds.

		That G^J is supermartingale follows easily from ∂/∂ tJ(t,x)+1/2Δ J(t,x)≤ L(t,x) and Ito's formula. Indeed, for t≤τ≤τ_O,
		
    [G_τ^J| ℱ_t] =    [∫_t^τ(∂/∂ tJ(t,B_t)+1/2Δ J(t,B_t)-L(t,B_t))dt+∇ J(t,B_t)· dB_t| ℱ_t]+G_t^J
    ≤    G_t^J.

		With the above definition of G^J we have that G^J_t-ψ(B_t)≥ -∫_0^tL(s,B_s)ds and
		[G_0^J]=∫_OJ(0,y)μ(dy), 
		which clearly shows that 𝒟_1(μ,ν)≤𝒟_0(μ,ν). 

		For the reverse inequality (which also follows from Proposition <ref>), 
		
		we will show that  given (ψ,G)∈ C(O)×𝒦_-γ^+, then for any ϵ>0, there is J∈ C_-γ^1,2(^+×O) such that V_ψ[J]≥ 0 and
		
    -∫_OJ(0,y)μ(dy)≥ -𝔼[G_0]-ϵ.

	  	Since J is admissible for the same ψ, then by taking the limit as ϵ→ 0, we get that 𝒟_1(μ,ν)≥𝒟_0(μ,μ). 

		We shall construct J as  an approximation of the viscosity solution J_ψ to V_ψ[J_ψ]=0, which may be defined for each (t,x) as
		
    J_ψ(t,x) := sup_τ∈ℛ^t,x{𝔼^t,x[ψ(B_τ)-∫_t^τ L(s,B_s)ds]}.

		 In particular, by compactness of the randomized stopping times and continuity of ψ, L and the paths of Brownian motion, there is a randomized stopping time τ^y that attains this value at (0,y) so that
		
    ∫_OJ_ψ(0,y)μ(dy) =    ∫_O𝔼^0,y[ψ(B_τ^y)-∫_0^τ^y L(t,B_t)dt]μ(dy)
    
    			=    𝔼[ψ(B_τ)-∫_0^τ L(t,B_t)dt]
    ≤    𝔼[G_τ] ≤𝔼[G_0],

		where τ∈ℛ is defined as τ^B_0 and the last inequality is implied by the supermartingale property of G. 
		
		
		
		Perron's method (see Lemma <ref>) implies that J_ψ may be approximated by a smooth supersolution, completing the proof.
	



	


§ ATTAINMENT IN SOBOLEV CLASS AND VERIFICATION






 §.§  Primal problem and regularity of optimal solutions

	We define a couple more function spaces that will be useful in our analysis. We let L^2_γ(^+;H_0^1(O)) denote the weighted Sobolev space with norm
	
    ϕ_L^2_γ(^+;H_0^1(O))^2=∫_^+2γ t∫_O|∇ϕ(t,x)|^2 dxdt,

	which we will see is a natural space for the density of η. We also define a time dependent Sobolev space, 𝒳, that is natural for the attainment of the value function J for the dual problem 𝒟_1(μ,ν).  These are the functions f that have f∈ L^2_-γ(^+;H_0^1(O)) and a weak time derivative ∂/∂ t f∈ L^2_-γ(^+;H^-1(O)), and the norm of 𝒳 is
	
    f_𝒳^2 = ∫_^+-2γ t[ f(t,·)_H_0^1(O)^2+∂/∂ tf(t,·)_H^-1(O)^2]dt.

	Given ψ∈ H_0^1(O) lower semicontinuous, the unique `minimal weak solution' of V_ψ[J_ψ]=0 in 𝒳 is shown to exist in <cit.>; see Definition <ref>. 
	
	
		We note that the attainment of 𝒫_0(μ,ν) and 𝒫_1(μ,ν) in the weak class of ℛ and ℳ_γ(^+×O)^2 follows from the proof of Theorems <ref> and <ref>. We shall now prove that the evolution equation (<ref>) implies additional regularity properties for η. We abuse notation to use η to refer to the density with respect to the Lebesgue measure.

 	
 		Suppose <ref> and <ref>, and that (η,ρ) is admissible.  We let μ̃(t,x) be the solution to the heat equation, ∂_tμ̃=1/2Δμ̃, with the  Dirichlet boundary condition on O and μ̃(0,·)=μ.  Then η≤μ̃  a.e., moreover, there is a uniform bound on the norm of η in the Sobolev space L^2_γ(^+;H^1_0(O)),
 		
    η_L^2_γ(^+;H^1_0(O))^2≤ Cμ_L^2(O)^2,

 		and ρ lies in the dual space of 𝒳.
 	
 	
 	
 	The proof is standard but we give it here for completeness. We approximate (η,ρ) by smooth functions (η_ϵ,ρ_ϵ) by a parabolic mollification, e.g. 		
    η_ϵ(t,x)= ∫_|y-x|<ϵ∫_t^t+ϵ^2 n_ϵ(s-t,y-x)η(ds,dy)

 		where 
 		
    n_ϵ(t,x):= 1/ϵ^d+2n(t/ϵ^2,x/ϵ)

 		for n a smooth nonnegative function supported in (0,1)× B(1,0) that integrates to 1.

 		From the equation (<ref>) we have that 
		
    ρ_ϵ(t,x)+∂/∂ tη_ϵ (t,x)-1/2Δη_ϵ(t,x)=0

		with η_ϵ,ρ_ϵ≥ 0, and μ_ϵ=η_ϵ(0,·)+ρ({0},·)→μ in L^2(O) as ϵ→ 0. Moreover, notice that the equation (<ref>) and the condition <ref> implies that η_ϵ satisfies the Dirichlet boundary condition for O, for sufficiently small ϵ.

		We assume ϵ is sufficiently small that μ_ϵ has support in O, and we define μ̃_ϵ to be the solution of the heat equation with Dirichlet boundary conditions on ∂ O and μ̃_ϵ(0,x)=μ_ϵ(x),

 		We let u(t,x)=η_ϵ(t,x)-μ̃_ϵ(t,x), so that u(0,x)=0, u= 0 in ∂ O,  and
		
    ∂/∂ t u(t,x)≤1/2Δ u(t,x).

		The parabolic maximum principle implies that u≤ 0 and hence η_ϵ≤μ̃_ϵ, and by taking ϵ→  0, we get η≤μ̃ a.e.

 		We use 2γ tη_ϵ as a test function for (<ref>) to obtain
		
    0=    ∫_^+2γ t∫_O[ ρ_ϵ(t,x)η_ϵ(t,x)+1/2|∇η_ϵ(t,x)|^2]dxdt
        +∫_^+∫_O[1/2∂/∂ t2γ tη_ϵ(t,x)^2-γ2γ tη_ϵ(t,x)^2]dxdt
    
    			=    ∫_^+2γ t∫_O[ρ_ϵ(t,x)η_ϵ(t,x)+1/2|∇η_ϵ(t,x)|^2]dxdt 
        -1/2η_ϵ(0,·)_L^2(O)^2-∫_^+γ2γ tη_ϵ(t,·)_L^2(O)^2dt.

		The first term (with ρ_ϵη_ϵ) is nonnegative and can be dropped.  The last two terms are bounded by comparison with the solution μ̃_ϵ.  For λ the smallest eigenvalue of -1/2Δ with Dirichlet boundary conditions, 
		
    μ̃_ϵ(t,·)_L^2(O)^2≤-2λ tμ_ϵ_L^2(O)^2.

		Since we have that μ_ϵ_L^2(O)→μ_L^2(O) as ϵ→ 0, the estimate (<ref>) follows for γ<λ.  With the additional regularity of η, and the embedding of 𝒳⊂ C_-γ(^+;L^2(O)), we have that ρ is a continuous linear functional of 𝒳.
 	

We can now deduce the following. 
	
		We suppose <ref>, <ref> and <ref>.  Then, 𝒫_1(μ,ν) is finite 
		 if and only if <ref> holds. Moreover, there exists an optimal nonnegative admissible pair (η,ρ)∈ L^2_γ(^+;H_0^1(O))×(𝒳^*∩ℳ_γ (^+×O)) for 𝒫_1(μ,ν). 
	
	
	First, due to weak* compactness of the space ℳ_γ(^+×O)^2 as well as the duality  	 
	Theorem <ref>,
	there exists optimal  admissible (η,ρ)∈ℳ_γ(^+×O)^2 with finite cost if and only if 𝒫_1(μ, ν) = 𝒟_1(μ,ν)<∞.  If <ref> fails, then there is h∈ C^2(O) with -1/2Δ h≥ 0 and
		
    ∫_O h(z) ν(dz)>∫_O h(y) μ(dy).

		We let ψ=J=α h and J satisfies V_ψ[J]≥ 0 and
		
    ∫_Oψ(z) ν(dz)-∫_O J(0,y)μ(dy)→ +∞

		as α→ +∞, making 𝒟_1(μ, ν) =+∞.

		Given <ref> 
		 we know that 𝒯(μ,ν)∅, and Proposition <ref> implies there exists an admissible pair (η,ρ) thus 𝒟_1(μ,ν) is finite.  The proof of the proposition is concluded by applying Lemma <ref> to show that if (η,ρ) exists then (η,ρ)∈ L^2_γ(^+;H_0^1(O))×(𝒳^*∩ℳ_γ (^+×O)).
	


 §.§  Dual attainment in Sobolev class

	We now address the attainment of the dual problem 𝒟_1(μ, ν).
		The upcoming theorem stating that the dual problem 𝒟_1(μ, ν) is attained at (ψ,J)∈ H_0^1(O)×𝒳 is one of our most important results.  We note that V_ψ[J]≥ 0 and V_ψ[J]=0 both make sense as a weak variational inequality in these spaces; see Definition <ref>. Furthermore, due to the embedding of 𝒳⊂ C_-γ(^+;L^2(O)) 
	 the dual value of ψ and J,  that is,
	
    ∫_Oψ(z)ν(dz)-∫_O J(0,y)μ(dy),

	is well defined given <ref>. We note that there are three ways that V_ψ[J]≥ 0 inadequately bounds ψ and J.  
	
		
  * Subtracting a positive function from ψ clearly decreases the value (<ref>). This is addressed easily, for example by supposing ψ(x)=inf{t; J(t,x)}, although we follow a slightly different approach.
		
  * Adding a non-negative supersolution, -∂_t w - 1/2Δ w≥ 0 to J, also decreases the value (<ref>), and is addressed easily by supposing V_ψ[J]=0.
		
  * The most sensitive degree of freedom comes from adding 
		a superharmonic function to both ψ and J, which also decreases the value (<ref>) given <ref>.
	

	We now prove a result that utilizes this intuition to provide the needed estimates for the proof of dual attainment.  In particular, we restrict to a class of solutions such that the weak notion of V_ψ[J]=0 coincides with the viscosity sense.

	
		We suppose <ref>,<ref>, <ref>,  <ref> and <ref>.  Maximizing (<ref>) over the set  of ψ and J satisfying the following has the same value as 𝒟_1(μ,ν) in (<ref>):
		
			
  *  ψ∈ H_0^1(O), J∈𝒳, and J satisfies V_ψ[J]≥ 0 weakly;
			
  *  ψ(x)≤ J(t,x)≤ 0 for almost all (t,x)∈^+×O;
			
  *  -1/2Δψ(x)≥ -D:=L_∞ weakly.
			
	

	
		When  maximizing (<ref>) over ψ∈ H_0^1(O) and J∈𝒳 satisfying V_ψ[J]≥ 0 weakly, the supremum is bounded above by 𝒫_1(μ,ν)=𝒟_1(μ,ν) because ψ and J have sufficient regularity to be used as test functions in (<ref>) and (<ref>), which implies the weak duality inequality. 

		If ψ∈ C(O)∩ H_0^1(O) then the viscosity solution J_ψ is in C(^+×O)∩𝒳 and is the unique weak solution to V_ψ[J]=0, which is also the smallest supersolution (infimum over supersolutions); see Proposition <ref>. Due to this, in the following three stage process, weak solutions and viscosity solutions may be used interchangeably.

	Step 1:	Given ψ_0∈ C(O) and J_0∈ C_-γ^1,2(^+×O)  with V_ψ_0 [J_0] ≥ 0, we can first approximate ψ_0 from below by ψ̂∈ C^∞(O) such that ψ_0-ϵ≤ψ̂≤ψ_0, and therefore
		
    ∫_Oψ̂(z)ν(dz)≥∫_Oψ_0(z)ν(dz)-ϵ  &   V_ψ̂ [J_0]≥ V_ψ_0 [J_0] ≥ 0.

		Then we define h to be the solution to the Poisson problem Δ h =0 with h=ψ̂ on ∂ O and we let ψ_1=ψ̂-h.  For Ĵ=J_0-h we have  V_ψ_1[Ĵ]≥ 0. Given <ref>, (<ref>) does not change upon replacing (ψ̂,J) with (ψ_1,Ĵ).   We let J_1 be the unique solution to V_ψ_1[J_1]=0 with Dirichlet boundary condition, and J_1∈ C_-γ(^+×O)∩𝒳.  Then (ψ_1,J_1) satisfy item <ref>, 
		and as J_1 is the smallest supersolution, we immediately have J_1≤Ĵ, hence (<ref>) again does not decrease.

		Step 2: We next define ϕ∈ C(O)∩ H_0^1(O) as the superharmonic envelope of ψ_1, equivalently 
		the viscosity solution given by the infimum over supersolutions of
		
    min{ϕ(x)-ψ_1(x),-1/2Δϕ(x)}=0.

	We define ψ_2:=ψ_1(x)-ϕ(x) and J_2(t,x):=J_1(t,x)-ϕ(x). Clearly, J_2≥ψ_2. Since ϕ is a supersolution of V_ψ_1[ϕ]≥ 0 we have  
	ϕ(x)≥ J_1(t,x) and thus J_2≤ 0. If J_2(t_1,x_1)<0 then ϕ(x_1)>J_1(t_1,x_1)≥ψ_1(x_1) and 
		
    -∂/∂ t J_2(t_1,x_1)-1/2Δ J_2(t_1,x_1)= -∂/∂ t J_1(t_1,x_1)-1/2Δ J_1(t_1,x_1)≥ -L(t_1,x_1).

		If J_2(t_1,x_1)=0, then since J_2≤ 0 it follows that
		
    -∂/∂ t J_2(t_1,x_1)-1/2Δ J_2(t_1,x_1)≥ 0≥ -L(t,x).

		We have shown that J_2 is a supersolution  
		
    V_ψ_2[J_2]≥ 0,
 and (ψ_2,J_2) satisfy item 
		<ref>.  
  		Moreover notice that 
		the difference in dual value is 
		
    ∫_O [-ϕ(z)]ν(z)dz-∫_O [-ϕ(y)]μ(y)dy≥ 0

		because -ϕ is subharmonic and μ≺ν by <ref>.


Step 3:
	We now modify the functions (ψ_2, J_2) to satisfy all the properties  <ref>, <ref>, and <ref>. 
	We consider ψ_3∈ C(O)∩ H_0^1(O) that solves the variational inequality
		
    min{ψ_3-ψ_2,-1/2Δψ_3+D} = 0.

		Here, we can take ψ_3 so that it is the smallest supersolution.
		Clearly, ψ_3≥ψ_2 and ψ_3 satisfies the item <ref>.

Consider
J̃_2(x) : = inf_t J_2 (t,x).  Notice that for each x either the infimum is attained at some finite t or  there is a sequence t_i →∞ such that lim_i →∞∂/∂ t J_2 (t_i, x) = 0 and lim_i→∞ J(t_i, x) =J̃ (x). As -∂_t J_2 - 1/2Δ J_2  ≥ -L ≥ -D, this implies that J̃ is a supersolution to (<ref>), therefore

    ψ_3 ≤J̃_2 ≤ J_2.


		Notice that 
		J_2 is also a supersolution of V_ψ_3[J_2]≥ 0. 	Therefore, if we let J_3 be the smallest supersolution  to solve V_ψ_3[J_3]=0 then  finally (ψ_3,J_3) satisfy items <ref>, <ref>, <ref>, 
		and  as ψ_3 ≥ψ_2 and J_3 ≤ J_2, we did not decrease the dual value more than ϵ. This completes the proof.
	

	
		Given ψ satisfying items <ref>, <ref>, <ref>,
		we may always select a representative that is lower semicontinuous (denoted by LSC(O)).  Then the value function J_ψ is lower semicontinuous and is a `discontinuous viscosity solution' to V_ψ[J]=0 <cit.>.  Furthermore it is verified in <cit.> (Chapter 3, Section 2) that the value function to the optimal stopping problem with terminal reward ψ is the “minimal weak solution” to V_ψ[J_ψ]=0.  However, J_ψ no longer coincides with the infimum over smooth supersolutions to V_ψ[J]≥ 0, e.g. consider a case where J_ψ≡ψ and ψ is not upper semicontinuous.
	


	

	The proof of dual attainment is now straightforward using Proposition <ref>.
	
		Suppose <ref>, <ref>, <ref>, <ref> and <ref>. The maximum of the Eulerian dual problem is attained at ψ∈  LSC(O)∩ H_0^1(O), and J_ψ∈  LSC(O)∩𝒳 which is the minimal weak solution of V_ψ[J_ψ]=0.
		
		For (η,ρ) that minimize the Eulerian problem 𝒫_1(μ,ν) the complementary slackness condition holds:
		
    0=    ∫_O∫_^+[J(t,x)-ψ(x)]ρ(dt,dx)
        + ∫_^+∫_O[-η(t,x)∂/∂ tJ(t,x) +1/2∇ J(t,x)·∇η(t,x)+L(t,x)η(t,x)] dxdt.
		

		
	
	
		We consider a maximizing sequence to the dual problem.
		By Proposition 
		<ref> 
		we may  assume that 
		(ψ^i,J^i)∈ H_0^1(O)×𝒳 with V_ψ^i[J^i]≥ 0,  
		ψ^i≤ J^i≤ 0, 
		and -Δψ^i(x)≥ -D.  
		The last two conditions and the maximum principle imply that there is a constant K depending on D and O such that ψ^i≥ -K. Therefore, we have the uniform bound on ψ^i_H_0^1(O) given by
		
    ∫_O |∇ψ^i(x)|^2dx =      ∫_O -Δψ^i(x) ψ^i(x) dx
    ≤    ∫_O D |ψ^i(x)|dx≤ DK|O|.

		Then there is a subsequence such that ψ^i_k⇀ψ in H_0^1(O). 
		Similarly, J^i_k⇀ J in 𝒳 (since J^i_k_𝒳≤ Cψ^i_k_H_0^1 by Proposition <ref>) with V_ψ[J]≥ 0 and ψ and J attain the maximum dual value.    Properties ii. and iii. are preserved in the weak limit, and Proposition <ref> shows that ψ has a lower semicontinuous representative.

		

		The optimizers J and ψ 
		now have  sufficient regularity to be used as   test functions in (<ref>) and (<ref>) 
		to obtain
		
    ∫_OJ(0,y)μ(y)dy=    ∫_^+∫_O[-η(t,x)∂/∂ tJ(t,x)+1/2∇ J (t,x)·∇η(t,x)]dxdt 
        +∫_O∫_^+ J(t,x)ρ(dt,dx); 
    ∫_Oψ(z) ν(dz) =    ∫_O∫_^+ψ (x)ρ(dt,dx)

		In view of Theorem <ref> we have
		
    ∫_O ψ(z)ν(z)dz-∫_OJ(0,y)μ(y)dy=∫_^+∫_O L(t,x)η(t,x)dxdt

		and add to (<ref>) we get (<ref>).
		Finally, we may also replace J by the minimal weak solution to V_ψ[J_ψ]=0. 
	

	As a consequence of Theorem <ref> we also have attainment of the problem 𝒟_0(μ,ν) in a weaker regularity class.

	
		Suppose the same hypotheses as Theorem <ref>, then the optimizers (ψ,J_ψ) may be selected to satisfy the dynamic programming principle
		
    J_ψ(t,x):=sup_τ∈ℛ^t,x{𝔼^t,x[ψ(B_τ)-∫_t^τ L(s,B_s)ds]}.

		Moreover, the process
		
    G_t:=J_ψ(t,B_t)-∫_0^t L(s,B_s)ds

		is a lower semicontinuous supermartingale (assuming G_t=G_t∧τ_O for the exit time τ_O), satisfies G_t-ψ(B_t)≥ -∫_0^tL(s,B_s)ds, and attains the optimal cost
		
    ∫_Oψ(z)ν(dz)-𝔼[G_0]=𝒫_0(μ,ν).

		For τ that minimizes the primal problem 𝒫_0(μ,ν), we have that G_t∧τ is a martingale and G_τ = ψ(B_τ)-∫_0^τ L(t,B_t)dt.
	
	
		Given lower semicontinuous ψ, the minimal weak solution J to V_ψ[J]=0 (with the Dirichlet boundary condition) coincides with the value function J_ψ that satisfies (<ref>); see Theorem 4.6 of Chapter 3 in <cit.> and note that since ψ is lower semicontinuous it may be approximated from below by continuous functions.

		By Proposition <ref>, (ψ,G) also attain the value of 𝒟_0(μ,ν), although G is only lower semicontinuous on the space of paths. The process G satisfies 
		
    G_t-ψ(B_t)≥ -∫_0^tL(s,B_s)ds,
 
		for t<τ_O and (ψ,G) has the same value that equals 𝒫_0(μ,ν).  That G is a supermartingale follows from the dynamic programming principle (<ref>):
		
    G_t ≥𝔼[ J_ψ(σ,B_σ)-∫_t^σ L(s,B_s)ds|ℱ_t]-∫_0^tL(s,B_s)ds=𝔼[G_σ|ℱ_t]
  
		for any stopping time t≤σ≤τ_O.

		If τ minimizes 𝒫_0(μ,ν) then
		
    𝔼[∫_0^τ L(t,B_t)dt] = 𝔼[ψ(B_τ)-J_ψ(0,B_0)],

		which implies that 𝔼[G_τ]≥𝔼[G_0].  For any stopping time 0≤σ≤τ, since G is a supermartingale 𝔼[G_τ]≤𝔼[G_σ]≤𝔼[G_0], and it follows that G_t∧τ is a martingale and G_τ = ψ(B_τ)-∫_0^τ L(t,B_t)dt almost surely.
	



§ OPTIMAL STOPPING BY HITTING OF BARRIER




 	We wish to characterize when the optimal stopping time is given by the hitting time of a barrier. 
	From Theorem <ref> the process must stop in the set where J(t,x)=ψ(x). We find that this set is given by the epi/hypergraph of a function s(x) if L is either strictly increasing or decreasing in time. In these cases the hitting time must be the first time the process enters this set. We denote the cases of time dependence of L as:

 	
 		
  *  The cost function L strictly increases in time;
	 	
  *  The cost function L strictly decreases in time;
	 	
  *  The cost function L is stationary in time.
	
	
	

 One may compare the results in this section to those  by Beiglböck, Cox and Huesmann <cit.>, where they obtain similar results in cases comparable to those we consider below. While their approach is based on a stochastic variational principle on path space analogous to cyclic monotonicity in optimal transport, ours uses the Eulerian formulation and the corresponding dual variational inequalities  developed in the previous sections insipired by the Kantorovich duality approach to optimal transport. 


	
	We start with the following monotonicity and regularity results for the dual functions. 
	
		Given <ref>, we suppose that ψ∈ LSC(O)∩ H_0^1(O) and J_ψ is the minimal weak solution of V_ψ[J_ψ]=0.

		
			
  * Given <ref> then J_ψ is non-increasing in time.  
			
  * Given <ref> then J_ψ is non-decreasing in time. 
			
  * Given <ref> then J_ψ is stationary in time.
		
		In each case we define the free boundary
		
    s(x):=inf{t∈^+; J_ψ(t,x)=ψ(x)  }   <ref>
    sup{t ∈^+; J_ψ(t,x)=ψ(x) }   <ref>
    
    				 0     <ref>.

	

	
		We use the dynamic programming principle for the value function (<ref>) for the proof.  We first suppose <ref> and fix x, t_1≤ t_2.  For any ϵ>0, there is a stopping time τ_2∈ℛ^t_2,x, i.e. τ_2≥ t_2, that nearly achieves the supremum of (<ref>) such that
		
    J_ψ(t_2,x) ≤𝔼^t_2,x[ ψ(B_τ_2)-∫_t_2^τ_2 L(s,B_s)ds] +ϵ.

		Then we let τ_1 = τ_2+t_1-t_2 ∈ℛ^t_1,x and the dynamic programming principle implies
		
    J_ψ(t_1,x) ≥𝔼^t_1,x[ ψ(B_τ_1)-∫_t_1^τ_1 L(s,B_s)ds]≥ J_ψ(t_2,x)-ϵ.

		For the second inequality we use <ref> as -L(s,y)≥ -L(s+t_2-t_1,y). Taking ϵ to 0 shows that J_ψ(t_1,x) ≥ J_ψ(t_2,x).

		Given <ref> the proof follows the same line by first selecting τ_1 to be nearly optimal starting from t_1 and defining τ_2=τ_1+t_2-t_1.  The same argument yields the inequality J_ψ(t_2,x)≥ J_ψ(t_1,x).   

		With <ref>, both arguments are valid, showing J_ψ(t_1,x)=J_ψ(t_2,x).
	

	
		An alternate proof of monotonicity for J_ψ by viscosity solution methods is possible if ψ is continuous. For example given <ref>, if we consider
		
    Ĵ(t,x) := sup{J_ψ(r,x); t≤ r},

		obviously Ĵ≥ J_ψ and Ĵ is non-increasing in time.  Then we can show that Ĵ is a viscosity subsolution to V_ψ[Ĵ]≤ 0 by translating the comparison function, after which the comparison principle proves Ĵ=J_ψ.
	

	The  monotonicity has allowed us to define the free boundary 
	s(x) of (<ref>). Then for the case of <ref> (resp. <ref>) we have the barrier set 
	
    R_c:= {(t,x); t≥ (resp.≤)  s(x)}
 and its `interior' 
    R_o:={(t,x); t> (resp. <)  s(x)}.

	
	
	  We let τ_o and τ_c denote their corresponding first hitting-time: 
	
    τ_o= inf{t; B_t∈ R_o},   τ_c= inf{t; B_t∈ R_c}.


	The cases <ref> and <ref> correspond to the classical Root and Rost embeddings, respectively (see Figure (<ref>)).  The case that L decreases until some fixed time t_0 and later increases also implies the corresponding monotonicity of J_ψ changing accordingly.  These so-called `cave embeddings' have been pointed out in <cit.>. A later work by Cox and Kinsley <cit.> deal with a specific one-dimensional non-Lagrangian cost that switches between Root and Rost-like frameworks along a fixed curve t_0(x). They then identify an explicit `cave barrier' that determines the embedding by using a PDE heuristic, which would be interesting to see if it could be made rigorous by a suitable refinement of our analysis. 
	
		
	
	The following Lemma shows how the barriers determine the density and stopping distribution of the process given that the process always stops in R_o and continues in the complement of R_c.  In the case of <ref> there is only one such admissible pair (η,ρ), whereas for <ref> the uniqueness holds up to the choice of how much mass to stop at time 0 on the set where s(x)=0.

	
 	
	Suppose <ref>, <ref>, <ref>, <ref> and <ref>. 
		We suppose R is a measurable forward-barrier such that (r,x)∈ R whenever (t,x)∈ R with t≤ r, and (t,x)∈ R if there is (t_i,x)∈ R with t_i→ t.  Then given μ there is a unique solution (η,ρ) to (<ref>) with η(R)=0 and ρ(R)=1.

		If instead R is a measurable backward-barrier such that (r,x)∈ R whenever (t,x)∈ R with t≥ r, and (t,x)∈ R if there is (t_i,x)∈ R with t_i→ t, then the solution (η,ρ) to (<ref>) with η(R)=0 and ρ(R)=1 is uniquely determined given the value of ρ on the set (0,x) where s(x)=0.
	

	
		We consider (σ,π)∈ L_γ^2(^+;H_0^1(O))×ℳ_γ∩𝒳^* that satisfy (<ref>) with source distribution α∈ L^2(O) and π({0},·)∈ L^2(O),
		
    -∫_Ow(0,y) α(dy)=    ∫_O∫_^+[∂/∂ tw(t,x)+1/2Δ w(t,x)]σ(dt,dx)
        -∫_O∫_^+ w(t,x)π(dt,dx).

		We define the potential U_t∈ H_0^1(O) by
		
    ∫_O1/2∇ h(x)·∇  U_t(x) = ∫_Oh(x)σ(t,x)dx+∫_O∫_0^th(x)π(ds,dx) ∀ h∈ H_0^1(O).

		Now for smooth compactly supported functions w∈ C_c^∞(^+×O) that vanish on ∂ O,
		
    ∫_O∫_^+1/2(-∂/∂ t∇ w(t,x))·∇ U_t(x)dtdx 
    
    			=    ∫_O∫_^+(-∂/∂ t w(t,x))σ(t,x)dtdx+ ∫_O∫_^+(-∂/∂ tw(t,x))∫_0^tπ(ds,dx)dt
    
    			=    ∫_O∫_^+ -1/2∇ w(t,x)·∇σ(t,x)dtdx+∫_O w(0,x)α(x)dx
        -∫_O w(0,y)π({0},dy).

		For any continuous function g∈ C(^+×O) with compact support in (0,∞)× O, we may select such a w with -1/2Δ w(t,x)=g(t,x), and after integrating by parts we obtain
		
    ∫_O∫_^+ g(t,x)∂/∂ tU_t(x) dtdx =∫_O∫_^+ -g(t,x)σ(t,x)dtdx.

		In particular, ∂/∂ tU_t(x)=-σ(t,x) for almost every (t,x).
		By the definition of U we also have -1/2Δ U_0(x)=α(x)-π({0},x), with U_t→ U_∞ as t→∞ and -1/2Δ U_∞(x)=∫_^+π(dt,x).
		In particular the potential belongs to  𝒳. We note that we have not assumed the non-negativity of σ and π. 

		
		 Using U_t as a test function in (<ref>) we obtain
		
    ∫_O U_0(x)α(x)dx=    ∫_O∫_^+[(-∂/∂ tU_t(x))σ(t,x)+1/2∇ U_t(x)·∇σ(t,x)]dtdx
        +∫_O∫_^+U_t(x)π(dt,dx)
    
    			=    ∫_O∫_^+[2σ(t,x)^2+σ(t,x)∫_0^tπ(ds,x)]dtdx
        +∫_O∫_^+U_t(x)π(dt,dx).



		Now we consider two solutions (η_0,ρ_0) and (η_1,ρ_1) satisfying the conditions of the lemma, and we let σ=η_0-η_1 and π=ρ_0-ρ_1.  Then we have that (σ,π) satisfy (<ref>)  with source measure that is identically zero.  Furthermore, σ=0 a.e. in R and π(Z)=0 for any measurable subset Z⊂ R^c.  By Lemma <ref> we have (σ,π)∈ L^2_γ(^+;H_0^1(O))×𝒳 and π({0},·)∈ L^2(O) because ρ_0({0},·)≤μ, and the same for (η_1,ρ_1).

		Assuming that R is a forward-barrier we have ∫_0^tπ(ds,x)=0 a.e. in R^c so ∫_O∫_^+∫_0^tπ(ds,x)σ(dt,dx)=0. In R we have U_t(x)=U_∞(x) due to d/dtU_t(x)=-σ(t,x)=0 for (t,x)∈ R, thus 
		
    ∫_O∫_^+U_t(x)π(dt,dx)=∫_O∫_^+U_∞(x)π(dt,dx)=1/2∫_O |∇ U_∞(x)|^2dx.
  
		The initial condition for U_t is U_0=0 because if ρ_1 is non-zero at (0,x) then it must equal α(x).
		Then the identity (<ref>) yields that 
		
    ∫_O∫_^+|σ(t,x)|^2dtdx + 1/2∫_O |∇ U_∞(x)|^2dx=0

		 and thus η_0=η_1 and consequentially ρ_0=ρ_1.

		In the case of a measurable backward-barrier, we instead have
		
    ∫_O∫_^+U_t(x)π(dt,dx)=∫_O∫_^+U_0(x)π(dt,dx)=-1/2∫_O|∇ U_0(x)|^2dx.

		The value of U_0 is 0 if s(x)≠0, however,	we must consider the possibility that π is non-zero at (0,x) in which case U_0(x) solves -1/2Δ U_0(x)=π({0},x), thus is uniquely determined by the value of π at t=0.  
	

	In the above lemma, we consider a potential function U_t associated to the density and stopping distribution involved in the Eulerian formulation, that essentially satisfy  the equation
	
    -1/2Δ U_t(x) = η(t,x) + ∫_0^tρ(ds,x),

	This potential also satisfies, in case <ref>, a quasivariational equation of the form

    min{∂_t U_t - 1/2Δ U_t,U_t-U_ν}=0,

	where -1/2Δ U_ν=ν, and -1/2Δ U_0=μ. 
Note that in one-dimension and for case <ref>, one can consider explicitly the potential 

    U_t(x)=𝔼[|x-B_t∧τ|],

which readily satisfies the above properties; this potential function has already been used in this particular case by <cit.> and <cit.>, and a closely related function was used for the case <ref> in one dimension by <cit.>.  	
	We thank A. Cox, T. De Angelis and M. Huesmann for pointing out these papers to us.     
		


	
		Suppose <ref>, <ref>, <ref>, and <ref>. We suppose (ψ,J_ψ) are optimal and that R_c and R_o are defined as above with τ_c and τ_o the hitting times in (<ref>).

		If <ref> then the unique optimal stopping time is given by  τ_c.

 		If <ref> then the same holds if the support of μ and ν is disjoint.  Otherwise, if s(x)=0 in the support of μ then the optimal stopping time is the unique randomized stopping time that satisfies τ_c≤τ≤τ_o and B_τ∼ν, in particular given B_0=x, τ=0 occurs with probability ν(x)/μ(x), and otherwise τ=inf{t>0;(t,B_t)∈ R_c}.
	
	
		We first show that if τ is optimal then τ_c≤τ≤τ_o.  From Corollary <ref> we have that J_ψ(τ,B_τ)=ψ(B_τ) almost surely, hence τ_c≤τ. We now show that 
		
    η(R_o)=𝔼[∫_0^τ1{[            1 (t,B_t)∈ R_o;            0    otherwise ]}dt]=0,

		which is equivalent to τ≤τ_o almost surely.  We let (η,ρ) be the density for B_t with t≤τ and stopping distribution of (τ,B_τ) of Proposition <ref>, and we let τ^t,x∈ℛ^t,x be the conditional expectation of τ given B_t=x as defined in (<ref>).
		From Corollary <ref> and Proposition <ref>, we have that
		
    0=    𝔼[G_τ-G_t∧τ]
    
    			=    𝔼[1{t≤τ}(ψ(B_τ)-J_ψ(t,B_t)+∫_t^τ L(s,B_s)ds)]
    
    			=    ∫_O (𝔼^t,x[ψ(B_τ^t,x)-J_ψ(t,x)+∫_t^τ^t,xL(s,B_s)ds])η(t,x)dx.

		We also have that for each (t,x)
		
    𝔼^t,x[ψ(B_τ^t,x)-J_ψ(t,x)+∫_t^τ^t,xL(s,B_s)ds]≤ 0,

		so it follows that for η-a.e. (t,x) equality holds in (<ref>), or, in other words, the randomized stopping time τ^t,x is optimal for (<ref>).	For η-a.e. (t,x)∈ R_o we have that
		
    ψ(x)=J_ψ(t,x) = 𝔼^t,x[ ψ(B_τ^t,x)-∫_t^τ^t,x L(s,B_s)ds].

		Now we define τ̂^t,x= τ^t,x -t + s(x)+ϵ∈ℛ^s(x)+ϵ,x and the dynamic programing principle implies that if τ^t,x>t then
		
    J_ψ(s(x)+ϵ,x) ≥    𝔼^s(x)+ϵ,x[ ψ(B_τ̂^t,x)-∫_s(x)+ϵ^τ̂^t,x L(r,B_r)dr]
    
    			>    𝔼^t,x[ ψ(B_τ^t,x)-∫_t^τ^t,x L(s,B_s)ds],

		where we have used either <ref>, ϵ>0 and t>s(x)+ϵ, or we have used <ref>, ϵ<0 and t<s(x)+ϵ. This contradicts that J_ψ(s(x)+ϵ,x)=ψ(x), which implies that τ^t,x=t and completes the claim that τ≤τ_o. 

		We have shown that ρ(R_c)=1 and η(R_o)=0.
		 Since R_o and R_c differ by a set of Lebesgue measure zero we also have η(R_c)=0.

		We next note that for τ_c there is  a corresponding pair (η̃,ρ̃) by  Proposition 
 <ref>.  Furthermore, from the definition of τ_c we have η̃(R_o)=0 and ρ̃(R_c)=1.

		Given <ref>, Lemma <ref> implies that η(R_c)=0 and ρ(R_c)=1 along with the initial condition uniquely determine η and ρ thus (η̃,ρ̃)=(η,ρ) and τ_c attains the value 𝒫_0(μ,ν) with B_τ_c∼ν, thus τ_c is optimal and τ=τ_c since τ≥τ_c.  

		In the case of <ref> we similarly apply Lemma <ref> but must also consider the case that s(x)=0. In this case exactly ν(x) mass must stop immediately for the target constraint (<ref>) to be satisfied.  Thus τ equals the stopping time that stops at time zero with probability ν(x)/μ(x) and otherwise is the first positive hitting time of R_c, i.e τ=inf{t>0;(t,B_t)∈ R_c}.
	

	
		It is well known that there is a unique forward (resp. backward) barrier yielding a hitting time that embeds the final measure into Brownian motion (see e.g., <cit.>).  This clearly implies that any Lagrangian satisfying <ref> (resp. <ref>) lead to the same free boundary and hence optimal stopping time.

		In the case of <ref>, i.e. that L(t,x)=L(x), we may easily construct an optimal dual potential by solving
		
    -1/2Δψ(x) = -L(x),

		with Dirichlet boundary conditions.  The value function is then time independent, i.e., J_ψ(t,x)=ψ(x) for all time, and every admissible stopping time has the same cost, 
 		
    𝔼[∫_0^τL(B_t)dt]=∫_O ψ(z)ν(dz)-∫_Oψ(y)μ(dy).


		Given a Lagrangian L satisfying <ref> (resp. <ref>), and the free boundary s(x) of (<ref>), one might expect that the optimal dual potential could be chosen to solve 
 		
    -1/2Δψ(x)=-L(s(x),x),

 		with Dirichlet boundary conditions. However, this is not true in general. The function
 		
    J(t,x) := 𝔼^t,x[ψ(B_τ_c^t,x)-∫_t^τ_c^t,xL(r,B_r)dr],

 		where τ_c^t,x is the first hitting time of R_c given B_t=x, satisfies V_ψ[J](t,x)=0 whenever t≠s(x). On the other hand, (ψ,J) may not be admissible because V_ψ[J](s(x),x)≱0 in the viscosity sense, or similarly (ψ,J) do not satisfy V_ψ[J]≥ 0 weakly.
 	



§ FREE BOUNDARY FLOW, BSDE AND EXAMPLES
 
	In this section we consider a few additional aspects of our results as well as  examples. 


 §.§ Free boundary equation

	It is useful to write down the strong form of the coupled free boundary problem that has arisen in our analysis.  
	The optimality criterion in the Eulerian formulation implies that for optimizers J(t,x)-ψ(x)=0 everywhere on the support of ρ and that J(t,x) solves the backwards parabolic equation
 	
    -∂/∂ tJ(t,x)=1/2Δ J (t,x)-L(t,x)

 	on the support of η. 

	For (t,x)∈ R_c^c we have the following heat equation for the density η,
	
    ∂/∂ tη = 1/2Δη(t,x),

	with Dirichlet boundary conditions along (s(x),x),
	
    η(s(x),x)=0,

	and an initial condition η(0,y)=μ(y). The quantities s(x) and μ uniquely determine η as shown in Lemma <ref> (excepting the case that R_c is a backward barrier and contains (0,x) in the support of μ).  

	To determine s(x) we need to use the constraint that the distribution of stopped particles equals ν.  Note that we must have ρ(dt,dx) = δ_s(x)(dt)ν(dx) so assuming sufficient regularity (especially on s(x)), the equation (<ref>) gives  (when L is increasing) 
	
    ∫_Ow(s(z),z)ν(z)dz=    ∫_O∫_^+ w(t,x)ρ(dt,dx) 
    
    		=    ∫_O∫_0^s(x)[∂/∂ t w(t,x)+1/2Δ w(t,x)]η(t,x)dtdx
        +∫_Ow(0,y)μ(y)dy
    
    		=    -1/2∫_O∫_0^s(x)∇·[w(t,x)∇η(t,x)]dtdx .

		Now apply the Stokes' theorem to get
	
    =    ∫_O1/2∇ s(x) ·[w(s(x),x)∇η(s(x),x)]dx.
 
	Thus when we consider the flux of stopping-particles we have  the   relation
	
    ν(z) = ±1/2∇ s(z) ·∇η(s(z),z).

	where the ± is determined by whether L increases or decreases and s(x) is hit from below or above.  This stopping-rate can be seen to be equivalent to the `two-sided' Stefan problem studied in 1D by <cit.>.

	


 §.§ Martingales and BSDE

	In comparing  the problems 𝒫_0(μ,ν) and 𝒟_0(μ,ν) we now have attainment of 𝒟_0(μ,ν) at a lower semicontinuous super martingale given by
	
    G_t = J_ψ(t,B_t)-∫_0^tL(s,B_s)ds.

	Indeed this martingale is the Snell envelope of the process Y_t=ψ(B_t)-∫_0^tL(s,B_s)ds
	as G_t∧τ is a martingale for τ the Snell hitting time, which agrees with the optimal stopping in the case of <ref> and <ref> (modulo behavior at t=0).

	To compare with the backward stochastic differential equations as studied in <cit.>, <cit.>, <cit.> and others, we assume that J_ψ∈ C_-γ^1,2(^+×O) for 
	J_ψ satisfying  
	  V_ψ[J_ψ]≥ 0.
	  Consider Z_t=J_ψ(t,B_t), the random vector P_t = ∇ J_ψ(t,B_t), and the random matrix Q_t=∇^2J_ψ(t,B_t). We have Z_t≥ψ(B_t) and Ito's formula shows that 
	
    P_t =    P_τ +∫_t^τ[∇∂/∂ tJ_ψ(s,B_s)+1/2∇Δ J_ψ(s,B_s)]ds+∫_t^τ∇^2J_ψ(s,B_s) dB_s
    
    		=    P_τ+∫_t^τ∇ L(s,B_s) ds + ∫_t^τ Q_sdB_s.

	In other words, (Z,P,Q) solve the backward stochastic differential equation
	
    -dP_t=    ∇ L(t,B_t)dt+Q_tdB_t, 
    
    		-dZ_t =    -L(t,B_t)dt-P_t· dB_t,

	with Z_τ =ψ(B_τ) and P_τ=∇ψ(B_τ), along with Z_t≥ψ(B_t) for t≤τ.


	
		This remark leads to a third dual formulation (that seems to require slightly more regularity of L):
		
    Maximize  ∫_Oψ(z)ν(dz)-𝔼[Z_0]

		subject to (P,Q,Z) solve (<ref>) for t≤τ with Z_τ =ψ(B_τ), P_τ=∇ψ(B_τ), and Z_t≥ψ(B_t) for t≤τ.
	

	

 §.§ Examples

	The simplest examples of optimal stopping times (although not fitting in our compactly supported setting) occur when ν(z)=μ̃(t_1,z) for μ̃ the solution to the heat equation with μ̃(0,y)=μ(y) and t_1 is a constant. 
	Since τ=t_1 is the hitting-time of a forward-barrier, by the results of Section <ref> (modulo the noncompactness of the supports), it follows that τ is optimal if L(t,x) is strictly increasing.
	 In the case that L(t,x)=L(t) we can easily compute the optimal cost
	
    𝒫_0(μ,ν)=∫_0^t_1L(t)dt.

	To compare with the dual problem, we let ψ solve
	
    -1/2Δψ(z)=-L(t_1),

	which has a bounded below solution ψ(z)=L(t_1)Q(z), where Q(z) is any nonnegative quadratic with ∇^2Q(z)=Σ and 1/2 trace(Σ) =1 (note that the difference of any two such solutions differs only by a harmonic polynomial).  The value function is solved by
	
    J_ψ(t,x)=ψ(x) +f(t)

	where f solves
	
    -f'(t) + L(t) = L(t_1)

	given by
	
    f(t)= L(t_1)(t_1-t)-∫_t^t_1 L(s)ds.

	We let Σ_μ denote the covariance of μ and Σ_ν denote the covariance of ν.  It follows from the heat equation that Σ_ν-Σ_μ = 1/2t_11.  Then the dual value is
	
    𝒟_1(μ,ν)   = ∫_^dψ(z)ν(dz)-∫_^dJ_ψ(0,y)μ(dy)
    
    		=     L(t_1)Σ· (Σ_ν - Σ_μ) -L(t_1)t_1+∫_0^t_1 L(t)dt= ∫_0^t_1 L(t)dt,

	demonstrating the duality principle.
	For the case that L(t) decreases, we would first
	subtract the overlap μ∧ν and let μ^+=μ- μ∧ν and ν^+=ν-μ∧ν, 
	and all the mass except μ^+ would stop immediately.  Then the mass of μ^+ would be transported to ν^+ along some free boundary s(x) with s(α)=0 where α is any point such that μ(α)=ν(α).

	We conclude with some figures illustrating the simulation of general distributions and Lagrangians that will be explored in a further numerical study.

	We have discretized the domain as the integers between 0 and 39.  The initial distribution μ is the uniform measure on the integers between 16 and 23, and the target measure ν is proportional to |sin(π x/13)|.  We perform the convex optimization of the dual problem to approximate the free boundary yielding the simulation for the increasing (I.) and decreasing (II.) cases, see Figure <ref>.
	
    The solution method does not depend on the property of the Lagrangian thus in Figure 2 we also simulate the Skorokhod embedding for an oscillating Lagrangian proportional to 1-cos(20π t).

	
	





§ 



 §.§ Weak duality

	
		The primal and dual problem have the same value 𝒫_0(μ,ν)=𝒟_0(μ,ν).
	
	
		We exploit a duality between progressively measurable continuous supermartingales with exponential growth, G∈𝒦^+_-γ, and randomized stopping times with exponential decay τ∼α∈ℛ with [γτ]<∞.  We define 𝒜_-γ⊂ C(^+×Ω) where Ω has the topology of uniform convergence, sup_(t,ω)∈^+×Ω-γ tA_t<∞, and -γ tA_t→ 0 uniformly on compact sets. Furthermore, we assume A∈𝒜_-γ is progressively measurable, i.e. for s∈ [0,t], s↦ A is ℱ_t measurable. We consider elements of the dual space 𝒜_-γ^* with ℙ as their Ω marginal, what satisfy that the disintegration β:Ω→ℳ(^+) has β([0,t]) is ℱ_t measurable for any t≥ 0.  
		The randomized stopping times, α∈ℛ, with exponential decay are such elements that also satisfy α≥ 0 and α(^+)=1.

		The dual relationship is given by, for A∈𝒜_-γ and τ∼α∈ℛ with [γτ]<∞,
		
    𝔼[A_τ]:=𝔼[ ∫_^+ A_tα(dt)].


		We define Θ:𝒜_-γ→∪{+∞} as
		
    Θ(f)= 0     A_t≥ -∫_0^tL(s,B_s)ds, ∀ (t,ω),
     +∞     otherwise

		so that the Legendre transform is, for τ∼α∈ℛ with [γτ]<∞,
		
    Θ^*(-α)=sup_A∈𝒜_-γ{-𝔼[A_τ]-Θ(A)}=  𝔼[∫_0^τ L(t,B_t)dt].

		For general β∈𝒜_-γ^*, the Legendre transform is +∞ if β≱0, and is the pairing of β and ∫_0^tL(s,B_s)ds otherwise. 

		We define Ξ to be
		
    Ξ(A) = inf_ψ∈ C(O),G∈𝒦^+_-γ{   -∫_Oψ(z)ν(dz)+𝔼[G_0]; G_t-ψ(B_t)≥ A_t}.

		Then we calculate the Legendre transform for β∈𝒜_-γ^*:
		
    Ξ^*(β) =    sup_A∈𝒜_-γ{∫_Ω∫_^+A_t(ω)β(dt,dω)-Ξ(A)}
    
    			=    sup_ψ∈ C(O),G∈𝒦^+_-γ{∫_Ω∫_^+[G_t(ω)-ψ(B_t(ω))]β(dt,dω)-𝔼[G_0]+∫_^dψ(z)ν(dz)}.

		For β∈𝒜_-γ^* with β≥ 0, then
		
    sup_G∈𝒦_-γ^+{∫_Ω∫_^+ G_t(ω)β(dt,dω)-[G_0]}=0

		if and only if β∈ℛ, and it is +∞ otherwise. Since and G̃∈ C(Ω) defines G∈𝒦_-γ^+ by G_t(ω):=G̃(ω), we have that the marginal on Ω of β is ℙ, and the growth condition follows easily from multiplying by -γ t.  The supermartingale property and the optional stopping theorem then implies that
		
    ∫_Ω∫_^+G_t(ω)β(dt,dω) =[G_τ]≤[G_0].


		By definition of Ξ we have that 𝒟_1(μ,ν)=-Ξ(A^L) where A_t^L=-∫_0^tL(s,B_s)ds.
		Similarly, the primal problem is
		
    sup_τ∈ℛ_γ{-Θ^*(-α)-Ξ^*(α)}.

		Fenchel-Rockafellar applies after showing there is A∈𝒜_-γ with Ξ[A],Θ[A]<∞ and Θ continuous at A, but this obviously holds, for example with A^L+γ t.
	




 §.§ Variational inequalities
 

	Suppose ψ and L are continuous, and J is lower semicontinuous.  Then we say that V_ψ[J]≥ 0 in the sense of viscosity  (viscosity supersolution)  if whenever a smooth function w touches J from below at (t,x), i.e. w(t,x)=J(t,x) and w(s,y)≤ J(s,y) for all (s,y)∈^+×O, then  V_ψ[w](t,x)≥ 0.

	Similarly, if J is upper semicontinuous we say that V_ψ[J]≤ 0 in the sense of viscosity  (viscosity subsolution)  if whenever w touches J from above at (t,x) then  V_ψ[w](t,x)≤ 0.

	For J continuous, we say that V_ψ[J]=0 in the sense of viscosity, if J is both a subsolution and supersolution. 






	Suppose ψ∈ H_0^1(O), ψ≤ 0 and -Δψ is bounded below.  Then there is a lower semicontinuous representative of ψ.  

	Similarly, suppose J ∈𝒳, J≤ 0,
	and -∂/∂ tJ-1/2Δ J is bounded below, then there is a lower semicontinuous representative of J. 


	Essentially this result follows from approximating from below by convolution with smooth cut-off functions and the mean value property of supersolutions.
	The limit of these approximations is lower semicontinuous. A classic resource is <cit.> and <cit.> does the parabolic version.  See also <cit.>. 




	Suppose that L∈ C_-γ(^+×O), ψ∈ C(O), then there is a unique viscosity solution J_ψ∈ C_-γ(^+×O) to V_ψ[J]=0 given by
	
	
    J_ψ(t,x) = inf{ϕ(t,x)∈ C_-γ^1,2(^+×O); V_ψ[ϕ]≥ 0}.



	Existence of a continuous solution can be found in <cit.>.  The proof that such a solution may be approximated above by a smooth supersolution can be done by regularization, see for instance <cit.>, <cit.>, <cit.>. 




	Given L∈ C_-γ(^+×O), ψ∈ H_0^1(O) and J∈𝒳 we say that V_ψ[J]≥ 0 weakly, if J(t,x)≥ψ(x) for almost every (t,x) and 
	
    ∫_^+∫_O[-w(t,x)∂/∂ tJ(t,x)+1/2∇ w(t,x)·∇ J(t,x)+w(t,x)L(t,x)]dxdt≥ 0

	for any w∈ L_γ(^+;H_0^1(O)) with w≥ 0.

	We say that V_ψ[J]=0 weakly if  V_ψ[J]≥ 0 in a weak sense and the  inequality (<ref>)  
	 holds 
	whenever J-ψ+w≥ 0.

	We say that J∈𝒳 is the minimal weak solution if V_ψ[J]=0 weakly and for every weak solution to V_ψ[J̃]=0, J(t,x)≤J̃(t,x) almost everywhere.


Our definition of weak solution and minimal weak solution is equivalent to the definitions in <cit.> (Chapter 3, Section 2) where they have used negative ψ and J and thus consider maximal weak solutions.  Note also that they use test functions that are equivalent to v(t,x)=-J(t,x)-w(t,x), i.e. satisfy v(t,x)≤ -ψ(x).



	Suppose <ref> and ψ∈ LSC(O)∩ H_0^1(O) with ψ≤ 0.  Then there is a unique function J_ψ∈𝒳, J_ψ≤ 0, that is the minimal weak solution to V_ψ[J_ψ]=0, and there is a constant C such that 
	
    J_ψ_𝒳≤ Cψ_H_0^1.


	Furthermore, J_ψ is the value function for the optimal stopping problem with terminal reward ψ and satisfies
	
    J_ψ(t,x) = sup_τ∈ℛ^t,x{𝔼^t,x[ψ(B_τ)-∫_t^τ L(s,B_s)ds]}



	See Theorem 4.6 in Chapter 3 of <cit.>.

	For the uniform bound, we use the test function w(t,x)= -2γ t(ψ(x)-J_ψ(t,x)), which satisfies J-ψ+w≥ 0, and thus (<ref>) implies
	
    1/2∫_O|J_ψ(0,·)|^2dx+1/2∫_^+∫_O-2γ t|∇ J_ψ(t,x)|^2dxdt
    ≤    ∫_Oψ(x)J_ψ(0,x)dx + ∫_^+∫_Oγ-2γ t (J_ψ(t,x)-2ψ(x))J(t,x)dxdt
        +∫_^+∫_O-2γ t( ∇ψ(x)·∇ J_ψ(t,x)+ (ψ(x)-J_ψ(t,x))L(t,x))dxdt
    ≤    Cψ_H_0^1(O)√(∫_O|J_ψ(0,·)|^2dx+∫_^+∫_O-2γ t|∇ J_ψ(t,x)|^2dxdt).







plain

