1 Introduction

A problem of optimal control of discrete systems arises in planning economics, optimization of complex technological systems in different issues of organization of production and investigation of operations, and also in controlling continuous processes are using up-to-date computer technologies. The Bellman dynamic programming method [1] is universal for optimal processes in discrete systems. But its application to concrete problems may be less effective [2] than the use of necessary optimality condition as Pontryagin’s maximum principle [3]. Historically, the theory of discrete processes has followed the Pontryagin maximum principle for continuous optimal control problems that is reduced to attempts for formulating the discrete analog of the maximum principle. Butkovskii [4] first showed that unlike the continuous case, a direct extension of Pontryagin’s maximum principle to discrete systems is impossible in general. Naturally such characteristics of these systems is of theoretical interest for researchers. In this connection, some researchers ([2, 5–13] and others) imposing extra conditions (for example, condition of convexity of the set of admissible velocities of the system, convexity in direction and so on) established that, subject to these conditions, the maximum principle is valid for discrete control systems. Following [4], many researchers [4, 10–21] tried to prove the maximum principle in the weakened form (local maximum, stationary) and obtained the higher order optimality conditions.

In spite of the fact that in the problems of optimization of discrete systems, there are many various and important results ([1, 2, 4–45] and others) the issue of necessary optimality conditions is still far from being completed. To begin with this concerns the generality of the conditions of input data of the problem under investigation. Therefore, there is necessity to study thoroughly the issues of the optimization of discrete optimal problems.

In the present paper, we consider a discrete optimization problem with rather general input data (without assumptions of convexity and smoothness) and taking into account the specific character (see Lemma 1) of the discrete system, we get a necessary optimality condition that is not formulated by the Hamilton-Pontryagin function. It should be noted that this optimality condition is characterized by the three peculiarities.

Firstly, this optimality condition permits to replace the many-dimensional minimization problem by the sequence of problems of less dimensions, i.e. the optimization problem under investigation, for each discrete time is reduced to minimization of the function of r variables, where r is the dimension of the control vector.

Secondly, considering some special optimization problems (including the problems with quadratic and special non-smooth quality criteria), it is proved that this condition contains the known and also new effective necessary optimality conditions, and some of them are different strengthenings of the discrete maximum principle.

Thirdly, this condition has a wide scope, it is stronger than the discrete maximum principle, the linearized maximum principle, the optimality condition of Euler type and local optimality conditions formulated in terms of different types of star neighborhoods (see Examples 1-3) and it is very useful when applying the contraction of the control sets suspicious for optimality that are highlighted with the help of more constructive local conditions. In conclusion, we give examples illustrating the richness of the content of the obtained results.

2 Problem statement

It is required to minimize the functional

$$ {\mathcal{S}} ( u ) =\Phi\bigl(x ( t_{1} ) \bigr) $$
(1)

on the solutions of the discrete system

$$ x ( t+1 ) =f \bigl( x ( t ) ,u ( t ) ,t \bigr) , \quad t\in T,\qquad x ( t_{0} ) =x^{\ast}, $$
(2)

under the constraint

$$ u ( t ) \in U ( t ) ,\quad t\in T. $$
(3)

Here \(x=(x_{1}, \ldots,x_{n})^{\prime}\) is a state vector (\(\vphantom{m}^{\prime}\) (the prime) is the transposition operation), \(u= (u_{1},\ldots ,u_{r} )^{\prime}\) is a control vector, t is time (discrete), \(x^{*}\) is the given vector, \(T= \{t_{0}, t_{0}+1, \ldots, t_{1}-1 \}\); \(U(t)\), \(t \in T\) are sets of r-dimensional Euclidean space \(E^{r}\); \(\Phi (x )\), \(x\in E^{n}\), \(f (x, u, t )\), \((x,u,t) \in E^{n}\times E^{r}\times [t_{0}, t_{1} ]\), are continuous functions.

The control \(u (t )\), \(t\in T\), responding to constraint (3), will be said to be admissible; the admissible control \(u (t )\), \(t\in T\), and the corresponding solution \(x (t )\), \(t\in T \cup \{t_{1}\}\), of the system (2), for which the functional (1) takes the least value, will be called optimal. In this case each pair \((u(t), x(t) )\) is called an optimal process.

Note that if in problem (1)-(3), \(U(t)\), \(t\in T\), are bounded, closed, and non-empty sets, then the optimal control \(u (t ) \) exists for any initial state \(x^{*}\) [13, p.31].

2.1 Formula of increment in quality functional

Let \(u^{0} (t ) \), \(\tilde{u} ( t ) \), \(t\in T\), be admissible controls; call the vector \(\Delta u ( t ) =\tilde {u} ( t ) -u^{0} ( t ) \), \(t\in T\), be an admissible increment of the control \(u^{0} ( t ) \), \(t\in T\). Call the increment \(\Delta u ( t ) \), \(t \in T\), special and denote it by the symbol \(\Delta ^{\ast}u ( t ) \), \(t\in T\), if

$$ \Delta ^{\ast}u ( t ) =\left \{ \begin{array}{l@{\quad}l} v-u^{0} ( \theta ) ,& t=\theta\in T\backslash \{ t_{1}-1 \} , \\ \tilde{v}-u^{0} ( \theta_{k} ) ,& t=\theta_{k}=\theta +k\in \{ \theta_{1},\theta_{2},\ldots \} \cap T, \\ 0, &t\in T\backslash \{ \theta, \theta _{k} \} , \end{array} \right . $$
(4)

where \(v\in U ( \theta ) \), \(\tilde{v}\in U ( \theta _{k} ) \).

By (2), the solutions \(x^{0} ( t ) \), \(\tilde{x} ( t ) \), \(t\in T\cup \{ t_{1} \} \), correspond to the controls \(u^{0} ( t ) \), \(\tilde{u} ( t ) \), \(t\in T\). The vector \(\Delta x ( t ) =\tilde{x} ( t ) -x^{0} ( t ) \), \(t\in T\cup \{ t_{1} \} \), is called an increment of the solution \(x^{0} ( t ) \), which corresponds to the increment \(\Delta u ( t ) \). To the special increment (4) there corresponds the special increment \({\Delta }^{\ast}x ( t ) \), \(t\in T\cup \{ t_{1} \} \), which satisfies the discrete system of the form

$$ \left \{ \begin{array}{l} {\Delta }^{\ast}x ( t+1 ) =f ( x^{0} ( t ) +{\Delta }^{\ast}x ( t ) , u^{0} ( t ) +{\Delta } ^{\ast}u ( t ) ,t ) -f ( x^{0} ( t ) , u^{0} ( t ) ,t ) , \\ \quad t\in \{ \theta_{1},\theta_{2}, \ldots \} \cap T , \\ {\Delta }^{\ast}x ( \theta_{1} ) ={\Delta }_{v}f ( x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta ) ,\qquad {\Delta }^{\ast}x ( t ) =0, \\ \quad t\in \{ t_{0},\ldots ,\theta \} , \theta_{i}=\theta+i, i=1,2,\ldots,\end{array} \right . $$
(5)

where \({\Delta }_{v}f ( x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta ) =f ( x^{0} ( \theta ) , v,\theta ) -f ( x^{0} ( \theta ) , u^{0} ( \theta ) ,\theta ) \).

Along with the system (5) consider the discrete system corresponding to the process \(( u^{0} ( t ) ,x^{0} ( t ) ) \) of the following form:

$$ \left \{ \begin{array}{l} z ( t+1;u^{0},x^{0},\alpha,\alpha_{k} ) =f ( x^{0} ( t ) +z ( t;u^{0},x^{0},\alpha,\alpha_{k} ) ,u^{0} ( t ) ,t ) -f ( x^{0} ( t ) ,u^{0} ( t ) ,t ) , \\ \quad t\in \{ \theta _{k+1},\theta_{k+2},\ldots \} \cap T, \\ z ( \theta_{k+1};u^{0},x^{0},\alpha,\alpha_{k} ) =f ( x^{0} ( \theta_{k} ) +z ( \theta_{k};u^{0},x^{0},\alpha ) ,\tilde{v},\theta_{k} ) -f ( x^{0} ( \theta _{k} ) ,u^{0} ( \theta_{k} ) ,\theta_{k} ) , \\ \quad \mbox{if }{t=\theta} _{k}\in T, \\ z ( t+1;u^{0},x^{0},\alpha ) =f ( x^{0} ( t ) +z ( t;u^{0},x^{0},\alpha ) ,u^{0} ( t ) ,t ) -f ( x^{0} ( t ) ,u^{0} ( t ) ,t ) , \\ \quad t\in \{ \theta _{1},\theta_{2},\ldots,\theta_{k-1} \} \cap T, \\ z ( \theta_{1};u^{0},x^{0},\alpha ) ={\Delta }_{v}f ( x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta ) ,\quad \theta\in T,\end{array} \right . $$
(6)

where \(\alpha= ( \theta,v ) \in T\times U ( \theta ) \), \(\alpha_{k}= ( \theta_{k},\tilde{v} ) \in \{ \theta_{1},\theta_{2}, \ldots \} \cap T\times U ( \theta_{k} ) \).

As is seen, the solution \(z(t;u^{0},x^{0},\alpha,\alpha_{k})\), \(t\in \{\theta_{1},\theta_{2},\ldots,t_{1}\}\) of the system (6), at the points \(\theta_{1},\theta_{2},\ldots,\theta_{k}\in T\) depends only on the parameter α, and therefore in a part of the system (6) the denotation of the form \(z(t;u^{0},x^{0},\alpha)\) is used. Since the system (6) is recurrent, it is not difficult to find its solution for concrete θ, \(\theta_{k}\), v, \(\tilde{v}\). It should be noted that the system (6) plays an important role in the investigation of problem (1)-(3).

Lemma 1

If \(z ( t;u^{0},x^{0},\alpha,\alpha_{k} ) \) is the solution of the system (6), which corresponds to the process \((u^{0} ( t ) ,x^{0}(t) ) \), then for the solution \(\Delta ^{\ast}x(t)\), \(T\cup \{ t_{1} \} \) of the system (5) corresponding to the increment (4) the following representations hold:

  1. (a)

    \(\Delta ^{\ast}x ( t ) =z ( t;u^{0},x^{0},\alpha ) \), if \(t\in \{ \theta_{1},\ldots,\theta_{k} \} \),

  2. (b)

    \(\Delta ^{\ast}x ( t ) =z ( t;u^{0},x^{0},\alpha ,\alpha_{k} ) \), if \(t\in \{ \theta_{k+1},\theta _{k+2},\ldots \} \cap \{ t_{0},\ldots,t_{1} \} \).

For proving Lemma 1 it suffices to solve the system (5) by the steps method taking into account (4) and (6).

Let \(x^{0} ( t ) \), \(t\in T\cup \{ t_{1} \} \) be the solution of the system (2) corresponding to the admissible control \(u^{0} ( t ) \), \(t\in T\). Following [46], we introduce the set

$$ U\bigl[x^{0} ( \cdot ) \bigr] ( t ) = \bigl\{ \hat{u}\in U ( t ) :f \bigl( x^{0} ( t ) ,\hat{u},t \bigr) =f \bigl( x^{0} ( t ) ,u^{0} ( t ) ,t \bigr) \bigr\} ,\quad t\in T. $$
(7)

Note that the sets \(U[x^{0} (\cdot )] (t )\), \(t\in T\), are non-empty and even if one set \(U[x^{0} (\cdot )] (\theta ) \) consists of at least two elements, then it permits one to acquire additional information on the optimality of the control \(u^{0} (t )\), \(t\in T\) (see Example 1). We also underline that in most cases it is not difficult to find the elements of the set \(U[x^{0} (\cdot )] (\theta )\), \(\theta\in T\). For example in problem (1)-(3), if \(f (x (t ),u (t ),t )=g (x (t ) )+A(x (t ),t)u(t)\), \(t\in T\), finding of the elements of the set \(U[x^{0} (\cdot )] (\theta )\) is reduced to the solution of the linear algebraic system of equations.

Lemma 2

If the control \(u^{0} ( t ) \), \(t\in T\), is optimal, then any control \(\hat{u} ( t ) \in U[x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), is optimal, and the pair \((\hat{u} ( t ) ,x^{0} ( t ) )\) is an optimal process.

The proof of Lemma 2 easily follows from the definition of the set (7).

Now let us consider the special increment \({\Delta }^{\ast}S ( u^{0} ) =S ( \tilde{u} ( t ) ) -S(u^{0} ( t ) )\) of the functional (1), corresponding to two admissible controls \(u^{0} ( t ) , \tilde{u} ( t ) =u^{0} ( t ) +\Delta ^{\ast}u ( t ) \), \(t\in T\), where \(\Delta ^{\ast}u ( t ) \), \(t\in T\), is defined by (4). Taking into account Lemma 1, we get a formula for the increment \(\Delta ^{\ast }S ( u^{0} ) \), caused by the increment (4):

$$ \Delta ^{\ast}S \bigl( u^{0} \bigr) =\Phi \bigl( x^{0} ( t_{1} ) +z \bigl( t_{1};u^{0},x^{0}, \alpha,\alpha_{k} \bigr) \bigr) -\Phi \bigl( x^{0} ( t_{1} ) \bigr) . $$
(8)

3 Optimality conditions

Theorem 3

Let \(u^{0} ( t ) \), \(t\in T\), be an admissible control, \(x^{0} ( t ) \), \(t\in T\), be the corresponding solution of the system (4). Then:

  1. (a)

    For the optimality of the control \(u^{0} ( t ) \), \(t\in T\) it is necessary that for any \(\hat{u}(t)\in U[x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), and for all \(\alpha= ( \theta ,v ) \in T\backslash \{ t_{1}-1 \} \times U ( \theta ) \), \(\alpha_{k}=(\theta_{k},\tilde{v})\in \{ \theta_{1},\theta _{2},\ldots \} \cap T\times U ( \theta_{k} ) \), the following inequality be fulfilled:

    $$ \Phi\bigl(x^{0}(t_{1})+z\bigl(t_{1}; \hat{u},x^{0},\alpha,\alpha_{k}\bigr)\bigr)-\Phi \bigl(x^{0}(t_{1})\bigr)\geq0, $$
    (9)

    where \(z ( t;\hat{u},x^{0},\alpha,\alpha_{k} ) \) is the solution of the system (6), corresponding to the process \((\hat{u}(t),x^{0}(t))\).

  2. (b)

    If: (1) in addition to the conjectures of (a) the set T consists of at most two points (\(T= \{ t_{0},t_{0}+1 \} \), \(t_{1}=t_{0}+2\)) and (2) even if along one control \(\hat{u}(t)\in U[x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), for instance along the control \(u^{0} ( t ) \), \(t\in T\), the inequality (9) is fulfilled for all \(\alpha = ( t_{0},v ) \), \(v\in U ( t_{0} ) \), \(\alpha _{1}=(t_{0}+1,\tilde{v})\), \(\tilde{v}\in U(t_{0}+1)\), then the control \(u^{0} ( t ) \), \(t\in T\), is an optimal control.

Proof

Taking into account the optimality condition \(\Delta ^{\ast}S ( u^{0} ) \geq0\) and Lemma 2, from (8) we get the proof of the statement (a) of the theorem. Now let us prove statement (b). Since the set T consists of at most two points, the increment (4) is arbitrary. Therefore by (8) and (9) we have

$$ \Delta S \bigl( u^{0} \bigr) =S \bigl( u ( t ) \bigr) -S \bigl( u^{0} ( t ) \bigr) \geq0 \quad \mbox{for all } u ( t ) =u^{0} ( t ) +\Delta u ( t ) \in U ( t ) . $$

Hence it follows that the admissible control \(u^{0} ( t ) \), \(t\in T\), is an optimal control. Statement (b) and consequently the theorem is proved. □

Remark 4

Introducing the function \(\lambda ( t;\hat {u},x^{0},\alpha ,\alpha_{k} ) =x^{0} ( t ) +z ( t;\hat {u},x^{0},\alpha ,\alpha_{k} ) \), \(t\in T\), we can write the condition (9) in the form

$$ \Phi \bigl( \lambda \bigl( t_{1};\hat{u},x^{0},\alpha, \alpha_{k} \bigr) \bigr) -\Phi \bigl( x_{0} ( t_{1} ) \bigr) \geq0, $$

where by (2), (6), \(\lambda ( \cdot ) \) is the solution of the system:

$$\begin{aligned}& \lambda \bigl( t_{1}+1;\hat{u}, x^{0},\alpha, \alpha_{k} \bigr) = f \bigl( \lambda \bigl( t;\hat{u},x^{0}, \alpha,\alpha_{k} \bigr) ,\hat{u} ( t ) ,t \bigr) ,\quad t\in \{ \theta_{k+1}, \theta_{k+2},\ldots \} \cap T, \\& \lambda \bigl( \theta_{k+1};\hat{u},x^{0},\alpha, \alpha_{k} \bigr) = f \bigl( \lambda \bigl( \theta_{k}; \hat{u},x^{0},\alpha \bigr) , \tilde{v},\theta_{k} \bigr) , \quad \theta_{k}=\theta+k\in T, \\& \lambda \bigl( t+1;\hat{u},x^{0},\alpha \bigr) = f \bigl( \lambda \bigl( t;\hat{u},x^{0},\alpha \bigr) ,\hat{u}(t), t \bigr) , \quad t\in \{ \theta_{1}, \theta_{2},\ldots,\theta_{k-1} \} , \\& \lambda \bigl( \theta_{1};\hat{u},x^{0},\alpha \bigr) = f \bigl( x^{0} ( \theta ) ,v,\theta \bigr) ,\quad \theta\in T\backslash \{ t_{1}-1 \} . \end{aligned}$$

Below we show the proved theorem has as a particular case a number of known and also new efficient (both in verification and computational aspects) optimality conditions.

Corollary 5

For the optimality of the admissible control \(u^{0} ( t ) \), \(t\in T\), it is necessary that for any \(\hat{u}(t)\in U[x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), and for all \(\alpha= ( \theta,v ) \in T\backslash \{ t_{1}-1 \} \times U ( \theta ) \), \(\forall \tilde{v}\in U ( t_{1}-1 ) \), the following inequalities be fulfilled:

$$\begin{aligned}& \Phi \bigl( f \bigl( x^{0} ( t_{1}-1 ) ,\tilde {v},t_{1}-1 \bigr) \bigr) -\Phi \bigl( f \bigl( x^{0} ( t_{1}-1 ) ,u^{0} ( t_{1}-1 ) ,t_{1}-1 \bigr) \bigr) \geq0, \end{aligned}$$
(10)
$$\begin{aligned}& \Phi \bigl( f \bigl( x^{0} ( t_{1}-1 ) +{z} \bigl( t_{1}-1;\hat {u},x^{0},\alpha \bigr) ,\hat{u} ( t_{1}-1 ) ,t_{1}-1 \bigr) \bigr) \\& \quad {}-\Phi \bigl( f \bigl( x^{0} ( t_{1}-1 ) ,\hat{u} ( t_{1}-1 ) ,t_{1}-1 \bigr) \bigr) \geq0, \end{aligned}$$
(11)

where \(z(t;\hat{u},x^{0},\alpha)\) is the solution of the system

$$ \left \{ \begin{array}{l} z ( t+1;\hat{u},x^{0},\alpha ) =f ( x^{0} ( t ) +z ( t;\hat{u},x^{0},\alpha ) ,\hat{u} ( t ) ,t ) -f ( x^{0} ( t ) ,u^{0} ( t ) ,t ) , \\ \quad t\in \{ \theta_{1},\theta_{2}, \ldots \} \cap T, \\ z ( \theta_{1};\hat{u},x^{0},\alpha ) ={\Delta }_{v}f ( x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta ) ,\quad \theta\in T, v\in U ( \theta ) . \end{array} \right . $$
(12)

Proof

Let \(\alpha= ( \theta, \hat{u} ( \theta ) ) \), \(\alpha_{k}= ( t_{1}-1,\tilde{v} ) \), where \(\theta\in T\backslash \{ t_{1}-1 \} \), \(\hat{u} ( \theta ) \in U[x^{0} ( \cdot ) ] ( \theta ) \), \(\tilde{v}\in U ( t_{1}-1 ) \). Then taking into account (7) for the solution of the system (6) corresponding to the process \(( \hat{u} ( t ) ,x^{0} ( t ) ) \), we have \(z ( t_{1};\hat{u},x^{0},\alpha,\alpha_{k} ) =\Delta _{\tilde{v}}f ( x^{0} ( t_{1}-1 ) ,\hat{u} ( t_{1}-1 ) ,t_{1}-1 ) \).

The validity of the condition (10) follows from (9). Further, if \(\alpha= ( \theta,v ) \in T\backslash \{ t_{1}-1 \} \times U ( \theta ) \), \(\alpha_{k}= ( \theta_{k}, \hat{u} ( \theta_{k} ) ) \in \{ \theta _{1},\theta_{2},\ldots \} \cap T\times U[x^{0} ( \cdot )] ( \theta_{k} ) \), then by (6), (7), from (9) we get condition (11). Thus, Corollary 5 is proved. □

Corollary 6

Let: (1) the vector function \(f(x,u,t)\) be linear with respect to x, i.e. \(f ( x,u,t ) =A ( u,t ) x+b ( u,t ) \), where \(A ( u,t ) \) is a matrix function of \(n\times n\) order, \(b ( u,t ) \) is an n-dimensional vector function, and (2) the quality criterion has the form \(\Phi=c^{\prime}x+x^{\prime n}\), where c is an n-dimensional vector, D is a matrix of \(n\times n\) order. Then for the optimality of the control \(u^{0} ( t ) \), \(t\in T\), it is necessary that for any \(\hat{u}(t)\in U[x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), the following inequalities be fulfilled:

(a)

$$ d^{\prime}z \bigl( t_{1};\hat{u},x^{0},\alpha, \alpha_{k} \bigr) + \frac{1}{2}z^{\prime} \bigl( t_{1};\hat{u},x^{0},\alpha,\alpha _{k} \bigr) \bigl(D+D^{\prime}\bigr)z \bigl( t_{1};\hat{u},x^{0}, \alpha,\alpha_{k} \bigr) \geq0 $$
(13)

for all \(\alpha= ( \theta,v ) \in T\backslash \{ t_{1}-1 \} \times U ( \theta ) \), \(\alpha_{k}= ( \theta_{k},\tilde{v} ) \in \{ \theta_{1},\theta_{2},\ldots \} \cap T\times U ( \theta_{k} ) \).

(b)

$$ \Delta_{v}H\bigl(\hat{\psi}(\theta ), x^{0}(\theta ),u^{0}( \theta ) , \theta \bigr)+\Delta _{v}f^{\prime }\bigl(x^{0}(\theta ),u^{0}( \theta ) , \theta \bigr)\widehat{\Psi }(\theta ){\Delta }_{v}f\bigl(x^{0}(\theta ),u^{0}( \theta ) , \theta \bigr)\leq 0 $$
(14)

for all \(\theta\in T\), \(v\in U ( \theta ) \). Here

$$\begin{aligned}& U\bigl[x^{0} ( \cdot ) \bigr] ( t ) =\bigl\{ \hat{u}\in U ( t ) :A ( \hat{u},t ) x^{0} ( t ) +b ( \hat{u} ,t ) \\& \hphantom{U\bigl[x^{0} ( \cdot ) \bigr] ( t ) ={}} =A \bigl( u^{0} ( t ) ,t \bigr) x^{0} ( t ) +b \bigl( u^{0} ( t ) ,t \bigr) \bigr\} ,\quad t\in T, \end{aligned}$$
(15)
$$\begin{aligned}& d=c+\bigl(D+D^{\prime }\bigr)x^{0}( t_{1}), \\& \Delta _{v}f \bigl( x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta \bigr) ={\Delta }_{v}A \bigl( u^{0} ( \theta ) ,\theta \bigr) x^{0} ( \theta ) +{\Delta }_{v}b \bigl( u^{0} ( \theta ) ,\theta \bigr) , \\& H(\hat{\psi},x,u,t)={\hat{\psi}}^{\prime}f ( x,u,t ) ={\hat { \psi}}^{\prime} \bigl[ A ( u,t ) x+b(u,t) \bigr], \end{aligned}$$
(16)
$$\begin{aligned}& \hat{\psi} ( t-1 ) =A^{\prime} \bigl( \hat{u} ( t ) ,t \bigr) \hat{\psi} ( t ) ,\quad t\in T, \qquad \hat{\psi} ( t_{1}-1 ) =-d, \end{aligned}$$
(17)
$$\begin{aligned}& \widehat{\Psi} ( t-1 ) =A^{\prime} \bigl( \hat{u} ( t ) ,t \bigr) \widehat{ \Psi} ( t ) A \bigl( \hat{u} ( t ) ,t \bigr) ,\quad t\in T,\qquad \widehat{\Psi} ( t_{1}-1 ) =-\frac{1}{2}\bigl(D+D^{\prime}\bigr), \end{aligned}$$
(18)

and the vector function \(z(t;\hat{u},x^{0},\alpha,\alpha_{k})\), \(t\in \{ \theta_{1},\ldots, t_{1} \} \), is the solution of the linear discrete system of the form

$$ \left \{ \begin{array}{l} z ( t+1;\hat{u},x^{0},\alpha,\alpha_{k} ) =A ( \hat {u} ( t ) ,t ) z ( t;{\hat{u},x}^{0},\alpha,\alpha_{k} ) , \quad t\in \{ \theta_{k+1},\theta_{k+2},\ldots \} \cap T, \\ z ( \theta_{k+1};\hat{u},x^{0},\alpha,\alpha_{k} ) =A ( \tilde{v},\theta_{k} ) z ( \theta_{k};\hat {u},x^{0},\alpha ) \\ \hphantom{z ( \theta_{k+1};\hat{u},x^{0},\alpha,\alpha_{k} ) =}{} +\Delta_{\tilde{v}}A ( u^{0} ( \theta_{k} ) ,\theta _{k} ) x^{0} ( \theta_{k} ) +{\Delta}_{\tilde {v}}b ( u^{0} ( \theta_{k} ) ,\theta_{k} ) , \quad \textit{if }\theta_{k}\in T, \\ z ( t+1;\hat{u},x^{0},\alpha ) =A ( \hat{u} ( t ) ,t ) z ( t;\hat{u},x^{0},\alpha ) , \quad t\in \{ \theta _{1},\ldots,\theta_{k-1} \} \cap T, \\ z ( \theta_{1};\hat{u},x^{0},\alpha ) ={\Delta}_{v}A ( u^{0} ( \theta ) ,\theta ) x^{0} ( \theta ) +{ \Delta}_{v}b ( u^{0} ( \theta ) ,\theta ) ,\quad \theta \in T\backslash \{ {t}_{{1}}{-}{1} \} . \end{array} \right . $$
(19)

Proof

From the conditions of Corollary 6 and by the system (6) it is seen that the vector function \(z(t;\hat{u},x^{0},\alpha,\alpha_{k})\) is the solution of the system (19). Therewith, by the formula

$$ \Phi ( x+\Delta x ) -\Phi ( x ) ={ \bigl( c+ \bigl( D+D^{\prime} \bigr) x \bigr) }^{\prime}\Delta x+\frac{1}{2}\Delta x^{\prime} \bigl(D+D^{\prime}\bigr)\Delta x $$

and by Lemma 1 the proof of the optimality condition (13) follows from the optimality condition (9).

Now we prove the optimality condition (14). From the optimality condition (13) in particular it follows that for any fixed \(\hat {u}(t)\in U{[x}^{0} ( \cdot ) ] ( t ) \), \(t\in T\), and for all \(\alpha= ( \theta,v ) \in T\times U ( \theta ) \) it is fulfilled the inequality:

$$ d^{\prime}z \bigl( t_{1};\hat{u},x^{0},\alpha \bigr) + \frac {1}{2}z^{\prime }\bigl(t_{1};\hat{u},x^{0}, \alpha\bigr) \bigl( D+D^{\prime} \bigr) z\bigl(t_{1};\hat {u},x^{0},\alpha\bigr)\geq0, $$
(20)

where \(z(t;\hat{u},x^{0},\alpha)\) is the solution of the system

$$\begin{aligned}& z\bigl(t+1;\hat{u},x^{0},\alpha\bigr)=A\bigl(\hat{u}(t),t\bigr)z \bigl(t;\hat{u},x^{0},\alpha\bigr), \quad t\in \{ \theta_{1}, \theta_{2},\ldots \} \cap T, \\& z\bigl(\theta_{1};\hat{u},x^{0},\alpha\bigr) ={ \Delta}_{v}A \bigl( u^{0}(\theta ),\theta \bigr) x^{0} ( \theta ) +{\Delta}_{v}b \bigl( u^{0} ( \theta ) ,\theta \bigr) \\& \hphantom{z\bigl(\theta_{1};\hat{u},x^{0},\alpha\bigr)} \equiv{\Delta}_{v}f \bigl( x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta \bigr) ,\quad v\in U(\theta). \end{aligned}$$
(21)

Now prove the optimality condition (14) sequentially by θ: \(\theta=t_{1}-1, t_{1}-2,\ldots,t_{0}\). Let \(\theta=t_{1}-1\). Then from (21) we have \(z(t_{1};\hat{u},x^{0},\alpha)={\Delta}_{v}f ( x^{0} ( t_{1}-1 ) , u^{0} ( t_{1}-1 ) ,t_{1}-1 ) \), where \(\alpha= ( t_{1}-1,v ) \), \(v\in U (t_{1}-1 ) \). Therewith assuming \(d=-\hat{\psi} ( t_{1}-1 ) \), \(\frac{1}{2} ( D+D^{\prime} ) =-\widehat{\Psi} ( t_{1}-1 ) \) and taking into account (16), from (20) we get the validity of the condition (14) at the point \(\theta=t_{1}-1\) for all \(v\in U ( t_{1}-1 ) \).

Let us continue the proof. Let \(\theta=t_{1}-k\in T\), \(k>1\), and \(\alpha =\alpha ( t_{1}-k,v ) \), \(v\in U ( t_{1}-k ) \). By means of the steps method, by (17), (21) it is easy to show that the following formulas hold:

$$\begin{aligned}& {\hat{\psi}}^{\prime} ( t_{1}-1 ) z\bigl(t_{1};\hat {u},{x}^{0},\alpha (t_{1}-k,v)\bigr) \\& \quad = {\hat{\psi}}^{\prime} ( t_{1}-k ) z \bigl( t_{1}-k+1;\hat{u}, x^{0},\alpha ( t_{1}-k,v ) \bigr) , \end{aligned}$$
(22)
$$\begin{aligned}& z^{\prime} \bigl( t_{1};\hat{u},{x}^{0},\alpha ( t_{1}-k,v ) \bigr) \widehat{\Psi} ( t_{1}-1 ) z \bigl(t_{1};\hat {u},{x}^{0},\alpha ( t_{1}-k,v ) \bigr) \\& \quad = z^{\prime} \bigl( t_{1}-k+1;\hat{u},{x}^{0}, \alpha ( t_{1}-k,v ) \bigr) \Psi ( t_{1}-k ) z \bigl(t_{1}-k+1;\hat{u} ,x^{0},\alpha ( t_{1}-k,v ) \bigr), \end{aligned}$$
(23)

where \(z(t_{1}-k+1;\hat{u}, x^{0},\alpha(t_{1}-k,v))={\Delta} _{v}f(x^{0}(t_{1}-k), u^{0}(t_{1}-k),t_{1}-k)\), and \(\hat{\psi} ( t_{1}-k ) \), \(\widehat{\Psi} ( t_{1}-k ) \) are determined as the solution of the system (17) and (18), respectively. Using (22), (23) and taking into account (16), inequality (20) implies the validity of the condition (14) at the point \(\theta=t_{1}-k \) for all \(v\in U ( t_{1}-k ) \). Thus, taking into account the arbitrariness of \(\theta\in T\) the optimality condition (14) is proved. Thus Corollary 6 is completely proved. □

Corollary 7

In problem (1)-(3) let \(f ( x,u,t ) =A ( u,t ) x+b ( u,t ) \), \(\Phi ( x ) =c^{\prime }x\), where \(A ( u,t ) \) is a matrix function of \(n\times n\) order, \(b ( u, t ) \) is an n-dimensional vector function, c is an n-dimensional vector. Then:

(1) For the optimality of the control \(u^{0} ( t ) \), \(t\in T\) in problem (1)-(3), it is necessary that for any \(\hat {u} ( t ) \in U [ x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), for all

$$\begin{aligned}& {\Delta}_{v}H\bigl(\hat{\psi} ( \theta ) ,x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta\bigr)\leq0\quad \textit{for all } \theta\in T, v\in U ( \theta ) , \end{aligned}$$
(24)
$$\begin{aligned}& {\Delta}_{v}H \bigl( \hat{\psi} ( \theta ) ,x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta \bigr) +{\Delta }_{\tilde{v}}H \bigl( \hat{\psi} ( \theta_{k} ) ,x^{0} ( \theta _{k} ) ,u^{0} ( \theta_{k} ) ,\theta_{k} \bigr) \\& \quad {}+{\Delta }_{\tilde{v}}H_{x}^{\prime} \bigl( \hat{ \psi} ( \theta _{k} ) ,x^{0} ( \theta_{k} ) , \hat{u} ( \theta _{k} ) ,\theta_{k} \bigr) z \bigl( \theta_{k};\hat{u},x^{0},\alpha \bigr) \leq0 \end{aligned}$$
(25)

for all \(\alpha= ( \theta,v ) \in T\backslash \{ t_{1}-1 \} \times U ( \theta ) \), \(\alpha_{k}= ( \theta _{k},\tilde{v} ) \in \{ \theta_{1},\theta_{2},\ldots \} \cap T\times U ( \theta_{k} ) \).

(2) If the set T consists of at most two points, i.e. \(T=\{t_{0},t_{0}+1\}\) and along the control \(u^{0} ( t ) \), \(t\in T\) inequality (25) is fulfilled for all \(\alpha= ( t_{0},v ) \), \(v\in U ( t_{0} ) \), \(\alpha_{1}=(t_{0}+1,\tilde{v})\), \(\tilde{v}\in U (t_{0}+1)\), then the control \(u^{0} ( t ) \), \(t\in T\), is an optimal control. Here the set \(U [ x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), is determined by (15); the function \(H(\hat{\psi},x,u,t)\) by (16); \(z(\theta_{k};\hat {u},x^{0},\alpha(\theta,v))\) is the value of the solution of the system (21) at the point \(\theta_{k}\), further

$$ {\Delta}_{\tilde{v}}H_{x}^{\prime}\bigl(\hat{\psi} ( \theta _{k} ) ,x^{0} ( \theta_{k} ) ,\hat{u} ( \theta_{k} ) ,\theta _{k}\bigr)={\hat{\psi}}^{\prime} ( \theta_{k} ) \bigl( A ( \tilde{v},\theta_{k} ) -A \bigl( \hat{u} ( \theta _{k} ) ,\theta_{k} \bigr) \bigr) ; $$
(26)

\(\hat{\psi} ( t ) \), \(t\in T\), is the solution of the system

$$ \hat{\psi} ( t-1 ) =A^{\prime} \bigl( \hat{u} ( t ) ,t \bigr) \hat{\psi} ( t ) ,\qquad \hat{\psi} ( t_{1}-1 ) =-c. $$
(27)

Proof

First we prove the optimality condition (25). By the conditions of Corollary 7, the optimality condition (13) takes the form

$$\begin{aligned}& c^{\prime}z \bigl( t_{1};\hat{u},{x}^{0},\alpha, \alpha_{k} \bigr) \geq0, \\& \quad \forall \hat{u} ( t ) \in U \bigl[ x^{0} ( \cdot ) \bigr] ( t ) ,t\in T, \forall\alpha= ( \theta,v ) \in T\backslash \{ t_{1}-1 \} \times U ( \theta ) , \\& \quad \forall\alpha_{k}= ( \theta_{k}, \tilde{v} ) \in \{ \theta_{1},\theta _{2},\ldots \} \cap T \times U ( \theta_{k} ) , \end{aligned}$$
(28)

where \(z ( t;\hat{u},{x}^{0},\alpha,\alpha_{k} ) \) is the solution of the system (19).

Let \(\theta\in T\backslash \{ t_{1}-1 \} \) and \(\theta _{k}\in \{ \theta_{1},\theta_{2},\ldots \} \cap T\). Then according to (16), (19), (27) by means of the steps method we get

$$\begin{aligned}& c^{\prime}z \bigl( t_{1};\hat{u},{x}^{0},\alpha, \alpha_{k} \bigr) \\& \quad = -{\hat{\psi}}^{\prime} ( t_{1}-1 ) A \bigl( \hat{u} ( t_{1}-1 ) ,t_{1}-1 \bigr) z \bigl( t_{1}-1; \hat{u},x^{0},\alpha ,\alpha _{k} \bigr) \\& \quad = -{\hat{\psi}}^{\prime} ( t_{1}-2 ) z \bigl(t_{1}-1;\hat{u},x^{0},\alpha, \alpha_{k}\bigr)=\cdots=-{\hat{\psi}}^{\prime} ( \theta _{k} ) z\bigl(\theta_{k+1};\hat{u},x^{0},\alpha, \alpha_{k}\bigr) \\& \quad = -\hat{\psi}^{\prime}(\theta_{k})A(\tilde{v}, \theta_{k})z \bigl( \theta_{k};\hat{u},x^{0}, \alpha \bigr) -\hat{\psi}^{\prime} ( \theta _{k} ) \bigl[{ \Delta }_{\tilde{v}}A \bigl( u^{0} ( \theta _{k} ) , \theta_{k} \bigr) x^{0} ( \theta_{k} ) \\& \qquad {} +{\Delta }_{\tilde{v}}b \bigl( u^{0} ( \theta_{k} ) ,\theta_{k} \bigr) \bigr] \\& \quad = -{\Delta }_{\tilde{v}}H \bigl( \hat{\psi} ( \theta _{k} ) ,x^{0} ( \theta_{k} ) ,u^{0} ( \theta_{k} ) ,\theta _{k} \bigr) \\& \qquad {} -{\hat{\psi}}^{\prime} ( \theta_{k} ) \bigl[ A ( \tilde{ v},\theta_{k} ) -A \bigl( \hat{u} ( \theta_{k} ) , \theta _{k} \bigr) \bigr] z \bigl( \theta_{k}; \hat{u},x^{0},\alpha \bigr) \\& \qquad {} -{\hat{\psi}}^{\prime} ( \theta_{k} ) A \bigl( \hat{u} ( \theta_{k} ) ,\theta_{k} \bigr) z \bigl( \theta_{k};\hat{u},x^{0},\alpha \bigr) . \end{aligned}$$
(29)

Further, for the last term of (29) quite similarly we have

$$\begin{aligned}& \hat{\psi}^{\prime}(\theta_{k})A \bigl( \hat{u} ( \theta_{k} ) ,\theta_{k} \bigr) z \bigl( \theta_{k};\hat{u},x^{0},\alpha \bigr) \\& \quad = \hat{\psi}^{\prime} ( \theta_{k-1} ) z \bigl( \theta_{k}; \hat{u},x^{0},\alpha \bigr) =\cdots \\& \quad = \hat{\psi}^{\prime}(\theta)z\bigl(\theta_{1}; \hat{u},x^{0},\alpha \bigr)={\Delta }_{v}H\bigl(\hat{\psi}( \theta),x^{0}(\theta),u^{0}(\theta),\theta\bigr). \end{aligned}$$
(30)

According to (26), (29), (30) from (28), we get the proof of the optimality condition (25).

Assuming \(\tilde{v}=\hat{u}(\theta_{k})\) and taking into account \(\hat{u} ( t ) \in U [ x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), from (25) in particular case for all \(\theta \in T\backslash \{ t_{1}-1 \} \) it follows the proof of the optimality condition (24) and for the proof of the condition (24) at the point \(\theta_{k}=t_{1}-1 \) it suffices to take into account \(v=u^{0}(\theta)\) in (25). The validity of the last statement of Corollary 7 using the scheme of the proof of the optimality condition (25) follows directly from statement (b) of the theorem. Consequently, Corollary 7 is proved. □

We stress that the optimality condition (24) for \(\hat{u} ( t ) =u^{0} ( t ) \), \(t\in T\), is obtained in [15].

Corollary 8

In the problem let \(f ( x,u,t ) =A ( u,t ) x+b ( u,t ) \), \(\Phi ( x ) =c^{\prime}x+\vert d^{\prime}x \vert \), where \(A ( u,t ) \) is a matrix function of order \(n\times n\), \(b (u, t)\) is an n-dimensional vector function, c and d are n-dimensional vectors. Then for the optimality of the admissible process \((u^{0} ( t ) ,x^{0} ( t ) )\) it is necessary that for any \(\hat{u} ( t ) \in U [ x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), and for all \(\theta\in T\), \(v\in U(\theta)\) the following inequality be fulfilled:

$$\begin{aligned}& \bigl\vert d^{\prime0} ( t_{1} ) \bigr\vert +{ \Delta }_{v}H\bigl({\hat{\psi}}_{c} ( \theta ) ,x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta\bigr) \\& \quad \leq\bigl\vert d^{\prime0} ( t_{1} ) -{ \Delta}_{v}H \bigl( {\hat{\psi}}_{d} ( \theta ) ,x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta \bigr) \bigr\vert , \end{aligned}$$
(31)

where the sets \(U[x^{0} ( t ) ](t)\), \(t\in T\), are determined by (15), \(H(\hat{\psi},x,u,t)\) by (16): \(\hat{\psi}_{c} ( t ) \), \(\hat{\psi}_{d} ( t ) \), are the solutions of the system (27) with the corresponding initial conditions

$$ {\hat{\psi}}_{c} ( t_{1}-1 ) =-c,\qquad {\hat{ \psi}}_{d} ( t_{1}-1 ) =-d. $$
(32)

Proof

It is easy to see that under the conditions of Corollary 8 the optimality condition (9) takes the form

$$\begin{aligned}& c^{\prime}z \bigl( t_{1};\hat{u},x^{0}, \alpha ( \theta,v ) \bigr) +\bigl\vert d^{\prime0} ( t_{1} ) +d^{\prime}z \bigl( t_{1},\hat{u},x^{0},\alpha ( \theta,v ) \bigr) \bigr\vert -\bigl\vert d^{\prime0} ( t_{1} ) \bigr\vert \geq0, \\& \quad \forall\alpha=\alpha ( \theta,v ) ,\theta\in T,v\in U(\theta ),\forall \hat{u}(t) \in U\bigl[x^{0} ( \cdot ) \bigr](t), t\in T, \end{aligned}$$
(33)

where \(z ( t;\hat{u},x^{0},\alpha ( \theta,v ) ) \) is the solution of the system (21).

According to (16), (21), (27), (32) it is easy (by applying the steps method) to get

$$\begin{aligned} c^{\prime}z \bigl( t_{1};\hat{u},x^{0},\alpha ( \theta,v ) \bigr) =&-{\hat{\psi}}_{c}^{\prime} ( t_{1}-1 ) A \bigl( \hat {u} ( t_{1}-1 ) ,t_{1}-1 \bigr) z \bigl( t_{1}-1;\hat {u},x^{0}, \alpha ( \theta,v ) \bigr) \\ =&-{\hat{\psi}}_{c}^{\prime} ( t_{1}-2 ) z \bigl( t_{1}-1;\hat {u},x^{0},\alpha ( \theta,v ) \bigr) \\ =&\cdots=-{\hat{\psi}}_{c}^{\prime} ( \theta ) z \bigl( \theta _{1};\hat{u},x^{0},\alpha ( \theta,v ) \bigr) \\ =&-\Delta_{v}H \bigl( {\hat{\psi}}_{\tilde{n}} ( \theta ) ,x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta \bigr) . \end{aligned}$$
(34)

Similarly we have

$$ d^{\prime}z \bigl( t_{1};\hat{u},x^{0},\alpha ( \theta,v ) \bigr) =-{\Delta}_{v}H \bigl( {\hat{\psi}}_{d} ( \theta ) ,x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta \bigr) . $$
(35)

Taking into account (34), (35) in (33), we get the proof of inequality (31), and thus Corollary 8 is proved. □

Corollary 9

In problem (1)-(3) let \(f ( x,u,t ) =A ( t ) x+b ( u,t ) \), \(\Phi ( x ) =c^{\prime}x\). Then for the optimality of the control \(u^{0} (t ) \), \(t\in T\), it is necessary and sufficient that for all \(\alpha=\alpha ( \theta,v ) \), \(\theta\in T\), \(v\in U(\theta)\) the following inequality be fulfilled:

$$ c^{\prime}z \bigl( t_{1};u^{0},x^{0},\alpha ( \theta,v ) \bigr) \geq0, $$
(36)

where \(z ( t;u^{0},x^{0},\alpha ( \theta,v ) ) \) is the solution of the system

$$ \left \{ \begin{array}{l} z(t+1;u^{0},x^{0},\alpha ( \theta,v )) =A ( t ) z ( t;u^{0},x^{0},\alpha ( \theta,v ) ) ,\quad t\in \{ \theta _{1},\theta_{2},\ldots \} \cap T, \\ z ( \theta_{1};u^{0},x^{0},\alpha ( \theta,v ) ) =b ( v,\theta ) -b ( u^{0} ( \theta ) ,\theta ) .\end{array} \right . $$
(37)

Proof

Under the conditions of Corollary 9 the necessity is obvious. Now we prove the second part of the corollary. Assume that along the admissible control \(u^{0} ( t ) \), \(t\in T \) condition (36) is fulfilled and let us prove that in this case the control \(u^{0} ( t ) \), \(t\in T\), is optimal. It suffices to show that the inequality

$$ \Delta S \bigl( u^{0} \bigr) =S \bigl( \tilde{u} ( t ) \bigr) -S \bigl( u^{0} ( t ) \bigr) =c^{\prime}\Delta x ( t_{1} ) \geq0 $$
(38)

is fulfilled for all arbitrary admissible controls \(\tilde{u} ( t ) \), \(t\in T\), where \(\Delta x ( t ) =\tilde{x} ( t ) -x ( t ) \), \(t\in T\), is the solution of the system

$$ \Delta x ( t+1 ) =A ( t ) \Delta x ( t ) +b \bigl( \tilde{u} ( t ) ,t \bigr) -b \bigl( u^{0} ( t ) ,t \bigr) ,\quad t\in T,\qquad \Delta x ( t_{0} ) =0. $$
(39)

According to (37), (39), by means of the steps method (sequentially with respect to t: \(t=t_{0}+1, t_{0}+2,\ldots,t_{1}\)) it is easy to show that

$$ \Delta x ( t ) =\sum_{\theta=t_{0}}^{t_{1}-1} z \bigl(t;u^{0},x^{0},\alpha\bigl(\theta,\tilde{u}(\theta)\bigr) \bigr),\quad t\in \{ t_{0}+1,t_{0}+2,\ldots,t_{1} \} . $$
(40)

Since the condition (36) is fulfilled, using (40) we get the validity of (38), i.e. we have

$$ \Delta S \bigl( u^{0} \bigr) =c^{\prime} \Delta x ( t_{1} ) =\sum_{\theta=t_{0}}^{t_{1}-1}c^{\prime}z \bigl(t_{1};u^{0},x_{0},\alpha \bigl(\theta, \tilde{u} ( \theta ) \bigr)\bigr)\geq0. $$

This proves the sufficiency of the condition (36), and thus Corollary 9 is proved. □

Remark 10

Under the conditions of Corollary 9, the optimality condition (24) has first been proved in [47] as a necessary and sufficient optimality condition, and taking into account the scheme of the proof of Corollary 7, it is easy to show that the discrete maximum principle from [47] and the optimality conditions (36) are equivalent.

Finally we prove the following statement.

Corollary 11

In problem (1)-(3) let us additionally suppose that the function \(\Phi ( x ) \) is continuously differentiable and \(f ( x,u,t ) \) is a continuously differentiable vector function with respect to x and u. Then:

1. If the sets \(U ( t ) \), \(t\in T\), are convex, then for the optimality of the control \(u^{0} ( t ) \), \(t\in T\), it is necessary that for any \(\hat{u} ( t ) \in U [ x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), and for all \(\theta\in T\), \(v\in U ( \theta ) \), the following inequality be fulfilled:

$$ H_{u}^{\prime}\bigl(\hat{\psi} ( \theta ) ,x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta\bigr) \bigl(v-u^{0} ( \theta ) \bigr)\leq0. $$
(41)

2. If the sets \(U ( t ) \), \(t\in T\), are open or \(u^{0} ( t ) \in \operatorname{int}U ( t ) \), \(t\in T\), then for the optimality of the control \(u^{0} ( t ) \), \(t\in T\), it is necessary that for any \(\hat{u} ( t ) \in U [ x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), and for all \(\theta\in T\) the following equality be fulfilled:

$$ H_{u} \bigl( \hat{\psi} ( \theta ) ,x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta \bigr) =0, $$
(42)

where the sets \(U [ x^{0} ( \cdot ) ] ( t ) \), \(t\in T\), are determined by (7); the function \(H(\hat{\psi},x,u,t)\) by (17); and the vector function \(\hat{\psi}(t)\) is the solution of the system

$$ \hat{\psi} ( t-1 ) =f_{x}^{\prime} \bigl( x^{0} ( t ) ,\hat{u} ( t ) ,t \bigr) \hat{\psi} ( t ) ,\qquad \hat{ \psi} ( t_{1}-1 ) =-\Phi_{x} \bigl( x^{0}(t_{1}) \bigr) . $$
(43)

Proof

First we prove the optimality condition (41). We use Corollary 6. Let \(\theta\in T\) and \(v\in U(\theta)\) be arbitrary fixed elements. By definition of the convex set for any \(\varepsilon\in[ 0,1]\) the vector \(v ( \varepsilon ) =u^{0} ( \varepsilon ) +\varepsilon(v-u^{0} ( \theta ) )\) is an element of the set \(U(\theta)\). By applying the steps method, for the solution \(z ( t; \hat{u},x^{0},\alpha ( \theta,v(\varepsilon) ) ) \), \(t\in T_{1}=\{\theta_{1}, \theta_{2},\ldots,t_{1}\}\), of the system (12) it is easy to get the expansion of the form

$$ z \bigl( t;\hat{u},x^{0},\alpha \bigl( \theta,v(\theta) \bigr) \bigr) =\varepsilon Z \bigl( t;\hat{u},x^{0} \bigr) f_{u} \bigl(x^{0} ( \theta ) ,u^{0} ( \theta ) ,\theta\bigr) \bigl( v-u^{0} ( \theta ) \bigr) +o ( \varepsilon ) . $$
(44)

Here the matrix function \(Z ( t;\hat{u},x^{0} ) \), \(t\in T_{1}\), is the solution of the system

$$ \begin{aligned} &Z \bigl( t+1;\hat{u},x^{0} \bigr) =f_{x} \bigl( x^{0} ( t ) ,\hat{u} ( t ) ,t \bigr) Z \bigl( t;\hat{u},x^{0} \bigr) ,\quad t \in \{ \theta_{1}, \theta_{2},\ldots \} \cap T, \\ &Z \bigl( \theta_{1};\hat{u},x^{0} \bigr) =E, \end{aligned} $$
(45)

where E is the unit \(n\times n\) matrix.

Note that we can write the statement of Corollary 6 in the following form [36]:

$$\begin{aligned}& \Phi\bigl(x^{0}(t_{1})+{ z}\bigl(t_{1}; \hat{u},x^{0},\alpha ( \theta, v ) \bigr)\bigr)-\Phi \bigl(x^{0}(t_{1})\bigr)\geq0, \\& \quad \forall\alpha=\alpha ( \theta, v ) \in T\times U ( \theta ) , \forall \hat{u}=\hat{u} ( t ) \in U \bigl[ x^{0} ( \cdot ) \bigr] ( t ) , t\in T. \end{aligned}$$

Hence by (44) we get

$$ \varepsilon\Phi_{x}^{\prime} \bigl( x^{0}(t_{1}) \bigr) Z \bigl( t_{1};\hat{u},x^{0} \bigr) f_{u}\bigl(x^{0} ( \theta ) ,u^{0} ( \theta ) , \theta\bigr) \bigl( v-u^{0} ( \theta ) \bigr) +o ( \varepsilon ) \geq0. $$
(46)

Further, similar to the scheme of the proof of (34), using (43), (45) we have

$$ \hat{\psi}^{\prime} ( t_{1}-1 ) Z \bigl( t_{1};\hat {u},x^{0} \bigr) =\hat{\psi}^{\prime} ( \theta ) Z \bigl( \theta_{1};\hat{u},x^{0} \bigr) . $$

Taking into account the last equality and \(Z ( \theta_{1};\hat{u} ,x^{0} ) =E\), (46) yields the proof of inequality (41). When the sets \(U ( t ) \), \(t\in T\), are open or \(u^{0} ( t ) \in\operatorname{int}U ( t ) \), \(t\in T\), the proof of the condition (42) follows directly from the optimality condition (41). This completes the proof of Corollary 11. □

Remark 12

Optimality conditions of type (41), (42) obtained in [19], for \({\hat{u} ( t ) =u}^{0} ( t ) \), \(t\in T\), are obtained, for example, in [4, 12, 13, 15, 16, 26, 34].

Remark 13

If \(f ( x, u,t ) \), \(\Phi ( x ) \) are continuously differentiable functions with respect to x, and the sets \(\{ f ( x, u,t ) :u\in U ( t ) \} \) are convex for any \(x\in E^{n}\), \(t\in T\), then similar to the scheme of the proof of Corollary 11, the discrete maximum principle follows as a particular case from the statement of Corollary 5 [7, 8, 13].

4 Discussion of the theorem and its corollaries. Examples

It should be noted that the necessary optimality condition (9) is rather general. The merit of the sufficient condition (9) compared with discrete maximum principle [7, 8, 13, 15] is that it has no convexity or smoothness conditions with respect to the input data of problem (1)-(3). Therefore the optimality condition (9) has a wider range of applications than the earlier known necessary optimality conditions (for example, [4, 9, 12–16, 18, 20, 21, 26, 34]). Note that the optimality condition (9) allows one to replace the many-dimensional minimization problem by a sequence of problems of less dimensions, and its application is convenient when its test is performed sequentially with respect to θ: \(\theta=t_{1}-1,t_{1}-2,\ldots,t_{0}\) (see Example 1). By Corollaries 5-11 and Remark 13 it is shown that the optimality condition (9) contains as a particular case both new and known optimality conditions. The necessary optimality conditions given in Corollaries 6-8 show how important it is to take into account the specific character of the concrete optimization problem (1)-(3).

Corollary 5 as an independent result is obtained in [36]. Taking into account the method of proof of Corollaries 6 and 7, we find that optimality (13) contains as a particular case the optimality conditions (14), (24), (25). The optimality conditions (24), (41), (42) following the sets \(U[x^{0} ( t ) ](t)\), \(t\in T\), are direct strengthenings of the discrete maximum principle, discrete analog of the linearized maximum principle and discrete analog of the Euler equation [4, 7, 8, 13, 15, 26], respectively (see Example 2). As is seen, optimality conditions (41), (42) are the corollaries of the condition (10), (11), though unlike the continuous [3] case, it is well known that [16, 34] in the general case they are not corollaries of the discrete maximum principle. Note that the discrete maximum principle under the conditions of Corollaries 6, 7 admits different strengthenings in the form of optimality conditions (14) and (25). The optimality condition of type (14) is obtained in another way in [16], and as far as we know the optimality conditions (25), (31) have no analog. It is interesting to note that verification of the optimality condition (25) at any two neighboring points θ, \(\theta_{1}\) is more convenient but not sufficient for its complete application (see Example 3). From the optimality condition (25) and Example 3 we conclude that in the discrete case, unlike the continuous one, the discrete principle of the maximum (as a necessary optimality condition of first order) is strengthened at the expense of multipoint variation of control as well.

The above is confirmed by the following examples.

Example 1

\(x_{1} ( t+1 ) =u_{1} ( t ) \), \(x_{2} ( t+1 ) =\vert x_{1} ( t ) \vert -\vert u_{1} ( t ) \vert \), \(x_{3} ( t+1 ) ={x}_{2} ( t ) u_{2} ( t ) \), \(x_{i} ( 0 ) =0\), \(i=1,2,3\); \(T=\{0,1,2\}\), \(u= ( u_{1},u_{2} ) ^{\prime\ast }\times U^{\ast}\), \(U^{\ast}= [ -1,-\frac{1}{2} ] \cup \{ 0 \} \cup [ \frac{1}{2},1 ] \), \(\Phi ( x ( 3 ) ) =x_{3}(3)\rightarrow \min\).

As an illustration of richness of the content and application scheme of the necessary optimality condition (11) we study the optimality of admissible control \(u^{0} ( t ) = ( u_{1} ( t ) ,u_{2} ( t ) ) ^{\prime} = ( 0,0 ) ^{\prime }\), \(t\in T\). It is easy to calculate (by (7), (13)) \(x^{0} ( t ) = ( 0,0,0 ) ^{\prime}\), \(t\in T\cup\{3\} \); \(U [ x^{0} ( \cdot ) ] (t)=\{\hat{u}={ ( 0,{\hat {u}}_{2} ) }^{\prime}: {\hat{u}}_{2}\in U^{\ast}\}\), \(t\in T\);

$$\begin{aligned}& z \bigl( 3;u^{0},x^{0};\alpha(2,v) \bigr) = \bigl( v_{1},-\vert v_{1}\vert ,0 \bigr) ^{\prime}, \\& z \bigl( 2;u^{0},x^{0};\alpha (1,v) \bigr) = \bigl( v_{1},-\vert v_{1}\vert ,0 \bigr) ^{\prime}, \\& z \bigl( 3;u^{0},x^{0};\alpha(1,v) \bigr) = \bigl( 0,\vert v_{1}\vert ,0 \bigr) ^{\prime}, \\& z \bigl( 1;u^{0},x^{0};\alpha ( 0,v ) \bigr) = \bigl( v_{1},-\vert v_{1}\vert ,0 \bigr) ^{\prime}. \end{aligned}$$

Let us apply Corollary 5. It is fulfilled for \(\hat{u} ( t ) =u^{0} ( t ) = ( 0,0 ) ^{\prime}\), \(t\in T\), and for all \(\theta ( \theta,v ) \), \(\theta\in T\), \(v=(v_{1},v_{2})^{\prime}\in U\): \(0\geq0\).

Now we check the condition (11) for \(\hat{u} ( t ) \equiv{ ( 0,1 ) }^{\prime}\in U [ x^{0} ( \cdot ) ] ( t ) \), \(t\in T\). We have

$$\begin{aligned} z \bigl( 3;\hat{u},x^{0};\alpha(2,v) \bigr) &={ \bigl( v_{1},-\vert v_{1}\vert ,0 \bigr) }^{\prime} ,z \bigl( 2;\hat{u},x^{0};\alpha (1,v) \bigr) \\ &={ \bigl( v_{1},-\vert v_{1}\vert ,0 \bigr) }^{\prime},z \bigl( 3;\hat{u},x^{0};\alpha(1,v) \bigr) \\ &=\bigl(0,\vert v_{1}\vert ,-\vert v_{1}\vert \bigr)^{\prime}. \end{aligned}$$

Not continuing calculations, we get the condition (11) for \(\hat{u} ( t ) \equiv{ ( 0,1 ) }^{\prime}\), \(t\in T\), \(\theta =1\in T \) is no longer fulfilled: \(z ( 3;\hat{u},x^{0};\alpha(1,v) ) =-\vert v_{1}\vert \geq0\), \(v_{1}\in U^{\ast}\).

Consequently, the control \(u^{0} ( t ) ={ ( 0,0 ) } ^{\prime}\), \(t\in T\), is not optimal by virtue of the optimality condition (11). Note that as the right-hand side is not differentiable with respect to x, u, we cannot use the necessary optimality conditions from [1, 2, 4–6, 9, 12–18, 20, 21, 23–26].

Example 2

As an illustration of the optimality condition (24) consider the problem:

$$\begin{aligned}& x_{1} ( t+1 ) =u_{1} ( t ) ,\qquad x_{2} ( t+1 ) =x_{1} ( t ) +u_{1} ( t ) ,\qquad x_{3} ( t+1 ) =x_{2}(t)u_{2} ( t ) , \\& x_{i} ( 0 ) =0,\quad i=1,2,3,t\in T= \{ 0,1 \} ,\qquad u= ( u_{1},u_{2} ) \in U=U^{\ast}\times U^{\ast}, \\& U^{\ast}= [ -2,2 ] ,\qquad \Phi \bigl( x ( 2 ) \bigr) =x_{3}(2)\rightarrow \min. \end{aligned}$$

Let us check the control \(u^{0} ( t ) ={ ( u_{1}^{0} ( t ) ,u_{2}^{0}(t) ) ^{\prime}\equiv(0,0)}^{\prime}\), \(t\in T\), for optimality. We have (by (16), (18), (7))

$$\begin{aligned}& x^{0} ( t ) ={ ( 0,0,0 ) }^{\prime0} ( 1 ) ={ ( 0,0,-1 ) }^{\prime0} ( 0 ) = ( 0,0,0 ) ^{\prime}; \\& U \bigl[ x^{0} ( \cdot ) \bigr] (t)=\bigl\{ \hat{u}={ ( 0,{\hat {u}}_{2} ) }^{\prime}: {\hat{u}}_{2}\in U^{\ast}\bigr\} , \quad t\in T;\qquad H \bigl( \psi^{0} ( t ) ,x^{0} ( t ) ,u ( t ) ,t \bigr) \equiv0, \end{aligned}$$

\(t\in T\), \(\forall u ( t ) \in U\), \(t\in T\). Obviously, the maximum principle in the present case is ineffective: \({\Delta }_{v}H (\psi ^{0} ( t ) ,x^{0} ( t ) ,u^{0} ( t ) ,t ) \equiv0\leq0\), \(t\in T\), \(v\in U\). However, application of the optimality condition (24) for \(\hat{u} ( t ) ={ ( 0,1 ) }^{\prime}\in U [ x^{0} ( \cdot ) ] ( t )\), \(t\in T\), and \(\theta=0\) leads to the contradictory result:

$$ {\Delta }_{v}H \bigl( \hat{\psi} ( 0 ) ,x^{0} ( 0 ) ,u^{0} ( 0 ) ,0 \bigr) =-v_{1}\leq0,\quad v_{1} \in U^{\ast}. $$

Here we have taken into account that \(\hat{\psi} (0 )=(0,-1,0)^{\prime}\) and \(H (\hat{\psi} (0 ),x^{0} (0 ),v,0 )=-v_{1}\).

Therefore, the considered control \(u^{0} ( t ) = ( 0,0 ) ^{\prime}\), \(t\in T\), cannot be optimal by virtue of optimality condition (24) Note that using this example, it is easy to show the richness of the content of the optimality conditions (43), (44).

Example 3

\(x_{1} ( t+1 ) =u ( t ) \), \(x_{2} ( t+1 ) =x_{1} ( t ) \), \(x_{3} ( t+1 ) =\vert u ( t ) \vert x_{2}(t)\), \(x_{i} ( 0 ) =0\), \(i=1,2,3\), \(T=\{0,1,2\}\), \(U= [ -1,1 ] \), \(\Phi ( x ( 3 ) ) =x_{3}\rightarrow \min\).

Let us illustrate the richness of the content and application of the optimality condition (25). We study the optimality of the control \(u^{0}(t)\equiv0\), \(t\in T\). We have (by (16), (18), (7), (21)):

$$\begin{aligned}& x^{0} ( t ) ={ ( 0,0,0 ) }^{\prime},\quad t\in T\cup \{3 \} , \\& \psi^{0} ( 2 ) ={ ( 0,0,-1 ) }^{\prime 0} ( t ) ={ ( 0,0,0 ) }^{\prime},\quad t=0,1; \\& H \bigl( \psi^{0} ( t ) ,x^{0} ( t ) ,u ( t ) \bigr) \equiv0,\quad t\in T,\qquad {\Delta }_{\tilde{v}}H_{x}^{\prime } \bigl(\psi^{0} ( 1 ) ,x^{0} ( 1 ) ,u^{0} ( 1 ) ,1 \bigr) = ( 0,0,0 ) ^{\prime}, \\& {\Delta }_{\tilde{v}}H_{x}^{\prime} \bigl( \psi^{0} ( 2 ) ,x^{0} ( 2 ) ,u^{0} ( 2 ) ,2 \bigr) = \bigl( 0,-\vert \tilde{v}\vert ,0 \bigr) ^{\prime},\qquad U \bigl[ x^{0} ( \cdot ) \bigr] ( t ) = \{ 0 \} ,\quad t\in T; \\& z \bigl( \theta_{1};u^{0},x^{0},\alpha(\theta,v) \bigr) ={ ( v,0,0 ) }^{\prime},\quad \theta\in \{ 0,1 \} ,\theta _{1}=\theta +1, \\& z \bigl( 2;u^{0},x^{0};\alpha(0,v) \bigr) = { ( 0,v,0 ) }^{\prime},\qquad z \bigl( 3;u^{0},x^{0};\alpha (0,v) \bigr) ={ ( 0,0,0 ) }^{\prime}, \\& z \bigl( 3;u^{0},x^{0};\alpha(1,v) \bigr) ={ ( 0,v,0 ) }^{\prime}. \end{aligned}$$

Taking into account these calculations, it is easy to be convinced that the optimality conditions (10), (11), (15), (24) leave the control \(u^{0} ( t ) =0\), \(t\in T\), among the pretenders for optimality. It is easy to see that the optimality condition (25) is fulfilled at all possible two neighboring points. However, it is not fulfilled at \(\theta=0\), \(\theta_{k}=2\) (non-neighboring points): \(-\vert \tilde{v}\vert v\leq0\), \(v,\tilde {v}\in U= [ -1,1 ] \), i.e. the control \(u^{0} ( t ) =0\), \(t\in T\), is not optimal.