next up previous contents index
Next: 2.7 Notes and references Up: 2.6 Second-order conditions Previous: 2.6.1 Legendre's necessary condition   Contents   Index

2.6.2 Sufficient condition for a weak minimum

We are now interested in obtaining a second-order sufficient condition for proving optimality of a given test curve $ y$ . Looking at the expansion (2.56) and recalling our earlier discussions, we know that we want to have $ \left.\delta^2 J\right\vert _{y}(\eta)>0$ for all admissible perturbations, which means having a strict inequality in (2.61). In addition, we need some uniformity to be able to dominate the $ o(\alpha^2)$ term. Since we saw that the $ P$ -dependent term inside the integral in (2.61) is the dominant term in the second variation, it is natural to conjecture--as Legendre did--that having $ P(x)>0$ for all $ x\in [a,b]$ should be sufficient for the second variation to be positive definite. Legendre tried to prove this implication using the following clever approach. For every differentiable function $ w=w(x)$ we have

$\displaystyle 0=\left.w\eta^2\right\vert _{a}^b=\int_a^b \frac d{dx}(w\eta^2)dx=\int_a^b(w'\eta^2+2w\eta\eta')dx

where the first equality follows from the constraint $ \eta(a)=\eta(b)=0$ . This lets us rewrite the second variation as

$\displaystyle \int_a^b\!\left(P(x)(\eta'(x))^2+Q(x)(\eta(x))^2\right)dx=

Now, the idea is to find a function $ w$ that makes the integrand on the right-hand side into a perfect square. Clearly, such a $ w$ needs to satisfy

$\displaystyle P(Q+w')=w^2.$ (2.61)

This is a quadratic differential equation, of Riccati type, for the unknown function $ w$ .

Let us suppose that we found a function $ w$ satisfying (2.64). Then our second variation can be written as

$\displaystyle \int_a^b \bigg(\sqrt{ P(x)} \eta'(x)+\frac {w(x)}{\sqrt{P(x)}}\eta(x)\bigg)^2dx= \int_a^b P(x)\bigg(\eta'(x)+\frac {w(x)}{P(x)}\eta(x)\bigg)^2dx$ (2.62)

(the division by $ P$ is permissible since we are operating under the assumption that $ P>0$ ). It is obvious that the right-hand side of (2.65) is nonnegative, but we claim that it is actually positive for every admissible perturbation $ \eta $ that is not identically 0. Indeed, if the integral is 0, then $ \eta'+\frac {w}{P}\eta\equiv
0$ . We also know that $ \eta(a)=0$ . But there is only one solution $ \eta:[a,b]\to \mathbb{R}$ of the first-order differential equation $ \eta'+\frac {w}{P}\eta=0$ with the zero initial condition, and this solution is $ \eta\equiv 0$ . So, it seems that we have $ \left.\delta^2 J\right\vert _{y}(\eta)>0$ for all $ \eta\not\equiv 0$ . At this point we challenge the reader to see a gap in the above argument.

The problem with the foregoing reasoning is that the Riccati differential equation (2.64) may have a finite escape time, i.e., the solution $ w$ may not exist on the whole interval $ [a,b]$ . For example, if $ P\equiv 1$ and $ Q\equiv -1$ then (2.64) becomes $ w'=w^2+1$ . Its solution $ w(x)=\tan(x-c)$ , where the constant $ c$ depends on the choice of the initial condition, blows up when $ x-c$ is an odd integer multiple of $ \pi/2$ . This means that $ w$ will not exist on all of $ [a,b]$ for any choice of $ w(a)$ if $ b-a\ge\pi$ .

We see that a sufficient condition for optimality should involve, in addition to an inequality like $ L_{y'y'}> 0$ holding pointwise along the curve, some ``global" considerations applied to the entire curve. In fact, this becomes intuitively clear if we observe that a concatenation of optimal curves is not necessarily optimal. For example, consider the two great-circle arcs on a sphere shown in Figure 2.13. Each arc minimizes the distance between its endpoints, but this statement is no longer true for their concatenation--even when compared with nearby curves. At the same time, the concatenated arc would still satisfy any pointwise condition fulfilled by the two pieces.

Figure: Concatenation of shortest-distance curves on a sphere is not shortest-distance

So, we need to ensure the existence of a solution for the differential equation (2.64) on the whole interval $ [a,b]$ . This issue, which escaped Legendre's attention, was pointed out by Lagrange in 1797. However, it was only in 1837, after 50 years had passed since Legendre's investigation, that Jacobi closed the gap by providing a missing ingredient which we now describe. The first step is to reduce the quadratic first-order differential equation (2.64) to another differential equation, linear but of second order, by making the substitution

$\displaystyle w(x)=-\frac{Pv'(x)}{v(x)}$ (2.63)

where $ v$ is a new (unknown) function, twice differentiable and not equal to 0 anywhere. Rewriting (2.64) in terms of $ v$ , we obtain

$\displaystyle P\bigg(Q-\frac{\frac

Multiplying both sides of this equation by $ v$ (which is nonzero), dividing by $ P$ (which is positive), and canceling terms, we can bring it to the form

$\displaystyle Qv=\frac d{dx}(Pv').$ (2.64)

This is the so-called accessory, or Jacobi, equation. We will be done if we can find a solution $ v$ of the accessory equation (2.67) that does not vanish anywhere on $ [a,b]$ , because then we can obtain a desired solution $ w$ to the original equation (2.64) via the formula (2.66).

Since (2.67) is a second-order differential equation, the initial data at $ x=a$ needed to uniquely specify a solution consists of $ v(a)$ and $ v'(a)$ . In addition, note that if $ v$ is a solution of (2.67) then $ \lambda v$ is also a solution for every constant $ \lambda$ . By adjusting $ \lambda$ appropriately, we can thus assume with no loss of generality that $ v'(a)=1$ (since we are not interested in $ v$ being identically 0). Among such solutions, let us consider the one that starts at 0, i.e., set $ v(a)=0$ . A point $ c>a$ is said to be conjugate to $ a$ if this solution $ v$ hits 0 again at $ c$ , i.e., $ v(c)=v(a)=0$ (see Figure 2.14). It is clear that conjugate points are completely determined by $ P$ and $ Q$ , which in turn depend, through (2.59), only on the test curve $ y$ and the Lagrangian $ L$ in the original variational problem.

Figure: A conjugate point

Conjugate points have a number of interesting properties and interpretations, and their theory is outside the scope of this book. We do mention the following interesting fact, which involves a concept that we will see again later when proving the maximum principle. If we consider two neighboring extremals (solutions of the Euler-Lagrange equation) starting from the same point at $ x=a$ , and if $ c$ is a point conjugate to $ a$ , then at $ x=c$ the distance between these two extremals becomes small (an infinitesimal of higher order) relative to the distance between the two extremals as well as between their derivatives over $ [a,b]$ . As their distance over $ [a,b]$ approaches 0, the two extremals actually intersect at a point whose $ x$ -coordinate approaches $ c$ . The reason behind this phenomenon is that the Jacobi equation is, approximately, the differential equation satisfied by the difference between two neighboring extremals; the next exercise makes this statement precise.

Suppose that $y$\ and $y+v$\ are two neighboring extremals of t...
...Q} and $\Vert\cdot\Vert$\ is a suitable norm (specify which one).

We see from (2.68) that $ v$ , which is the difference between the two extremals, satisfies the Jacobi equation (2.67) modulo terms of higher order. A linear differential equation that describes, within terms of higher order, the propagation of the difference between two nearby solutions of a given differential equation is called the variational equation (corresponding to the given differential equation). In this sense, the Jacobi equation is the variational equation for the Euler-Lagrange equation. This property can be shown to imply the claims we made before the exercise. Intuitively speaking, a conjugate point is where different neighboring extremals starting from the same point meet again (approximately). If we revisit the example of shortest-distance curves on a sphere, we see that conjugate points correspond to diametrically opposite points: all extremals (which are great-circle arcs) with a given initial point intersect after completing half a circle. We will encounter the concept of a variational equation again in Section 4.2.4.

Now, suppose that the interval $ [a,b]$ contains no points conjugate to $ a$ . Let us see how this may help us in our task of finding a solution $ v$ of the Jacobi equation (2.67) that does not equal 0 anywhere on $ [a,b]$ . The absence of conjugate points means, by definition, that the solution with the initial data $ v(a)=0$ and $ v'(a)=1$ never returns to 0 on $ [a,b]$ . This is not yet a desired solution because we cannot have $ v(a)=0$ . What we can do, however, is make $ v(a)$ very small but positive. Using the property of continuity with respect to initial conditions for solutions of differential equations, it is possible to show that such a solution will remain positive everywhere on $ [a,b]$ .

In view of our earlier discussion, we conclude that the second variation $ \left.\delta^2 J\right\vert _{y}$ is positive definite (on the space of admissible perturbations) if $ P(x)>0$ for all $ x\in [a,b]$ and there are no points conjugate to $ a$ on $ [a,b]$ . We remark in passing that the absence of points conjugate to $ a$ on $ [a,b]$ is also a necessary condition for $ \left.\delta^2 J\right\vert _{y}$ to be positive definite, and if $ \left.\delta^2 J\right\vert _{y}$ is positive semidefinite then no interior point of $ [a,b]$ can be conjugate to $ a$ . We are now ready to state the following second-order sufficient condition for optimality: An extremal $ y(\cdot)$ is a strict minimum if $ L_{y'y'}(x,y(x),y'(x))>0$ for all $ x\in [a,b]$ and the interval $ [a,b]$ contains no points conjugate to $ a$ .

Note that we do not yet have a proof of this result. Referring to the second-order expansion (2.56), we know that under the conditions just listed $ \left.\delta J\right\vert _{y}(\eta)=0$ (since $ y$ is an extremal) and $ \left.\delta^2 J\right\vert _{y}(\eta)$ given by (2.58) is positive, but we still need to show that $ \left.\delta^2 J\right\vert _{y}(\eta)\alpha^2$ dominates the higher-order term $ o(\alpha^2)$ which has the properties established in Exercise 2.12. Since $ P(x)=\frac 12 L_{y'y'}(x,y(x),y'(x))>0$ on $ [a,b]$ , we can pick a small enough $ \delta>0$ such that $ P(x)>\delta$ for all $ x\in [a,b]$ . Consider the integral

$\displaystyle \int_a^b \left((P(x)-\delta)(\eta'(x))^2+Q(x)(\eta(x))^2\right)dx.$ (2.65)

Reducing $ \delta$ further towards 0 if necessary, we can ensure that no points conjugate to $ a$ on $ [a,b]$ are introduced as we pass from $ P$ to $ P-\delta$ (thanks to continuity of solutions of the accessory equation with respect to parameter variations). This guarantees that the functional (2.69) is still positive definite, hence

$\displaystyle \int_a^b \left(P(x)(\eta'(x))^2+Q(x)(\eta(x))^2\right)dx>\delta\int_a^b(\eta'(x))^2dx$ (2.66)

for all admissible perturbations (not identically equal to 0).

In light of our earlier derivation of Legendre's condition, we know that the term depending on $ (\eta')^2$ is in some sense the dominant term in (2.60), and the inequality (2.70) indicates that we are in good shape. Formally, we can handle the other, $ \eta^2$ -dependent term in (2.60) as follows. Use the Cauchy-Schwarz inequality with respect to the $ \mathcal L_2$ norm2.4 to write

$\displaystyle \eta^2(x)=\left(\int_a^x 1\cdot\eta'(z) dz\right)^2

From this, we have

$\displaystyle \int_a^b \eta^2(x)dx\le\int_a^b(x-a)dx\int_a^b(\eta'(z))^2dz= \frac{(b-a)^2}2\int_a^b(\eta'(x))^2dx.$ (2.67)

Now, Exercise 2.12 tells us that the term $ o(\alpha^2)$ in (2.56) takes the form (2.60) where for $ \alpha$ close enough to 0 both $ \vert\bar P\vert$ and $ \vert\bar Q{(b-a)^2}/2\vert$ are smaller than $ \delta/2$ for all $ x\in [a,b]$ and all $ \eta $ with $ \Vert\eta\Vert _1=1$ . Combined with (2.58), (2.70), and (2.71) this implies $ J(y+\alpha\eta)>J(y)$ for these values of $ \alpha$ (except of course $ \alpha=0$ ), proving that $ y$ is a (strict) weak minimum.

The above sufficient condition is not as constructive and practical as the first-order and second-order necessary conditions, because to apply it one needs to study conjugate points. The simpler necessary conditions can be exploited first, to see if they help narrow down candidates for an optimal solution. It should be observed, though, that the existence of conjugate points can be ruled out if the interval $ [a,b]$ is taken to be sufficiently small.

% latex2html id marker 8605Justify the term \lq\lq principle of \e... automatically its minima on sufficiently
small time intervals.

As for the multiple-degrees-of-freedom setting, let us make the simplifying assumption that $ L_{yy'}$ is a symmetric matrix (i.e., $ {L}_{{y_i}{y_j'}}={L}_{{y_j}{y_i'}}$ for all $ i,j\in\{1,\dots,n\}$ ). Then it is not difficult to show, following steps similar to those that led us to (2.58), that the second variation $ \left.\delta^2 J\right\vert _{y}$ is given by the formula

$\displaystyle \left.\delta^2 J\right\vert _{y}(\eta)=\int_a^b\left((\eta')^T(x)P(x)\eta'(x)+

where $ P(x)$ and $ Q(x)$ are symmetric matrices still defined by (2.59). In place of $ w$ introduced at the beginning of this subsection we need to consider a symmetric matrix $ W$ , and a suitable modification of our earlier square completion argument yields the Riccati matrix differential equation

$\displaystyle Q+W'=WP^{-1}W

(note that $ W'$ denotes the derivative of $ W$ , not the transpose). This quadratic differential equation is reduced to the second-order linear matrix differential equation $ QV=\frac d{dx}(PV')$ by the substitution $ W=-PV'V^{-1}$ , where $ V$ is a matrix. Conjugate points are defined in terms of $ V$ becoming singular. Generalizing the previous results by following this route is straightforward. Riccati matrix differential equations and their solutions play a central role in the linear quadratic regulator problem, which we will study in detail in Chapter 6.

next up previous contents index
Next: 2.7 Notes and references Up: 2.6 Second-order conditions Previous: 2.6.1 Legendre's necessary condition   Contents   Index
Daniel 2010-12-20