# Discrete-Time Zhang Neural Networks for Time-Varying Nonlinear Optimization

Authors: Min Sun; Maoying Tian; Yiju Wang
Journal: Discrete Dynamics in Nature and Society
 (2019)

---

## Abstract

As a special kind of recurrent neural networks, Zhang neural network (ZNN) has been successfully applied to various time-variant problems solving. In this paper, we present three Zhang et al. discretization (ZeaD) formulas, including a special two-step ZeaD formula, a general two-step ZeaD formula, and a general five-step ZeaD formula, and prove that the special and general two-step ZeaD formulas are convergent while the general five-step ZeaD formula is not zero-stable and thus is divergent. Then, to solve the time-varying nonlinear optimization (TVNO) in real time, based on the Taylor series expansion and the above two convergent two-step ZeaD formulas, we discrete the continuous-time ZNN (CTZNN) model of TVNO and thus get a special two-step discrete-time ZNN (DTZNN) model and a general two-step DTZNN model. Theoretical analyses indicate that the sequence generated by the first DTZNN model is divergent, while the sequence generated by the second DTZNN model is convergent. Furthermore, for the step-size of the second DTZNN model, its tight upper bound and the optimal step-size are also discussed. Finally, some numerical results and comparisons are provided and analyzed to substantiate the efficacy of the proposed DTZNN models.


---

## Body

## 1. Introduction

As a subcase of nonlinear programming, nonlinear optimization has been widely encountered in a variety of scientific and engineering applications, and many applications can be modeled or reformulated as nonlinear optimization, e.g., the Markowitz mean-variance model in finance, the transportation problem in management, the shortest path in network model, the (non)convex separable optimization in image denoising, etc. [1, 2]. Due to its fundamental roles, nonlinear optimization has been extensively studied by many researchers during the last several centuries, and many efficient algorithms have been developed and investigated in the literature [3–7], which can be classified into two categories. The first category includes the first-order iteration methods, which only use the first derivative information of the objective function, such as the steepest descent method, the conjugate gradient method, and the memory gradient method. These methods are suitable to solve large-scale nonlinear optimization due to their simple structure and low storage. Numerically the conjugate gradient method and the memory gradient method usually perform better than the steepest descent method [6]. The second category includes the Newton method and its variants, e.g., the quasi-Newton BFGS and DFP methods, which need to compute the second derivative of the objective function or an approximation of it. Therefore they are not suitable to solve large scale nonlinear optimization though they possess locally fast convergent rate. Then, to overcome the drawback of the quasi-Newton method, Nocedal [7] designed a limited memory BFGS method (L-BFGS) for nonlinear optimization, and numerical results indicate that the L-BFGS method is very efficient due to its low storage. In addition, during the last decades neural network has drawn extensive attention of researchers and practitioners due to its nice properties, e.g., distributed storage, high-speed parallel-processing, hardware applications, and superior performance in large-scale online applications [8]. Some neural networks have been developed to solve nonlinear optimization during the last decades [9–11].Most of the above algorithms are designed intrinsically for solving static nonlinear optimization (SNO); therefore they might not be effective enough for solving time-varying nonlinear optimization (TVNO), whose objective function, denoted byf(x(t),t), is a multivariate function with respect to the decision variable x and the time variable t. The connection between SNO and TVNO is obvious: (1) SNO is a special case of TVNO, and when x(t)=x for any t≥0, TVNO reduces to SNO; (2) the discrete-time form of TVNO, whose objective function is f(xk,tk)(tk=kτ,k=0,1,…) and τ>0 denoting the sampling gap, can be viewed as a sequence of SNO. At each single time instant t=tk, TVNO can be viewed as a static nonlinear optimization, and consequently it can be solved by the above mentioned algorithms. However this treatment is not advisable due to the following three reasons: (1) it is usually inefficient and lowly precise due to it need to solve a sequence of SNO [12]; (2) in the online solution process of discrete-time TVNO, the present and/or previous data with respect to xi(i≤k) should be used sufficiently to generate the unknown decision variable xk+1; (3) most importantly, at time instant tk, we do not know the future information such as the function values f(x(tk+1),tk+1), and only the current and past information for time instances tj with j≤k can be used. Therefore, the conventional static methods and the neural networks in [9–11], which are based on the future information, cannot solve TVNO.As a special recurrent neural network, Zhang neural network (ZNN), named after Chinese scholar Zhang Yunong, serves as a unified approach to solve various online time-varying problems, such as time-varying quadratic function minimization [13], future minimization [14], time-varying matrix pseudoinversion [8], and TVNO [12, 15, 16]. For example, based on ZNN, Jin et al. [15] presented a one-step discrete-time ZNN (DTZNN) model for TVNO, whose maximal residual error is theoretically O(τ2). Subsequently, Guo et al. [12] proposed two DTZNN models for TVNO, which belong to three-step DTZNN with steady-state residual error (SSRE) changing in an O(τ3) manner. Then, quite recently Zhang et al. [16] presented a general four-step discrete-time derivative dynamics model and a general four-step DTZNN model for TVNO; both models contain a free parameter which can take any values of the interval (1/12,1/6) and is convergent with truncation error of O(τ4).Generally speaking, in the real-time solution process of TVNO, the more the past data is utilized, the smaller the truncation error of the corresponding Zhang et al. discretization (ZeaD) formula is. For example, the truncation errors of the one-step DTZNN model in [15], the three-step DTZNN models in [12], the general three-step DTZNN models in [17], and the four-step DTZNN models in [16] are O(τ2),O(τ3),O(τ3), and O(τ4), respectively. The corresponding ZeaD formulas are summarized in Table 1, in which the effective domains of the parameter a1 in [17] and [16] are (-∞,0) and (1/12,1/6), respectively. Obviously, the general ZeaD formula with a1=-1/2,-1/10 in [17] reduces the two special ZeaD formulas in [12].Table 1
ZeaD formulas used in [12, 15–17].
Formula n-step General form Truncation error [15] f ˙ k = f k + 1 - f k τ 1 No O(τ2) [12] f ˙ k = 2 f k + 1 - 3 f k + 2 f k - 1 - f k - 2 2 τ 3 No O(τ3) [12] f ˙ k = 6 f k + 1 - 3 f k - 2 f k - 1 - f k - 2 10 τ 3 No O(τ3) [17] f ˙ k = ( - a 1 + 1 / 2 ) f k + 1 + 3 a 1 f k - ( 3 a 1 + 1 / 2 ) f k - 1 + a 1 f k - 2 τ 3 Yes O(τ3) [16] f ˙ k = ( a 1 + 1 / 3 ) f k + 1 - ( 4 a 1 - 1 / 2 ) f k + ( 6 a 1 - 1 ) f k - 1 τ - ( 4 a 1 - 1 / 6 ) f k - 2 - a 1 f k - 3 τ 4 Yes O ( τ 4 )In this paper we are going to further study the ZeaD formula, and three ZeaD formulas are presented, including a special two-step ZeaD formula with truncation errorO(τ3), a general two-step ZeaD formula with truncation error O(τ2), and a general five-step ZeaD formula with truncation error O(τ5). We prove that the first two ZeaD formulas is convergent while the third ZeaD formula is not zero-stable and thus is divergent. Then, based on the Taylor series expansion and the above two convergent ZeaD formulas, we discrete the continuous-time ZNN (CTZNN) model for TVNO and thus get a special two-step DTZNN model and a general two-step DTZNN model for TVNO. Theoretical analyses indicate that the first DTZNN model is divergent, while the second DTZNN model is convergent for any a1∈(-1/2,+∞) and the step-size h∈(0,(2+4a1)/(1+a1)). In addition, the tight upper bound of the step-size h and the optimal step-size are also discussed.The rest of the paper is organized as follows. We first recall some basic definitions and results in Section2, including problem formulation of TVNO, continuous-time ZNN (CTZNN) model for TVNO, and the general n-step ZeaD formula. In Section 3, a special two-step ZeaD formula with truncation error of O(τ3) and a general two-step ZeaD formula with truncation error of O(τ2) are presented and analyzed, and we also prove that the five-step ZeaD formula with truncation error of O(τ5) or O(τ6) is divergent in this section. Furthermore, based on the two convergent ZeaD formulas, two discrete-time ZNN (DTZNN) models for TVNO are presented, and we prove that the first DTZNN model is not convergent and the second DTZNN is convergent. Later, in Section 4, some numerical experiments are presented to illustrate and compare the performances of the convergent two-step DTZNN model with other variants. Finally, a concluding remark with future research direction is given in Section 5. The main contributions of this paper are summarized as follows.(1) Three ZeaD formulas are presented, including a special two-step ZeaD formula, a general two-step ZeaD formula, and a general five-step ZeaD formula, whose convergence and stability are discussed in detail.(2) Two DTZNN models are given to solve TVNO based on two convergent two-step ZeaD formulas, whose convergence is also studied in detail.(3) The feasible region of the step-sizeh in the convergent DTZNN model is studied, and its tight upper bound and the optimal step-size are also discussed.(4) The high precision of the convergent DTZNN model is substantiated in numerical tests.


## 2. Preliminaries

In this section, the results in [12, 16] are summarized for the foundation of further discussion, including the problem formulation of TVNO, the CTZNN model for TVNO, and the general ZeaD formula.Firstly, the problem formulation of the TVNO is as follows [16]:(1)minxt∈Rn⁡fxt,t∈R,t∈0,tf,where the time-varying nonlinear function f(·,·):Rn×[0,tf]→R is second-order differentiable and bounded. Problem (1) aims to find x(t)∈Rn such that the function f(x(t),t) achieves its minimum at any time t≥0. Thus in the sequent analyse, we assume that the solution of problem (1) exists at any time t≥0.It is well known that it is often hard to find the global optimum solution of time-invariant nonlinear optimization by traditional numerical algorithms [3, 6]. Therefore, researchers have resorted to find the stationary point of time-invariant nonlinear optimization. We also transform problem (1) into finding its stationary point x(t), which satisfies the following nonlinear equations:(2)gxt,t≐∂fxt,t∂xt=0∈Rn,∀t∈0,tf,where symbol ≐ denotes the computational assignment operation. In the following, we aim to find the solutions of problem (2) at any time t≥0. Generally speaking, the solutions of problem (1) are the solutions of problem (2), but the inverse may be not, and if f(x(t),t) is convex with respect to x(t), the inverse also holds [3].Settinge(t)=g(x(t),t) in the following Zhang neural network (ZNN) design formula [18](3)e˙t≐detdt=-γet,γ>0,we get the following continuous-time ZNN (CTZNN) model of problem (1) [15](4)x˙t=-Hxt,t-1γgxt,t+gtxt,t,where gt(x(t),t) is the partial derivative of the mapping g(x(t),t) with respect to its second variable t, i.e.,(5)gtxt,t=∂gxt,t∂t=∂2fxt,t∂xt∂t=∂2f∂x1∂t,∂2f∂x2∂t,…,∂2f∂xn∂t⊤∈Rn,and H(x(t),t) is the Hessian matrix of problem (1), i.e.,(6)
H
x
t
,
t
=
∂
2
f
∂
x
1
∂
x
1
∂
2
f
∂
x
1
∂
x
2
⋯
∂
2
f
∂
x
1
∂
x
n
∂
2
f
∂
x
2
∂
x
1
∂
2
f
∂
x
2
∂
x
2
⋯
∂
2
f
∂
x
2
∂
x
n
⋮
⋮
⋱
⋮
∂
2
f
∂
x
n
∂
x
1
∂
2
f
∂
x
n
∂
x
2
⋯
∂
2
f
∂
x
n
∂
x
n
∈
R
n
×
n
,which is assumed to be positive definite throughout the paper to ensure that the stationary point x(t) of problem (1) is also its solution.Remark 1.
The main difference of the CTZNN model (4) and the neural network models in [9–11] lies in the former including the information of the time derivative gt(x(t),t) to get fast and accurate solution of TVNO, while the motion equation in the latter neural network models for SNO and other optimization problems, such as variational inequalities and complementarity problems, can be expressed by(7)x˙t=Fx,and F(x):Rn→Rn, which is a mapping with respect to the decision variable x and is an implicit function with respect to t. Furthermore, it generally satisfies F(x∗)=0, where x∗ is a solution of problem solving. When x(t)=x for any t≥0, that is to say that TVNO only contains the decision variable x and thus reduces to SNO, the CTZNN model (4) reduces to(8)x˙t=-γHx-1gx.Obviously -γHx∗-1g(x∗)=0 for any x∗ being a solution of SNO; thus the CTZNN model (4) becomes a special neural network for SNO when x(t)=x for any t≥0.The generaln-step ZeaD formula is defined as follows [19]:(9)fk˙=1τ∑i=1n+1aifk-n+i+Oτp,where n is the amount of the steps of ZeaD formula (9); ai∈R(i=1,2,…,n+1) denotes the coefficients; O(τp) denotes the truncation error; fk is the value of f(t) at time instant tk=kτ, i.e., fk=f(tk); k denotes the updating index. Equation (9) with a1≠0,an+1≠0 is termed as n-step pth-order ZeaD formula.


## 3. Multistep ZeaD Formulas and Discrete-Time Models

In this section, we first propose two two-step ZeaD formulas with truncation error ofO(τ3) and O(τ2) and prove that the five-step ZeaD formula with truncation error of O(τ5) or O(τ6) is not convergent. Then, two DTZNN models for TVNO are presented and analyzed subsequently.


### 3.1. Concepts of Convergence of Discrete-Time Models

The following concepts about zero-stability and consistency are used to analyze the theoretical results of our proposed discrete-time models [20].Concept 1.
The zero-stability of ann-step discrete-time method(10)xk+1+∑i=1nαixk+1-i=τ∑i=0nβivk+1-ican be checked by determining the roots of the characteristic polynomial P(υ)=υn+∑i=1nαkυn-i. If the roots of P(υ)=0 are such that(i)
all roots lie in the unit disk, i.e.,υ≤1,(ii)
any roots on the unit circle (i.e.,υ=1) are simple (i.e., not multiple),
then, then-step discrete-time method is zero-stable.Concept 2.
Ann-step discrete-time method is said to be consistent with order p, if its truncation error is O(τp) with p>0 for the smooth exact solution.Concept 3.
For ann-step discrete-time method, it is convergent, i.e., x[t-t0/τ]→x∗(t) for all t∈[t0,tf], as τ→0, if and only if such an algorithm is zero-stable and consistent (see Concepts 1 and 2). That is, zero-stability and consistency result in convergence. In particular, a zero-stable and consistent method converges with the order of its truncation error.


### 3.2. Multistep ZeaD Formulas

Based on the Taylor series expansion(11)fk+1=fk+τfk˙+τ22fk¨+τ33!fk⃛+…+τmm!fkm+Oτm+1,where m is a nonnegative integer, we can derive the two-step ZeaD formula, which is presented in the following lemma.Lemma 2 (see [21]).
The two-step ZeaD formula with truncation error ofO(τ3) can be expressed as(12)fk˙=fk+1-fk-12τwhich is convergent, and the general two-step ZeaD formula with truncation error of O(τ2) can be expressed as(13)fk˙=1+a1fk+1-1+2a1fk+a1fk-1τ,which is convergent for any a1∈(-1/2,+∞)\{0}.Proof.
The proof is presented in AppendixA.After we received the reviewers’ comments on the paper, we were brought to the attention of the references [21, 22], which have presented the rigorous proofs of Lemma 2 and the following Lemma 5. However, for the completeness of the paper, we have decided to give the proofs in the Appendix.Remark 3.
Ifa1=0, then the general two-step ZeaD formula (13) reduces to the one-step ZeaD formula in [15](14)xk+1=xk-Hxk,tk-1hgxk,tk+τgtxk,tk.Then, in the following the effective domain of a1 is set as (-1/2,+∞).Corollary 4.
For any fixed and sufficiently small sampling gapτ>0, the truncation error of the general two-step ZeaD formula (13) is decreasing as the parameter a1→-1/2+.Proof.
For any fixed and sufficiently small sampling gapτ>0, from the proof of Lemma 2, the truncation error is dominated by the term(15)a1+12τ2fk¨,which obviously becomes smaller as a1→-1/2+.The following theorem reveals that five-step ZeaD formula with truncation error ofO(τ5) or O(τ6) is not convergent.Lemma 5 (see [22]).
Five-step ZeaD formula with truncation error ofO(τ5) or O(τ6) is not convergent.Proof.
The proof is presented in AppendixB.Remark 6.
The polynomial (B.15) (see Appendix B) has five roots, which are denoted by γi(a6)(i=1,2,…,5). Defining the moduli maximum function as(16)Qa6=max⁡γia6∣i=1,2,…,5.Figure1 shows the graph of the function A(a6), from which we observe that Q(a6) is always bigger than 1 except a6=0. However, from the definition of the general n-step ZeaD formula, we have that a6≠0.Figure 1
The graph of the moduli maximum functionQ(a6).


### 3.3. Discrete-Time ZNN Models

In this subsection, two discrete-time ZNN (DTZNN) models are presented for TVNO based on the two convergent two-step ZeaD formulas (12) and (13).Firstly, applying the two-step2th-order ZeaD formula (12) to discretize the CTZNN model (4), we get the following DTZNN model for TVNO:(17)xk+1=xk-1-Hxk,tk-1hgxk,tk+2τgtxk,tk,where the step-size h=2τγ>0.Similarly, applying the general two-step1th-order ZeaD formula (13) to discretize the CTZNN model (4), we get the following DTZNN model for TVNO:(18)xk+1=1+2a11+a1xk-a11+a1xk-1-Hxk,tk-1hgxk,tk+τ1+a1gtxk,tk,where the step-size h=τγ/(1+a1)>0 and a1∈(-1/2,+∞).Remark 7.
(I) The DTZNN models (17) and (18) can also be used to solve SNO. In this case, gt(xk,tk)=0, and thus as pointed in [12], the DTZNN model (17) reduces to xk+1=xk-1-hHxk,tk-1g(xk,tk). Furthermore, when h=1, we have(19)xk+1=xk-1-Hxk,tk-1gxk,tk,which is exactly the Newton algorithm for SNO [3]. Furthermore, in this case, the DTZNN model (18) reduces to(20)xk+1=1+2a11+a1xk-a11+a1xk-1-hHxk,tk-1gxk,tk,which can be viewed a two-step iterative method for SNO when a1≠-1/2.
(II) The iterative schemes of DTZNN models (17) and (18) are similar to those of discrete neural network (DNN) models in [9–11], which are obtained by discreting the motion equation of neural network (7) by the Euler method, and can be expressed by(21)xk+1=Gxk,tk,where G(x):Rn→Rn. Generally, the sequence {xk} generated by the iterative scheme (21) converges globally to a solution of the static problem solving, while in the following we shall prove that the sequence generated by the DTZNN model (18) is convergent in the sense that the sequence of steady-state residual error (SSRE) gxk,tk2 converges to zero with order O(τ2). In fact, the following Theorem 9 indicates that g(xk,tk)2 can be written as gxk,tk2=c1r1k+c2r2k+O(τ2), where max⁡r1,r2<1. Therefore, at the time instant tk (for sufficiently large k), the generated iterate xk can approximate the solution x∗(tk) of TVNO with high precision when the sampling gap τ is sufficiently small, such as τ=0.01,0.001.Theorem 8.
Suppose{(xk,tk)} is the sequence generated by the two-step DTZNN model (17), and let g(xk,tk)2 be the generated steady-state residual error (SSRE). Then the sequence gxk,tk2 is divergent.Proof.
LetΔxk=xk+1-xk and Δxk-1=xk-xk-1. Then, the proposed two-step DTZNN model (17) can be reformulated as(22)12Δxk+12Δxk-1=-Hxk,tk-1h2gxk,tk+τgtxk,tk.On the other hand, by the Taylor series expansion, we have(23)gxk+1,tk+1=gxk,tk+Hxk,tkΔxk+τgtxk,tk+Oτ2,and(24)gxk-1,tk-1=gxk,tk-Hxk,tkΔxk-1-τgtxk,tk+Oτ2,where O(Δxk2) and O(Δxk-12) are absorbed into O(τ2) as they are assumed to be of the same order of magnitude [20]. By the algebraic manipulation “(23)/2 − (24)/2,” the following results can be obtained:(25)12gxk+1,tk+1-12gxk-1,tk-1=12Hxk,tkΔxk+Δxk-1+τgtxk,tk+Oτ2,which together with (22) implies(26)12gxk+1,tk+1-12gxk-1,tk-1=-h2gxk,tk+Oτ2,i.e.,(27)gxk+1,tk+1-Oτ2-gxk-1,tk-1-Oτ2=-hgxk,tk-Oτ2.Setting Gk=g(xk+1,tk+1)-O(τ2), (27) can be written as(28)Gk+1+hGk-Gk-1=0.The characteristic equation of the difference equation (28) is(29)λ2+hλ-1=0,which has two different real roots from the discriminant Δ=h2+4>0. By [23], at least one root of the real quadratic equation (29) is greater than or equal to one in modulus. Thus, the sequence {Gk} is divergent, so is the sequence {g(xk,tk)}. The proof is completed.Theorem 9.
Suppose{(xk,tk)} is the sequence generated by the two-step DTZNN model (18), and let g(xk,tk)2 be the generated steady-state residual error (SSRE). Then for any a1∈(-1/2,+∞) and the step-size h∈(0,(2+4a1)/(1+a1)), we have that limk→∞⁡g(xk,tk)2} is of order O(τ2), and thus the sequence {g(xk,tk)2} convergence of order O(τ2) is to zero.Proof.
LetΔxk=xk+1-xk and Δxk-1=xk-xk-1. Then, the two-step DTZNN model (18) can be reformulated as(30)1+a1Δxk-a1Δxk-1=-Hxk,tk-11+a1hgxk,tk+τgtxk,tk.By the algebraic manipulation “(1+a1)× (23)+a1× (24),” we get the following equation: (31)1+a1gxk+1,tk+1+a1gxk-1,tk-1=1+2a1gxk,tk+Hxk,tk1+a1Δxk-a1Δxk-1+τgtxk,tk+Oτ2,which together with (30) implies(32)1+a1gxk+1,tk+1+a1gxk-1,tk-1=1+2a1-1+a1hgxk,tk+Oτ2,i.e.,(33)gxk+1,tk+1-Oτ2+a11+a1gxk-1,tk-1-Oτ2)=1+2a1-1+a1h1+a1gxk,tk-Oτ2).Similarly, letting Gk=g(xk+1,tk+1)-O(τ2), (33) can be written as(34)Gk+1-1+2a1-1+a1h1+a1Gk+a11+a1Gk-1=0.The characteristic equation of the difference equation (34) is(35)λ2-1+2a1-1+a1h1+a1λ+a11+a1=0.By [23], two roots of (35) are less than one in modulus if and only if(36)a11+a1<1,1+2a1-1+a1h1+a1<1+a11+a1.Obviously, the first inequality always holds for any a1>-1/2; therefore we only analyze the second inequality, which is equivalent to(37)1+2a1-1+a1h<1+a1+a1,and thus(38)1+2a1-1+a1h<1+2a1.So(39)0<h<2+4a11+a1.Then, the sequence {Gk} is convergent for any a1∈(-1/2,+∞) and step-size h∈(0,(2+4a1)/(1+a1)), so is the sequence {g(xk,tk)}. The proof is completed.Obviously, two initial states (i.e.,x0,x1) are needed to start the iteration of the DTZNN model (18). We use the following DTZNN model [15] to initiate the iterative computation:(40)x1=x0-Hx0,t0-1hgx0,t0+τgtx0,t0.Remark 10.
The upper bound of the step-sizeh, that is, (2+4a1)/(1+a1), is an increasing function with respect to the parameter a1, and when a1→+∞, it converges to 4.The following theorem shows that the upper bound of the step-sizeh, that is, (2+4a1)/(1+a1), is tight.Theorem 11.
For anya1>-1/2, if h≥(2+4a1)/(1+a1), then the sequence {g(xk,tk)2} generated by the DTZNN model (18) does not converge to zero.Proof.
Ifh≥(2+4a1)/(1+a1), then the characteristic equation of the difference equation (34) reduces to(41)λ2+1+2a11+a1λ+a11+a1=0,which has two different real roots(42)λ1=-1,λ2=-a11+a1.Thus the general solution of the difference equation (34) is(43)Gk=c1-1k+c2a11+a1k,where c1,c2 are two arbitrary constant which are determined by two initial states x0,x1. So, the limit of the sequence {Gk} general does not exist except c1=0, which indicates that the sequence {g(xk,tk)2} generally does not converge to zero. This completes the proof.In the remainder of this subsection, let us investigate the optimal step-size for givena1∈(-1/2,+∞). The discriminant of (35) is(44)Δ=11+a12h¯2-21+2a1h¯+1,where h¯=(1+a1)h∈(0,2+4a1). Set Δ1=h¯2-2(1+2a1)h¯+1, which is a quadratic function with respect to h¯, and its discriminant is(45)Δ¯=4a11+a1.The following analyses are divided into two cases according to the sign of Δ¯.(1) Ifa1∈(-1/2,0), Δ¯ is less than zero, and thus Δ is positive, which indicates that (35) has two different real roots, which are denoted by λ1,λ2. Therefore, it holds that(46)λ1+λ2=-1+2a1-1+a1h1+a1,λ1λ2=a11+a1,and the second equation indicates that λi(i=1,2) have contrary sign; then we assume that λ1>0,λ2<0 without loss of generality. Furthermore, for any a1∈(-1/2,0) and the step-size h∈(0,(2+4a1)/(1+a1)), from Theorem 9, we have 0≤λi<1(i=1,2). The general solution of (34) can be written as(47)Gk=c1λ1k+c2λ2k,which together with (46) results in the following model to determine the optimal step-size(48)minc1λ1k+c2λ2ks.t.λ1+λ2=-1+2a1-1+a1h1+a1,λ1λ2=a11+a1,0<λ1<1,-1<λ2<0,0<h<2+4a11+a1.However, the nonlinear optimization problem (48) is often difficult to solve, and in the following we give an intuitive analyses about the optimal step-size. Obviously, the smaller max⁡{λ1,λ2} is, the smaller the term Gk is. Thus, under the constraint conditions of (48), we aim to minimize the term λ1-λ2 and equivalently minimize the term λ1-λ22, which can be written as (49)λ1-λ22=λ1-λ22-4λ1λ2,=Δ=11+a121+a12h2-21+a11+2a1h+1.Obviously λ1-λ22 obtains the minimum value at h∗=(1+2a1)/(1+a1)∈(0,(2+4a1)/(1+a1)).(2) Ifa1∈[0,+∞), Δ¯ is nonnegative. (I) For any h∈(1+2a1+a11+a1/(1+a1),(2+4a1)/(1+a1)), Δ>0. Similar to the above analyse, the optimal step-size can be approximately by h∗ which belongs to the interval ((1+2a1+a1(1+a1))/(1+a1),(2+4a1)/(1+a1)). (II) For any h∈(0,(1+2a1+a1(1+a1))/(1+a1)],Δ≤0, which indicates that (35) has a multiple root or two complex conjugate roots, which are denoted by λ1,λ2 again and satisfy λ1=λ2. Then, according to the general solution formula of the difference equation, we minimize λ12 to approximate the optimal step-size. Obviously λ12=a1/(1+a1), which is independent of the step-size h; therefore the optimal step-size can also be approximated by h∗.Overall, we get the following theorem.Theorem 12.
For any givena1∈(-1/2,+∞), the optimal step-size of the DTZNN model (18) can be approximated by h∗=(1+2a1)/(1+a1).


## 3.1. Concepts of Convergence of Discrete-Time Models

The following concepts about zero-stability and consistency are used to analyze the theoretical results of our proposed discrete-time models [20].Concept 1.
The zero-stability of ann-step discrete-time method(10)xk+1+∑i=1nαixk+1-i=τ∑i=0nβivk+1-ican be checked by determining the roots of the characteristic polynomial P(υ)=υn+∑i=1nαkυn-i. If the roots of P(υ)=0 are such that(i)
all roots lie in the unit disk, i.e.,υ≤1,(ii)
any roots on the unit circle (i.e.,υ=1) are simple (i.e., not multiple),
then, then-step discrete-time method is zero-stable.Concept 2.
Ann-step discrete-time method is said to be consistent with order p, if its truncation error is O(τp) with p>0 for the smooth exact solution.Concept 3.
For ann-step discrete-time method, it is convergent, i.e., x[t-t0/τ]→x∗(t) for all t∈[t0,tf], as τ→0, if and only if such an algorithm is zero-stable and consistent (see Concepts 1 and 2). That is, zero-stability and consistency result in convergence. In particular, a zero-stable and consistent method converges with the order of its truncation error.


## 3.2. Multistep ZeaD Formulas

Based on the Taylor series expansion(11)fk+1=fk+τfk˙+τ22fk¨+τ33!fk⃛+…+τmm!fkm+Oτm+1,where m is a nonnegative integer, we can derive the two-step ZeaD formula, which is presented in the following lemma.Lemma 2 (see [21]).
The two-step ZeaD formula with truncation error ofO(τ3) can be expressed as(12)fk˙=fk+1-fk-12τwhich is convergent, and the general two-step ZeaD formula with truncation error of O(τ2) can be expressed as(13)fk˙=1+a1fk+1-1+2a1fk+a1fk-1τ,which is convergent for any a1∈(-1/2,+∞)\{0}.Proof.
The proof is presented in AppendixA.After we received the reviewers’ comments on the paper, we were brought to the attention of the references [21, 22], which have presented the rigorous proofs of Lemma 2 and the following Lemma 5. However, for the completeness of the paper, we have decided to give the proofs in the Appendix.Remark 3.
Ifa1=0, then the general two-step ZeaD formula (13) reduces to the one-step ZeaD formula in [15](14)xk+1=xk-Hxk,tk-1hgxk,tk+τgtxk,tk.Then, in the following the effective domain of a1 is set as (-1/2,+∞).Corollary 4.
For any fixed and sufficiently small sampling gapτ>0, the truncation error of the general two-step ZeaD formula (13) is decreasing as the parameter a1→-1/2+.Proof.
For any fixed and sufficiently small sampling gapτ>0, from the proof of Lemma 2, the truncation error is dominated by the term(15)a1+12τ2fk¨,which obviously becomes smaller as a1→-1/2+.The following theorem reveals that five-step ZeaD formula with truncation error ofO(τ5) or O(τ6) is not convergent.Lemma 5 (see [22]).
Five-step ZeaD formula with truncation error ofO(τ5) or O(τ6) is not convergent.Proof.
The proof is presented in AppendixB.Remark 6.
The polynomial (B.15) (see Appendix B) has five roots, which are denoted by γi(a6)(i=1,2,…,5). Defining the moduli maximum function as(16)Qa6=max⁡γia6∣i=1,2,…,5.Figure1 shows the graph of the function A(a6), from which we observe that Q(a6) is always bigger than 1 except a6=0. However, from the definition of the general n-step ZeaD formula, we have that a6≠0.Figure 1
The graph of the moduli maximum functionQ(a6).


## 3.3. Discrete-Time ZNN Models

In this subsection, two discrete-time ZNN (DTZNN) models are presented for TVNO based on the two convergent two-step ZeaD formulas (12) and (13).Firstly, applying the two-step2th-order ZeaD formula (12) to discretize the CTZNN model (4), we get the following DTZNN model for TVNO:(17)xk+1=xk-1-Hxk,tk-1hgxk,tk+2τgtxk,tk,where the step-size h=2τγ>0.Similarly, applying the general two-step1th-order ZeaD formula (13) to discretize the CTZNN model (4), we get the following DTZNN model for TVNO:(18)xk+1=1+2a11+a1xk-a11+a1xk-1-Hxk,tk-1hgxk,tk+τ1+a1gtxk,tk,where the step-size h=τγ/(1+a1)>0 and a1∈(-1/2,+∞).Remark 7.
(I) The DTZNN models (17) and (18) can also be used to solve SNO. In this case, gt(xk,tk)=0, and thus as pointed in [12], the DTZNN model (17) reduces to xk+1=xk-1-hHxk,tk-1g(xk,tk). Furthermore, when h=1, we have(19)xk+1=xk-1-Hxk,tk-1gxk,tk,which is exactly the Newton algorithm for SNO [3]. Furthermore, in this case, the DTZNN model (18) reduces to(20)xk+1=1+2a11+a1xk-a11+a1xk-1-hHxk,tk-1gxk,tk,which can be viewed a two-step iterative method for SNO when a1≠-1/2.
(II) The iterative schemes of DTZNN models (17) and (18) are similar to those of discrete neural network (DNN) models in [9–11], which are obtained by discreting the motion equation of neural network (7) by the Euler method, and can be expressed by(21)xk+1=Gxk,tk,where G(x):Rn→Rn. Generally, the sequence {xk} generated by the iterative scheme (21) converges globally to a solution of the static problem solving, while in the following we shall prove that the sequence generated by the DTZNN model (18) is convergent in the sense that the sequence of steady-state residual error (SSRE) gxk,tk2 converges to zero with order O(τ2). In fact, the following Theorem 9 indicates that g(xk,tk)2 can be written as gxk,tk2=c1r1k+c2r2k+O(τ2), where max⁡r1,r2<1. Therefore, at the time instant tk (for sufficiently large k), the generated iterate xk can approximate the solution x∗(tk) of TVNO with high precision when the sampling gap τ is sufficiently small, such as τ=0.01,0.001.Theorem 8.
Suppose{(xk,tk)} is the sequence generated by the two-step DTZNN model (17), and let g(xk,tk)2 be the generated steady-state residual error (SSRE). Then the sequence gxk,tk2 is divergent.Proof.
LetΔxk=xk+1-xk and Δxk-1=xk-xk-1. Then, the proposed two-step DTZNN model (17) can be reformulated as(22)12Δxk+12Δxk-1=-Hxk,tk-1h2gxk,tk+τgtxk,tk.On the other hand, by the Taylor series expansion, we have(23)gxk+1,tk+1=gxk,tk+Hxk,tkΔxk+τgtxk,tk+Oτ2,and(24)gxk-1,tk-1=gxk,tk-Hxk,tkΔxk-1-τgtxk,tk+Oτ2,where O(Δxk2) and O(Δxk-12) are absorbed into O(τ2) as they are assumed to be of the same order of magnitude [20]. By the algebraic manipulation “(23)/2 − (24)/2,” the following results can be obtained:(25)12gxk+1,tk+1-12gxk-1,tk-1=12Hxk,tkΔxk+Δxk-1+τgtxk,tk+Oτ2,which together with (22) implies(26)12gxk+1,tk+1-12gxk-1,tk-1=-h2gxk,tk+Oτ2,i.e.,(27)gxk+1,tk+1-Oτ2-gxk-1,tk-1-Oτ2=-hgxk,tk-Oτ2.Setting Gk=g(xk+1,tk+1)-O(τ2), (27) can be written as(28)Gk+1+hGk-Gk-1=0.The characteristic equation of the difference equation (28) is(29)λ2+hλ-1=0,which has two different real roots from the discriminant Δ=h2+4>0. By [23], at least one root of the real quadratic equation (29) is greater than or equal to one in modulus. Thus, the sequence {Gk} is divergent, so is the sequence {g(xk,tk)}. The proof is completed.Theorem 9.
Suppose{(xk,tk)} is the sequence generated by the two-step DTZNN model (18), and let g(xk,tk)2 be the generated steady-state residual error (SSRE). Then for any a1∈(-1/2,+∞) and the step-size h∈(0,(2+4a1)/(1+a1)), we have that limk→∞⁡g(xk,tk)2} is of order O(τ2), and thus the sequence {g(xk,tk)2} convergence of order O(τ2) is to zero.Proof.
LetΔxk=xk+1-xk and Δxk-1=xk-xk-1. Then, the two-step DTZNN model (18) can be reformulated as(30)1+a1Δxk-a1Δxk-1=-Hxk,tk-11+a1hgxk,tk+τgtxk,tk.By the algebraic manipulation “(1+a1)× (23)+a1× (24),” we get the following equation: (31)1+a1gxk+1,tk+1+a1gxk-1,tk-1=1+2a1gxk,tk+Hxk,tk1+a1Δxk-a1Δxk-1+τgtxk,tk+Oτ2,which together with (30) implies(32)1+a1gxk+1,tk+1+a1gxk-1,tk-1=1+2a1-1+a1hgxk,tk+Oτ2,i.e.,(33)gxk+1,tk+1-Oτ2+a11+a1gxk-1,tk-1-Oτ2)=1+2a1-1+a1h1+a1gxk,tk-Oτ2).Similarly, letting Gk=g(xk+1,tk+1)-O(τ2), (33) can be written as(34)Gk+1-1+2a1-1+a1h1+a1Gk+a11+a1Gk-1=0.The characteristic equation of the difference equation (34) is(35)λ2-1+2a1-1+a1h1+a1λ+a11+a1=0.By [23], two roots of (35) are less than one in modulus if and only if(36)a11+a1<1,1+2a1-1+a1h1+a1<1+a11+a1.Obviously, the first inequality always holds for any a1>-1/2; therefore we only analyze the second inequality, which is equivalent to(37)1+2a1-1+a1h<1+a1+a1,and thus(38)1+2a1-1+a1h<1+2a1.So(39)0<h<2+4a11+a1.Then, the sequence {Gk} is convergent for any a1∈(-1/2,+∞) and step-size h∈(0,(2+4a1)/(1+a1)), so is the sequence {g(xk,tk)}. The proof is completed.Obviously, two initial states (i.e.,x0,x1) are needed to start the iteration of the DTZNN model (18). We use the following DTZNN model [15] to initiate the iterative computation:(40)x1=x0-Hx0,t0-1hgx0,t0+τgtx0,t0.Remark 10.
The upper bound of the step-sizeh, that is, (2+4a1)/(1+a1), is an increasing function with respect to the parameter a1, and when a1→+∞, it converges to 4.The following theorem shows that the upper bound of the step-sizeh, that is, (2+4a1)/(1+a1), is tight.Theorem 11.
For anya1>-1/2, if h≥(2+4a1)/(1+a1), then the sequence {g(xk,tk)2} generated by the DTZNN model (18) does not converge to zero.Proof.
Ifh≥(2+4a1)/(1+a1), then the characteristic equation of the difference equation (34) reduces to(41)λ2+1+2a11+a1λ+a11+a1=0,which has two different real roots(42)λ1=-1,λ2=-a11+a1.Thus the general solution of the difference equation (34) is(43)Gk=c1-1k+c2a11+a1k,where c1,c2 are two arbitrary constant which are determined by two initial states x0,x1. So, the limit of the sequence {Gk} general does not exist except c1=0, which indicates that the sequence {g(xk,tk)2} generally does not converge to zero. This completes the proof.In the remainder of this subsection, let us investigate the optimal step-size for givena1∈(-1/2,+∞). The discriminant of (35) is(44)Δ=11+a12h¯2-21+2a1h¯+1,where h¯=(1+a1)h∈(0,2+4a1). Set Δ1=h¯2-2(1+2a1)h¯+1, which is a quadratic function with respect to h¯, and its discriminant is(45)Δ¯=4a11+a1.The following analyses are divided into two cases according to the sign of Δ¯.(1) Ifa1∈(-1/2,0), Δ¯ is less than zero, and thus Δ is positive, which indicates that (35) has two different real roots, which are denoted by λ1,λ2. Therefore, it holds that(46)λ1+λ2=-1+2a1-1+a1h1+a1,λ1λ2=a11+a1,and the second equation indicates that λi(i=1,2) have contrary sign; then we assume that λ1>0,λ2<0 without loss of generality. Furthermore, for any a1∈(-1/2,0) and the step-size h∈(0,(2+4a1)/(1+a1)), from Theorem 9, we have 0≤λi<1(i=1,2). The general solution of (34) can be written as(47)Gk=c1λ1k+c2λ2k,which together with (46) results in the following model to determine the optimal step-size(48)minc1λ1k+c2λ2ks.t.λ1+λ2=-1+2a1-1+a1h1+a1,λ1λ2=a11+a1,0<λ1<1,-1<λ2<0,0<h<2+4a11+a1.However, the nonlinear optimization problem (48) is often difficult to solve, and in the following we give an intuitive analyses about the optimal step-size. Obviously, the smaller max⁡{λ1,λ2} is, the smaller the term Gk is. Thus, under the constraint conditions of (48), we aim to minimize the term λ1-λ2 and equivalently minimize the term λ1-λ22, which can be written as (49)λ1-λ22=λ1-λ22-4λ1λ2,=Δ=11+a121+a12h2-21+a11+2a1h+1.Obviously λ1-λ22 obtains the minimum value at h∗=(1+2a1)/(1+a1)∈(0,(2+4a1)/(1+a1)).(2) Ifa1∈[0,+∞), Δ¯ is nonnegative. (I) For any h∈(1+2a1+a11+a1/(1+a1),(2+4a1)/(1+a1)), Δ>0. Similar to the above analyse, the optimal step-size can be approximately by h∗ which belongs to the interval ((1+2a1+a1(1+a1))/(1+a1),(2+4a1)/(1+a1)). (II) For any h∈(0,(1+2a1+a1(1+a1))/(1+a1)],Δ≤0, which indicates that (35) has a multiple root or two complex conjugate roots, which are denoted by λ1,λ2 again and satisfy λ1=λ2. Then, according to the general solution formula of the difference equation, we minimize λ12 to approximate the optimal step-size. Obviously λ12=a1/(1+a1), which is independent of the step-size h; therefore the optimal step-size can also be approximated by h∗.Overall, we get the following theorem.Theorem 12.
For any givena1∈(-1/2,+∞), the optimal step-size of the DTZNN model (18) can be approximated by h∗=(1+2a1)/(1+a1).


## 4. Numerical Results

In this section, we present some numerical results to substantiate the efficiency and superiority of the proposed DTZNN model (18) (denoted by DTZNN-I) for TVNO and compared with the one-step DTZNN model (14) (denoted by DTZNN-II) in [15]. All the numerical experiments are performed on an Thinkpad laptop with Intel Core 2 CPU 2.10 GHZ and RAM 4.00 GM. All the programs are written in Matlab R2014a.Consider the following TVNO [16]:(50)minx∈R4⁡fxt,t=x1t+10sin⁡πt402+x2t+t42+x3t-exp⁡-t42+0.025t-1x3tx4t+x1t+ln⁡sin⁡πt40+12x2t+sin⁡t8+cos⁡t82-x1t+x1t+sintx3t+x4t+exp⁡-t42,and we can get its stationary point by Matlab, which is omitted due to its complicated expression. Now, we use DTZNN-I and DTZNN-II to solve problem (50), and the parameters are set as follows: τ=0.01s or 0.001s, h=0.1, and a1=-1/3. The initial state vector x0=x(0)=1,2,3,4⊤ with time duration being 10s. The trajectories of SSRE g(xk,tk)2 of TVNO problem (50) generated by the two tested DTZNN models are depicted in Figure 2.Figure 2
Trajectories of SSREg(xk,tk)2 of problem (50) generated by the DTZNN models (14) and (18), left τ=0.01, right τ=0.001.Figure2 illustrates that the performance of the DTZNN model (18) with a1=-1/3 is better than that of the DTZNN model (14), and both generated SSREs converge to zero in an O(τ2) manner. So when the sampling gap τ>0 decreases, both SSREs can be made sufficiently small.Figure3 depicts the trajectories of the theoretical solution xi∗(tk)(i=1,2,3,4) of problem (50) and xi(tk)(i=1,2,3,4) generated by the DTZNN model (18) with a1=-1/3,τ=0.01, which shows that the numerical results generated by the DTZNN model (18) approximate the theoretical solution xi∗(tk)(i=1,2,3,4) with high accuracy.Figure 3
Trajectories ofxi∗(tk)(i=1,2,3,4) and xi(tk)(i=1,2,3,4) generated by the DTZNN models (14) and (18) and their difference for problem (50).Figure4 shows the trajectories of f(xk,tk) generated by the two tested models and their differences when τ=0.01, from which we can find that f(xk,tk) generated by the DTZNN-I model is generally smaller than that generated by the DTZNN-II model, which means that the former is more accurate than the latter.Figure 4
Trajectories off(xl,tk) generated by the DTZNNs model (18) for problem (50).Now, let us verify Theorem11, and we compare the numerical results generated by the DTZNN model (18) with τ=0.01,a1=-1/2,h=0.1 and those generated by the DTZNN model (18) with τ=0.01,a1=-1/3,h=(2+4a1)/(1+a1)=1. The numerical results are depicted in Figure 5, from which we find that the generated sequence gxk,tk2 does not converge to zero when a1=-1/2 or h is equal to the upper bound (2+4a1)/(1+a1), and these are consistent to Theorem 11.Figure 5
Trajectories of SSREg(xk,tk)2 generated by the DTZNN model (18) for problem (50).In the remainder of this section, let us verify Theorem12 with τ=0.01,a1=-1/3,h=0.1 and the optimal step-size h=0.5 for fixed a1=-1/3. The numerical results are depicted in Figure 6, which shows the performance of the DTZNN model with h=0.5 is better than that of the DTZNN model with h=0.1, and this is consistent to Theorem 12.Figure 6
Trajectories of SSREg(xk,tk)2 generated by the DTZNN model (18) with different step-size for problem (50).


## 5. Conclusion

In this paper, we have investigated a convergent two-step ZeaD formulas with truncation error ofO(τ3), a convergent general two-step ZeaD formula with truncation error of O(τ2) and a general five-step ZeaD formula with truncation error of O(τ5), which is not convergent. Then, based on the two convergent ZeaD formulas, we presented two DTZNN models for TVNO and proved that one is divergent and the other with the free parameter a1∈(-1/2,+∞) and step-size 0<h<(2+4a1)/(1+a1) is convergent. We also proved that (2+4a1)/(1+a1) is tight upper bound of h and (1+2a1)/(1+a1) is the optimal step-size. Numerical results illustrate that the proposed DTZNN model is efficient for solving TVNO.In the future the following two issues related to this paper deserve further studying: (I) Theorem12 only considers the optimal step-size for any given a1∈(-1/2,0), and therefore we need to study the optimal step-size for any given a1∈(0,+∞); (II) the general three-step DTZNN model and the general four-step DTZNN model proposed in [16, 17] both do not give the relationship of the free parameter a1 and step-size h, and therefore we are going to extend the technique used in Theorems 8 and 9 to study the two general multistep DTZNN models and explore the relationship of the parameter a1 and the step-size h.



---

*Source: 4745759-2019-04-08.xml*