%\magnification=\magstephalf
%\input mymacros
\def\rr{{\rm I}\kern-.2em{\rm R}}
\null
\vskip 1cm
\centerline{{\bf 18 EXAMPLES OF CALCULUS OF VARIATIONS}}

\vskip 1mm
\centerline{{\bf  AND OPTIMAL CONTROL PROBLEMS}}

\vskip 5mm
\centerline{{\it H.~J.~Sussmann --- November 1, 2000}}

\vskip 1cm
\noindent{\it Here is a list of examples of calculus of variations and/or 
optimal control problems. Some are easy, others hard. Three of them
are still unsolved. Some can be solved directly by elementary
arguments, others cannot be solved unless one uses the machinery of
the calculus of variations or optimal control. Some statements may
look a little bit too technical at this point, but will become clearer
later in the course. In all the problems, when we talk about ``all
paths'' we mean ``all appropriately smooth paths.''  The precise
meaning will depend on the problem, and usually this question---of
choosing the correct space of functions or paths in which to work---is
regarded nowadays as part of the problem. On the other hand, the
founders of the subject---people like the Bernoulli brothers, Newton,
Leibniz, Euler, Lagrange, to name a few---were perfectly happy talking
about ``all paths,'' without ever being troubled by the fact that not
every function has a derivative and not every function can be
integrated.  For the purposes of this particular discussion, you can
follow our illustrious predecessors and just forget about the choice
of the space of paths.}

\bigbreak


\item{{\bf 1.}} ({\it The oldest of all calculus of variations problems; 
at least 3000 years old, for $n=2$ or $n=3$, of course.)} Of all paths
$\xi:[0,1]\mapsto\rr^n$ such that $\xi(0)=A$, $\xi(1)=B$, find the
paths or paths that minimize the integral
$$J(\xi)=\int_0^1\|\dot\xi(t)\|\,dt\,,$$
where $\|\cdot\|$ is Euclidean norm, that is, 
$\|(x_1,\ldots,x_n)\|=\sqrt{\sum_{i=1}^nx_i^2}$, and
$A$, $B$ are two given points in $\rr^n$.

\medbreak
\item{{\bf 2.}} ({\it The rope-stretching problem.)} Given the length
of a string, find the configurations that {\it maximize} the distance
between the endpoints. (NOTE: this is easily proved to be equivalent
to Problem 1.  In ancient Egypt and India the art of {\it
rope-stretching} was practiced in order to produce segments and other
geometrical figures, showing knowledge of the fact that a segment
solves the rope-stretching problem.  In Egypt, according to
Democritus, geometric constructions were carried out with the help of
specialized workers---whom Democritus describes as experts in
``composing lines,'' and calls by the Greek word ``harpenodaptai,''
which means ``rope-stretchers''---by means of pegs and cords. Their
skills were used to build altars, temples and pyramids, where it was
deemed necessary to produce certain geometric shapes that would obey
very precise specifications, such as being made of perfectly straight
segments or perfect circles. These demands often originated with the
Gods, who insisted that an altar or temple be built so as to meet very
strict requirements, failing which their wrath would be unleashed upon
the builders and their communities. Rope-stretching is a good analog
device for making long segments {\it precisely because the solution of the
rope-stretching problem is a segment}.  This is one of the oldest
examples I know of mathematics applied to engineering.)

\medbreak
\item{{\bf 3.}} ({\it A more modern version of Problem 1.)} Same question 
as in Problem 1, but $\|\cdot\|$ is now a general norm on $\rr^n$, not
necessarily Euclidean or smooth or strictly convex. (A good example to
keep in mind is the ``$\ell^1$ norm'' given by 
$\|x\|=|x_1|+\ldots+|x_n|$.)

\medbreak
\item{{\bf 4.}} ({\it The isoperimetric problem, also known as 
``Dido's'' problem, inspired by the story told by Virgil (70-19 BCE)
in the {\bf Aeneid} about the foundation of Carthage, ca. 850 BCE;
more than 2100 years old; essentially solved by 
{\bf Zenodorus}, ca. 200-140 BCE, who showed that, 
(i)~among all polygons with a given
perimeter $P$ and given number $N$ of sides, the regular polgyon has the
largest area, and (ii)~a circle had a larger area than any regular polygon
of the same perimeter.}) Of all simple closed rectifiable curves
\hbox{$\xi:[0,1]\mapsto\rr^2$} of a given length $L$, find the ones that 
maximize the enclosed area.

\medbreak
\item{{\bf 5.}} ({\it The light reflection problem, mathematically 
trivial but historically important; about 1900 years old.}) Of all
paths in the closed upper half plane $\{(x,y)\in\rr^2:y\ge 0\}$ that
go from a given point $A$ to another point $B$ and go through at least
one point in the $x$ axis, find the ones of minimum length. (NOTE:
Hero of Alexandria---believed to have been born in 10 CE and to have
died in 75 CE---pointed out in his {\it Catoptrics} that when a
light ray emitted by an object is reflected by a mirror it follows a
path from the object to the eye which is the shortest of all possible
such paths. {\it This is the first example in history of an
explanation of a physical phenomenon on the basis of a ``curve
minimization principle.''})

\medbreak
\item{{\bf 6.}} ({\it The light refraction problem, easily doable today as a
Freshman Calculus exercise, but important for people such as Leibniz
when they were first able to solve it; about 350 years old.  In his
1684 {\it Nova Methodus} paper, Leibniz wrote, referring to his
solution of the light refraction and other related problems, that ``Other 
very learned men have sought in many devious ways what someone
versed in this calculus can accomplish in these lines as by
magic. $\ldots$ This is the beginning of much more sublime Geometry,
pertaining to even the most difficult and most beautiful problems of
applied mathematics, which without our differential calculus or
something similar noone could attack with any such ease.''})
Assuming that the speed of light is equal to a constant $c_+$ when
$y>0$ and to a different constant $c_-$ when $y<0$, find the light
rays (i.~e., minimum time paths) from a given point $A$ in the open
upper half plane to another given point $B$ in the open lower half
plane.

\medbreak
\item{{\bf 7.}} ({\it The catenary; solved incorrectly by Galileo in 
the 1630s; solved correctly by Johann Bernoulli in 1691.})  Find the
shape of a chain (or rope) of uniform mass density and given length
$L$, held fixed at its endpoints, and otherwise hanging
freely. Mathematically, this becomes: given two points $A$, $B$ in the
two-dimensional plane $\rr^2$, and a length $L$ (which should be 
$\ge{\rm dist}(A,B)$),
then, among all the paths $[0,1]\ni t\mapsto\xi(t)=(x(t),y(t))$ such that
$\xi(0)=A$, $\xi(1)=B$, and $\int_0^1\sqrt{\dot x(t)^2+\dot y(t)^2}\,dt=L$,
find the one that minimizes the integral
$$
J(\xi)=\int_0^1y(t)\sqrt{\dot x(t)^2+\dot y(t)^2}dt\,.
$$
(Note: $J(\xi)$ is equal to $L$ times the ordinate of the center of mass
of the hanging chain. So the problem amounts to finding the path whose
center of mass is as low as possible.)

\medbreak
\item{{\bf 8.}} ({\it The brachistochrone; solved incorrectly by Galileo in 
1638; solved correctly by Johann Bernoulli and others in 1696-7.})  
Suppose we drop a particle at a point $A$ so that it will fall freely 
along a curve $\xi$ going from $A$ to another point $B$. For given $A$, $B$,
how should $\xi$ be chosen so that the falling time is minimized?

\item{} The above is, roughly, Johann Bernoulli's formulation of the problem. 
A standard translation into mathematics, found in most textbooks, is
as follows.  The energy $E$ is constant, and 
$E=K+P$, where $K$ is kinetic energy and $P$ is potential energy. 
Since $K={1\over 2}(\dot x^2+\dot y^2)$ (assuming the particle mass
to be equal to $1$) and $P=gy$, we have 
$$
{1\over 2}(\dot x^2+\dot y^2)+gy=E\,.
$$
If we write $A=(a,\alpha)$, $B=(b,\beta)$, and assume further that our
curve is actually given by $y=\varphi(x)$, $a\le x\le b$, we have
$$
{1\over 2}\Biggl(\Big({dx\over dt}\Big)^2+\Big({dy\over dt}\Big)^2\Biggr)+gy=E\,,
$$
so
$$
\Big({dx\over dt}\Big)^2+\Big({dy\over dt}\Big)^2=2E-2gy\,,
$$
$$
(dx)^2+(dy)^2=(2E-2gy)(dt)^2\,,
$$
$$
\Big(1+\Big({dy\over dx}\Big)^2\Big)(dx)^2=(2E-2gy)(dt)^2\,,
$$
$$
dt={\sqrt{1+\Big({dy\over dx}\Big)^2}\over\sqrt{2E-2gy}}\,dx\,,
$$
and then our problem is to minimize the integral 
$$
J(\varphi)=\int_a^b{\sqrt{1+\varphi'(x)^2}\over\sqrt{2E-2g\varphi(x)}}\,dx\,,
$$
among ``all functions'' $\varphi:[a,b]\to\rr$ such that 
$\varphi(a)=\alpha$, $\varphi(b)=\beta$, and $g\varphi(x)\le E$ for all $x$. 

\item{} If we factor out the $\sqrt{2}$ and just omit it, take $g=1$ (which is 
possible by a suitable choice of units) and relabel $E-\varphi$ as our
new $\varphi$, then the integral becomes
$$
J(\varphi)=\int_a^b{\sqrt{1+\varphi'(x)^2}\over\sqrt{\varphi(x)}}\,dx\,,
$$
and the constraint on $\varphi$ is just $\varphi(x)\ge 0$ for all $x$. 

\item{} {\it Later in the course we will discuss whether the above 
formulation is a satisfactory translation into mathematics of Johann
Bernoulli's original statement. It will be argued that it is a very
imperfect translation, and that a much better one is possible and yields 
nicer results.} 

\medbreak
\item{{\bf 9.}} ({\it The ``reflected brachistochrone.''})
Assuming that the speed of light $c(x,y)$ is equal to $\sqrt{|y|}$,
find the light rays (i.~e., minimum time paths) from a given point 
$A$ to another given point $B\in\rr^2$.



\medbreak
\item{{\bf 10.}} ({\it One-dimensional soft landing}.) For the system 
$$
\dot x=y\,,\qquad\dot y=u\,,\qquad |u|\le 1\,,
$$
given a starting position $x_-$ and velocity $y_-$, find the path of 
minimum time that ends at $x=0$, $y=0$.  

\medbreak
\item{{\bf 11.}} ({\it $n$-dimensional soft landing}.) Same as 
in Problem 10, but now $x$, $y$, $u$ are $n$-dimensional vectors, and 
the constraint on $u$ is $\|u\|\le 1$, $\|\cdot\|$ being Euclidean norm.

\medbreak
\item{{\bf 12.}} ({\it Fuller's problem; a very important problem,
famous because of the surprising nature of the solutions.}) 
For the system 
$$
\dot x=y\,,\qquad\dot y=u\,,\qquad |u|\le 1\,,
$$
given a starting position $x_-$ and velocity $y_-$, find the path 
ending at $(0,0)$ and defined on an interval $[0,T]$ for some
$T>0$ (to be found) that minimizes the integral
$\int_0^Tx(t)^2\,dt$.

\medbreak
\item{{\bf 13.}} Given $a\in\rr$, $b\in\rr$, $L>0$, find,
of all functions $\xi:[0,L]\mapsto\rr$ such that 
$\xi(0)=a$, $\xi(L)=b$, and $|\dot\xi(t)\|\le 1$ for all $t$,
the ones that minimize the integral 
$$
J(\xi)=\int_0^L\xi(t)^2\,dt\,.
$$

\medbreak
\item{{\bf 14.}} ({\it The ``Markov-Dubins problem,'' going back to 
A.~A.~Markov, 1887. Solved by L.~Dubins in 1957 for $n=2$, and by
H.~Sussmann in 1992 for $n=3$. D.~Mittenhuber later proved that the $n>3$
case reduces to the $n=3$ case.})  Of ``all paths'' $\xi$ in $\rr^n$ 
that are parametrized by arc-length (that is, $\|\dot\xi(t)\|=1$ for
all $t$), satisfy the {\it curvature bound} \ $\|\ddot\xi(t)\|\le 1$,
\ and go from a given initial point $x_-$ and initial direction $v_-$ to
a given terminal point $x_+$ and terminal direction $v_+$, find the
ones of minimum length. 

\medbreak
\item{{\bf 15.}} ({\it The ``Markov-Dubins-Reeds-Shepp problem,'' 
a variant of Problem 9, solved by J.~Reeds and L.~Shepp in 1990 for $n=2$,
and by Sussmann in 1992 for $n=3$. Mittenhuber later proved that the
$n>3$ case reduces to the $n=3$ case.})  Of ``all paths'' $\xi$ in
$\rr^n$ that satisfy $\dot\xi(t)=\varepsilon(t)v(t)$,
$\varepsilon(t)\in\{-1,1\}$, $\varepsilon(\cdot)$ measurable,
$v(\cdot)$ Lipschitz, $\|\dot v(t)\|\le 1$, that go from a given
initial point $x_-$ and initial direction $v_-$ to a given terminal
point $x_+$ and terminal direction $v_+$, find the ones of minimum
length. (NOTE: think of a ``vehicle'' that is moving
in such a way that at each time $t$ it points to some direction
$v(t)$---so $v(t)$ is a unit vector---and the motion takes place with
speed $1$, while at the same time the vehicle can turn---that is,
$v(t)$ can change---but with a bound $\|\dot v(t)\|$ on how fast this
can happen. Then the Dubins case corresponds to a vehicle that is
not allowed to back up---that is, $\varepsilon=1$---whereas the
Reed-Shepp case corresponds to allowing backups, that is 
$\varepsilon=\pm 1$.)

\medbreak
\item{{\bf 16.}} ({\it The ``Markov-Dubins problem with angular acceleration
control,'' a variant of Problem 9. Still open, although some 
partial---and rather counterintuitive---results are known.}) For the system
$$
\dot x=\cos\theta\,,\qquad\dot y=\sin\theta\,,\qquad
\dot\theta=\omega\,,\qquad\dot\omega=u\,,\qquad\|u\|\le 1\,,\eqno{(1)}
$$
of ``all paths'' $t\mapsto(x(t),y(t),\theta(t),\omega(t))\in\rr\times
\rr\times S^1\times\rr$ 
that go from a given initial condition $(x_-,y_-,\theta_-,\omega_-)$
to a given terminal condition $(x_+,y_+,\theta_+,\omega_+)$,
find the ones of minimum length. 

\medbreak
\item{{\bf 17.}} ({\it General regularity of optimal controls.
Still open, although some answers are known, and the answers that are
known are somewhat surprising, as will be explained later in the
course.})  For two smooth (i.~e., $C^\infty$) vector fields $f$ and
$g$ in $\rr^n$, and two points $A$, $B$ in $\rr^n$, let $P(f,g,A,B)$
be the following {\it minimum time problem}: find a $T\ge 0$ and a
measurable function $[0,T]\ni t\mapsto u(t)\in[-1,1]$ such that the
solution $[0,T]\ni t\mapsto\xi(t)\in\rr^n$ of the O.D.E. initial value
problem
$$
\dot\xi(t)=f(\xi(t))+u(t)g(\xi(t))\,,\quad\xi(0)=A\,,
$$
exists on $[0,T]$, is such that $\xi(T)=B$, and $T$ is as small as possible. 

\item{} Which of the following statements are true?

\itemitem{a.} Whenever $f$, $g$ are $C^\infty$ vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most finitely many points of discontinuity. 

\itemitem{b.} Whenever $f$, $g$ are real-analytic vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most finitely many points of discontinuity. 

\itemitem{c.} Whenever $f$, $g$ are real-analytic vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most finitely many points of non-analyticity. 

\itemitem{d.} Whenever $f$, $g$ are $C^\infty$ vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most countably many points of discontinuity. 

\itemitem{e.} Whenever $f$, $g$ are real-analytic vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most countably many points of discontinuity. 

\itemitem{f.} Whenever $f$, $g$ are real-analytic vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most countably many points of non-analyticity. 

\itemitem{g.} Whenever $f$, $g$ are $C^\infty$ vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most a set of measure zero of points of discontinuity. 

\itemitem{h.} Whenever $f$, $g$ are real-analytic vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most a set of measure zero of points of discontinuity. 

\itemitem{i.} Whenever $f$, $g$ are real-analytic vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ has at most a set of measure zero of points of non-analyticity. 

\itemitem{j.} Whenever $f$, $g$ are $C^\infty$ vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ is continuous on some dense open set of its interval of definition.

\itemitem{k.} Whenever $f$, $g$ are real-analytic vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ is continuous on some dense open set of its interval of definition.

\itemitem{$\ell$.} Whenever $f$, $g$ are real-analytic vector fields 
and $P(f,g,A,B)$ has a unique solution $(T,u(\cdot))$, then 
$u(\cdot)$ is real-analytic on some dense open set of its interval of 
definition.

\medbreak
\item{{\bf 18.}} ({\it General regularity of subriemannian minimizers.
Still open, although several erroneous proofs of an affirmative answer
have appeared in the literature, e.~g. one by R.~Strichartz in
J. Diff. Geometry {\bf 24}, 1983, pp.~221-263, later retracted in the
same journal, {\bf 30}, 1989, pp.~595-596.}) A {\it subriemannian metric}
is like a Riemannian metric except that the metric is only defined
(and smooth) on a smooth subbundle $E$ of the tangent bundle,
and only curves $\xi$ whose direction $\dot\xi(t)$ at each time
$t$ belongs to the corresponding space $E(\xi(t))$ are permitted.
Are all length-minimizers smooth (if parametrized by arc-length)? 

\end

