数理解析研究所講究録 1246 巻 2002 年 50-5550
最適化問題に対する Riccati 方程式
The Riccati equation for an optimization problem
川崎 英文 (九州大学・数理)
H. Kawasaki, Kyushu University, JAPAN1Introduction
Conjugate point is aglobal concept in the calculus of variations, and it is akey factorof optimality conditions. In variational problems, the variable is not avector in
but afunction $x(t)$ . Recently, we established conjugate point theory for an elementary$x$$R^{n}$

extremal problem:$(P_{0})$

Minimize$f(x)$

x$\in R^{n}$.

, and weIn [3], we defined the Jacobi equation and (strict) conjugate points fordescribed necessary- and sufficient optimality conditions in terms of conjugate points.
Furthermore, we extended the conjugate point theory to aconstrained case in [4].
On the other hand, the Riccati equation also plays an important role in the classicalconjugate point theory. The aims of this paper are to introduce the Riccati equation to, and to discuss optimality in terms of the solution for the Riccati equation.
In Section 2, we briefly review the classical conjugate point theory. In Section 3, we
presented in [3]. In Section 4, we define the Riccati
review the conjugate points forin terms of, and we describe asufficient optimality conditions forequation for
the Riccati equation. In Section 5, we clarify the algebraic meaning of the solution for
the Riccati equation.
$(P_{0})$$(P_{0})$$(P_{0})$$(P_{0})$$(P_{0})$2The classical conjugate point theoryLet$\overline{x}$be aminimum for the simplest problem in the calculus of variations:(SP)

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

subject to $x(0)=A$ , $x(T)=B$, and theThen it satisfies the Euler equation:
Legendre condition: $P(t):=f_{i\dot{x}}(t,\overline{x}(t),x(it))\geq 0$ .
Legendre attempted to prove that asufficient condition for $F(x)$ have aweak minin additionis the strengthened Legendre condition:
imum atsee
fiuitful,
is
idea
his
goal,
to
the
get
did
not
to the Euler equation. Though Legendre[2, p. 104]. His approach was to first write the second variation$df_{\dot{x}}(t,\overline{x}(t),i-(t))/dt=f_{x}(t,\overline{x}(t),\overline{x}.(t))$$f_{\dot{\mathit{0}}e\dot{x}}(t,\overline{x}(t),\overline{x}.(t))>0$$\mathrm{x}(\mathrm{t})$$I(y):= \int_{0}^{T}\{P\dot{y}^{2}+Ry^{2}\}dt$

for$y(0)=\mathrm{y}\{\mathrm{T})=0$

51
of $F(x)$ at$\overline{x}$in the form

$I(y)= \int_{0}^{T}\{P\dot{y}^{2}+Ry^{2}+\frac{d}{dt}(wy^{2})\}dt=\int_{0}^{T}\{P\dot{y}^{2}+2y\dot{y}w+(R+\dot{w})y^{2}\}dt$,(1)

where $w(t)$ is an arbitrary piecewise smooth function. Next, he observed that thestrengthened Legendre condition would be sufficient if it were possible to find afunction$w(t)$ for which the integrand in (1) is aperfect square. However, this is not always
possible, since $w(t)$ would have to satisfy the Riccati equation$P(R+\dot{w})=w^{2}$,(2)

and although the Riccati equation may not have asolution on the whole interval $[0, T]$ .
Furthermore, by the change of variable$w=- \frac{\dot{y}}{y}P$,(3)

the Riccati equation is transformed into the Jacobi equation: $d(P\dot{y})/dt=Ry$ , which
implies that the Riccati equation has asolution $w(t)$ except zero points of anon-trivial
solution $y(t)$ of the Jacobi equation.
In general, conjugate points are defined by the Jacobi equation:$\frac{d}{dt}\{\overline{f}_{\dot{x}x}y+\overline{f}_{\dot{x}\dot{x}}\dot{y}\}=\overline{f}_{xx}y+\overline{f}_{x\dot{x}}\dot{y}$.

If there exists anon-trivial solution $y(t)$ of the Jacobi equation with $y(0)=0$ , then any
zero point $c>0$ of $y(t)$ is said to be conjugate to 0.

THEOREM 1(Jacobi) A sufficient condition for a feasible solution
be a minimumis the combined condition of the Euler equation, the strengthened Legendre condition,and that there are no points conjugate to 0on $[0, T]$ . Conversely, if is a minimum
and the strengthend Legendre condition is satisfied, then there are no points conjugate
to 0on $[0, T)$ .
$\overline{x}(t)$$\overline{x}$3The Jacobi equation for$(P_{0})$In this section, we review the conjugate point theory forpresented in [3]. According to Sylvester’s criterion, an-symmetric matrix $A=(a_{ij})$ is positive definite$(k=1, \ldots, n)$ are positive, where
if and only if its descending principal minors$(P_{0})$$n\cross n$$|A_{k}|$$A_{k}:=(a_{ij})(1\leq i, j\leq k)$.

The following lemma shows that the determinant of any square matrix is expandedwith respect to the descending principal minors.

LEMMA 1$([\mathit{3}J)$

For any$n\cross n$-mxetrix A={\^a ), its determinant is expanded as follows:(4)$|A|= \sum_{k=0}^{n-1}\sum_{\rho\in S(k+1,n)}\epsilon(\rho)a_{k+1\rho(k+1)}a_{k+2\rho(k+2)}\cdots a_{n\rho(n)}|A_{k}|$where $|A_{0}|:=1$ ,denotes the sign of , and $S(k +1,\mathrm{n})$ denotes the set of all
permutations on $\{k +1, \ldots,n\}$ satisfying that there is no $\ell>k$ such that is close
on $\{\ell+1, \ldots, n\}$ .
$\mathrm{e}(\mathrm{p})$$\rho$$\rho$$\rho$$d$

52
DEFINITION 1, ,$y_{0}$$\ldots$$([\mathit{3}J)$

For any$n\cross n$-mati $A=(a_{ij})$ , we call the recursion relation on$y_{n}$$y_{k}= \sum_{\dot{|}=0}^{k-1}\sum_{\rho\in S(\dot{\iota}+1,k)}\epsilon(\rho)a_{t+1\rho(:+1)}a_{t+2\rho(\dot{|}+2)}\ldots a_{k\rho(k)}y_{\dot{1}}$k $=1$ ,,\ldots ,n(5)

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

(6)Concerning the reason why we call the recursion relation (5) the Jacobi equation, readers
may refer to [3, p. 57].
THEOREM 2
For any
point conjugate to 1.
$([\mathit{3}J)$$n\cross n$-symmetric matrix$A$, $A>0$ if and only if there is no

THEOREM 3
A sufficient condition for an extremal to be a minimum for.
is that there is no point conju gate to 1for the Hesse matrix$([\mathit{3}J)$$\overline{x}$$(P_{0})$$f’(\overline{x})$4The Riccati equation for$(P_{0})$, and we clarify the relationshipIn this section, we define the Riccati equation for
between the Riccati equation and the Jacobi equation. As we saw in Section 2, the key
point to derive the (classical) Riccati equation was the perfect square. This idea works, too.
very well when we define the Riccati equation for
Let us first consider the case where is atridiagonal matrix.
$(P_{0})$$(P_{0})$$A$

A$=(\begin{array}{llll}a_{1} b_{1} b_{\mathrm{l}} a_{2} \ddots \ddots \ddots b_{n-1} b_{n-\mathrm{l}} a_{n}\end{array})$

Suppose that the quadratic form $x^{T}Ax$ (xperfect squares$x^{T}Ax$

for some$w_{1}$,$\in R^{n})$.

is expressed as asummation of$=$$a_{1}x_{1}^{2}+a_{2}x_{2}^{2}+\cdots+a_{\mathfrak{n}}x_{n}^{2}+2b_{1}x_{1}x_{2}+2b_{2}x_{2}x_{3}+\cdots+2b_{1*-1}x_{2*-1}x_{n}$$=$$(w_{1}x_{1}+ \frac{b_{1}}{w_{1}}x_{2})^{2}+\cdots+(w_{n-1}x_{n-1}+\frac{b_{n-1}}{w_{n-1}}x_{n})^{2}+w_{n}^{2}x_{n}^{2}$\ldots ,$w_{n}\in R/\{0\}$. Then$w_{1}^{2}=a_{1}$,$\{w_{k}\}$

(7)

$n$

has to satisfy$w_{k}^{2}=a_{k}- \frac{b_{k-1}^{2}}{w_{k-1}^{2}}$(k $=2,$\ldots n).

(8)

53
On the other hand, the Jacobi equation (5) for the tridiagonal matrix reduces to$Ilk=a_{k}y_{k-1}-b_{k-1}^{2}y_{k-2}$

Dividing (9) by$y_{k-1}$.

(9), we get$\frac{y_{k}}{y_{k-1}}=a_{k}-b_{k-1}^{2}\frac{y_{k-2}}{y_{k-1}}$

.

(10)

Comparing (10) with (8), we obtain$w_{k}^{2}= \frac{y_{k}}{y_{k-1}}$

.

(11)

Hence there is no nonzero $w_{k}\in R$ when $y_{k-1}y_{k}\leq 0$ . This fact matches the classicalresult mentioned in Section 2.
For any matrix , by dividing the Jacobi equation (5) by, we obtain the definition of the Riccati equation.
$A$$y_{k-1}$

DEFINITION 2For any$n\cross n$follows.

matrix $A=(a_{ij})$ , we define the Riccati equation as,$w_{1}^{2}$$=$$a_{11}$$w_{k}^{2}$$=$$a_{kk}+ \sum_{\ell=1}^{k-1}\sum_{\rho\in S(\ell,k)}\frac{\epsilon(\rho\rangle a_{\ell\rho(\ell)}a_{\ell+1\rho(\ell+1)}\cdots a_{k\rho\langle k)}}{w_{\ell}^{2}w_{\ell+1}^{2}\cdots w_{k-1}^{2}}$

,

$k$

$=2$

,

$\ldots$, .
$n$

The following theorem states the relationship between conjugate points and the
Riccati equation.

THEOREM 4Let be conjugate to 1. Then the Riccati eqttation has a solution,, $w_{k-1}\in R/\{0\}$ , but it hcns no solution $w_{k}\in R/\{0\}$ . Conversely,,, $w_{k-1}\in$$R/\{0\}$ satisfy the Riccati equation, andif there is no $w_{k}\in R/\{0\}$ satisfying the Riccati
equation, then is conjugate to 1.
$k$$w_{1}$$ifw_{1}$$\ldots$$\ldots$$k$

THEOREM 5A sufficient condition for an extremal to be a minimum foris that$(k=1,\ldots,n)$
the Riccati equation has non-zero real solution
for the Hesse matrix$(P_{0})$$\overline{x}$$w_{k}$$A=f’(\overline{x})$.

5Perfect squares
As we have seen in the beginning of Section 4, when is apositive definite tridiagonal
matrix, the quadratic form $x^{T}Ax$ can be expressed as asummation of perfect squares.
The aim of this section is to prove that the above observation is true for an arbitrary
positive definite matrix .
$A$

$n$

$A$

LEMMA 2Let

$A$

be an

$n\cross n$-symmetric matrix, and divide $A$ as follows.
$A=(\begin{array}{ll}\alpha a^{T}a B\end{array})$

,

(12)

where
, $a\in R^{n-1}$ , and $B$ is an $(n-1)\cross(n-1)$ -symmetric matrix. Then $A>0$
if and only if $\alpha>0$ and $B-aa^{T}/\alpha>0$ .
$\alpha\in R$

54
THEOREM 6Let A be a positive-definite matrix of order n, Then the quadratic form$x^{T}Ax$ is expressed as a summationof n perfect squares by the folloing procedure.

Step 1Divide A and x as (12) andStep 2$x^{T}=(x_{1}, y^{T})\in R\cross R^{\mathfrak{n}-1}$, respectively.

$x^{T}Ax=( \sqrt{\alpha}x_{1}+\frac{a^{T}y}{\sqrt{\alpha}})^{2}+y^{T}(B-\frac{aa^{T}}{\alpha})y$

Step 3Choose$B- \frac{aa^{T}}{\alpha}$

as

$A$

, and go to Step 1.

Theorem 6is rephrased as follows.

be a positive-definite matrix of order n. Then the quadratic
THEOREM 7Let A$x^{T}Ax$ is expressed as a summationof n perfect squares
form$=(a_{j}.\cdot)$$x^{T}Ax= \sum_{k=1}^{n}a_{kk}(k)\{x_{k}+\frac{\sum_{j=k+1}^{n}a_{kj}(k)x_{j}}{a_{kk}(k)}\}^{2}$

where $x^{T}=$$(x_{1}, \ldots,x_{n})$and$a_{ij}(k)\dot{u}$. (1)$\alpha_{j}$

(13)

,

inductively defined by$:=\alpha_{j}.$,$1\leq i$, j$\Phi.\mathrm{j}(k+1):=a_{j}.\cdot(k)-\cdot\frac{a_{k}.(k)a_{kj}(k)}{a_{kk}(k)}$$\leq n$

,

(14)

,

$k+1\leq i$, j

The following theorem provides an explicit representation of.
the algebraic meaning of$\leq n$.

$a_{\dot{|}j}(k)$(15), and it clarifies$\{w_{k}\}$be the
THEOREM 8Let $A=(\alpha_{j}.)$ be a positive-definite matrix of size , letequation.
the
Riccatibe the solution ofsequence defined by (14) and (15), and let
Then
(16)
$n$

$a_{\dot{|}j}(k)$$\{w_{k}\}$$\alpha_{j(k)=a_{j}+\sum_{\ell=1}^{k-1}\sum_{\rho\in S_{j}(\ell,k-1)}\frac{\epsilon(\rho)a_{\ell\rho(\ell)}a_{\ell+1\rho(\ell+1)}\cdots a_{k-1\rho(k-1)}a_{\rho(\dot{|})}}{w_{\ell}^{2}w_{\ell+1}^{2}\cdots w_{k-1}^{2}}}.\dot{.}.\cdot.\cdot$

denote the set of all bijections$\ell’+1$ ,, $k-$$\rho:\{\ell,\ell+1, \ldots, k-1,i\}arrow\{\ell,\ell+1, \ldots,k-1,j\}$ which satisfies thatfor any $k=1$ ,$\ldots$,$n$

and $k\leq i$ , $j\leq n$ , where$S_{j}\dot{.}(\ell, k-1)$$\rho(\{\ell’,$$1,i\})\neq\{\ell’,\ell’+1, \ldots, k-1,j\}$for any$\ell<\ell’\leq k-1$

$w_{k}^{2}=a_{kk}(k)$for any k $=1$ ,\ldots ,.

$fit\iota rffiemore$$\ldots$

,

(17)

n.

The relation (17) guarantees that one may test the positive-definiteness of A by meansof the procedure in Theorem 2or equivalently (14) and (15)55References[1] A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, 1968.
[2] I. M. GELFAND AND S. V. Fomin, Calculus of variations, Prentice Hall, 1963.
[3] H. KAWASAKI, A conjugate points theory for a nonlinear programming problem’
SIAM J. Control Optim., 40 (2001), pp. 54-63.
[4] H. KAWASAKI, Conjugate points for anonlinear programming problem with constraints, J. Nonlinear Convex Anal., 1(2000), pp. 287-293.
[5] H. KAWASAKI, The Riccati equation for nonlinear programming problems, Kyushu
University Preprint Series in Mathematics, 2001-12 (2001)