# A Nonlinear Projection Neural Network for Solving Interval Quadratic Programming Problems and Its Stability Analysis

Authors: Huaiqin Wu; Rui Shi; Leijie Qin; Feng Tao; Lijun He
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

This paper presents a nonlinear projection neural network for solving interval
quadratic programs subject to box-set constraints in engineering applications. Based on the Saddle point theorem, the equilibrium point of the proposed neural network is proved to be equivalent to the optimal solution of the interval quadratic optimization problems. By employing Lyapunov function approach, the global exponential stability of the proposed neural network is analyzed. Two illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.


---

## Body

## 1. Introduction

In lots of engineering applications including regression analysis, image and signal progressing, parameter estimation, filter design and robust control, and so forth [1], it is necessary to solve the following quadratic programming problem:(1.1)min12xTQx+cTx,subjecttox∈Ω,
where Q∈Rn×n, c∈Rn, and Ω is a convex set. When Q is a positive definite matrix, the problem (1.1) is said to be the convex quadratic program. When Q is a semipositive definite matrix, the problem (1.1) is said to be the degenerate convex quadratic program. In general, the matrix Q is not precisely known, but can only be enclosed in intervals, that is, Q̲≤Q≤Q¯. Such quadratic program with interval data is named as interval quadratic program usually. In the recent years, there have been some project neural network approaches for solving the problem (1.1); see, for example, [2–15], and the references therein. In [2], Kennedy and Chua presented a primal network for solving the convex quadratic program. This network contains a finite penalty parameter, so it converges an approximate solution only. To overcome the penalty parameter, in [3, 4], Xia proposed several primal projection neural networks for solving the convex quadratic program and it dual, and analyzed the global asymptotic stability of the proposed neural networks when the constraint set Ω is a box set. In [5, 6], Xia et al. presented a recurrent projection neural network for solving the convex quadratic program and related linear piecewise equation, and gave some conditions of the exponential convergence. In [7, 8], Yang and Cao presented a delayed projection neural network for solving problem (1.1), and analyzed the global asymptotic stability and exponential stability of the proposed neural networks when the constraint set Ω is a unbounded box set. In order to solve the degenerate convex quadratic program, Tao et al. [9] and Xue and Bian [10, 11] proposed two projection neural networks, and proved that the equilibrium point of the proposed neural networks was equivalent to the KT point of the quadratic programming problem. Particularly, in [10], the proposed neural network was shown to have complete convergence and finite-time convergence, and the nonsingular part of the output trajectory with respect to Q has an exponentially convergent rate. In [12, 13], Hu and Wang designed a general projection neural network for solving monotone linear variational inequalities and extended linear-quadratic programming problems, and proved that the proposed network was exponentially convergent when the constraint set Ω is a polyhedral set.In order to solve the interval quadratic program, in [14], Ding and Huang presented a new class of interval projection neural networks, and proved the equilibrium point of this neural networks is equivalent to the KT point of a class of interval quadratic program. Furthermore, some sufficient conditions to ensure the existence and global exponential stability for the unique equilibrium point of interval projection neural networks are given. To the best of the authors knowledge, the work in [14] is first to study solving the interval quadratic program by a projection neural network. However, the interval quadratic program discussed in [14] is only a quadratic program without constraints, thus has many limitations in practice. It is well known that the quadratic program with constraints is more popular.Motivated by the above discussion, in the present paper, a new projection neural network for solving the interval quadratic programming problem with box-set constraints is presented. Based on the Saddle theorem, the equilibrium point of the proposed neural network is proved to be equivalent to the KT point of the interval quadratic program. By using the fixed point theorem, the existence and uniqueness of an equilibrium point of the proposed neural network are analyzed. By constructing a suitable Lyapunov function, a sufficient condition to ensure the existence and global exponential stability for the unique equilibrium point of interval projection neural network is obtained.This paper is organized as follows. Section2 describes the system model and gives some necessary preliminaries; Section 3 gives the proof of the existence of equilibrium point of the proposed neural network, and discusses the global exponential stability of the proposed neural network; Section 4 provides two numerical examples to demonstrate the validity of the obtained results. Some conclusions are drawn in Section 5.


## 2. A Projection Neural Network Model

Consider the following interval quadratic programming problem:(2.1)min12xTQx+cTxsubjecttog≤Dx≤h,Q̲≤Q≤Q¯,
where Q=(qij)n×n, Q̲=(qij̲)n×n, Q¯=(qij¯)n×n∈Rn×n; c,g,h∈Rn, and D=diag(d1,d2,…,dn) is a positive definite diagonal matrix. Q̲≤Q≤Q¯ means qij̲≤qij≤qij¯, i,j=1,…,n. The Lagrangian function of the problem (2.1) is (2.2)L(x,u,η)=12xTQx+cTx-uT(Dx-η),Q̲≤Q≤Q¯,
where u∈Rn is referred to as the Lagrange multiplier and η∈X={u∈Rn∣g≤u≤h}. Based on the well-known Saddle point theorem [1], x* is an optimal solution of (2.1) if and only if there exist u* and η*, satisfying L(x*,u,η*)≤L(x*,u*,η*)≤L(x,u*,η), that is,(2.3)12x*TQx*+cTx*-uT(Dx*-η*)≤12x*TQx*+cTx*-u*T(Dx*-η*)≤12xTQx+cTx-u*T(Dx-η).
By the first inequality in (2.3), (u-u*)T(Dx*-η*)≥0, for all u∈Rn, hence Dx*=η*. Let f(x)=(1/2)xTQx+cTx-u*TDx. By the second inequality in (2.3), f(x*)-f(x)≤u*T(η-η*), for all x∈Rn, η∈X. If there exists x¯∈Rn such that f(x*)-f(x¯)>0, then 0<u*T(η-η*), for all η∈X, which is contradictive when η=η*. Thus, for any x∈Rn, it follows that f(x*)-f(x)≤0 and u*T(η-η*)≥0, for all η∈X.By using the project formulation [16], the above inequality can be equivalently represented as η*=PX(η*-u*), where PX(u)=[PX(u1),PX(u2),…,PX(un)]T is a project function, and, for i=1,2,…,n, (2.4)PX(ui)={gi,ui<gi,ui,gi≤ui≤hi,hi,ui>hi.
On the other hand, f(x*)≤f(x), for all x∈Rn. This implies that (2.5)∇f(x*)=Qx*+c-Du*=0.
Thus, x* is an optimal solution of (2.1) if and only if there exist u* and η*, such that (x*,u*,η*) satisfies(2.6)Dx=η,Qx+c-Du=0,η=PX(η-u).
From (2.6), it follows that Dx=PX(Dx-u). Hence, x* is an optimal solution of (2.1) if and only if there exists u* such that (x*,u*) satisfies (2.7)Qx+c-Du=0,Dx=PX(Dx-u).
Substituting u=D-1(Qx+c) into the equation Dx=PX(Dx-u), we have (2.8)Dx=PX(Dx-D-1Qx-D-1c),
where
(2.9)D-1=(1d10⋯001d2⋯0⋮⋮⋱⋮00⋯1dn),D-1Q=(1d1q111d1q12⋯1d1q1n1d2q211d2q22⋯1d2q2n⋮⋮⋱⋮1dnqn11dnqn2⋯1dnqnn).
By the above discussion, we can obtain the following proposition.Proposition 2.1.
Letx* be a solution of the project equation
(2.10)Dx=PX(Dx-D-1Qx-D-1c),
then, x* is an optimal solution of the problem (2.1).In the following, we propose a neural network, which is said to be the interval projection neural network, for solving (2.1) and (2.10), whose dynamical equation is defined as follows:
(2.11)dx(t)dt=PX(Dx-D-1Qx-D-1c)-Dx,t>t0,x(t0)=x0,Q̲≤Q≤Q¯.
The neural networks (2.11) can be equivalently written as(2.12)dxi(t)dt=PX(dixi-1di∑j=1nqijxj-cidi)-dixi,t>t0,xi(t0)=xi0,qij̲≤qij≤qij¯,i=1,…,n,j=1,…,n.
Figure 1 shows the architecture of the neural network (2.11), where M=(mij)n×n=D-D-1Q, C=D-1c, and D=(dij)n×n.Figure 1
Architecture of the proposed neural network in (2.11).Definition 2.2.
The pointx* is said to be an equilibrium point of interval projection neural network (2.11), if x* satisfies
(2.13)0=PX(Dx*-D-1Qx*-D-1c)-Dx*.By Proposition2.1 and Definition 2.2, we have the following theorem.Theorem 2.3.
The pointx* is an equilibrium point of the interval projection neural network (2.11) if and only if it is an optimal solution of the interval quadratic program (2.1).Definition 2.4.
The equilibrium pointx* of the neural network (2.11) is said to be globally exponentially stable, if the trajectory x(t) of the neural network (2.11) with the initial value x0 satisfies
(2.14)∥x(t)-x*∥≤c0exp(-β(t-t0)),∀t≥t0,
where β>0 is a constant independent of the initial value x0 and c0>0 is a constant dependent on the initial value x0. ∥·∥ denotes the 1-norm of Rn, that is, ∥x∥=∑i=1n|xi|.Lemma 2.5 (see [17]).
LetΩ⊂Rn be a closed convex set. Then,
(2.15)(v-PΩ(v))T(PΩ(v)-u)≥0,∀u∈Ω,v∈Rn,∥PΩ(u)-PΩ(v)∥≤∥u-v∥,∀u,v∈Rn,
where PΩ(u) is a project function on Ω, given by PΩ(u)=argminy∈Ω∥u-y∥.


## 3. Stability Analysis

In order to obtain the results in this paper, we make the following assumption for the neural network (2.11):(3.1)H1:qii≤di2,di2-did*<qii̲-∑j=1,j≠inqji*<di2,i=1,2,…,n,
where d*=max1≤i≤n1/di, qji*=max{|qji̲|,|qji¯|}.Theorem 3.1.
If the assumptionH1 is satisfied, then there exists a unique equilibrium point for the neural network (2.11).Proof.
Let𝒯(x)=D-1PX(Dx-D-1Qx-D-1c),x∈Rn. By Definition 2.2, it is obvious that the neural network (2.11) has a unique equilibrium point if and only if 𝒯 has a unique fixed point in Rn. In the following, by using fixed point theorem, we prove that 𝒯 has a unique fixed point in Rn. For any x,y∈Rn, by Lemma 2.5 and the assumption H1, we can obtain that
(3.2)∥𝒯(x)-𝒯(y)∥=∥D-1PX(Dx-D-1Qx-D-1c)-D-1PX(Dy-D-1Qy-D-1c)∥≤∥D-1∥∥PX(Dx-D-1Qx-D-1c)-PX(Dy-D-1Qy-D-1c)∥≤∥D-1∥∥(Dx-D-1Qx-D-1c)-(Dy-D-1Qy-D-1c)∥=∥D-1∥∥(D-D-1Q)(x-y)∥≤∥D-1∥∥D-D-1Q∥∥x-y∥=max1≤i≤n1di·max1≤i≤n(di-1diqii+1di∑j=1,j≠in|qji|)·∥x-y∥≤d*max1≤i≤n(di-1diqii̲+1di∑j=1,j≠inqji*)∥x-y∥=max1≤i≤nℓi∥x-y∥,
where ℓi=d*(di-(1/di)qii̲+(1/di)∑j=1,j≠inqji*). By the assumption H1, 0<d*(di-(1/di)qii̲+(1/di)∑j=1,j≠inqji*)<1, i=1,2,…,n. This implies that 0<max1≤i≤nℓi<1. Equation (3.2) shows that 𝒯 is a contractive mapping, and hence 𝒯 has a unique fixed point. This completes the proof.Proposition 3.2.
If the assumptionH1 holds, then for any x0∈Rn, there exists a solution with the initial value x(0)=x0 for the neural network (2.11).Proof.
Letℱ=D(𝒯-ℐ), where ℐ is an identity mapping, then ℱ(x)=PX(Dx-D-1Qx-D-1c)-Dx. By (3.2), we have
(3.3)∥ℱ(x)-ℱ(y)∥=∥D(𝒯-ℐ)(x)-D(𝒯-ℐ)(y)∥≤max1≤i≤ndi(1+max1≤i≤nℓi)∥x-y∥,∀x,y∈Rn.
Equation (3.3) means that the mapping ℱ is globally Lipschitz. Hence, for any x0∈Rn, there exists a solution with the initial value x(0)=x0 for the neural network (2.11). This completes the proof.Proposition3.2 shows the existence of the solution for the neural network (2.11).Theorem 3.3.
If the assumptionH1 is satisfied, then the equilibrium point of the neural network (2.11) is globally exponentially stable.Proof.
By Theorem3.1, the neural network (2.11) has a unique equilibrium point. We denote the equilibrium point of the neural network (2.11) by x*.
Consider Lyapunov function𝒱(t)=∥x(t)-x*∥=∑i=1n|xi(t)-xi*|. Calculate the derivative of 𝒱(t) along the solution x(t) of the neural network (2.11). When t>t0, we have
(3.4)d𝒱(t)dt=∑i=1nxi(t)-xi*|xi(t)-xi*|d(xi(t)-xi*)dt=∑i=1nxi(t)-xi*|xi(t)-xi*|(PX(dixi-1di∑j=1nqijxj-cidi)-dixi)=∑i=1nxi(t)-xi*|xi(t)-xi*|(PX(dixi-1di∑j=1nqijxj-cidi)-dixi*+dixi*-dixi)=-∑i=1ndi|xi(t)-xi*|+∑i=1nxi(t)-xi*|xi(t)-xi*|(PX(dixi-1di∑j=1nqijxj-cidi)-dixi*)≤(-min1≤i≤ndi)∑i=1n|xi(t)-xi*|+∑i=1n|PX(dixi-1di∑j=1nqijxj-cidi)-dixi*|=(-min1≤i≤ndi)∥x-x*∥+∥PX(Dx-D-1Qx-D-1c)-Dx*∥.
Noting Dx*=PX(Dx*-D-1Qx*-D-1c), by Lemma 2.5, we have
(3.5)∥PX(Dx-D-1Qx-D-1c)-Dx*∥=∥PX(Dx-D-1Qx-D-1c)-PX(Dx*-D-1Qx*-D-1c)∥≤∥(Dx-D-1Qx-D-1c)-(Dx*-D-1Qx*-D-1c)∥≤∥(D-D-1Q)(x-x*)∥≤∥D-D-1Q∥∥x-x*∥.
Hence,
(3.6)d𝒱(t)dt≤(-min1≤i≤ndi+max1≤i≤n(di-1di|qii|+1di∑j=1,j≠in|qji|))·∥x-x*∥≤(-1d*+max1≤i≤n(di-1diqii̲+1di∑j=1,j≠inqji*))·∥x-x*∥=max1≤i≤nℓi′∥x-x*∥,
where ℓi′=di-(1/di)qii̲+(1/di)∑j=1,j≠inqji*-(1/d*). By the assumption H1, ℓi′<0. Hence, max1≤i≤nℓi′<0. Let ℓ*=min1≤i≤n|ℓi′|, then ℓ*>0. Equation (3.6) can be rewritten as d𝒱(t)/dt≤-ℓ*∥x-x*∥. It follows easily that ∥x(t)-x*∥≤∥x0-x*∥exp(-ℓ*(t-t0)), for all t>t0. This shows that the equilibrium point x* of the neural network (2.11) is globally exponentially stable. This completes the proof.


## 4. Illustrative Examples

Example 4.1.
Consider the interval quadratic program defined byD=diag(2,1), g=(2,2)T, h=(3,2)T, cT=(-1,-1), Q̲=(30.10.10.7), Q¯=(3.10.20.20.8), and Q*=(qji*)=(3.10.20.20.8).The optimal solution of this quadratic program is(1,2) under Q=Q̲ or Q=Q¯. It is easy to check that(4.1)3.0<q11<3.1,q11<d12=4,0.7<q22<0.8,q22<d22=1,d12-d1d*=2<q11̲-q21*=3.0-0.2<d12=4,d22-d2d*=0<q22̲-q12*=0.7-0.2<d22=1.
The assumption H1 holds. By Theorems 3.1 and 3.3, the neural network (2.11) has a unique equilibrium point which is globally exponentially stable, and the unique equilibrium point (1,2) is the optimal solution of this quadratic programming problem.In the case ofQ=Q̲, Figure 2 reveals that the projection neural network (2.11) with random initial value (2.5,-0.5) has a unique equilibrium point (1,2) which is globally exponentially stable. In the case of Q=Q¯, Figure 3 reveals that the projection neural network (2.11) with random initial value (-2.5,3) has the same unique equilibrium point (1,2) which is globally exponentially stable. These are in accordance with the conclusion of Theorems 3.1 and 3.3.Figure 2
Convergence of the state trajectory of the neural network with random initial value (2.5,-0.5); Q=Q̲ in this example.Figure 3
Convergence of the state trajectory of the neural network with random initial value (-2.5,3); Q=Q¯ in this example.Example 4.2.
Consider the interval quadratic program defined byD=diag(1,2,2), g=(1,2,3)T, h=(2,3,4)T, cT=(1,1,1), Q̲=(0.80.20.30.230.10.30.13.5), Q¯=(0.90.30.40.33.10.20.40.23.6), and Q*=(qji*)=(0.90.30.40.33.10.20.40.23.6).The optimal solution of this quadratic program is(1,1,1.5) under Q=Q̲ or Q=Q¯. It is easy to check that(4.2)0.8<q11<0.9,q11<d12=1,3.0<q22<3.1,q22<d22=4,3.5<q33<3.6,q33<d32=4,d12-d1d*=0<q11̲-(q21*+q31*)=0.8-(0.3+0.4)<d12=1,d22-d2d*=2<q22̲-(q12*+q32*)=3.0-(0.3+0.2)<d22=4,d32-d3d*=0<q33̲-(q13*+q23*)=3.5-(0.4+0.2)<d32=4.
The assumption H1 holds. By Theorems 3.1 and 3.3, the neural network (2.11) has a unique equilibrium point which is globally exponentially stable, and the unique equilibrium point (1,1,1.5) is the optimal solution of this quadratic programming problem.In the case ofQ=Q̲, Figure 4 reveals that the projection neural network (2.11) with random initial value (-0.5,0.6,-0.8) has a unique equilibrium point (1,1,1.5) which is globally exponentially stable. In the case of Q=Q¯, Figure 5 reveals that the projection neural network (2.11) with random initial value (0.8,-0.6,0.3) has the same unique equilibrium point (1,1,1.5) which is globally exponentially stable. These are in accordance with the conclusion of Theorems 3.1 and 3.3.Figure 4
Convergence of the state trajectory of the neural network with random initial value (-0.5,0.6,-0.8); Q=Q̲ in this example.Figure 5
Convergence of the state trajectory of the neural network with random initial value (0.8,-0.6,0.3); Q=Q¯ in this example.


## 5. Conclusion

In this paper, we have developed a new projection neural network for solving interval quadratic programs, the equilibrium point of the proposed neural network is equivalent to the solution of interval quadratic programs. A condition is derived which ensures the existence, uniqueness, and global exponential stability of the equilibrium point. The results obtained are highly valuable in both theory and practice for solving interval quadratic programs in engineering.



---

*Source: 403749-2010-08-29.xml*