Keywords

1 Introduction

The paper concerns necessary (and sufficient) global optimality conditions for the following discrete optimal control problem (problem (P)):

$$\begin{aligned}&x(t+1)=f\big (t,x(t),u(t)\big ),\quad x(0)=x_0,\end{aligned}$$
(1)
$$\begin{aligned}&u(t)\in U(t),\quad t\in T, \\&J(\sigma )=l\big (x(N)\big )\rightarrow \min . \nonumber \end{aligned}$$
(2)

Here, \(x(t)\in R^n\), sets \(U(t)\subset R^m\) are compact for all \(t\in T:=\{0,\ldots ,N-1\}\). By \(\sigma \) we denote collections of vectors \(\{x(t),u(t)\}=\{x(0),\ldots ,x(N),\) \(u(0),\ldots ,u(N-1)\}\), i.e. admissible processes of problem (P) (pairs of trajectories and controls), D stands for the set of all admissible processes in problem (P), and \(\bar{\sigma }=\{\bar{x}(t),\bar{u}(t)\}\in D\) is the reference (examined) process.

The functions f(t, x, u) are assumed to be continuous with respect to (w.r.t.) (x, u) and continuously differentiable w.r.t. x for all \(t\in T\), the cost function l(x) is smooth.

First of all, we are interested in the necessary conditions for optimality of \(\bar{\sigma }\), using feedback controls \(\{v(t,x)\}\) with the property of descent w.r.t. the functional J. Such controls are constructed via special solution of discrete Hamilton-Jacobi type inequality for weakly decreasing functions \(\varphi (t,x)\) [1]. This special solution (being support majorant for the cost function J at point \(\bar{\sigma }\)) is completely defined by the trajectory \(\{\psi (t)\}\) adjoint to the process \(\bar{\sigma }\).

Being applied to classical optimal control problems in differential systems, the discussed approach leads to a rather effective and constructive necessary optimality condition. This condition, called Feedback Minimum Principle (FMP) [2, 3], essentially strengthens the Pontryagin Maximum Principle. In [1] an analogue of the feedback principle was obtained for discrete optimal control problems, linear in the state variable. The present work contains a generalization of the results [2, 3] for nonlinear discrete problem (P).

To illustrate our necessary optimality conditions, we consider certain modifications of examples from [4, 5], which were used as counter-examples for the Discrete Maximum Principle (DMP) [4,5,6,7,8]. In such modifications, necessary optimality conditions with feedback controls are more effective either if DMP is not applicable at all, or when it is not able to discard nonoptimal processes. In the second case, FMP does work and leads to an optimal process.

2 Construction of Feedback Descent Controls

For a discrete dynamic system, the property of weak decrease of a function \(\varphi (t,x): T\times R^n\rightarrow R\) means that for any initial position \((t_*,x_*)\) there exists a trajectory \(\{x(t)\}\), \(t=t_*,\ldots ,N\), \(x(t_*)=x_*\) (with a corresponding admissible control \(\{u(t)\}\), \(t=t_*,\ldots ,N-1\)) such that \(\varphi \big (t+1,x(t+1)\big )-\varphi \big (t,x(t)\big )\le 0\) for \(t=t_*,\ldots ,N\). The following Hamilton-Jacobi type inequality guarantees the property of weak decrease:

$$\begin{aligned} \min \limits _{u\in U(t)} \varphi \big (t+1,f(t,x,u)\big )-\varphi (t,x)\le 0\quad \forall x\in R^n,\; t\in T. \end{aligned}$$
(3)

Necessary optimality conditions, discussed below, use solutions of (3) under appropriate boundary conditions.

Let us describe the construction of a desired solution to inequality (3).

Introduce the Pontryagin function

$$ H(t,x,\psi ,u)=\langle \psi , f(t,x,u)\rangle , $$

the adjoint (for \(\bar{\sigma }\)) system

$$\begin{aligned} \psi (t)=H_x\big (t,\bar{x}(t),\psi (t),\bar{u}(t)\big ),\quad \psi (N)=l_x\big (\bar{x}(N)\big ) \end{aligned}$$
(4)

(note that the terminal condition corresponds to the minimum condition of the Pontryagin function in DMP) and the function

$$\begin{aligned} \varphi ^*(t,x)=\langle \psi (t)-l_x\big (\bar{x}(t)\big ), x \rangle +l(x) \end{aligned}$$
(5)

(\(\langle \cdot ,\cdot \rangle \) stands for the scalar product). Due to the terminal condition in (4), we obtain

$$\begin{aligned} \varphi ^*(N,x)=l(x). \end{aligned}$$
(6)

It is easy to see that the following equality holds:

$$\begin{aligned} \begin{array}{c} \displaystyle \sum \limits _{t\in T} \Big [\varphi ^*\Big (t+1,f\big (t,x(t),u(t)\big )\Big )-\varphi ^*\big (t,x(t)\big )\Big ]=\\ J(\sigma )-\varphi ^*(0,x_0)\quad \forall \sigma \in D. \end{array} \end{aligned}$$
(7)

Introduce the function

$$\begin{aligned} K(t,x,u)=\varphi ^*\big (t+1,f(t,x,u)\big )-\varphi ^*(t,x). \end{aligned}$$
(8)

Then, by equalities (5)–(7), one can obtain the exact formula for the increment of the cost functional J:

$$\begin{aligned} J(\sigma )-J(\bar{\sigma })=\sum \limits _{t\in T} \Big [K\big (t,x(t),u(t)\big )-K\big (t,\bar{x}(t),\bar{u}(t)\big )\Big ]\quad \forall \sigma \in D. \end{aligned}$$
(9)

Based on the previous formula (see also (7)) for any position (t, x) we define the set \(U_*(t,x)\) of feedback controls, which may generate the deepest descent for functionals (9) and (7). Evidently, if \(\bar{\sigma }\) is an optimal process, then descent controls do not exist for \(\bar{\sigma }\).

The discussed idea leads to the following multivalued \(\varphi ^*\)-extremal map:

$$\begin{aligned} U_*(t,x)=\mathop {\mathrm {Argmin}}\limits _{u\in U(t)} \Big [H\big (t,x,p(t+1),u\big )+l\big (f(t,x,u)\big )\Big ],\quad t\in T, \end{aligned}$$
(10)

where

$$ p(t)=\psi (t)-l_x\big (\bar{x}(t)\big ),\quad t=0,\ldots ,N. $$

Any sequence of vectors \(\{v(t,x)\}\), \(t\in T\), satisfying the inclusion \(v(t,x)\in U_*(t,x)\) on \(T\times R^n\), generates a trajectory \(\{x^v(t)\}\) of the discrete system

$$\begin{aligned} x(t+1)=f\Big (t,x(t),v\big (t,x(t)\big )\Big ),\quad x(0)=x_0, \end{aligned}$$
(11)

and the open-loop control \(\big \{u^v(t)=v\big (t,x^v(t)\big )\big \}\). Denote by \(D_*\) the set of sequences \(\nu =\big \{x^v(t),v(t,x)\big \}\), which may be obtained in this way. Let \(J(\nu )=l\big (x^v(N)\big )\) \(\forall \nu \in D_*\).

Theorem 1

If process \(\bar{\sigma }=\big \{\bar{x}(t),\bar{u}(t)\big \}\) is optimal for problem (P), then the following inequality holds:

$$ J(\bar{\sigma })\le J(\nu )\quad \forall \nu \in D_*. $$

In other words, there are no feedback descent controls at the point \(\bar{\sigma }\) which can be generated by the \(\varphi ^*\)-extremal map \(U_*(t,x)\).

To prove the Theorem, it is sufficient to note that any sequence \(\nu \in D_*\) generates the pair \(\sigma =\big \{x^v(t),u^v(t)\big \}\in D\) such that \(J(\sigma )=J(\nu )\).

The presented idea does not demand multifunction \(U_*(t,x)\) to be constructed by the extremal principle, at all. In fact, any map \(V(t,x)\subset U(t)\) on \(T\times R^n\) could be chosen instead of \(U_*(t,x)\). Of course, such a casual mapping V(t, x) is generically useless.

Let us show that \(\varphi ^*\)-extremal multifunction (10) for feedback descent controls corresponds to a solution of the Hamilton-Jacobi inequality (3). The latter one is designed by some “calibration” of function \(\varphi ^*\).

Let R(t) be a reachable set of system (1), (2) at t; obviously, R(t) is a compact set in \(R^n\) \(\forall t=1,\ldots ,N\). Given an open set \(Q(t)\supseteq R(t)\) for all \(t=1,\ldots ,N\), define (see also (8))

$$\begin{aligned}&m(t)=\sup \limits _{x\in Q(t)} \min \limits _{u\in U(t)} K(t,x,u),\quad t\in T,\\[10pt]&r(t)=r(t+1)-m(t),\quad r(N)=0,\\[10pt]&\widetilde{\varphi }(t,x)=\varphi ^*(t,x)-r(t),\quad (t,x)\in T\times Q(t). \end{aligned}$$

It is easy to check that function \(\widetilde{\varphi }\) satisfies the condition of weak decrease (3) on \(T\times Q(t)\), and the \(\widetilde{\varphi }\)-extremal multifunction for descent controls coincides with \(U_*(t,x)\). This reasoning provides additional justification for using the set of feedback descent controls (10).

We also stress an important role of Theorem 1 for applications. If process \(\bar{\sigma }\) does not satisfy this necessary optimality condition, then one has a process that improves \(\bar{\sigma }\) (new process has a smaller value of the cost functional J).

Example 1

Consider a modification of Example 2 from [4, p. 431], which is used to show that DMP is not applicable to problems of optimal control for systems, obtained by a difference approximation of continuous ones, in general. Modification is due to a square term in the cost function. The example illustrates the applicability of Theorem 1 in contrast to DMP.

$$\begin{aligned}&J=x^2(2)+y(2)\rightarrow \min ;\\&\displaystyle x(t+1)=x(t)+\frac{1}{2} u(t),\quad x(0)=0,\\&y(t+1)=y(t)+x^2(t)-u^2(t),\quad y(0)=0,\\&|u(t)|\le 1,\quad t=0,1. \end{aligned}$$

One can check that

$$ \min J=\min \limits _{|u(t)|\le 1,\; t=0,1} \Big \{-\frac{1}{4}\Big [2u^2(1)+\big (u(1)-u(0)\big )^2\Big ]\Big \}=-\frac{7}{4}, $$

and the minimum is attained by \(u_0^*=\pm 1\), \(u_1^*=\mp 1\).

The Pontryagin function is

$$ H=\psi (t+1)\Big [x(t)+\frac{1}{2} u(t)\Big ]+y(t)+x^2(t)-u^2(t), $$

and the adjoint system writes

$$ \psi (t)=\psi (t+1)+2x(t),\quad \psi (2)=2x(2). $$

Let us consider the process \(\bar{\sigma }\) with \(\bar{u}\equiv -1\),

$$ \begin{array}{ll} \bar{x}(1)=-\displaystyle \frac{1}{2},\quad &{} \bar{x}(2)=-1,\\ \bar{y}(1)=-1,&{} \displaystyle \bar{y}(2)=-\frac{7}{4},\\ \bar{\psi }(1)=-3,&{} \bar{\psi }(2)=-2, \end{array} $$

and \(J(\bar{\sigma })=\displaystyle -\frac{3}{4}\).

Let us test this process by the necessary optimality condition proposed Theorem 1. The selectors of \(U_*(t,x)\) are described by the following conditions:

$$ \begin{array}{lll} t=0:&{}\displaystyle \quad -u_0-\frac{3}{4} u_0^2\rightarrow \min \quad \quad &{}\Rightarrow \quad U_*(0,x_0)=\{1\};\\ t=1:&{} \displaystyle \quad -\frac{3}{4} u_1^2+x_1u_1\rightarrow \min \quad \quad &{}\Rightarrow \quad U_*(1,x_1)= \left\{ \begin{array}{ll} \{-1\},&{} x_1>0,\\ \{1\},&{} x_1<0,\\ \{-1,1\}, &{} x_1=0. \end{array} \right. \end{array} $$

Any feedback control \(v: v(t,x)\in U_*(t,x)\) generates process \(\widetilde{\sigma }\) with \(\widetilde{u}(0)=1\), \(\widetilde{u}(1)=-1\), \(\displaystyle \widetilde{x}(1)=\frac{1}{2}\), \(\displaystyle \widetilde{x}(2)=0\), \(\widetilde{y}(1)=-1\), \(\displaystyle \widetilde{y}(2)=-\frac{7}{4}\), \(J(\widetilde{\sigma })=\displaystyle -\frac{7}{4}\). Obviously, \(\widetilde{\sigma }\) brings a global solution. Notice that the optimal process \(\widetilde{\sigma }\) does not satisfy DMP.

Example 2

This example is aimed to show that Theorem 1 is rather effective to discard nonoptimal DMP-extrema (control processes satisfying DMP).

Consider the following nonconvex problem:

$$\begin{aligned}&J=y(2)-ax^2(2)\rightarrow \min ;\\&x(t+1)=x(t)+(t-1)u(t),\quad x(0)=0,\\&y(t+1)=y(t)+\big (u(t)-1\big )x(t),\quad y(0)=0,\\&|u(t)|\le 1,\quad t=0,1; \quad a>0. \end{aligned}$$

It is easy to check that

$$ \min J = \min \limits _{|u(t)|\le 1,\; t=0,1}\big \{-\big (u(1)-1\big )u(0)-au^2(0)\big \}=-2-a. $$

Let us specify some objects. The Pontryagin function:

$$ H=\psi (t+1)\big (x(t)+(t-1)u(t)\big )+y(t)+\big (u(t)-1\big )x(t), $$

and the adjoint system:

$$ \psi (t)=\psi (t+1)+u(t)-1,\quad \psi (2)=-2ax(2). $$

The H-minimum condition looks as follows: \(\big [(t-1)\psi (t+1)+x(t)\big ]u_t\rightarrow \min ;\; |u_t|\le 1\).

Consider the process \(\bar{\sigma }\): \(\bar{u}\equiv 1\), \(\bar{x}(1)=\bar{x}(2)=-1\), \(\bar{y}\equiv 0\), \(\bar{\psi }\equiv 2a\), \(J(\bar{\sigma })=-a\). Notice that \(\bar{\sigma }\) satisfies DMP.

Let us apply Theorem 1 to \(\bar{\sigma }\). The \(\varphi ^*\)-extremal map (10) is defined by the following optimization problems:

$$ \begin{array}{lll} t=0:&{} \quad -au_0^2\rightarrow \min \quad &{}\Rightarrow \quad U_*(0,x_0)=\{\pm 1\};\\[10pt] t=1:&{} \quad x_1u_1\rightarrow \min \quad &{}\Rightarrow \quad U_*(1,x_1)= \left\{ \begin{array}{ll} \{-1\},&{} x_1>0,\\[7pt] \{1\},&{} x_1<0,\\[7pt] [-1,1], &{} x_1=0. \end{array} \right. \end{array} $$

Choosing the feedback control v(t, x):

$$ v(0)=-1,\quad v(1,x)=\left\{ \begin{array}{ll}-1,\quad &{} x\ge 0,\\ 1,&{} x<0,\end{array}\right. $$

one can obtain the process \(\widetilde{\sigma }\): \(\widetilde{u}\equiv -1\), \(\widetilde{x}(1)=\widetilde{x}(2)=1\), \(\widetilde{y}(1)=0\), \(\widetilde{y}(2)=-2\) with \(J(\widetilde{\sigma })=-2-a<-a=J(\bar{\sigma })\).

Thus, Theorem 1 leads to the global extremum \(\widetilde{\sigma }\), starting from \(\bar{\sigma }\).

3 Feedback Minimum Principle

In continuous optimal control problems, FMP [2, 3] states that an optimal trajectory of the considered problem is necessarily optimal for a certain auxiliary problem of dynamic optimization, called the accessory one. Moreover, the analogue of Theorem 1 was covered by FMP. Below we show that for discrete optimization problems the situation is significantly different compared to the continuous case. However, this is not surprising: for example, in continuous optimization problems, the Pontryagin Maximum Principle is a universal necessary condition, but in discrete problems, it is not always the case [4,5,6,7,8].

Denote by \((P_*)\) the following discrete problem of closed-loop (feedback) control:

$$ J(\nu ):=l\big (x(N)\big )\rightarrow \min ,\quad \nu \in D_*, $$

where pairs \(\nu =\{x(t), v(t,x)\}\) satisfy system (11) and the inclusion \(v(t,x)\in U_*(t,x)\) on \(T\times R^n\).

In general, the pair \(\big \{\bar{x}(t), \bar{u}(t)\big \}\) is not admissible in problem \((P_*)\). The following minimum condition \(M(\bar{\sigma })\) guarantees that \(\bar{\sigma }\in D_*\):

$$ \bar{u}(t)\in U_*\big (t,\bar{x}(t)\big )\quad \forall t\in T. $$

By (10), \(M(\bar{\sigma })\) is equal to the condition

$$\begin{aligned}&H\big (t,\bar{x}(t),p(t+1),\bar{u}(t)\big )+l\Big (f\big (t,\bar{x}(t),\bar{u}(t)\big )\Big )=\\&\min \limits _{u\in U(t)} \Big [H\big (t,\bar{x}(t),p(t+1),u\big )+l\Big (f\big (t,\bar{x}(t),u\big )\Big )\Big ]\quad \forall t\in T. \end{aligned}$$

Given a process \(\bar{\sigma }\) satisfying condition \(M(\bar{\sigma })\), introduce the feedback control \(\bar{v}(t,x)\in U_*(t,x)\) in the following way:

$$\begin{aligned} \bar{v}(t,x)=\left\{ \begin{array}{ll} \bar{u}(t),&{} (t,x)\in \text{ orb } \bar{x}(t),\\ \text{ any } w(t,x)\in U_*(t,x),&{} (t,x)\notin \text{ orb } \bar{x}(t), \end{array} \right. \end{aligned}$$
(12)

where \(\text{ orb } \bar{x}(t)=\big \{\left. \big (t,\bar{x}(t)\big )\,\right| \, t=0,\ldots ,N\big \}\) is the orbit of trajectory \(\bar{x}(t)\).

It is easy to see that \(\bar{\nu }=\big \{\bar{x}(t),\bar{v}(t,x)\big \}\in D_*\). Then by Theorem 1 one can derive FMP as follows:

Theorem 2

Let process \(\bar{\sigma }=\big \{\bar{x}(t),\bar{u}(t)\big \}\) be optimal for problem (P) and satisfy the minimum condition \(M(\bar{\sigma })\). Then process \(\bar{\nu }=\big \{\bar{x}(t),\bar{v}(t,x)\big \}\) with control (12) is optimal for problem \((P_*)\).

In the assumptions of this theorem, problem \((P_*)\) appears to be accessory (for \(\bar{\sigma }\)) in the classical sense. It means that \((P_*)\) is a variational type problem, designed to analyze the optimality of process \(\bar{\sigma }\).

FMP, generalizing Theorem 1, is a very attractive theoretical result. However, it is difficult to solve the accessory problem in practice. Therefore, in applications, one normally applies Theorem 1 instead of Theorem 2 (using the “trial and error” method when choosing selectors of multifunction \(U_*(t,x)\)). In addition, the class of problems, for which FMP is valid, is restricted by condition \(M (\bar{\sigma })\). Although this condition is often met, it is not necessary at all (see Example 2, where process \(\bar{\sigma }\) with \(\bar{u}\equiv 1\) is admissible in problem \((P_*)\) but does not solve it).

Example 3

Consider a modification of Example 6.46 from [5, Vol. II, p. 249] which shows a failure of DMP for optimal processes. At the same time, FMP holds here for some values of parameters.

$$\begin{aligned}&J=x^2(3)+y(3)\rightarrow \min ;\\&x(t+1)=g\big (t,u(t)\big ),\quad x(0)=0,\\&y(t+1)=ax^2(t)+by(t)-\displaystyle \frac{a}{b}g^2\big (t,u(t)\big ),\quad y(0)=0,\\&u(t)\in U,\quad t=0,1,2; \quad a>0,\;b>0, \end{aligned}$$

the function \(g(t,\cdot )\) is continuous, the set U is compact.

$$ \min J=\min \limits _{u(2)\in U} \frac{b-a}{b} g^2\big (2,u(2)\big ). $$

It means that any admissible process \(\bar{\sigma }\) with \(\bar{u}(2)\in \mathop {\mathrm {Argmin}}\limits _{u\in U} \displaystyle \frac{b-a}{b} g^2\big (2,u(2)\big )\) is optimal.

The Pontryagin function is

$$ H=\psi (t+1)g\big (t,u(t)\big )+\xi (t+1)\Big [ax^2(t)+by(t)-\frac{a}{b}g^2\big (t,u(t)\big )\Big ] $$

(here, \(\xi (t)\) is the adjoint of y).

Let us consider any optimal process and denote it by \(\bar{\sigma }=\big (\bar{x}(t),\bar{y}(t),\bar{u}(t)\big )\). The corresponding trajectory \((\bar{\psi },\bar{\xi })\) of adjoint system (4) is

$$ \begin{array}{lll} \bar{\psi }(1)=2abg\big (0,\bar{u}(0)\big ),\quad &{} \bar{\psi }(2)=2ag\big (1,\bar{u}(1)\big ),\quad &{} \bar{\psi }(3)=2g\big (2,\bar{u}(2)\big ),\\ \bar{\xi }(1)=b^2,&{} \bar{\xi }(2)=b,&{} \bar{\xi }(3)=1. \end{array} $$

One can check that \(\bar{\sigma }\) does not satisfy DMP. Moreover, for \(t=0,1\), the Pontryagin function H reaches on \(\bar{u}(t)\) its maximum (rather than minimum), and the H-minimum conditions are as follows:

$$ \begin{array}{ll} t=0:&{} \quad ab\Big [2g\big (0,\bar{u}(0)\big )g\big (0,u_0\big )-g^2\big (0,u_0\big )\Big ]\rightarrow \min ,\quad u_0\in U; \\ t=1:&{} \quad a\Big [2g\big (1,\bar{u}(1)\big )g\big (1,u_1\big )-g^2\big (1,u_1\big )\Big ]\rightarrow \min ,\quad u_1\in U. \end{array} $$

When \(t=2\), the “\(H\rightarrow \min \)” condition takes the form

$$ 2g\big (2,\bar{u}(2)\big )g\big (2,u_2\big )-\frac{a}{b}g^2\big (2,u_2\big )\rightarrow \min ,\quad u_2\in U. $$

Therefore, all optimal processes do not satisfy DMP.

Let us check FMP for optimal process \(\bar{\sigma }\). The \(\varphi ^*\)-extremal multifunction (10) leads to the following conditions:

$$ \begin{array}{ll} t=0:&{} \quad (ab-1)\Big [2g\big (0,\bar{u}(0)\big )g\big (0,u_0\big )-g^2\big (0,u_0\big )\Big ]\rightarrow \min ,\quad u_0\in U; \\ t=1:&{} \quad (a-1)\Big [2g\big (1,\bar{u}(1)\big )g\big (1,u_1\big )-g^2\big (1,u_1\big )\Big ]\rightarrow \min ,\quad u_1\in U;\\ t=2:&{} \quad \displaystyle \frac{b-a}{b}g^2\big (2,u_2\big )\rightarrow \min ,\quad u_2\in U \end{array} $$

(compare with the previous formulas). It means that condition \(M(\bar{\sigma })\) is satisfied and \(\bar{\sigma }\) is admissible for problem \((P_*)\) only when \(a\le 1\) and \(ab\le 1\). By the way, the conditions of Theorem 1 for \(\bar{\sigma }\) are evidently relaxed.

Example 4

Now we propose another case, where Theorems 1 and 2 accompany one another. Consider the following modification of Example 3 from [4, p. 432]:

$$\begin{aligned}&J=ax^2(2)+y(2)\rightarrow \min ;\\&x(t+1)=2u(t),\quad x(0)=0,\\&y(t+1)=y(t)+x^2(t)-u^2(t),\quad y(0)=0,\\&|u(t)|\le 1,\quad t=0,1; \quad a\in R. \end{aligned}$$

Obviously,

$$ \min J=\min \limits _{|u(t)|\le 1,\; t=0,1} \Big \{3u^2_0+(4a-1)u^2_1\Big \}. $$

Therefore, the minimizing controls are the following:

  • if \(\displaystyle a>\frac{1}{4}\), then \(u^*\equiv 0\);

  • if \(\displaystyle a=\frac{1}{4}\), then \(u^*_0=0\), \(u^*_1\in [-1,1]\);

  • if \(\displaystyle a<\frac{1}{4}\), then \(u^*_0=0\), \(u^*_1\in \{-1,1\}\).

Any optimal process \(\bar{\sigma }\) does not satisfy DMP for \(a>0\), but it satisfies condition \(M(\bar{\sigma })\) and Theorems 1 and 2 (\(\forall a\)). However, in the case \(a<\displaystyle \frac{1}{4}\) the condition \(M(\sigma )\) does not hold for the process \(\sigma \equiv 0\). Nevertheless, by applying Theorem 1 the process \(\sigma \) could be discarded.

4 Comparison with Known Necessary Optimality Conditions

Theorems 1 and 2 offer certain necessary conditions for global optimality, and the scope of application of constructive Theorem 1 is unlimited. As is known [6], only necessary conditions for a weak minimum have similar universality—in the class of sufficiently small variations \(|x (t) - \bar{x} (t) |\) and \( | u (t) - \bar{u} (t)|\) for all t. Therefore, these local conditions of optimality are less effective than those obtained above (both theoretically and practically).

The DMP is a necessary condition for a strong minimum (variations \(|u (t) - \bar{u} (t)| \) do not have to be small), and in this sense DMP is more attractive than the conditions for a weak minimum. However, this criterion is not universal—it is valid for problem (P) under certain convexity conditions on the set \( f \big (t, x, U (t) \big ) \); the simplest of these conditions is the convexity of \( f \big (t, x, U (t) \big ) \) \( \forall x \in R^n \) and \( t \in T \). Theorems 1 and 2 do not imply these assumptions; however, FMP contains the assumption \( M (\bar{\sigma }) \) on the reference process. Therefore, a direct comparison of FMP with DMP in their applicability is difficult. However, as the examples show, the combination of Theorems 1 and 2 exceeds DMP (for problems where DMP is applicable) in efficiency. Note also that in the case when l is linear, condition \( M (\bar{\sigma }) \) coincides with the extremal condition from DMP, but, along with \( M (\bar{\sigma }) \), FMP requires \(\bar{\sigma }\) to be optimal for the accessory problem \( (P_*) \). This fact essentially strengthens the necessary condition.

The previous examples show that FMP is more applicable than DMP. The case of linear cost function can be found, e.g., in [1] (this example coincides with Example 2, excepting the linear cost function \(J=y(2)\)). Now, we present another eloquent case:

Example 5

This quadratic modification of Example 8 by [4, p. 433] presents the situation when all optimal processes do not satisfy DMP, while FMP does hold for each one.

$$\begin{aligned}&J=x^2(2)+y(2)\rightarrow \min ;\\&x(t+1)=u(t),\quad x(0)=0,\\&y(t+1)=y(t)+x^2(t),\quad y(0)=0,\\&u(t)\in \{-1,+1\},\quad t=0,1. \end{aligned}$$

Notice that any admissible process is optimal.

The Pontryagin function is

$$ H=\psi (t+1)u(t)+x^2(t)+y(t), $$

and the adjoint system takes the form:

$$ \psi (t)=2x(t),\quad \psi (2)=2x(2). $$

It is notable that any optimal process \(\bar{\sigma }\) does not satisfy the DMP:

$$ 2\bar{x}(t+1)u_t\rightarrow \min \quad \Rightarrow \quad u^*_t=-\mathrm{sign\,}\bar{u}(t). $$

At the same time, FMP holds for all optimal processes: \(M(\bar{\sigma })\) and FMP lead to the condition

$$ u_t^2\rightarrow \min ;\quad u_t\in \{-1,+1\}. $$

5 Sufficient Optimality Conditions

We proceed with the natural inequality

$$ \varDelta J(\bar{\sigma })=J(\sigma )-J(\bar{\sigma })\ge 0\quad \forall \sigma \in D, $$

where the increment \(\varDelta J(\bar{\sigma })\) is described by the exact formula (9) (see also (5) and (8)).

Let R(t) denote a compact reachable set of discrete system (1), (2) at time t, and \(E(t)\supseteq R(t)\) be its outer estimate by some compact set \(E(t)\subset R^n\) (here, \(t=1,\ldots ,N\)). Introduce the function

$$\begin{aligned} \mu (t)=\min \limits _{(x,u)\in E(t)\times U(t)} K(t,x,u). \end{aligned}$$
(13)

Represent this formula in a more traditional form — introduce the following objects:

$$\begin{aligned} h(t,x,\psi )=\min \limits _{u\in U(t)} \Big [ H(t,x,\psi ,u)+l\big (f(t,x,u)\big )\Big ] \end{aligned}$$
(14)

(an analogue of the lower Hamiltonian of problem (P)),

$$\begin{aligned} \mathcal K(t,x)=h\big (t,x,p(t+1)\big ) -l(x)-\langle p(t), x\rangle \end{aligned}$$
(15)

(the extended lower Hamiltonian). So, function \(\mu (t)\) from (13) can be defined in the following way:

$$\begin{aligned} \mu (t)=\min \limits _{x\in E(t)} \mathcal K(t,x),\quad t=1,\ldots ,N. \end{aligned}$$
(16)

By the definition of function \(\mu (t)\) and formula (9), one obtains the following sufficient optimality condition:

Theorem 3

Let a process \(\bar{\sigma }=\big \{\bar{x}(t),\bar{u}(t)\big \}\) satisfy the minimum condition:

$$ \mathcal K\big (t,\bar{x}(t)\big )=\mu (t),\quad t=1,\ldots ,N, $$

where functions \(\mathcal K\) and \(\mu \) are defined by equalities (13)–(16) on some compact sets \(E(t)\supseteq R(t)\), \(t=1,\ldots ,N\). Then \(\bar{\sigma }\) is optimal for (P).

Theorem 3 gives a first-order sufficient optimality condition, since it uses only the first derivatives of the input data. However, no convexity assumptions are imposed.

Note that these conditions are well combined with the necessary conditions of Theorems 1 and 2, since they are formulated in the same constructions: FMP can be applied iteratively. Assumed that these iterations stop, the resulting process can be checked for optimality by Theorem 3.

6 Conclusion

In the paper nonlocal necessary and sufficient optimality conditions with feedback comparison controls are obtained for nonconvex discrete control problems. The main results are related to the necessary optimality conditions in the class of feedback descent controls (Theorems 1 and 2). These conditions are constructive, independent of DMP, and lead to an efficient iterative algorithm for improving the control (see, e.g., [9]).

This algorithm seems efficient for solving complex discrete control problems with terminal constraints on trajectory, using the methods of penalty functions, modified Lagrangians, etc. Indeed, in all these methods, the associated problems of unconditional optimization should be also solved globally.

Theoretically, it is of interest to generalize Theorems 1 and 2 to more complex problems with constraints, analyze the connection with the quasi-maximum condition [5, 7] (the influence of the time quantization frequency on the optimality conditions), the effect of relaxation of the problem, etc. These questions are also important for the theory of optimal control in differential systems.