数理解析研究所講究録
1187 巻 2001 年 58-65

58

Conjugate points for a nonlinear programming problem 1
Hidefumi KAWASAKI
Graduate School of Math., Kyushu Univ.
Nonlinear Analysis and Convex Analysis,
Organizer: Prof. W. TakahashiAug. 29, 2000,

Conjugate points” is a global concept in calculus of variation, and plays an importantrole in discussing optimality. Though it has been a theme of differential geometry, mathematical programming approach has been recently developed with several extensions of
the conjugate points theory to optimal control problems and variational problems withbutstate constraints. In these extremal problems, the variable is not a vector in$x(t)$
a function. So a simple and natural question arises. Is it possible to establish aconjugate points theory for a minimization problem: minimize $f(x)$ on $x\in R^{n}$ ? In[3], the author positively answered this question. He introduced ”the Jacobi equation”
and ”conjugate points” for it, and describe optimality conditions in terms of”conjugate
points”. In this paper, we extend it to a constrained nonlinear programming.
”$x$$R^{n}$

1. Jacobi’s conjugate points theory
In this section, we review the classical conjugate points theory for the simplest problem
in calculus of variations :$(SP)$

Minimize$\int_{0}^{T}f(t, x(t),\dot{X}(t))dt$

subject to$x(\mathrm{O})=A,$$x(T)=B$ .

If is a weak minimum for $(SP)$ , then it satisfies the Euler equation. Legendre attempted
and the Legendre condition
satisfies theto prove its inverse, that is, he expected that if a feasible solution, thenEuler equation and the strengthened Legendre condition:
would be a weak minimum. However, his conjecture was false. Jacobi solved thisbe a feasible solution forproblem by introducing ”conjugate points” in 1837. Let$(SP)$ , then conjugate points are defined via the Jacobi equation:$df_{x}(t,\overline{X}(t),\overline{x}(t))/dt=$$\overline{x}$$f_{\dot{x}x}(t,\overline{X}(t),\overline{x}(t))\geq 0$$f_{x}(t,\overline{x}(t),\overline{x}(t))$$\overline{x}(t)$$f_{xx}(t,\overline{X}(t),\overline{x}(t))>0$$\overline{x}(t)$$\overline{x}(t)$$\frac{d}{dt}\{\overline{f}_{xx}(t)y(t)+\overline{f}_{xx}(t)\dot{y}(t)\}=\overline{f}_{xx}(t)y(t)+\overline{f}_{xx}(t)\dot{y}(t)$(1).

, etc. A point $c\in(0, T]$ is said to be conjugate to$t=0$ if there exists a non-trivial solution $y(t)$ of the Jacobi equation (1) on $[0, c]$ and$y(\mathrm{O})=y(c)=0$ . Then Jacobi proved the following result:

where$\overline{f}_{\dot{x}x}(t):=f_{x\dot{x}}(t,\overline{X}(t),\overline{x}(t))$

THEOREM 1 (Jacobi) If
is a weak minimum for the simplest problem $(SP)$ andit satisfies the strengthened Legendre condition, then there is no point conjugate to $t=0$
on $[0, T)$ . Conversely, if
satisfies the Euler equation and the strengthened Legendre
condition, and if there is no point conjugate to $t=0$ on $[0, T]$ , thenis a weak$\overline{x}(t)$$\overline{x}(t)$$\overline{x}(t)$$m\iota ni\ovalbox{\tt\small REJECT} mum$.

1Supported in part by Grant-in-Aid for Scientific Research No. 11440033 from the Ministry of Education, Science, Sports, and Culture of Japan.

59
Recently, ”conjugate points” has been extended to complex extremal problems suchas optimal control problems and variational problems with state constraints, see e.g.
Kawasaki-Zeidan [5], Loewen-Zheng [7], Warga [9], Zeidan [10], and Zeidan-Zezza [11] [12] [13].
The present paper is outside of this trend. In this, we first quote the conjugate
points theory [3] for an unconstrained nonlinear programming problem $(P)$ :$\mathrm{p}_{\mathfrak{c}\backslash }\mathrm{p}\mathrm{e}\mathrm{r}$Minimize$(P)$$f(x)$

on$x\in R^{n}$,: $R^{n}arrow R$ is assumed to be twice continuously differentiable. It seems towhere
the author that one reason why researchers have not paid much attention to conjugate
points for $(P)$ lies in the f.ollowing elementary results on it:$f$

THEOREM 2 If is a minimum for $(P)f$ then it satisfies
andConversely, if satisfies
and, then it is a minimum forstand for non-negative defin. $ite$ and positive definite, respectively.
$an,d’$$f’(\overline{x})=0$$\overline{x}$$\overline{x}$$,,\geq$

”

)

$>$

$f’(\overline{x})=0$

,
where

$f”(\overline{x})\geq 0$$f”(\overline{X})>0$$(P)\rangle$”

Theorem 2 seems to assert that there is no room for ”conjugate points” to play a role in$(P)$ . However, an interesting connection between Jacobi’s condition and the theory ofquadratic forms was discussed in Gelfand and Fomin [1, p.125]. We quote it in the next
section. Furthermore, the author [2] recently found a stimulating example that strongly
indicates possibility to establish a conjugate points theory for $(P)$ , see Example 1 below.
Example 1 ([2]) Let us first consider the shortest path problem on the unit sphere. The problem is finding a shortest path on joining two points $A=(1,0,0)$ andin, where $0<T<2\pi$ is given. When $T>\pi$ , the equatorial arc, say$AB$ , in Fig. 1 is not a weak minimum. Indeed, take another great circle arc (the broken
curve in Fig. 1) joining and $C=(-1,0,0)$ , say $AC$ , and join $AC$ and the equatorialarc $CB$ . Then it has the same length with the equatorial arc $AB$ . However, we get ashorter curve by taking a short cut around $C$ .
$S$$R^{3}$$S$$B=(\cos\tau_{\mathrm{s}},\mathrm{i}\mathrm{n}T, 0)$$A$

Figure 1
is conjugate to . Next, let us
According to the classical conjugate point theory,
approximate the shortest path problem by an extremal problem in a finite dimensional
space as follows:
$A$

$C$

1: Take a finite number of equally located longitudes
and $B\in\ell_{n+1}$ , see Fig. 2.
assume that, on each for $k=1,2,$
sayone
point,.
2: Choose
3: Minimize the length of the polygonal curve joining $A,$$\ell_{0},$$\ell_{1},$$\ldots,$$\ell_{n+}1$$A\in\ell_{0}$$X_{k}$$p_{k}$$\ldots n$$X_{1},$$\ldots,$$X_{n},$$B$.

, where we

60

Figure 2

Figure 3

Then the above observation on the classical shortest path problem can be also applied
to this extremal problem in. In fact, by taking a short cut around $C$ in Fig. 3, we
obtain a shorter polygonal curve. Hence can be regarded as a conjugate point in thefinitedimensional analogue.
$R^{n}$$C$

2. Connection between Jacobi’s condition and Quadratic FormIn this section, we quote from [1, p.127] an interesting observation on a connection
between Jacobi’s condition and the theory of quadratic forms in. According to theclassical conjugate point theory, the quadratic functional$R^{n}$$\int_{0}^{T}\{P\dot{y}^{2}+Ry^{2}\}dt$,(2)

where $P(t)>0$ and $R(t)\in R$ , is positive for all non-trivial $y(t)$ such that $y(\mathrm{O})=y(T)=$
if and only if $[0, T]$ contains no point conjugate to , where the corresponding Jacobi
equation is
$0$

$0$

$\frac{d}{dt}\{P\dot{y}\}=Ry$,see [1, p.lll]. By introducing the points $0=t_{0}<t_{1}<\cdots<t_{n}<t_{n+1}=T$, we
get $n+1$ -equal parts of length $\triangle t:=T/(n+1)$ . Then the quadratic functional (2) isapproximated by the quadratic form:$\sum_{k=0}^{n}\{P_{k}(\frac{y_{k+1}-y_{k}}{\triangle t})2+Rkyk\}2\triangle t$,

where $P_{k}:=P(t_{k}),$ $R_{k}:=R(t_{k}),$ $y_{k}:=y(t_{k})$ , and $y_{0}=y_{n+1}=0$ . By putting$R_{k}\triangle t+(P_{k-1}+P_{k})/\triangle t,$ $b_{k}:=-P_{k-1}/\triangle t,$ $y=(y_{1}, \ldots , y_{n})$, and$A_{n}$

$:=$

,

(3)

$a_{k}$

$:=$

(4)

61
quadratic form (3) is expressed as. So, let us now discuss. According to Sylvester’s criterion,ofis positive definite if and only if its de$(k=1,\ldots,n)$scending principal minors
are positive. On the other hand, there isa recurrence formula for tribunal matrix (4)$y^{T}A_{\mathrm{t}},y$$\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}_{\mathrm{V}}\mathrm{c}\mathrm{x}\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}11\mathrm{e}\mathrm{s}\mathrm{S}$$A_{n}$$A_{[\iota}$$|A_{k}|,$$|A_{k}|=a_{k}|A_{k-1}|-b^{2}k-1|A_{k_{-}2}|$

By making the change of variables $Y_{0}:=0$ ,$Y_{1}:=\triangle t$$Y_{k+1}:= \frac{(\triangle t)^{k.1}+.|A_{k}|}{P_{1}\cdot P_{k}}$

.

(5)

, and

, $k=1,$$\ldots,$$n$,recursion relation (5) reduces to$\frac{P_{k}\frac{Y_{i+1}-Y_{k}}{\triangle t}-P_{k1^{\frac{Y_{k}-Y_{k-1}}{\triangle t}}}-}{\triangle t}=R_{k}Y_{k}$.

(6)

in (6), we get the Jacobi equation $d(P\dot{Y})/dt=RY$ . Therefore expanTending(5)
sion
can be regarded as the Jacobi equation.
$\triangle tarrow \mathrm{O}$

3. Conjugate Points for (P)In this section, we define the Jacobi equation and conjugate points for $(P)$ , anddescribe sufficient optimality conditions in terms of conjugate points.
First, let us discuss positive-definiteness of symmetric matrices. According to Sylvester’s
criterion, an-symmetric matrix $A=(a_{ij})$ is positive-definite if and only if its descending principal minors $|A_{k}|(k=1, \ldots,n)$ are positive, where$n\cross n$$A_{k}:=$ .
The following lemma shows that the determinant of any square matrix is expanded w.r.t.
the descending principal minors:
LEMMA 1 ([3]) For any $n\mathrm{X}n- matr?\dot{x}A=(a_{ij})$ , its determinant is expanded as follows:(7)$|A|= \sum_{=k0}^{n-1}\sum_{\beta}\epsilon(\rho)ak+1\rho(k+1)a_{k2}(k+2)\ldots a_{n\rho(}+\rho n)|A_{k}|$where $|A_{0}|:=1,$
denotes the sign of , and the summation is taken over all permutations on $\{k+1, \ldots, n\}$ satisfying that there is no $p>k$ such that is closed on$\epsilon(\rho)$$\rho$$\rho$$\rho$$\{\ell+1, \ldots, n\}$.

When is tridiagonal, expansion (7) reduces to (5). So we obtain our definition of
the Jacobi equation and conjugate points for (P):$A$

62
DEFINITION 1$/\mathrm{t}_{0},$$\ldots,$$([,U\mathit{3}J)$

For any$n\cross n$-matrtr $A=(a_{ij})$ , we call th, recvrsion relation on$e$$y,\iota$$/ \mathrm{t}\mathrm{A}\cdot=\sum_{0}^{-}\mathrm{A}\cdot 1i=\sum_{\rho}\in(\rho)ai+1\rho(i+1)ai+2\rho(i+2)\ldots ak\rho(k)^{\mathrm{t}_{i}}J$,$k=1,$$\ldots,$

(8)

$n$

the Jacobi equation for A. We say that is conjugate to 1 if the solutionof theJacobi equation with $y_{0}>0$ changes the sign from positive to non-positive at . Namely,$k$$\{y_{i}\}$$k$$y_{0}>0,$ $y_{1}>0,$$\ldots,$$y_{k-1}>0$ ,and$y_{k}\leq 0$

For any $(n, n)$ -symmetric matrix $A,$
THEOREM 3
only is there is no point conjugate to 1.
$([\mathit{3}J)$(9).

is positive-definite if and$A$

THEOREM 4 ([3]) A sufficient condition for an extremal to be a minimum for $(P)$there is no point conjugate to 1.
is that, concerning the Hesse matrix$\overline{x}$$f”(\overline{x})\rangle$

REMARK 1 It is easy to give a necessary optimality condition for $(P)$ in ternw of conare
jugate points, see [3]. However, since the descending principal minors
sufficiency
thethe situation is slightly different fromnot enough to characterize$A\geq 0\Rightarrow|A_{k}|\geq 0(1\leq k\leq n)$ is true, its inverse
implication
thethoughcase. Namely,
is not true in general. In order to check $A\geq 0$ , we have to test the sign of all principal
minors.
$|A_{1}|,$$\ldots,$$|A_{n}|$$A\geq 0_{\rangle}$

4. Example
Example 2 ([3]) This example is same with Example 1. Here we compute conjugate
points for it. By means of the spherical coordinates, any point on the k-th longitude. Hence the minimization
is expressed as $X_{k}=(\sin\theta(t_{k})\cos t_{k}, \sin\theta(t_{k})\sin tk,$
$X_{n+1}=$
problem of the length of the polygonal arc joining $n+2$ points
is formulated as follows:$p_{k}$$\cos\theta(t_{k}))$$\mathrm{A}=X_{0},$$X_{1},$$\ldots,$$B$$(P_{1})$Minimizethat corresponds to the equatorial arc
where $\theta_{0}=\theta_{n+1}=\pi/2$ . The variable. Then the Hesse matrix of at isis$\theta\in R^{n}$$\overline{\theta}(t)\equiv\pi/2$$\overline{\theta}:=(\pi/2, \ldots, \pi/2)$$\overline{\theta}$

$f$

(10)

$f”( \overline{\theta})=\frac{1}{\sqrt{2(1-c)}}$where $c:=\cos\triangle t$ . Since$k \{=\frac{\sin(k+1)\triangle t}{\sin\triangle t}$,

63
the principle minor of size
we conclude that$k$of (10) is positive if $(k+1)\triangle t<\pi$ . Since $\triangle t=T/(n+1)$ ,(a) when $T<\pi$ , there is no point conjugate to 1,(b) when $T\geq\pi$ , the first number$k_{\mathrm{S}}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\mathrm{f}\mathrm{y}\mathrm{i}\mathrm{n}\mathrm{g}^{\frac{k+1}{n+1}}\geq\pi/T$

is conjugate to 1,

which matches the classical result.

5. Constrained caseIn this section, we deal with a nonlinear programming problem with equality constraints:
Minimizesubject to$(P_{2})$$f(x)$$h(x):=(h_{1}(t), \ldots, hm(x))^{T}=(0, \ldots , 0)^{T}$,$x\in R^{n}$

Before going further, we remark that all the results in this section can be easily extended to the case where there are equality and inequality constraints under the strict
complimentarity assumption.
$(j\in$. In the following, we assume that
Now, let be a feasible solution for$J)$ are linearly independent. Then there exists
andsuch that$(P_{2})$$\overline{x}$$h_{j}’(\overline{x}),$$L’(\overline{x})=0$$\lambda\in R^{m}$if$\xi^{T}L^{J\prime}(\overline{X})\xi\geq 0$$h’(\overline{X})\xi=0$

(11)

,

where $L(x):=f(x)+\lambda^{T}h(X)$ . Conversely, if there exists A
and
if $h’(\overline{x})\xi=0(\xi\neq 0)$ ,$\in R^{m}$such that$L’(\overline{x})=0$(12)$\xi^{T}L’’(\overline{x})\xi>0$.
is a minimum, see Fiacco andcan be divided as $h’(\overline{x})=(B, N)$ , where
has full rank,-matrix
Since$B$ is an $m\cross m$-nonsingular matrix and $N$ is an $m\cross(n-m)$ -matrix. Similarly, we divide
is equivalent to $y=-B^{-1}Nz$ , so
as $\xi=(y, z)\in R^{m}\cross R^{n-m}$ . Thenthat$\xi^{\tau_{L’}\prime}(\overline{x})\xi=z^{T}(-N\tau B-T, I)L’’(\overline{X})z$
(13)

then

$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{C}\mathrm{k}$$\overline{x}$$m\cross n$$h’(\overline{x})$$h’(\overline{x})$$h’(\overline{x})\xi=0$$\xi\in R^{n}$Hence the following matrix is the key to describe optimality conditions.
(14)$K:=(-N^{T}B^{-\tau}, I)L’’(\overline{x})$is
THEOREM 5 A sufficient condition for a feasible solution be a minimum for$K$$L’(\overline{x})=0and_{J}$concerning
such thatthat there exists
defined by (14), there
is no point conjugate 1.
$(P_{2})$$\overline{x}$$\lambda\in R^{m}$

Example 3 In Example 2, we computed conjugate points for a finite-dimensional analogue to the classical shortest path problem on the unit sphere . Here we present
another approach. It is treating the problem as a constrained problem:$S$, $n+1$ , let
be the ring defined by $\{(\cos\frac{kT}{n+1}, y, z)\in S\}$ .
1. For $k=1,$, on each
for $k=1,2,$.
2: Choose one point, say$A=(1,0,0),$ofthepolygonal curve joining
3: Minimize the length$\ldots$$R_{k}$$X_{k}$$R_{k}$$\ldots n$$X_{1},$$(\cos T, \sin\tau, 0)$.

$\ldots,$$x_{n},$

$B=$

64

Figure 4
Then this finite-dimensional analogue is formulated as follows:$\min$$f(y_{1}, \ldots, yn’ 1z, \ldots, zn)$$:= \sum_{k=0}\sqrt{(y_{k+1}-y_{k})2+(Z_{k}+1-z_{k})2+(\cos(k+1)\triangle t-\cos k\triangle t)2}n$$\mathrm{s}.\mathrm{t}$.

$(y_{0}, z_{0})=(0,0)$,$(y_{n++1}1, z_{n})=(\sin T, 0)$$h_{k}(y_{1}, \ldots , y_{n}, z_{1}, \ldots , z_{n}):=y_{k}^{2}+z_{k}^{2}-\sin k2\triangle t=0$,

$k=1,$$\ldots,$$n$,

where $\triangle t:=T/(n+1)$ . Since the equatorial arc corresponds to$(\overline{y},\overline{z}):=(\overline{y}_{1}, \ldots,\overline{y}_{n’ 1,.,n}\overline{Z}..\overline{z})=(\sin\triangle t, \ldots, \sin n\triangle t, \mathrm{o}, \ldots, 0)$

it can be easily seen thatsin$2\triangle t$.

$\sin n\triangle t000.\cdot$$h’(\overline{y},\overline{z})=2(\sin\triangle t$
$..$

.

(15)

$000..\cdot \text{ノ}\backslash$Hence we may choose as $B$ and $N$ in (13)

$B=2$

,

$N=$

,

respectively. Furthermore, we get $L(y, z)=f(y, z)- \sin\triangle t\sum_{k}^{n}=1(y_{k}^{2}+z_{k}^{2}-\sin^{2}k\triangle t)$ .
Hence$(-N^{T}B^{-T}, I)=L_{zz}= \frac{1}{\sin\frac{\triangle t}{2}}$65where $c:=\cos\triangle t$ , which is same with (10) up to constant. Therefore we get the sameconclusion with Example 2.

References[1] I. M. Gelfand and S. V. Fomin, Calculus of variations, Prentice Hall, 1963.
[2] H. Kawasaki, Conjugate points for a minimization problem in a finite dimensional
space, Kyushu University Preprint Series in Mathematics, No. 23 (1999), pp. 1-12.
[3] H. Kawasaki, A conjugate points for a minimization problem in a finite dimensional
space, revised.

[4] 川崎英文, 「極値問題の大域的性質 : 共役点」, 第 11 回 RAMP シンポジウム論文集,
85-96 (1999, Oct.19).

[5] H. Kawasaki and V. Zeidan, Conjugate points for variational problems with equality
and inequality state constraints, to appear in SIAM J. Control Optim.
[6] S. Koga and H. Kawasaki, Legendre-type optimality conditions for a variational
problem with inequality state constraints, Math. Programming, 84 (1999), pp. 421-

434.
[7] P. D. Loewen and H. Zheng, Generalized conjugate points for optimal control problems, Nonlinear Anal., 22 (1994), pp. 771-791.

[8] G. Strang, Linear Algebra and its Applications, Academic Press, New York, 1976.
[9] J. Warga, A second-order Lagrangian condition for restricted control problems, J.
Optim. Theory Appl., 24 (1978), pp. 475-483.
[10] V. Zeidan, The Riccati equation for optimal control problems with mixed statecontrol constraints: necessity and sufficiency, SIAM J. Control and Optim., 32(1994), pp. 1297-1321.
[11] V. Zeidan and P. Zezza, The conjugate point condition for smooth control sets, J.
Math. Anal. Appl., 132 (1988), pp. 572-589.
[12] V. Zeidan and P. Zezza, Coupled points in the calculus of variations and applications
to periodic problems, Trans. Amer. Math. Soc., 315 (1989), pp. 323335.

[13] V. Zeidan and P. Zezza, Coupled points in optimal control theory, IEEE Trans.
Automat. Control, 36 (1991), pp. 1276-1281.

kawasaki@math.kyushu-u.ac.jp