一类非线性方程和非线性不等式问题的数值算法研究
|
摘要
本文主要探讨求解对称非线性方程组和非线性不等式组的算法.
第一章,我们研究求解对称非线性方程组的基于信赖域搜索的修正牛顿算法.首先将对称非线性方程组的求解等价转换为求解无约束最优化问题的全局最优解.之后,我们提出一个基于信赖域搜索的修正牛顿算法来求解对称非线性方程组,该算法通过求解一个非线性方程组来确定搜索方向,并且算法产生的序列包含于一个有界的水平集中.我们在适当的条件下证明了该算法具备全局收敛的性质和局部二次收敛速度.还选取了两个实验算例来验证算法,并在问题维数为10,100,200,300,400,500等情况下分别做了数值实验,每次实验都选取了5组不同的初始值以此来验证算法的有效性.
第二章,我们讨论求解非线性不等式组的模拟退火混合遗传算法.首先将非线性不等式组等价转换成一个非光滑方程组,然后借助光滑化辅助函数将问题等价转换成求解光滑的无约束最小化问题,并在此基础上提出模拟退火混合遗传算法.该算法具有遗传算法和模拟退火算法所具备的全局搜索能力,又弥补了遗传算法容易早熟的缺陷,数值实验有力地说明了算法的有效性.
第三章,我们总结全文,并介绍该课题尚待解决的问题和对未来研究工作的展望.
In this thesis, the algorithms for solving symmetric nonlinear equations and nonlinear inequalities problems are discussed.
In chapter one, a trust-region-based modified Newton method for solving sym-metric nonlinear equations is studied. At first, the symmetric nonlinear equations are reformulated as a kind of unconstrained optimization problem. Then the trust-region-based modified Newton method is presented for solving symmetric nonlinear equations. In this algorithm, the searching direction by solving nonlinear equations. Besides, the iteration sequences generated by this algorithm are included in a level set which is bounded. The sequences generated by this algorithm globally converge to the solution of symmetric nonlinear equations under some additional assump-tions. What's more, this algorithm has the property of local quadratic convergence. Two examples are quoted as the numerical examples which are computed under different dimensions of the problems including 10,100,200,300,400 and 500 with five sets of initial values, which powerfully illustrate the efficiency of the algorithm presented.
In chapter two, an adaptive simulated annealing floating point genetic algo-rithm for solving nonlinear inequalities problem is studied. At first, the nonlinear inequalities problems are reformulated as a set of nonsmoothing equations, then by making use of the smoothing auxiliary function the problem was equally converted as the smoothing unconstrained optimization problems. Based on this transformula-tion, the adaptive simulated annealing floating point genetic algorithm is presented, which not only posses the global searching capability of adaptive simulated an-nealing algorithm and genetic algorithm, but also make up the shortage of genetic algorithm. In the end, the numerical experiment powerfully illustrate the efficiency of the algorithm presented.
In chapter three, the whole thesis is generated. Besides the unsolved problems in this field and some suggestions for our further study are also pointed out.
第一章,我们研究求解对称非线性方程组的基于信赖域搜索的修正牛顿算法.首先将对称非线性方程组的求解等价转换为求解无约束最优化问题的全局最优解.之后,我们提出一个基于信赖域搜索的修正牛顿算法来求解对称非线性方程组,该算法通过求解一个非线性方程组来确定搜索方向,并且算法产生的序列包含于一个有界的水平集中.我们在适当的条件下证明了该算法具备全局收敛的性质和局部二次收敛速度.还选取了两个实验算例来验证算法,并在问题维数为10,100,200,300,400,500等情况下分别做了数值实验,每次实验都选取了5组不同的初始值以此来验证算法的有效性.
第二章,我们讨论求解非线性不等式组的模拟退火混合遗传算法.首先将非线性不等式组等价转换成一个非光滑方程组,然后借助光滑化辅助函数将问题等价转换成求解光滑的无约束最小化问题,并在此基础上提出模拟退火混合遗传算法.该算法具有遗传算法和模拟退火算法所具备的全局搜索能力,又弥补了遗传算法容易早熟的缺陷,数值实验有力地说明了算法的有效性.
第三章,我们总结全文,并介绍该课题尚待解决的问题和对未来研究工作的展望.
In this thesis, the algorithms for solving symmetric nonlinear equations and nonlinear inequalities problems are discussed.
In chapter one, a trust-region-based modified Newton method for solving sym-metric nonlinear equations is studied. At first, the symmetric nonlinear equations are reformulated as a kind of unconstrained optimization problem. Then the trust-region-based modified Newton method is presented for solving symmetric nonlinear equations. In this algorithm, the searching direction by solving nonlinear equations. Besides, the iteration sequences generated by this algorithm are included in a level set which is bounded. The sequences generated by this algorithm globally converge to the solution of symmetric nonlinear equations under some additional assump-tions. What's more, this algorithm has the property of local quadratic convergence. Two examples are quoted as the numerical examples which are computed under different dimensions of the problems including 10,100,200,300,400 and 500 with five sets of initial values, which powerfully illustrate the efficiency of the algorithm presented.
In chapter two, an adaptive simulated annealing floating point genetic algo-rithm for solving nonlinear inequalities problem is studied. At first, the nonlinear inequalities problems are reformulated as a set of nonsmoothing equations, then by making use of the smoothing auxiliary function the problem was equally converted as the smoothing unconstrained optimization problems. Based on this transformula-tion, the adaptive simulated annealing floating point genetic algorithm is presented, which not only posses the global searching capability of adaptive simulated an-nealing algorithm and genetic algorithm, but also make up the shortage of genetic algorithm. In the end, the numerical experiment powerfully illustrate the efficiency of the algorithm presented.
In chapter three, the whole thesis is generated. Besides the unsolved problems in this field and some suggestions for our further study are also pointed out.
引文
[1]李佳峰,陈万春.防空导弹最优弹道的协态估计优化算法[J].北京航空航天大学学报,2009,10：1179-1182.
[2]刘丽丽,文浩,金栋平等.绳系卫星轨道转移最优控制[J].航空学报,2009,30(2)：332-336.
[3]王镜,邵春福,毛科俊.公交换乘优惠的双层规划模型[J].中国公路学报,2008,21(2)：93-97.
[4]Wang J Q. Multi-criteria classification approach with polynomial aggregation func-tion and incomplete certain information [J]. System Engineering and Electronics,2006, 17(3):546-550.
[5]何郁波,马昌凤.非线性不等式组的信赖域算法[J].工程数学学报,2008,26(2)：22-230.
[6]蒋丽华,马昌凤.L-M方法解非线性不等式组[J].合肥工业大学学报,2007,30(7)：918-921.
[7]Li D, Fukushima M. A global and superlinear convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations [J]. SIAM Journal on Numerical Analysis, 1999,37:152-172.
[8]Ortega J M, Rheinboldt W C. Iterative of nonlinear equations in several variables[M]. New York:Academic Press,1970.
[9]匡继昌.常用不等式(第三版)[M].济南：山东科学技术出版社,2004.
[10]Gu Z Q, Liao F C, Zhai ding. The decentralized guaranteed control of descriptor system [J]. Journal of Basic Science and Engineering,2004,12(3):322-327.
[11]何郁波,马昌凤,梁茜.非线性不等式组的牛顿法[J].云南大学学报,2006,28(S1)：40-44.
[12]Li D, Fukushima M. A global and superlinear convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations[J]. SIAM Journal on Numerical Analysis, 1999,37:152-172.
[13]Wei Z, Yuan G, Lian Z. An approxiamtion Gauss-Newton-based BFGS method for solving symmetric nonliear equations[J]. Guangxi Science,2004,11(2):91-99.
[14]Yuan G, Lu X. An approxiamtion Gauss-Newton-based BFGS method with descend directtions for solving symmetric nonliear equations[J]. OR Transactions,2005,8(4): 10-26.
[15]Yuan G, Lu X. A nonmonotone Gauss-Newton-based BFGS method for solving sym-metric nonliear equations [J]. Journal of Lanzhou Univerisity (Natural Sciences) [J], 2005,41:851-855.
[16]Yuan G, Wei Z, Lu X. A modified Gauss-Newton-based BFGS method for solving symmetric nonliear equations[J]. Guangxi Science,2006,13(4):288-292.
[17]Yuan G, Lu X, Wei Z. A modified trust-region method with global convergence for symmetric nonliear equations [J]. Mathematica Numerica Sinica,2007,29(3):225-234.
[18]Yuan G, Li X. A new nonmontone conjuate gradient method for symmetric nonlinear equations[J]. Guangxi Science,2009,16(2):109-112.
[19]袁亚湘.信赖域方法的收敛性[J].计算数学,1994,16(3)：333-346.
[20]Rosen E M. A review of quasi-newton methods in nonlinear equation solving and unconstrained optimization [J]. computing machinery, national conference,21st, Los Angeles, Calif,1996:37-41.
[21]Daniel J W. Newton method for nonlinear inequalitions[J]. Numer Math,1973,21: 381-387.
[22]Sahba M. On the solution of nonlinear inequalities in a finite number of iterations[J]. Numer Math,1985,46:229-236.
[23]程维新,陈永强.求解非线性不等式组的有限步终止算法[J].河南师范大学学报,2010,38(2)：24-28.
[24]王宜举,修乃华.非线性规划理论与算法[M].陕西：陕西科学技术出版社,2004.
[25]马昌凤.最优化方法及其Matlab程序设计[M].北京：科学出版社,2010：7483.
[26]Yamakawa E, Fukushima M. Testing parallel bariable transformation [J]. Comput. Optim. Appl.,1999,13:253-274.
[27]Yuan G, Lu X. A new backtracking inexact BFGS method for symmetric nonlinear equations[J]. Computers and mathematics with application,2008,55(1):116-129.
[28]Sagastizabal C A, Solodov M V. Parallel Variable Distribution for Constrained Op-timization [J]. Computational optimization and applications,2008,22(1):111-131.
[29]More J J, Garbow B S, Hillstrome K E. Testing unconstrained optimization soft-ware[J]. ACM Trans. Math. Software,1981,7:17-41.
[30]Dong C L, Jorge Nocedal. On the limited memory BFGS method for large scale optimization[J]. Mathematical Programming,1989,45(1):503-528.
[31]Duff I S. Sparse matrix test problems [J]. ACM Transactions on Mathematical Soft-ware,1989,15(1):503-528.
[32]Ron S, Dembo, Trond Steihaug. Truncated-newton algorithms for large-scale uncon-strained optimization [J]. Mathematical Programming,1983,26(2):190-212.
[33]Grippo L, Lampariello F. A class of nonmontone stabilization methods in uncon-strained optimization [J]. Numerische Mathematik,1991,59(1):779-805.
[34]Avriel M. Nonlinear Programming analysis and methods[M]. Shanghai:Prentice-Hall, 1976.
[35]曾毅.浮点遗传算法在非线性方程组求解中的应用[J].华东交通大学学报,2005,22(1)：10-15.
[36]周明,孙树栋.遗传算法原理及应用[M].北京：国防工业出版社,1999.
[37]Orvicosh D, Davis L. Using a Genetic Algorithm to Optimize Problems With Feasi-bility Constraints[M]. Process of 1st IEEE Conference on Evolutionary Computation, 1994:548-553.
[38]叶海,马昌凤.求解非线性不等式组的混合遗传算法[J].福建师范大学学报,2010,26(1)：18-21.
[39]刘勇,康立山,陈毓屏.非数值并行算法(第二册)－遗传算法[M].北京：科学出版社,1995.
[40]康立山,谢云,尤矢勇,等.非数值并行算法(第一册)－模拟退火算法[M].北京：科学出版社,1994.
[41]Ma C. A globally convergent Levenberg-Marquardt method for the least 2-norm so-lution of nonlinear inequatilities[J]. Applied Mathematics and Computation,2008, 20(6):133-140.
[42]Mayne D Q, Polak E, Heunis A J. Solving nonlinear inequalities in a finite number of iteration[J]. Optimization Theory Application,1981,33:207-221.
[43]Chen X. On the convergence of Broyden-like methods for nonlinear equation with nondifferentiable terms [J]. Ann Inst Statist Math,1990,42:387-401.
[44]Chen X, Qi L. Parameterized newton method and Broyden-like method for solving nonsmooth equations[J]. Computational Optimization and Application,1994,3:157-179.
[45]Chen X, Yamamoto T. On the convergence of some quasi-Newton method for solving nonlinear equations with nondifferentiable operators[J]. Computing,1992,58:87-94.
[46]Ma C. Convergence analysis of a successive approximation quasi-Newton method for solving nonlinear complementarity problems[J]. Journal Mathematical Research and Exposition,2006,26(1):179-188.
[47]Liu G. A trust region algorithm for unconstrained nonsmooth optimization and its convergence[J]. Mathematical Nummerica Sinica,1998,20(2):113-120.
[48]Fletcher R. Practical Methods of Optimization, Vol.2, Constrained Optimization[M]. New York:John Wiley and Sons,1981.
[49]Fletcher R, Leyffer S, Toint P L. On the global convergence of a fliter-SQP algo-rithm^]. SIAM J Numer Anal,1986,23:707-716.
[50]Fletcher R. An overview of unconstrained optimization, in Algorithms for Continuous Optimization:The state of the art[M]. Boston:Academic Publishers,1994:109-143.
[51]Gokldberg D E. Genetic Algorithms in Search[M], Optimization and Machine Learn-ing Addision-Wesley,1989:440-483.
[52]江建.模拟退火混合遗传算法及其实现[M].重庆文理学院学报,2009,28(5)：65-67.
[53]袁亚湘,孙文瑜.最优化理论与方法[M].北京：科学出版社,1997.
[2]刘丽丽,文浩,金栋平等.绳系卫星轨道转移最优控制[J].航空学报,2009,30(2)：332-336.
[3]王镜,邵春福,毛科俊.公交换乘优惠的双层规划模型[J].中国公路学报,2008,21(2)：93-97.
[4]Wang J Q. Multi-criteria classification approach with polynomial aggregation func-tion and incomplete certain information [J]. System Engineering and Electronics,2006, 17(3):546-550.
[5]何郁波,马昌凤.非线性不等式组的信赖域算法[J].工程数学学报,2008,26(2)：22-230.
[6]蒋丽华,马昌凤.L-M方法解非线性不等式组[J].合肥工业大学学报,2007,30(7)：918-921.
[7]Li D, Fukushima M. A global and superlinear convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations [J]. SIAM Journal on Numerical Analysis, 1999,37:152-172.
[8]Ortega J M, Rheinboldt W C. Iterative of nonlinear equations in several variables[M]. New York:Academic Press,1970.
[9]匡继昌.常用不等式(第三版)[M].济南：山东科学技术出版社,2004.
[10]Gu Z Q, Liao F C, Zhai ding. The decentralized guaranteed control of descriptor system [J]. Journal of Basic Science and Engineering,2004,12(3):322-327.
[11]何郁波,马昌凤,梁茜.非线性不等式组的牛顿法[J].云南大学学报,2006,28(S1)：40-44.
[12]Li D, Fukushima M. A global and superlinear convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations[J]. SIAM Journal on Numerical Analysis, 1999,37:152-172.
[13]Wei Z, Yuan G, Lian Z. An approxiamtion Gauss-Newton-based BFGS method for solving symmetric nonliear equations[J]. Guangxi Science,2004,11(2):91-99.
[14]Yuan G, Lu X. An approxiamtion Gauss-Newton-based BFGS method with descend directtions for solving symmetric nonliear equations[J]. OR Transactions,2005,8(4): 10-26.
[15]Yuan G, Lu X. A nonmonotone Gauss-Newton-based BFGS method for solving sym-metric nonliear equations [J]. Journal of Lanzhou Univerisity (Natural Sciences) [J], 2005,41:851-855.
[16]Yuan G, Wei Z, Lu X. A modified Gauss-Newton-based BFGS method for solving symmetric nonliear equations[J]. Guangxi Science,2006,13(4):288-292.
[17]Yuan G, Lu X, Wei Z. A modified trust-region method with global convergence for symmetric nonliear equations [J]. Mathematica Numerica Sinica,2007,29(3):225-234.
[18]Yuan G, Li X. A new nonmontone conjuate gradient method for symmetric nonlinear equations[J]. Guangxi Science,2009,16(2):109-112.
[19]袁亚湘.信赖域方法的收敛性[J].计算数学,1994,16(3)：333-346.
[20]Rosen E M. A review of quasi-newton methods in nonlinear equation solving and unconstrained optimization [J]. computing machinery, national conference,21st, Los Angeles, Calif,1996:37-41.
[21]Daniel J W. Newton method for nonlinear inequalitions[J]. Numer Math,1973,21: 381-387.
[22]Sahba M. On the solution of nonlinear inequalities in a finite number of iterations[J]. Numer Math,1985,46:229-236.
[23]程维新,陈永强.求解非线性不等式组的有限步终止算法[J].河南师范大学学报,2010,38(2)：24-28.
[24]王宜举,修乃华.非线性规划理论与算法[M].陕西：陕西科学技术出版社,2004.
[25]马昌凤.最优化方法及其Matlab程序设计[M].北京：科学出版社,2010：7483.
[26]Yamakawa E, Fukushima M. Testing parallel bariable transformation [J]. Comput. Optim. Appl.,1999,13:253-274.
[27]Yuan G, Lu X. A new backtracking inexact BFGS method for symmetric nonlinear equations[J]. Computers and mathematics with application,2008,55(1):116-129.
[28]Sagastizabal C A, Solodov M V. Parallel Variable Distribution for Constrained Op-timization [J]. Computational optimization and applications,2008,22(1):111-131.
[29]More J J, Garbow B S, Hillstrome K E. Testing unconstrained optimization soft-ware[J]. ACM Trans. Math. Software,1981,7:17-41.
[30]Dong C L, Jorge Nocedal. On the limited memory BFGS method for large scale optimization[J]. Mathematical Programming,1989,45(1):503-528.
[31]Duff I S. Sparse matrix test problems [J]. ACM Transactions on Mathematical Soft-ware,1989,15(1):503-528.
[32]Ron S, Dembo, Trond Steihaug. Truncated-newton algorithms for large-scale uncon-strained optimization [J]. Mathematical Programming,1983,26(2):190-212.
[33]Grippo L, Lampariello F. A class of nonmontone stabilization methods in uncon-strained optimization [J]. Numerische Mathematik,1991,59(1):779-805.
[34]Avriel M. Nonlinear Programming analysis and methods[M]. Shanghai:Prentice-Hall, 1976.
[35]曾毅.浮点遗传算法在非线性方程组求解中的应用[J].华东交通大学学报,2005,22(1)：10-15.
[36]周明,孙树栋.遗传算法原理及应用[M].北京：国防工业出版社,1999.
[37]Orvicosh D, Davis L. Using a Genetic Algorithm to Optimize Problems With Feasi-bility Constraints[M]. Process of 1st IEEE Conference on Evolutionary Computation, 1994:548-553.
[38]叶海,马昌凤.求解非线性不等式组的混合遗传算法[J].福建师范大学学报,2010,26(1)：18-21.
[39]刘勇,康立山,陈毓屏.非数值并行算法(第二册)－遗传算法[M].北京：科学出版社,1995.
[40]康立山,谢云,尤矢勇,等.非数值并行算法(第一册)－模拟退火算法[M].北京：科学出版社,1994.
[41]Ma C. A globally convergent Levenberg-Marquardt method for the least 2-norm so-lution of nonlinear inequatilities[J]. Applied Mathematics and Computation,2008, 20(6):133-140.
[42]Mayne D Q, Polak E, Heunis A J. Solving nonlinear inequalities in a finite number of iteration[J]. Optimization Theory Application,1981,33:207-221.
[43]Chen X. On the convergence of Broyden-like methods for nonlinear equation with nondifferentiable terms [J]. Ann Inst Statist Math,1990,42:387-401.
[44]Chen X, Qi L. Parameterized newton method and Broyden-like method for solving nonsmooth equations[J]. Computational Optimization and Application,1994,3:157-179.
[45]Chen X, Yamamoto T. On the convergence of some quasi-Newton method for solving nonlinear equations with nondifferentiable operators[J]. Computing,1992,58:87-94.
[46]Ma C. Convergence analysis of a successive approximation quasi-Newton method for solving nonlinear complementarity problems[J]. Journal Mathematical Research and Exposition,2006,26(1):179-188.
[47]Liu G. A trust region algorithm for unconstrained nonsmooth optimization and its convergence[J]. Mathematical Nummerica Sinica,1998,20(2):113-120.
[48]Fletcher R. Practical Methods of Optimization, Vol.2, Constrained Optimization[M]. New York:John Wiley and Sons,1981.
[49]Fletcher R, Leyffer S, Toint P L. On the global convergence of a fliter-SQP algo-rithm^]. SIAM J Numer Anal,1986,23:707-716.
[50]Fletcher R. An overview of unconstrained optimization, in Algorithms for Continuous Optimization:The state of the art[M]. Boston:Academic Publishers,1994:109-143.
[51]Gokldberg D E. Genetic Algorithms in Search[M], Optimization and Machine Learn-ing Addision-Wesley,1989:440-483.
[52]江建.模拟退火混合遗传算法及其实现[M].重庆文理学院学报,2009,28(5)：65-67.
[53]袁亚湘,孙文瑜.最优化理论与方法[M].北京：科学出版社,1997.