郭東生， 徐鳳

(華僑大學 信息科學與工程學院， 福建 廈門 361021)

求解時變線性不等式離散算法的設計與分析

郭東生， 徐鳳

(華僑大學 信息科學與工程學院， 福建 廈門 361021)

提出一種用于求解時變線性不等式的數值算法.通過引入一個時變向量(其每個元素都大于或等于零)，將時變線性不等式轉化為一個時變矩陣向量方程，并給出用于求解該方程的連續(xù)時間模型(即神經網絡).采用歐拉差分公式將其離散化，推導得到相應的離散算法，并通過理論分析和數值實驗驗證該離散算法的有效性.結果表明：所提出的離散算法的穩(wěn)態(tài)誤差(SSRE)具有O(τ2)的變化規(guī)律，當τ的數值減小10倍，算法的穩(wěn)態(tài)誤差可減小100倍.

線性不等式； 時變； 離散算法； 歐拉差分公式； 穩(wěn)態(tài)誤差

Abstract： A numerical algorithm for time-varying linear inequality solving is proposed. By introducing a time-varying vector (of which each element is greater than or equal to zero), we convert the time-varying linear inequality to a time-varying matrix-vector equation. A continuous-time model (i.e., the neural network) is then presented to solve such an equation. Using Euler′s difference formula to discretize the continuous-time model, we propose the corresponding discrete algorithm. Both theoretical analysis and numerical results further substantiate the efficacy of such algorithm. These results also indicate that the steady-state residual error (SSRE) of the proposed discrete algorithm changes in anO(τ2) manner with beingτthe sampling gap; when theτvalue decreases by 10 times, the SSRE reduces by 100 times.

Keywords： linear inequality； time-varying； discrete algorithm； Euler′s difference formula； steady-state residual error

近年來，不等式在科學研究和工程應用領域扮演著越來越重要的角色[1-6].在不等式的研究中，如何有效求解形如Ax≤b的線性不等式是一個重要課題，且已受到廣泛關注.對于線性不等式，許多研究學者提出了相應的求解方法[7-10]，如文獻[7]設計的迭代算法，開發(fā)的連續(xù)時間神經網絡模型，文獻[8]展示的離散時間神經網絡模型.但是，這些方法都是針對時不變線性不等式進行設計的，而對于時變線性不等式，采用前述方法進行求解得到的結果會有明顯滯后誤差[11].針對時變線性不等式的求解，文獻[11]設計一種新型神經網絡模型，并通過對比來說明該模型的有效性和優(yōu)越性.文獻[12-13]分別開發(fā)以隱式動力學方程和顯式動力學方程描述的兩種神經網絡模型.為了硬件(如數字電路)實現的目的，針對文獻[13]的神經網絡模型，本文設計開發(fā)相應的數值算法,用以求解時變線性不等式.

1 問題和模型描述

不失一般性，所研究的時變線性不等式[11-13]為

式(1)中:A(t)∈Rn×n和b(t)∈Rn分別是光滑時變的系數矩陣和向量;x(t)∈Rn是需要求解(1)得到的未知向量.需要說明的是，式(1)是一個具有代表性的時變線性不等式，文中的設計方法可拓展求解其他類型的不等式(如時變李雅普諾夫矩陣不等式[14]).為了保證式(1)中x(t)的存在，文中僅考慮系數矩陣A(t)在時間t∈[0，+∞)內是非奇異的情況.

文獻[13]展示了時變線性不等式(1)的求解可等價于時變矩陣向量方程的求解，即

式(2)中:Λ(t)=[λ1(t)，λ2(t)，…，λn(t)]T∈Rn是一個需要求解的未知向量;時變向量Λ2(t)=D(t)×Λ(t)∈Rn，其中,對角線矩陣D(t)∈Rn×n，D(t)=diag(λ1(t)，λ2(t)，…，λn(t)).

基于上述轉換，文獻[13]設計了如下的神經網絡模型，用以求解時變矩陣向量方程(2)及時變線性不等式(1)，即

定理1對于時變線性不等式(1)，給定一個光滑時變的非奇異系數矩陣A(t)∈Rn×n和一個光滑時變的系數向量b(t)∈Rn,則模型(3)的狀態(tài)向量y(t)從一個隨機產生的初始狀態(tài)y(0)∈R2n出發(fā)，收斂到時變矩陣向量方程(2)的一個精確解.該解的前n個元素組成時變線性不等式(1)一個精確的時變解.

2 新離散算法及其理論分析

式(4)中：h=τγ>0∈R為步長.式(4)便是文中所提出用以求解(1)的離散算法.

定理2所提出的離散算法是一個一致的和收斂的方法，且對于所有的時間tk∈[t0，tfinal]，以其截斷誤差O(τ2)的階數收斂.

顯然，去掉式(5)中的O(τ2)，正是文中所提出的離散算法(4).換言之，離散算法(4)的截斷誤差為O(τ2)，這表明該算法具有2階的一致性.

綜合上述分析可得，離散算法(4)是零穩(wěn)定和一致的[19].因此，所提出的離散算法(4)是一個一致的和收斂的方法，且對于所有的時間tk∈[t0，tfinal]，以其截斷誤差O(τ2)的階數收斂.證畢.

3 數值實驗驗證

對于時變線性不等式(1)，系數矩陣A(t)和向量b(t)為

當τ=0.01和h=0.5時，采用所提離散算法求解變線性不等式(1)，其數值結果如圖1所示.

(a) xk的軌跡 (b) Λk的軌跡

(c) 計算誤差的軌跡 (d) 測試誤差的軌跡圖1 采用離散算法求解時變線性不等式(1)的數值實驗結果(τ=0.01， h=0.5)Fig.1 Numerical results of using discrete algorithm (τ=0.01， h=0.5) to solve time-varying linear inequality (1)

由圖1(a),(b)可知：基于5個隨機產生的初始狀態(tài)，由離散算法計算得到的xk和Λk的狀態(tài)軌跡是時刻變化的.圖1(c)顯示了計算誤差‖ek‖2=‖Qkyk-bk‖2的變化特點，即計算誤差快速減小并維持在一個小的數值范圍內，且其最大穩(wěn)態(tài)誤差為1.056×10-3.這就意味著xk和Λk正是時變矩陣向量方程(2)的時變解.對于滿足式(2)的xk，這就是時變線性不等式(1)的一個時變解，即Akxk≤bk.

當τ=0.001和h=0.5時，采用所提離散算法求解變線性不等式(1)，其數值結果如圖2所示.

(a) xk的軌跡 (b) 計算誤差的軌跡圖2 采用離散算法求解時變線性不等式(1)的數值結果(τ=0.001， h=0.5)Fig.2 Numerical results of using discrete algorithm (τ=0.001， h=0.5) to solve time-varying linear inequality (1)

由圖2(a)可知：由離散算法計算得到xk的狀態(tài)軌跡是時變的.由圖2(b)可知：計算誤差快速減小并維持在一個小數值范圍內，且其最大穩(wěn)態(tài)誤差為1.059×10-5.顯然，這些結果再次表明離散算法能有效求解時變線性不等式(1).另外，對比圖1(c)和圖2(b)可知：隨著τ的減小(從0.01到0.001)，相應的穩(wěn)態(tài)誤差也減小(從10-3到10-5).因此，離散算法的計算性能可以通過減小τ的數值來得到提高.

為了進一步研究，采用不同的τ和h來對所提出的離散算法進行數值實驗，結果如圖3,4所示.

(a) τ=0.1 (b) τ=0.01 (c) τ=0.001圖3 不同τ值采用離散算法求解時變線性不等式(1)的誤差狀態(tài)軌跡(h=0.4)Fig.3 Error state trajectory of using discrete algorithm under different τ values (h=0.4) to solve time-varying linear inequality (1)

(a) τ=0.1 (b) τ=0.01 (c) τ=0.001圖4 不同的τ值下采用離散算法求解時變線性不等式(1)的誤差狀態(tài)軌跡(h=0.6)Fig.4 Error state trajectory of using discrete algorithm under different τ values (h=0.6) to solve time-varying linear inequality (1)

由圖3,4可知：對于固定τ的數值，采用不同的h的數值，離散算法的計算性能都有所不同(即相應的穩(wěn)態(tài)誤差都不一樣).特別地，對于固定的h，減小τ的數值，離散算法的計算性能能夠得到更有效的提高.具體而言，當τ的數值減小10倍，離散算法的穩(wěn)態(tài)誤差能夠減小100倍，即所提出的離散算法的穩(wěn)態(tài)誤差具有O(τ2)的變化規(guī)律.這也就意味著可通過合理地減小τ的值來有效地滿足應用實踐中所需要的精度.總的來說，上述的數值實驗結果很好地表明了所提出離散算法的有效性.

4 結束語

為求解時變線性不等式(1)，結合歐拉差分公式推導得到一種離散算法，并給出相應的理論結果來說明其計算性能.通過數值實驗，進一步驗證所提出的離散算法的有效性.結果表明，所提出的離散算法的穩(wěn)態(tài)誤差與采樣間隔τ具有O(τ2)的變化關系，可以有效地求解時變線性不等式(1).

[1] 莊梁，林燦煌，孫洪飛.受擾線性不確定系統魯棒H∞混合鎮(zhèn)定[J].華僑大學學報(自然科學版),2017,38(2):147-152.DOI:10.11830/ISSN.1000-5013.201702003.

[2] 朱劍峰.調和K-擬共形映照下Heinz不等式的精確估計[J].華僑大學學報(自然科學版),2014,35(3):354-357.DOI:10.11830/ISSN.1000-5013.2014.03.0354.

[3] KLAPPER A.Improved multi-covering bounds from linear inequalities and supercodes[J].IEEE Transactions on Information Theory，2004，50(3):532-536.DOI:10.1109/TIT.2004.825504.

[4] GUO Dongsheng，ZHANG Yunong.Acceleration-level inequality-based MAN scheme for obstacle avoidance of redundant robot manipulators[J].IEEE Transactions on Industrial Electronics，2014，61(12):6903-6914.DOI:10.1109/TIE.2014.2331036.

[5] GUO Dongsheng，LI Kene.Acceleration-level obstacle-avoidance scheme for motion planning of redundant robot manipulators[J].Proceedings of IEEE International Conference on Robotics and Biomimetics.Qingdao:IEEE Press，2016:1313-1318.DOI:10.1109/ROBIO.2016.7866508.

[6] XIAO Lin，ZHANG Yunong.Dynamic design， numerical solution and effective verification of acceleration-level obstacle avoidance scheme for robot manipulators[J].International Journal of Systems Science，2016，47(4):932-945.DOI:10.1080/00207721.2014.909971.

[7] YANG Kai，MURTY K G，MANGASARIAN O L.New iterative methods for linear inequalities[J].Journal of Optimization Theory and Applications，1992，72(1):163-185.DOI:10.1007/BF00939954.

[8] CICHOCKI A，BARGIELA A.Neural networks for solving linear inequality systems[J].Parallel Computing，1997，22(11):1455-1475.DOI:10.1016/S0167-8191(96)00065-8.

[9] LABONTE G.On solving systems of linear inequalities with artificial neural network[J].IEEE Transactions on Neural Networks，1997，8(3):590-600.DOI:10.1109/72.572098.

[10] XIA Youshen，WANG Jun，HUNG D L.Recurrent neural networks for solving linear inequalities and equations[J].IEEE Transactions on Circuits and Systems Ⅰ，1999，46(4):452-462.DOI:10.1109/81.754846.

[11] XIAO Lin，ZHANG Yunong.Zhang neural network versus gradient neural network for solving time-varying linear inequalities[J].IEEE Transactions on Neural Networks，2011，22(10):1676-1684.DOI:10.1109/TNN.2011.2163318.

[12] GUO Dongsheng，ZHANG Yunong.A new variant of the Zhang neural network for solving online time-varying linear inequalities[J].Proceedings of the Royal Society A，2012，468(2144):2255-2271.DOI:10.1098/rspa.2011.0668.

[13] GUO Dongsheng，ZHANG Yunong.ZNN for solving online time-varying linear matrix-vector inequality via equality conversion[J].Applied Mathematics and Computation，2015，259(C):327-338.DOI:10.1016/j.amc.2015.02.060.

[14] GUO Dongsheng，ZHANG Yunong.Zhang neural network for online solution of time-varying linear matrix inequality aided with an equality conversion[J].IEEE Transactions on Neural Networks and Learning Systems，2014，25(2):370-382.DOI:10.1109/TNNLS.2013.2275011.

[15] MATHEWS J H，FINK F D.Numerical methods using MATLAB[M].4th ed.New Jersey:Prentice Hall，2004:1-696.

[16] 張雨濃，郭東生，徐思洪,等.未知目標函數之一階數值微分公式驗證與實踐[J].甘肅科學學報，2009，21(1):13-18.DOI:10.3969/j.issn.1004-0366.2009.01.005.

[17] 張雨濃，侯占偉，郭東生.基于前向差分的一階數值微分公式驗證與實踐[J].數學的實踐與認識，2012，42(3):199-204.DOI:10.3969/j.issn.1000-0984.2012.03.031.

[18] MITRA S K.Digital signal processing: A computer-based approach[M].3rd ed.Beijing:Tsinghua University Press，2006.

[19] GRIFFITHS D F，HIGHAM D J.Numerical methods for ordinary differential equations: Initial value problems[M].London:Springer-Verlag London Ltd，2010.

(責任編輯： 陳志賢英文審校： 黃心中)

DesignandAnalysisofDiscreteAlgorithmforTime-VaryingLinearInequalitySolving

GUO Dongsheng， XU Feng

(College of Information Science and Engineering， Huaqiao University， Xiamen 361021， China)

10.11830/ISSN.1000-5013.201612043

2016-12-21

郭東生(1987-)，男，副教授，博士，主要從事神經網絡、數值算法和機器人方面的研究.E-mail:gdongsh@hqu.edu.cn.

國家自然科學基金資助項目(61603143)； 福建省自然科學基金資助項目(2016J01307)； 華僑大學中青年教師科技創(chuàng)新計劃資助項目(ZQN-YX402)； 華僑大學高層次人才科研啟動項目(15BS410)

O 221.2; TP 183

A

1000-5013(2017)05-0732-05