From: "David Ziskind" Subject: Re: Average over a line integral Date: 2 Apr 1999 01:30:03 -0600 Newsgroups: sci.math.research Keywords: Choosing a path to maximize average value William G. Macready wrote in article <7dj1ra$rm9$1@sloth.swcp.com> regarding the problem of maximizing the ratio of two functionals (average value of f along path). Specifically, the problem is to determine the R1->R1 function y which relatively maximizes the functional E in the unconstrained endpoint sense, where E is defined by: E(z) =def Int[f(xt,zt)*((x't)^2+(z't)^2))^(1/2) dt] / Int[((x't)^2+(z't)^2))^(1/2) dt] -Int indicates: integral from 0 to 1. -z is a dummy variable, and represents an R1->R1 function. z is used in place of y to avoid confusion with the maximizing element. -x is a given R1->R1 function. f is a given R2->R1 function. -y is an "unknown", to be determined by the maximization requirement. -Both y(0) and y(1) are unconstrained (and should be allowed to vary so as to fulfill the maximization requirement). We can obtain a necessary condition for the maximization requirement by following the usual Euler-Lagrange strategy. In this case, because of the unconstrained endpoints, the problem is translated into a related problem of maximizing another functional (say "e") with the relation E(z) = e(z, z(0), z(1)). The original problem is then addressed by maximizing e over the appropriate set of triples (z, a, b), with z in R1->R1, a in R1, and b in R1. In setting up the functional e, the dependency on z is "direct", and the dependency on a (and b) is "indirect", i.e., a (and b) enter through terms such as z(a,b,t). However, the distinction between "direct" versus "indirect" does not change the strategy or mechanics of computing stationary (aka critical) values. Thus, in summary, the program is: - compute the variational derivative w/r to z and set it equal to zero, - compute the ordinary derivative w/r to a and set it equal to zero, - compute the ordinary derivative w/r to b and set it equal to zero. It can be shown via the calculus that each of these three derivatives must be zero when (y, a, b) is a maximizing triple. Finally, as the functional to be maximized is the ratio of two integrals, rather than a single integral is in the classic situation, it will be found that this leads to an integro-differential equation as the necessary condition (versus the classic Euler-Lagrange ODE), and also, that the necessary condition can be efficiently stated using a Lagrange multiplier. To formulate the necessary condition, we introduce the following intermediates: (Kf)(g,h) =def f(x(t),g)*[(x't)^2+h^2]^(1/2) -K has built-in, or concealed dependency on x(t), and x'(t). When one encounters K below the occurrence of x(t) and x'(t) is always the same, and thus for brevity, these arguments are not shown explicitly. -Kf has functional dependency on f. The definition of K shows f as an argument because we will also have need to write expressions such as (Ku)(g,h), where u is another function entirely different from f. -The evaluated Kf is a function mapping R2->R1. That is, g, and h are ordinary numbers (R1 elements). (The symbols g and h are used here to represent numbers rather than in the more traditional appointment as symbols for functions.) u(p,q) =def 1 for all p, q. That is, u is the unit function. Note that (Ku)(p,q) is actually just [(x't)^2+q^2]^(1/2). Thus, the derivative of (Ku)(p,q) w/r to p is zero. L(y) =def Int[(Kf)(yt,y't) dt] / Int[(Ku)(yt,y't) dt] L is a functional mapping (R1->R1) into R1. Q =def Kf - L(y)*Ku -Note that Q is a mapping of the same type as Kf; ie, an R2->R1 map. -Q has functional dependency on y (through L) which for brevity is not shown explicitly. P1Q represents the partial derivative of Q w/r to the first argument, ie P1Q(g,h) = (d/dg)(Q(g,h)). (Again, g, h are used here to represent ordinary numbers.) P2Q is the partial derivative of Q w/r to the second argument. We can now give the NECESSARY CONDITION. NC(y) iff(def) a) (P1Q)(yt,y't) = (d/dt)[(P2Q)(yt,y't)] for all 0<=t<=1 b) (P2Q)(y0,y'0) = 0 c) (P2Q)(y1,y'1) = 0 It is worth noting that P1Q, P2Q have the concealed functional dependency on y, so this system is more complicated then it appears on the surface. Note that in "a" the differentiation w/r to t sees t dependency in both the arguments yt, y't and also within the expression P2Q itself. Writing this out, we have in part: (P2Q)(yt,y't) = (P2(Kf))(yt,y't) - etc = (d/dh){(Kf)(g,h)}(g=yt,h=y't) - etc = (d/dh){f(xt,g)*[(x't)^2+h^2]^(1/2)}(g=yt,h=y't) - etc = f(xt,g)*[(x't)^2+h^2]^(-1/2)*h}(g=yt,h=y't) - etc = f(xt,yt)*[(x't)^2+(y't)^2]^(-1/2)*y't - etc CONCLUSION We have the following result: If y relatively maximizes E in the unconstrained endpoint sense, then NC(y) holds true. The problem of finding the maximizing element however is only begun. We first have to solve the complicated integro-differential system given by NC(y). In most cases, this will be quite difficult, and series methods will have to employed. A further difficulty is that such solutions may or may not be relative maxima. It is a characteristic of the stationary value strategy that such values may be (relative) maxima, minima, or "other", and the literature of the calculus of variations includes various tests to distinguish between the three situations. This seems to be a complicated subject and I can't really offer any firm information -- my impression is that inflection points and saddle points will occur as in vector transformations but do not know if there are other situations as well. Let us finish by thinking about how the system NC(y) might be solved. I would suggest the following approach: 1) Expand y in a (generalized) Fourier series. In other words, set y equal to the inverse Fourier transform of some infinite-vector c. 2) Left-operate on "a" by the (forward) Fourier series transform. 3) The result is that "a" is transformed into an (infinite-vector into infinite-vector) transformation. 4) "b" and "c" give two additional relations involving the infinite-vector c; Fourier series expansion of y is assumed as before. 5) Choose the order of accuracy desired and truncate the Fourier series expansion to the first n terms. 6) Retain the first n-2 equations from the infinity produced by "2". 7) Append the two additional equations supplied by "4". 8) The result is a system of n equations in n unknowns (truncated c vector), and can be solved in various ways, e.g., Newton-Raphson iteration. 9) With the values of truncated c vector known explicitly, evaluate (inverse Fourier transform onto truncated c) and obtain the approximate y. Sufficiency tests are discussed in: -Korn and Korn, "Mathematical Handbook for Scientists and Engineers", 2nd Edition, McGraw-Hill, 1967, ISBN 0070353700; -Bronshtein and Semendyayev, "Handbook of Mathematics", Van Nostrand Reinhold, New York, 1985, ISBN 0-442-21171-6. David Ziskind ziskind@ntplx.net ============================================================================== From: "David Ziskind" Subject: Re: Average over a line integral Date: 8 Apr 1999 00:00:06 -0500 Newsgroups: sci.math.research This is a follow-up to my prior post dated Friday, April 02, 1999 2:30 AM, which had identifiers: David Ziskind , and <01be7ccf$caea9bc0$LocalHost@default> In the problem discussed in that post, there is a difficulty in the problem formulation that was overlooked -- as stated, the problem has a trivial least upper bound and typically there is no maximum. To determine a lub, one would simply determine the (xt,yt) giving greatest f(xt,yt) (an interior maximum is assumed) and spend as much time there is possible. Thus, we would construct a path with a very high frequency sinusoid which repeatedly bracketed the highest mountain top with many small North-South excursions (and minimal West-to-East travel if x't=1). Such an extremely long path within a very small region would dominate the average to as great a degree as desired. This trivial result is not what we are after. The deduction and suggested series calculation in the prior post leads to a result which is strongly controlled by the discarding of the high-frequency terms in the finite calculation. Possibly, we would obtain results which coincide with intuitive notions of following the highest ridge but it seems difficult to put this on a rigorous footing. The original problem seems to express a fairly simple idea -- travel from start line to finish line, keeping as high as possible, and do not spend a lot of time wandering back-and-forth across the ridge line. Accordingly, I think the problem statement can be revived by redefining E in the following way: E(z) =def Int[f(xt,zt)*((x't)^2+(z't)^2)^(1/2) dt] / Int[{1+b*k(x't,x''t,z't,z''t)}*((x't)^2+(z't)^2)^(1/2) dt] This is similar to before, with the new factor of 1+b*k(...) in the denominator which introduces a penalty for non-zero path curvature. k(...) here is the absolute measure of curvature for a path in the plane and is given by the traditional formula |(x't*z''t-z't*x''t)/((x't)^2+(z't)^2)^(3/2)|. The greater the curvature, the greater is the penalty. For nearly straight segments, the penalty is nearly zero and the weight is nearly one. b is a parameter determining how strongly the penalty is felt. The analysis, calculation, and results for this new E are very similar to those in the prior post. The main difference is that the Euler-Lagrange system now incorporates third order derivatives. Referring to the prior post, we make the following changes. Two new quantities k and w are introduced. (There is no relationship between k and the forthcoming K, they are two entirely different objects). k(p,q,r,s) =def |(p*s-r*q)/(p^2+r^2)^(3/2)| w(p,q,r,s) =def 1+b*k(p,q,r,s) We now also have two unit functions: u(p,q) =def 1 for all p,q v(p,q,r,s) =def 1 for all p,q,r,s The remaining intermediates parallel those in the prior post: (Kfw)(g,h,i) =def f(xt,g)*w(x't,x''t,h,i)*[(x't)^2+h^2]^(1/2) g,h,i are ordinary numbers (reals). f, w are used in this line as dummy symbols and are substitutable -- thus, e.g., w is not restricted to 1+b*k. L(y) =def Int[(Kfv)(yt,y't,y''t) dt] / Int[(Kuw)(yt,y't,y''t) dt] Q =def Kfv - L(y)*Kuw To express the Euler-Lagrange system compactly, it is convenient to define a new quantity J: J(t) =def (P2Q)(yt,y't,y''t) - (d/dt)[(P3Q)(yt,y't,y''t)] Note that J(t) has t dependency in two ways: a) through the arguments yt, y't, and y''t; and b) through Q which contains concealed dependency on xt, x't, and x''t. The necessary condition is now given by: NC(y) iff(def) a) (P1Q)(yt,y't,y''t) = (d/dt)(J(t)) for all 0<=t<=1 b) J(0) = 0 c) J(1) = 0 The condition NC(y) is obtained when the maximum is computed over an appropriate set U, say, a set of (Y,g,h) triples. (The preceding u is entirely different from U.) A suggested definition for "(Y,g,h) is in U" is: Y is in R3->R1 and g,h are in R1 and (there exist c,d such that) (for all a,b) ( Y(a,b,0)=a and Y(a,b,1)=b and (P3Y)(a,b,0)=c and (P3Y)(a,b,1)=d) . The problem is now a mix of unconstrained and constrained end-point conditions. The y in NC(y) is given by y(t)=Y(a*,b*,t) with a*, b* indicating the maximizing end-points. In the prior post, the exemplary expansion of P2Q is specific to the earlier form and does not hold for the new definition. The nine step suggested program for solving NC(y) carries over unchanged. ADDITIONAL ITEMS: (1) In the prior post, the "result" given following "CONCLUSION" is subject to the hypothesis that the three mentioned derivatives of the functional "e" do in fact exist. This qualification continues in the new formulation. (2) In paragraph five of the prior post, "is in" should be "as in". David Ziskind ziskind@ntplx.net