The paper raises an optimal impulsive control problem with trajectories of bounded variation described by a nonsmooth measure differential equation. The addressed singular problem of dynamic optimization can be equivalently transformed to an ordinary terminally constrained optimal control problem of a specific structure. For the transformed problem, we present a new form of nonlocal necessary optimality condition. The condition, named the nonsmooth feedback maximum principle, operates with feedback inputs and performs the property of potential control improvement, while standing within standard objects of the nonsmooth maximum principle. A counter-positive version of the nonsmooth feedback maximum principle performs a conceptual iterative algorithm for optimal control, which can be used for numeric implementation of the optimal impulsive control problem. Since numeric analysis of the transformed model requires its discretization, a major portion of the paper is paid to a discrete-time counterpart of the transformed problem. For this class of optimization problems, a discrete-time version of a nonlocal necessary optimality condition is derived. Based on this optimality condition, an iterative numeric algorithm is developed.
The original object of our study is an optimal impulsive control problem (P ) for a measure-driven dynamical system of the form:
Minimize the linear form ⟨c; x(t1)⟩ subject to dx = f (x) dt + g(x) (dt);
x(t0 ) = x0; t ∈ [t0; t1]; | |([t0; t1])≤ M: (1) (2) (3) Here, ⟨·; ·⟩ denotes the scalar product in Rn. As the input data we are given reals t0; t1 ∈ R, t0 < t1,vectors c; x0 ∈ Rn and functions f; g : Rn → Rn. The part of control input is played by a signed scalar-valued Borel measure on [t0; t1], and | | denotes its total variation; condition (3), where M > 0 is given, expresses the constraint on the total action of controller during the considered time period. We accept a technical convention that the trajectories x : [t0; t1] → Rn of the measure differential equation (2) are right-continuous functions; by x(t ) we denote the left one-sided limit of a function x at a point t.
For simplicity, we deal with the linear cost functional. Problems with cost functions of classes C2 and C1 can be somehow reduced to the addressed linear case [Dykhta, 2015].
For theoretical motivation and practical applications as well as ground foundations of the impulsive control theory (e.g. an adequate concept of solution to the measure differential equation (2), (3)) one can review [Arutyunov et al., 2010, Bressan et al., 1994, Motta et al., 1995, Miller et al., 2013] and the bibliography therein. 2
Transformation to Ordinary Optimal Control Problem and Feedback Necessary Optimality Condition for the Transformed Problem Our standing hypotheses (H) are as follows: the functions f; g are locally Lipschitz continuous. Note that the vector fields f; g are not supposed to be continuously differentiable.
As is known from impulsive control theory [Miller et al., 2013, Rishel, 1965, Warga, 1965], problem (P ) can be equivalently transformed to an ordinary control problem with absolutely continuous states and bounded measurable controls. This is done by a discontinuous time reparameterization [Miller et al., 2013]. The reparameterization leads to a regular nonsmooth optimal control problem with the simplest scalar terminal constraint of equality type. This problem, called the reduced problem, has a specific structure presented below (we keep the same notations as above).
Given a finite interval T = [0; T ] and a real yT > 0, consider the following optimal control problem (RP ) (c, x0, f and g are the same as in the previous section): ( x˙ ) y˙
Minimize I( ) , ⟨c; x(T )⟩ subject to , z˙ = F (z) , A collection , (z; v) , (x; y; v) is called a control process of system (4), where controls are measurable functions v : T → [−1; 1], and state trajectories are absolutely continuous functions z , (x; y) : T → Rn × R+ such that z satisfies differential equation (4) almost everywhere (a.e.) with respect to (w.r.t.) the Lebesgue measure on T together with a certain control v. A process satisfying conditions (4)–(6) is said to be admissible.
Let ¯ = (z¯; v¯) denote an admissible reference process, whose optimality is of our interest.
In the first part of the paper, we present nonlocal necessary optimality condition for problem (RP ). This condition extends the result [Dykhta, 2015, Dykhta, 2016, Dykhta, 2014, Dykhta, 2014 (2)] (obtained for smooth free-endpoint problems), called the “feedback minimum principle”, to the addressed particular class of nonsmooth problems with terminal constraints. Below, we will operate with feedback controls of a specific “extremal” structure, that can improve non-optimal extremal open-loop controls, while employing only the formalism of the nonsmooth maximum principle [Dem’yanov et al., 1985, Clarke, 2013, Clarke et al., 1998]. 2.1
Introduce necessary constructions and recall basic facts related to the formalism of nonsmooth maximum principle for problem (RP ).
The Pontryagin function (the non-maximized Hamiltonian) is written as
H(x; ; ; v) = (1 − |v|)H0(x; ; ) + vH1(x; ); H0(x; ; ) , ⟨ ; f (x)⟩ + ;
H1(x; ) , ⟨ ; g(x)⟩ (notice that H is independent of y).
The adjoint differential inclusion takes the form:
(T ) = −c; where @xH stands for the partial (w.r.t. x) Clarke generalized differential of H [Clarke et al., 1998, Clarke, 2013] (@xH is independent of ). Denote by Ψ(¯) the set of all solutions to adjoint differential inclusion (7) corresponding to ¯, i.e., absolutely continuous functions : T → Rn with (T ) = −c. The “variable” = const is dual of y: since is not defined by a transversality condition, it can be regarded as a free parameter, which will play an important role in defining auxiliary feedback controls with the property of potential improvement of local extrema.
The maximized Hamiltonian takes the form
max H = max {H0; |H1|}; v2[ 1;1] and the maximizer is the following multifunction (x; ) → [−1; 1]: Following [Dykhta, 2015, Dykhta, 2016, Dykhta, 2014, Dykhta, 2014 (2)], a potential improvement of a reference process ¯ — neglecting the terminal constraint — can be provided by feedback controls v being selections of the extremal multivalued map (8) contracted to an adjoint trajectory ( ; ) with ∈ Ψ(¯) and ∈ R, i.e. v(t; x) ∈ V (x; (t)).
Deep roots of the feedback optimality conditions ground in the technique of modified Lagrangians majorating the increment of the cost function (in the state-linear case, the technique produces an exact increment formula). These majorants can be defined by weakly monotone (w.r.t. the system’s dynamics) functions of the Lyapunov type [Clarke et al., 1998]. Due to the principle of extremal aiming, such weakly monotone functions produce feedback controls that potentially “improve” extremal open-loop controls for free-endpoint problems. 2.3
A feedback control of system (4) is an arbitrary function v : T × Rn × R+ → [−1; 1]. Since feedbacks are generically discontinuous w.r.t. z, the closed-looped system (4) is also typically discontinuous [Filippov, 1988, Krasovskij et al., 1988, Matrosov et al., 1980]. We operate with two notions of solution to a feedback-controlled system: (C) Carath´eodory feedback solution [Clarke et al., 1998] being an absolutely continuous function z = (x; y) turning (4) into identity and satisfying a.e. on T the mixed constraint v(t) = v(t; z(t)), and (KS) Krasovskii-Subbotin generalized sampling solutions [Clarke et al., 1998, Krasovskij et al., 1988, Subbotin, 2003].
By a control synthesis of system (4) we mean an arbitrary everywhere defined single-valued mapping w :
Rn+1 7→ [−1; 1], i.e. a family of control functions vz, parameterized by state z ∈ Rn+1. Note that any feedback
control defines a control synthesis by setting vz(t) , v(t; z) for a.e. t ∈ T . For system (4), closed-looped by a
synthesis w, we employ the notion of model predictive (MP) feedback solution, which differs from both C and
KS
Given a feedback control v, let Z(v) denote the set of solutions of all three types. 2.4
Let v be a selection of (8). Then an arbitrary solution z = (x; y) ∈ Z(v) does not satisfy the terminal constraint y(T ) = yT .
First successful attempts to extend feedback optimality conditions to smooth problems with rightpoint constraints can be found in [Dykhta, 2017]. In our case, a specific structure of problem (RP ) enables take the terminal condition into account directly, based on an obvious description of the controllability set of trajectory component y to the point (T; yT ). This can be done by using — instead of (8) — the following “corrected” multifunction:
Vˇ (t; z; ) = {0}; y ≤ t − T + yT ;
Sign H1(x; ); y ≥ yT ; V (x; ); otherwise.
Let V ( ), ∈ R, denote the -parametric set of feedbacks, which are single-valued selections of (9), contracted to an adjoint state ∈ Ψ(¯): v(t; z) ∈ Vˇ (t; z; (t)).
It is easy to check that any solution z = (x; y) ∈ Z(v) to the reduced system, closed-looped by v, does satisfy the terminal condition. 2.5
Now we are ready to perform the announced nonlocal necessary optimality condition for problem (RP ).
Introduce the following accessory reduced problem (ARP ):
Minimize ⟨c; x(T )⟩ subject to the inclusion z , (x; y) ∈ ∪ ∪ ∪
Z(v): 2R 2Ψ(¯) v2V ( ) Lemma. Let ¯ = (z¯; v¯) satisfy the nonsmooth maximum principle. Then, z¯ is admissible for (ARP ), i.e., there exist ¯ ∈ R, ¯ ∈ Ψ(¯) and v ∈ V¯( ¯) such that z¯ = z, and z ∈ Z(v) is a Carath´eodory solution of (4).
The announced nonlocal necessary optimality condition for problem (RP ) is performed by the following Theorem 1 (nonsmooth feedback maximum principle, NFMP). Assume that ¯ = (z¯; v¯) solves problem (RP ). Then z¯ = (x¯; y¯) is a minimizer for (ARP ).
For proofs and further details we refer to [Sorokin et al., 2017, Staritsyn et al., 2016]. 3
A practical application of NFMP for numerical implementation of optimal control problems implies step-by-step integration of ordinary dynamic system (4) and adjoint differential inclusion (7); another problem consists in reasonable choice of the feedback descent control — a proper selection of (9). After that, the original closedlooped system should be again numerically integrated, and the outcome will be a quasi-admissible control process, which potentially improve the reference one in the sense of cost. These operations require a certain coordination, which is, by now, not clear for us.
In this section, we propose an alternative approach for numerical solution of control problem (RP ) based on
discretization. For the discrete version of (RP ), we obtain an analog of NFMP
For the ease of presentation, we will keep the same notation as in previous sections.
Consider the simplest explicit Euler discretization of problem (RP ) (while there is no restriction to employ more complicated difference schemes).
Let now t perform a discrete time scale, i.e., t = 0; 1; :::; N , where N is a number of time moments, and the time lag is h = T =N . The discrete version (DP ) of the reduced problem (RP ) takes the form:
Minimize I( ) , ⟨c; x(N )⟩ subject to ( x(t + 1) ) y(t + 1) , z(t + 1) = x(t) + h[(1 − |v(t)|)f (x(t))+ g(x(t))v(t)]
[ ] y(t) + h 1 − |v(t)|
; (9) (10) (11) (12)
Again, a collection , (z; v) = (x; y; v) is said to be a control process of system (10), where v = {v(t); t = 0; N − 1} is a control and z = {z(t); t = 0; N }, z(t) = (x(t); y(t)), is a trajectory; a process satisfying conditions (10)–(12) is called admissible. A reference process is denoted by ¯, as above. Similarly to the continuous case (see section 2.4), feedback controls – selections of (14) – produce closed-looped solutions to (10), which do not satisfy the rightpoint constraint in (11). To force the solutions meet the terminal conditions, similarly to (9), we define the corrected extremal multifunction for discrete-time problem (DP ):
{−A; A}; H0d > H1d ; Sign H1d; H0d < H1d ; [A; 1]; H0d = H1d > 0; [−1; −A]; H0d = −H1d > 0; [−1; −A] ∪ [A; 1]; otherwise.
A = A(yt) = yt − yT + 1; h
B = B(t; yt) = yt − yT + N − t;
h (13) (14) (15)
Given a reference process ¯ = (z¯ = (x¯; y¯); v¯), let us take a related reference adjoint state ∈ Ψ(¯) being a solution to the adjoint inclusion (13), and denote by Vd( ) the set of single-valued selections v of multifunction (15), contracted to the chosen function : v(t; zt) ∈ Vˇ d(t; zt; t+1). By z(v) = (x(v); y(v)) we denote a solution of system (10), closed-looped by the feedback v.
Theorem 2 (discrete nonsmooth feedback maximum principle — DNFMP). Assume that ¯ = (z¯; v¯) solves problem (DP ). Then, for all z = (x; y)(v) such that v ∈ V ( ), ∈ Ψd(¯) and ∈ R it holds
⟨c; x¯(N )⟩ ≤ ⟨c; x(N )⟩:
The presented necessary condition for global optimality extends and strengthens the maximum principle for discrete control problems of class (DP ): First, Theorem 2 does not require any convexity assumptions on the system’s velocity set (in this situation, the discrete maximum principle is not applicable). Second, if we are in conditions when the Maximum Principle is actually applicable (say, g(x) = 0 ∀x ∈ Rn), DNFMP discards nonextremal control processes and, as certain academic example show, can improve also nonoptimal extrema. 3.3
A counter-positive form of DNFMP turns into the following conceptual iterative algorithm for optimal control:
Step 0 (initialization). Given an initial (not necessarily admissible!) control v¯ = {v¯(t); t = 0; : : : ; N − 1}, find the corresponding trajectory of (10): z¯ = z(v¯) = (x¯; y¯) : x¯ = {x¯(t); t = 0; : : : ; N }; y¯ = {y¯(t); t = 0; : : : ; N }: Set ¯ = (z¯; v¯), Irec := I(¯) = ⟨c; x¯(N )⟩.
Step 1. Calculate an adjoint trajectory ¯ = (¯) ∈ Ψd(¯) by solving (13) along ¯.
Step 2. Choose a parameter ∈ R.
Step 3. Calculation of the feedback control v and respective trajectory z = (x ; y ): For t = 0; : : : ; N − 1, calculate: • the feedback at time t: v(t; z (t)) ∈ Vˇ d(t; x (t); y (t); ¯t+1), • the state z (t + 1) = (x (t + 1); y (t + 1)) as a solution of (10) under v (t) = v(t; z (t)).
Step 4. If I( ) = ⟨c; x (N )⟩ ≤ ⟨c; x¯(N )⟩ = Irec, then set v¯ := v = {v (t) = v(t; z (t)); t = 0; : : : ; N − 1}, z¯ := z , ¯ := (z¯; v¯), Irec := I(¯) and go to Step 1. In other case we go to Step 2 or Step 1.
The process can be stopped as soon as
|I( ) − Irec| < " (" > 0 is a parameter of the algorithm):
1) A very specific form of the multifunction (15) is due to the constraint y(N ) = yT , which is required to be satisfied strictly. If the constraint is met with accuracy to within h (i.e. |y(N ) − yT | ≤ h), (15) can be replaced by the map 2) The set of potentially discarding feedback controls and trajectories of (DP ) is extended due to the presence of a free parameter ∈ R (see Step 2). On the other hand, for practical implementation, the range of should be a priori estimated. In fact, an extremal process ¯ may admit multiple adjoint trajectories ( ¯; ¯) (see Theorem 2). Given a multivalued map O(t) : {0; 1; : : : ; N −1} → Rn, which contains the trajectory tube of system (10) started at (t; x) = (0; x0), the valued of is ranged in the interval [ ; +], where =
inf t2f0;1;:::;N 1g + =
sup t2f0;1;:::;N 1g { { − sup xt2O(t)
inf − xt2O(t)
H0d(xt; ¯(t + 1); 0) +
inf xt2O(t) H0d(xt; ¯(t + 1); 0) + sup xt2O(t)
H1d(xt; ¯(t + 1)) }; H1d(xt; ¯(t + 1)) }: 3) The problem of constructive calculation of the adjoint state ¯ ∈ Ψ(¯) on Step 1 remains open to us. Principally, one can adopt here any desired technique based on the apparatus of the maximum principle. The work is partially supported by the Russian Foundation for Basic Research, grants nos 16-31-60030, 16-0800272, 16-31-00184, and 17-01-00733.