Optimal Control Problem with State Constraints

Abstract

We deal with methods of parameter continuation in applied optimal control problem using the maximum principle and the direct method of descent in the space of controls. Universal method for solving boundary-value problem with fixed right end is suggested. The example of the problems of dynamic portfolio is presented. The problem was solved by reducing to a linear programming (LP) one by integrating system the explicit Euler method. When one asked prescribed accuracy of the calculations due to the fineness of the partition of the segment we obtained LP problem of large dimension. This raises two major problems: (1) optimal solution within a reasonable time; (2) incorrectness of the LP problem. To find the optimal solution we apply the method of continuation the parameter. We divide the interval of integration into a number of nested segments and use parallel calculations.

Introduction

A Problem of Dynamic Portfolio

Problem of dynamic portfolio and restrictions on the control and state coordinates, respectively

Q1

Q(t)

Q2; R1

R(t)

R2; t 2 [0; T ]; V (t) 0; F (t) 0; S(T ) 0; t 2 [0; T ]: One required to find max S(T ) involving the const A mathematical model of the dynamics of the securities market has the form (problem A0)

V (0) = 0; F (0) = 0; S(0) = 0; V (T ) = 0; F (T ) = 0: Here F (t) — the portfolio of securities, V (t) — the value of bank debt on the loan, S(t) — the balance of the account transactions, Q(t) — the rate of change in volume of funds used for the line of credit, R(t) — the rate of change of portfolio securities field, 0 — the rate paid on the loan, — the rate of received dividends; Q(t); R(t) — control functions; V (t); F (t); S(t) — the phase variables.

To find the optimal solution we apply the method of continuation the parameter. We divide the interval of integration into a number of nested segments On the segment we carry out discretization of the problem based on the explicit Euler method. Since the segment is small, we obtain as a result of the linear programming (LP) problem of small dimension. For this problem is fulfilled the conditions (3)

V˙ = Q; F˙ = R; S˙ = 0V + F + Q

R; t 2 [0; T ]:

Constraints (1) – (2) with zero initial and boundary conditions 153

V (0) = 0; F (0) = 0; S(0) = 0; V (t1) = 0; F (t1) = 0; S(t1) ! max: Note that the solution of the problem always exists and is unique. As a result we obtain the optimal control u10 = (Q10; R10).

Next, we use this solution as a first approximation to the solution of the problem for a segment [0; t2]. This process can be extended up to tm = T . Note that the optimal solution obtained at the previous interval, is admissible in a subsequent extended interval.

It is well known that the maximum principle for the problem A0 is trivial for some value 0 and . To obtain meaningful maximum principle we consider the perturbed system (problem A1)

V˙ = Q

V; F˙ = R; S˙ = 0V + F + Q

R; t 2 [0; T ]:

All the remaining constraints (1) – (3) are unchanged. The following theorems hold true.

Theorem 1. Let > 0. Then for the problem A1 a non-trivial principle of the maximum Π0 in the form of

Dubovitskii-Milyutin [Dikusar & Milyutin, 1989] is valid.

Theorem 2. Let > 0. Then the values of the functional S0(T ) and S1(T ) for the problems A0 and A1 asymptotically coincide.

The maximum principle Π0 [Dikusar & Umnov, 2002] reduces the original problem to a boundary value problem for the selection V (0) and F (0) thus to satisfy the boundary conditions (3). Here V (0) and F (0) — the conjugate variables.

Let put T = t1 (4) and on the segment [0; t1] we solve the boundary value problem. In this case, we obtain, the initial values V1 = V (0) and F1 = F (0). We use the obtained values V1 and F1 for the solution of the boundary value problem A1 as a first approximation. Forecasting methods allow us to generate information in order to calculate the next approximation for V1 and F1 on the segment 0; t1]; i = 2; :::; m . (1) (2) (3) (4) (5)

Discrete Scheme for Solution of Portfolio Dynamic Problem

The proposed scheme was used for solution portfolio dynamic problem. Let us denote: S(k) — the rest of assets on current account, k = [1; N ]; Q(k) — volume of assets used on credit line, k = [1; N ]; R(k) — volume of portfolio, k = [1; N ]; q(k) — payment of interest for credit, k = [1; N ]; r(k) — return on current account, k = [1; N ]; V (k) — quantity of debt on credit, k = [1; N ], 0(k) — price of assets on credit, k = [1; N ]; 0(k) — coupon yield of assets, k = [1; N ].

The variable are connected by following dynamics for k = [1; N 1].

1◦. Dynamic of account S(k + 1) = S(k) + Q(k) R(k) + r(k)

2◦. Dynamic of interest payment for credit

3◦. Dynamic of obtaining dividends

initial conditions S(1) = V (1) = F (1) = 0; boundary conditions V (N ) = F (N ) = 0.

To be maximized is a functional that in difference form is equivalent P (N ) =

The following statement are true 1◦. In the case V (1) = F (1) = S(1) = 0 we have 2◦. For boundary conditions F (N ) = V (N ) = 0 we get

In result we have more simple form of dynamical system S(k) = P (k) + V (k);

P (N ) ! max , S(N ) ! max :

Here we consider piecewise constant control variables 0(k) and (k)

(6) (7) (8) (9) (10) under conditions The quantities !n and n were estimated by Newton’s method in the case of local quadratical approximation.

Meaningful analysis the obtained results shows that in case of instable market of value assets there is unique jump reaction of market on value credit lines in the moment k0 depending on revenue (11) in the moment k1. In other words, there is functional dependence k0 from k1. That can be used by governing units for improvement situation on financial markets and, for example, for optimization of taxes. 4

Parametric Linearization Method in the Discrete Optimal Control Problem The problem has parameters 0 and . So we give parallel calculations in Sobolev-Statnikov algorithm. We make the net and calculations.

We concentrate on the treatment of the following class of nonlinear discrete optimal control problems. To be minimized is a functional

I(N ) =

N ∑ F (x(k); u(k); k); k=0 u 2 Rz;

x 2 Rn x(k + 1) = fi(x(k); u(k); k); i = [1; n]; k = [1; N gj (x(k); u(k); k) 0; j = [1; m]; where x(k) is state vector, u(k) is control vector; all functions are continuously differentiable with respect to their argument. We suggest also that control-state constraints (3) are regulars [Dikusar & Milyutin, 1989].

As was showed, for example [1, 2, 3, 4], the solution of the problem (1)–(3) can be based on necessary and sufficient optimality conditions such as:

1. Principle optimality of Bellman for dynamical systems;

2. Maximum principle for optimal control problems with complicated constraints of general type;

3. Necessary and sufficient optimality conditions in mathematical programming problems. Our paper is devoted special, but widely occurred in applications, class of nonlinear discrete optimal control problems with control-state constraints, allowing linearization of the original problem by parametrization a subset of control functions.

Let p(k), p(k) 2 Rl be subset of control, which reduced initial problem (1)–(3) to linear one for fixed p(k).

In result we have linear parametric optimization problem subject to

N ∑ (dT (k; p(k))x(k) + eT (k; p(k))u(k)) ! min k=1 {x;u} x(k + 1) = A(k; p(k))x(k) + B(k; p(k))u(k) + s(k; p(k)); 8k = [1; N G(k; p(k))x(k) + K(k; p(k))u(k) + w(k; p(k)) 0; where A(k; p(k)), B(k; p(k)), s(k; p(k)), G(k; p(k)), K(k; p(k)), w(k; p(k)) are matrices of corresponded dimensions.

We assume that solution the problem (4)–(6) exists and satisfies optimality condition in the form of

Dubovitski–Milyutin.

Linearity of the problem (4)–(6) give us opportunity to use two level scheme for its solution.

At first we solve linear problem (4)–(6) on lower level for fixed p(k), k = [1; N ]. After, on upper level, we seek the minimum (4) on set of p(k), k = [1; N ] for fixed x∗(k) and u∗(k) obtained from the solutions on lower level.

Then we continue the process iteratively. Algorithm for solution of the problem (4)–(6) depends on form of the functions d(k; p(k)), e(k; p(k)), G(k; p(k)), K(k; p(k)), w(k; p(k)), k = [1; N ] and we must take into account that explicit relation of the solution on the parameter p(k) is unknown.

For getting solution (4)–(6) and forming output files we used C++ and OC Windows 2K-XP with basic version of algorithm for analysis incomplete mathematical models. (11) (12) (13) (14) (15) (16)

2◦. Dynamic of interest payment for credit

3◦. Dynamic of obtaining dividends

initial conditions S(1) = V (1) = F (1) = 0; boundary conditions V (N ) = F (N ) = 0.

To be maximized is a functional that in difference form is equivalent P (N ) =

The following statement are true 1◦. In the case V (1) = F (1) = S(1) = 0 we have 2◦. For boundary conditions F (N ) = V (N ) = 0 we get

In result we have more simple form of dynamical system S(k) = P (k) + V (k);

P (N ) ! max , S(N ) ! max :

Here we consider piecewise constant control variables 0(k) and (k)

(17) (18) (19) (20) (21) The quantities !n and n were estimated by Newton’s method in the case of local quadratical approximation.

Meaningful analysis the obtained results shows that in case of instable market of value assets there is unique jump reaction of market on value credit lines in the moment k0 depending on revenue (11) in the moment k1. In other words, there is functional dependence k0 from k1. That can be used by governing units for improvement situation on financial markets and, for example, for optimization of taxes. 5

Parallel Calculations

Message passing interface (MPI) is complex enough but serves as standard de-facto for parallel calculations [Dolmatova & Olenev, 2014]. MathWorks has developed an application for the creation of parallel and distributed programs using the MPI library funds and their implementation on the platform of MATLAB, which simplifies the practical use of parallel computing on multicore computers, clusters, and GRID-systems.

To determine the optimal geometry of the trajectories of the initial problem it is reduced to a discrete one and then it is solved by methods of linear and non-linear programming. The boundary value problem is solved with the use of continuous analogue of the Newton and gradient methods. The Jacobian matrix is calculated using parallel procedures. To solve the problems of linear and non-linear programming methods factor analysis is used.

It solved the problem of eigenvalues for the matrix of observations in the case of linear large-scale problems. Based on MATLAB software package designed for problems of an optimal control with the use of distributed computing and GRID-technologies for the numerical solution of this problem of eigenvalues.

For the administration and configuration of parallel calculations in MATLAB, they use two applications: (1) Parallel Computing Toolbox (PCT), (2) MATLAB Distributed Computing Server (MDCS).

You can develop your program on a multicore desktop computer using Parallel Computing Toolbox and then scale up it to use a cluster supercomputer, a cloud, or a grid by running it on MATLAB Distributed Computing

Server [Olenev et al., 2015].

Parallel calculations in MATLAB [Olenev et al., 2015] are used here to find parameters 0 and in the problem of dynamic portfolio. As a result, the process of calculations was speeded up by an order of magnitude. Acknowledgements The authors were supported by the Russian Foundation of Basic Research (project no. 15-07-08952). [Umnov, 2002] Umnov, E.A. (2002) Construction of optimal control in the problems of investment activity on instable market of value assets. Issue \Processing and Modeling". Moscow: MIPT.

References

[Dikusar & Milyutin , 1989] Dikusar, V.V. , & Milyutin , A.A. ( 1989 ) Qualitative and Numerical Methods in Maximum Principle . Moscow: Nauka.

[Propoi , 1973] Propoi, A.I. ( 1973 ) Elements of Theory Discrete Optimal Processes . Moscow: Nauka.

[Moiseev , 1971] Moiseev, N.N. ( 1971 ) Numerical Methods in Theory of Optimal Systems . Moscow: Nauka.