# Solution to Singular Optimal Control by Backward Differential Flow

Authors: Jinghao Zhu; Shangrui Zhao; Guohua Liu
Journal: Journal of Control Science and Engineering
 (2013)

---

## Abstract

This paper presents a backward differential flow for solving singular optimal control problems. By using Krotov equivalent transformation, the cost functional is converted to a class of global optimization problems. Some properties of the flow are given to reveal the significant relationship between the dynamic of the flow and the geometry of the feasible set. The proposed method is also used in solving a class of variational problems. Some examples are illustrated.


---

## Body

## 1. Introduction

In this paper, we are interested in solving the following optimal control problem:(1)(P):minJ(u)=∫0T‍[cTx+g(u)]dt,s.t.x˙=Ax+Bu,x(0)=x0,t∈[0,T],
where A∈Rn×n, B∈Rn×m are constant matrices, the initial state x0 is a constant vector in Rn, c∈Rn is a constant vector, and g(u) is a polynomial of degree 2l having the form
(2)g(u)=u12l+u22l+⋯+um2l+f(u1,u2,…,um),
where f(u1,u2,…,um) is a polynomial of degree less than 2l. We assume that ∇2g(u)≥0. The problem (P) is a singular optimal control problem. The admissible control function u(·), taking values in Rm, is integrable and bounded on [0,T]. The set of all admissible controls is denoted by Φ. This problem often comes up as a main objective in general optimal control theory [1, 2].With Krotov [3] equivalent transformation, the optimal control problem (P) can be converted to some auxiliary optimization problems with constraints. A class of backward differential equations [4] relying continuously on time point t∈[0,T] is introduced for solving these optimization problems.The rest of the paper is organized as follows. In Sections2 and 3, with Krotov extension method [3], we convert the optimal control problem (P) to a class of constrained global optimization problems. In Sections 4 and 5, we introduce the theory of backward differential flow [4] for global optimizations. We illustrate the solution to the problem (P) by an example in Section 6. An application of the proposed method in a kind of variational problem is included in Section 7. The last section is the conclusion of the paper.


## 2. Krotov Equivalent Extension

Letφ(t) be the solution to the following ordinary equation:
(3)φ˙(t)+ATφ(t)=c,φ(T)=0.
The cost functional J(u) of the problem (P) can be rewritten as follows:
(4)J(u)=∫0T[cTx(t)+p(u(t))]dt=∫0T[(u(t))φ˙T(t)x(t)+φT(t)Ax(t)+φT(t)Bu(t)+g(u(t))-φT(t)Bu(t)]dt=∫0T[(u(t))φ˙T(t)x(t)+φT(t)x˙(t)+g(u(t))-φT(t)Bu(t)]dt=φT(T)x(T)-φT(0)x0+∫0T[g(u(t))-φT(t)Bu(t)]dt=-φT(0)x0+∫0T[g(u(t))-φT(t)Bu(t)]dt,
noting that φ(T)=0. So we have
(5)minΦJ(u)=-φT(0)x0+minΦ∫0T[g(u(t))-φT(t)Bu(t)]dt.
It suffices for minimizing J(u) over Φ to do the following global optimization for each t∈[0,T]:
(6)minRm{g(u)-φT(t)Bu}.For eacht∈[0,T], let ht(u)=g(u)-φT(t)Bu. For given t, ht(u) is a polynomial having the same form as g(u) in (2) except for the linear part. In particular, ∇2ht(u)=∇2g(u)≥0, (∀t∈[0,T]).Remark 1.
Krotov extension [3] has been used in (5) for finding an optimal control.


## 3. Global Minimizers of a Polynomial

Letp(u) be a polynomial over Rm having the same form as g(u) or ht(u). Here we briefly introduce the main result in [5, 6] for estimating a bound of global minimizers for the polynomial p(u) over Rm. For the polynomial p(u), we have the constrained optimization with the minimum denoted by I as follows:
(7)I=min∑1≤j1,j2,…,j2l≤m∂2lp(0)∂uj1∂uj2⋯∂uj2lsj1sj2⋯sj2ls.t.s12+s22+⋯+sm2=1.
The following result gives a bound of all global minimizers for the polynomial p(u) over Rm.Theorem A (see [6]).
IfI>0, all the global minimizers of the polynomial p(u) stay inside the ball ∥u∥<a, where
(8)a=max{1,(2l)!(m+m2/2!+⋯+m2l-1/(2l-1)!)MI},M=max{|∂kp(0)∂uj1⋯∂ujk|:0≤k≤2l-1,1≤j1,j2,…,jk≤m|∂kp(0)∂uj1…∂ujk|}.If further letM>maxt∈[0,T]∥φT(t)B∥, then there is a bound a>0 such that for all t the global minimizers of ht(u) stay inside ∥u∥<a. Therefore, for t∈[0,T] the optimization problem (6) is equivalent to the following constrained optimization problem:
(9)min{ht(u):∥u∥≤a}.Remark 2.
The unconstrained global optimization (6) has been converted to a constrained one here for constructing a backward flow in next section.


## 4. Canonical Backward Differential Flow

In what follows the polynomialp(u) still stands for g(u) or ht(u) as in the previous section. We keep the assumption ∇2p(u)≥0 as in Section 1. We introduce the theory of canonical backward differential flow [2] for solving the following optimization problem
(10)min{p(u),s.t.u∈D},
where D={u∈Rm:∥u∥≤a} with the radius a being got in Section 2 such that all minimizers of p(u) over D stay in intD={u∈Rm:∥u∥<a}.Since∇2p(u)≥0(∀u∈D), we have, for ρ>0(11)∇2p(u)+ρI>0,∀u∈D.
For the pair (ρ^,u^)∈R+×D with u^≠0 satisfying the following K-T equation:
(12)∇p(u^)+ρ^u^=0,
we define the flow u^(ρ) near (ρ^,u^) by the following ordinary differential equation:
(13)du^(ρ)dρ+[∇2p(u^(ρ))+ρI]-1u^(ρ)=0,u^(ρ^)=u^.
The canonical dual function [4, 7] with respect to the flow u^(ρ) is defined as follows:
(14)pd(ρ)=p(u^(ρ))+ρ2[u^T(ρ)u^(ρ)-a2].Lemma 3 (see [4]).
For a given flow defined by (13), one has
(15)dpd(ρ)dρ=12[u^T(ρ)u^(ρ)-a2],(16)d2pd(ρ)dρ2=-(du^(ρ)dρ)T[∇2p(u^(ρ))+ρI]du^(ρ)dρ.Lemma 4 (see [4]).
Letu^(ρ) be the flow defined by (13) and pd(ρ) be the corresponding canonical dual function defined by (14), one has(i)
for everyρ>0, d2pd(ρ)/dρ2≤0;(ii)
ifρ^>0, then dpd(ρ)/dρ monotonously decreases in [ρ^,+∞);(iii)
ifρ^>0 and u^(ρ^)∈D, then pd(ρ) monotonously decreases in [ρ^,+∞).Definition 5 (see [4]).
Letu^(ρ) be the flow defined by (13). When being restricted in (0,ρ^],u^(ρ) is called the backward differential flow.


## 5. Global Optimization

In this section, we use the backward differential flow to find a global minimizer to the optimization problem (10). In what follows we assume that ∇p(0)≠0.SinceD is closed and bounded, there is a ρ*>0 such that ρ*>supD∥∇p(u)∥ and ∇2p(u)+ρ*I>0, for all u∈D. By Brown fixed-point theorem [8], we have a nonzero point u*∈intD such that
(17)∇p(u*)+ρ*u*=0,∇2p(u)+ρ*I>0,∀u∈D.
Since ∇2p(u)≥0 in Rm, ∇2p(u)+ρI>0 in Rm provided that ρ>0. It follows from the differential equation,
(18)du^(ρ)dρ+[∇2p(u^(ρ))+ρI]-1u^(ρ)=0,u^(ρ*)=u*
that a differential flow u^(ρ) corresponding to the problem (10) exists in (0,+∞). By (14), (15), we see that on the flow for every ρ∈(0,+∞)(19)∇p(u^(ρ))+ρu^(ρ)=0,∇2p(u)+ρI>0,∀u∈Rm.
Since u*∈intD, the flow u^(ρ)∈intD as ρ≥ρ* by Lemma 4. We claim that the backward flow u^(ρ)(0<ρ≤ρ*) also keeps staying inside D. If this is not true, then there is a ρ~∈(0,ρ*) such that ∥u^(ρ~)∥=a. Since p(u)+(ρ~/2)uTu is convex, by (19) we deduce that, for u∈D,
(20)p(u)≥p(u)+ρ~2[uTu-a2]≥infD{p(u)+ρ~2[uTu-a2]}=p(u^(ρ~))+ρ2[u^T(ρ~)u^(ρ~)-a2]=p(u^(ρ~)).
This contradicts the fact that the minimizer of p(u) over D will stay in intD. By (15), this implies that, for every ρ>0, u^=u^(ρ) is the unique point over D such that
(21)∇p(u^)+ρu^=0.
Consequently, by the classical ordinary differential equation theory, the backward differential flow u^(ρ) got by (18) can also be got by the following initial value problem:
(22)du^(ρ)dρ+[∇2p(u^(ρ))+ρI]-1u^(ρ)=0,u^(ρ^)=u^.
In conclusion we have reached the following result.Lemma 6.
For every positive parameterρ^, there is solely a point u^ located inside D, such that
(23)∇p(u^)+ρ^u^=0.
Further, the differential flow corresponding to the problem (10) is unique and can be got by the equation
(24)du^(ρ)dρ+[∇2p(u^(ρ))+ρI]-1u^(ρ)=0,u^(ρ^)=u^.Remark 7.
In other words, the differential flowu^(ρ) corresponding to the problem (10) does not depend on changing the initial condition.Theorem 8.
Letu^(ρ) be the backward flow corresponding to the problem (10). Then u*=limρ→0+u^(ρ) exists and u* is a global minimizer of p(u) over D.Proof.
By Lemma3, the backward flow u^(ρ) is well defined in (0,+∞) and u^(ρ)∈D, for all ρ>0. Since {u^(ρ):ρ∈(0,+∞)} is bounded, there is a point u*∈D and a decreasing sequence of positives ρj(j=1,2,…) such that limj→∞ρj=0 and limj→∞u^(ρj)=u*. By Lemma 4, noting that pd(ρ) is increasing monotonously as the positive variable ρ goes to zero monotonously, we have
(25)limρ→0+pd(ρ)=limj→∞pd(ρj)=limj→∞[p(u^(ρj))+ρj2(u^(ρj)Tu^(ρj)-a2)]=p(u*).
On the other hand, along the flow u^(ρ), for each ρ∈(0,+∞) we have
(26)∇{p(u^(ρ))+ρ2[u^T(ρ)u^(ρ)-a2]}=∇p(u^(ρ))+ρu^(ρ)=0,
and for all u∈D(27)∇2{p(u)+ρ2[uTu-a2]}=∇2p(u)+ρI>0,
noting that ∇2p(u)≥0 on D. Thus, for all u∈D,
(28)p(u)≥p(u)+ρ2[uTu-a2]≥infD{p(u)+ρ2[uTu-a2]}=p(u^(ρ))+ρ2[u^T(ρ)u^(ρ)-a2]=pd(ρ).
Let ρ→0+, and we have, by (28), (25), for all u∈D,
(29)p(u)≥limρ→0+pd(ρ)=p(u*).
We conclude that u* is a global minimizer of p(u) over the ball D.


## 6. Solution to Singular Optimal Control

To solve the singular optimal control problem (P), by Lemma6 and Theorem 8, we present the following algorithm.Algorithm 9.
(i) Chooseρ^>0.
(ii) Fort∈[0,T], solve ∇p(u^)-BTφ(t)+ρ^u^=0.
(iii) Solve(30)du^(ρ)dρ+[∇2p(u^(ρ))+ρI]-1u^(ρ)=0,u^(ρ^)=u^.
(iv) Fort∈[0,T], ut*=u^(0+). Go back to (ii).Sinceφ(t) is continuous and the solution of the canonical backward differential equation relies on the parameter t∈[0,T] for the initial value continuously, we see that ut* will be dependent of the parameter t∈[0,T] continuously. It follows from Krotov extension method that the optimal control of (P) is u^(t)∶=ut*,t∈[0,T].Example 10.
Given the polynomial onR2:
(31)g(u)=u14+u24+3u12+3u22+6u1u2+2u1+2u2+3,
consider the following singular optimal control problem:
(32)minJ(u)=∫01‍[cTx+g(u)]dt,s.t.x˙=Ax+Bu,x(0)=0,t∈[0,1],
where
(33)c=(11)T,A=(1011),B=(11-12).
Fort∈[0,1], we have ht(u)=g(u)+(1-te1-t)u1+(-2+(3-t)e1-t)u2. Noting that ∇2g(u)≥0, we have ∇2ht(u)≥0. By Theorem A, for ht(u), we have the global optimization problem
(34)min{ht(u),s.t.∥u∥≤64}.
By Algorithm 9, for simplicity, choose ρ^=1 and solve the following algebraic differential equation
(35)ρ^=1,du1dρ=-(12u22+6+ρ)u1-6u2(12u12+6+ρ)(12u22+6+ρ)-36,du2dρ=--6u1+(12u12+6+ρ)u2(12u12+6+ρ)(12u22+6+ρ)-36,u1(ρ^)=u^1,u2(ρ^)=u^2,4u^13+6u^1+6u^2+ρ^u^1=-3+te1-t,4u^23+6u^2+6u^1+ρ^u^2=(t-3)e1-t,
to get the corresponding canonical backward differential flow u(ρ)=(u1(ρ)u2(ρ))T,ρ∈(0,1]. For each t define ut*=u(0+)=(u1(0+)u2(0+))T. We get an optimal control for the problem (32): u^(t)=ut*. Table 1 contains some data of approximate value on the optimal control.Table 1
Some data on the optimal control for Example10.
t
u
~
(
t
)
0
(0.4816–1.0559)
0.1
(0.4697–0.9972)
0.2
(0.4516–0.9387)
0.3
(0.4284–0.8801)
0.4
(0.3996–0.8207)
0.5
(0.3646–0.7595)
0.6
(0.3219–0.6949)
0.7
(0.2686–0.6240)
0.8
(0.1985–0.5409)
0.9
(0.0927–0.4274)
0.95
(0.0040–0.3376)
1.0
(−0.1652–0.1652)


## 7. Application in a Variational Problem

In this section, we use backward differential flows developed in Sections4 and 5 to deal with the following variational problem:
(36)(P):minu(·)∈C([0,1],R1)J(u)=∫01[u4(t)+∫0t‍u(s)ds]dt.
This kind of problem appears very often in many complex systems from nonconvex analysis of phase transitions to discrete optimization in network design and communication [9, 10].The functionalJ(u) of the variational problem (P) can be rewritten as follows:
(37)J(u)=∫01‍[u4+∫0t‍u(s)ds]dt=∫01‍[u4(t)+(1-t)u(t)]dt.
For t∈[0,1], let ht(u)=u4+(1-t)u. Noting that ∇2ht(u)=12u2≥0, with Algorithm 9, for simplicity, choose ρ^=1. To get the corresponding canonical backward differential flow ut(ρ),ρ∈(0,1], we have the following differential equation:
(38)dudρ=-u(12u2+ρ),4u3(1)+u(1)=t-1.
We have
(39)ut(0+)=[(t-1)4]1/3.
For each t∈[0,1] defining ut*=ut(0+), we get the solution to the variational problem (36):
(40)u^(t)=ut*=[(t-1)4]1/3.


## 8. Concluding Remarks

In this paper, a new approach to solve singular optimal control is presented. As the first step of this approach, we convert the original optimal control problem to a ball constrained optimization problem. Then a differential equation is established by the K-T equation with the ball constrained nonlinear programming. The main contribution is the development of constructive backward differential flow which can be effectively used for finding a global minimizer. A kind of variational problems can also be solved by this method.



---

*Source: 678679-2013-04-09.xml*