绝对值方程的算法及其收敛性分析
|
摘要
绝对值方程(AVE)Ax-??的研究来源于线性互补问题,是非线性方程的一种特例.由于绝对值方程与线性互补问题,双线性规划问题的等价性,对于一些重要的问题,如线性规划、二次规划、线性互补等都可以等价的转化为绝对值方程,因此绝对值方程问题有着极强的应用背景.
本文主要是在Mangasarian等人的工作基础上,对求解绝对值方程问题做了进一步研究.根据绝对值的非光滑性,分别提出了求解绝对值方程的光滑Newton方法和一种负梯度下降算法,分析了函数的特殊性质,在理论上证明了算法的可行性和收敛性,并且通过数值实验表明这两种算法是可行的.
本文共分四章,主要结构如下：
第一章绪论,主要是对绝对值方程问题的来源及研究背景做了简要的阐述,介绍了绝对值方程的研究现状及研究成果,具体分析了现有的几个有效算法和研究思想.
第二章,基于区间矩阵[A—I,A+I]是正则的条件下,由光滑函数的思想,直接给出绝对值方程的一个光滑函数,建立解决绝对值方程的光滑牛顿算法,并证明了算法的收敛性.本章中所给出的条件要比A的奇异值大于1这个条件要弱.在区间矩阵[A—I,A+I]是正则的条件下,建立了算法的全局收敛性.
第三章,根据绝对值方程等价于广义线性互补问题,借助FB-函数的性质,先将绝对值方程转化为求解方程组φ(x)=0的解.然后通过光滑Jacobian函数的思想,将函数φ(x)光滑化,并在区间矩阵[A—I,A+I]是正则的条件下,讨论了φ(x)的光滑函数中。(x)的基本性质.而后给出一种光滑Newton方法,在区间矩阵[A—I,A+I]是正则的条件下,证明该算法全局超线性收敛到绝对值方程的唯一解.通过数值实验可知本章中的算法是可行的,并且有较快的收敛速度.
第四章,首先将绝对值方程转化成一个求解函数最小值的无约束优化问题,然后提出一种负梯度下降算法,并且证明了算法的可行性和收敛性.由数值实验的结果可知该算法是可行的.
The study of the absolute value equations(AVE)Ax|x|=b, A∈n×n, bn∈is inspired from the linear complementary problem(LCP). The AVE is a spe-cial class of nonlinear equations. The absolute value equations is equivalent tolinear complementary problem and bilinear programming problem, therefore, lin-ear programming, quadratic programming, linear complementary and so on canbe transformed equivalently to absolute value equations. So the absolute valueequations have strong application background.
We mainly give a research on solving absolute value equations in this paper.According to the nonsmoothing of the absolute value, we propose a smoothingNewton method and a negative gradient descent algorithm for solving the absolutevalue equations. And we prove the feasibility and the convergence of algorithms.Preliminary numerical results show that the two algorithms are promising. Thefull thesis is divided into four chapters.
The first chapter is the introduction. We describe the application back-grounds, the research situations and achievements of the absolute value equationsproblem. Several efective algorithms and the research ideas are analyzed in thischapter.
In the second chapter,we directly give a smoothing function of the absolutevalue equations. And then,under the condition that the interval matrix [A I, A+I] is regular, we propose a smoothing Newton method for solving AVE.The convergence of the algorithm is proved.
In the third chapter, we transform the AVE into a semismooth functionequations Φ(x)=0based on Fischer-Burmeister function and generalized lin-ear complementary problem. And then, we give a smoothing function Φ (x) ofΦ(x), and also discuss the basic properties of it. Then we propose an imporved smoothing Newton method for solving AVE. Under the condition that the inter-val matrix [A—I, A+I] is regular, the imporved algorithm is global superlinear convergence to the unique solution of the absolute value equations. Numerical results of this chapter show that the algorithm is feasible.
In Chapter4, in order to avoid the non-differentiability of the absolute value function, we transform the absolute value equations into a unconstrained opti-mization problem. Then we propose a negative gradient descent algorithm. The feasibility and convergence of the algorithm are also proved. Numerical results show that the algorithm is feasible.
本文主要是在Mangasarian等人的工作基础上,对求解绝对值方程问题做了进一步研究.根据绝对值的非光滑性,分别提出了求解绝对值方程的光滑Newton方法和一种负梯度下降算法,分析了函数的特殊性质,在理论上证明了算法的可行性和收敛性,并且通过数值实验表明这两种算法是可行的.
本文共分四章,主要结构如下：
第一章绪论,主要是对绝对值方程问题的来源及研究背景做了简要的阐述,介绍了绝对值方程的研究现状及研究成果,具体分析了现有的几个有效算法和研究思想.
第二章,基于区间矩阵[A—I,A+I]是正则的条件下,由光滑函数的思想,直接给出绝对值方程的一个光滑函数,建立解决绝对值方程的光滑牛顿算法,并证明了算法的收敛性.本章中所给出的条件要比A的奇异值大于1这个条件要弱.在区间矩阵[A—I,A+I]是正则的条件下,建立了算法的全局收敛性.
第三章,根据绝对值方程等价于广义线性互补问题,借助FB-函数的性质,先将绝对值方程转化为求解方程组φ(x)=0的解.然后通过光滑Jacobian函数的思想,将函数φ(x)光滑化,并在区间矩阵[A—I,A+I]是正则的条件下,讨论了φ(x)的光滑函数中。(x)的基本性质.而后给出一种光滑Newton方法,在区间矩阵[A—I,A+I]是正则的条件下,证明该算法全局超线性收敛到绝对值方程的唯一解.通过数值实验可知本章中的算法是可行的,并且有较快的收敛速度.
第四章,首先将绝对值方程转化成一个求解函数最小值的无约束优化问题,然后提出一种负梯度下降算法,并且证明了算法的可行性和收敛性.由数值实验的结果可知该算法是可行的.
The study of the absolute value equations(AVE)Ax|x|=b, A∈n×n, bn∈is inspired from the linear complementary problem(LCP). The AVE is a spe-cial class of nonlinear equations. The absolute value equations is equivalent tolinear complementary problem and bilinear programming problem, therefore, lin-ear programming, quadratic programming, linear complementary and so on canbe transformed equivalently to absolute value equations. So the absolute valueequations have strong application background.
We mainly give a research on solving absolute value equations in this paper.According to the nonsmoothing of the absolute value, we propose a smoothingNewton method and a negative gradient descent algorithm for solving the absolutevalue equations. And we prove the feasibility and the convergence of algorithms.Preliminary numerical results show that the two algorithms are promising. Thefull thesis is divided into four chapters.
The first chapter is the introduction. We describe the application back-grounds, the research situations and achievements of the absolute value equationsproblem. Several efective algorithms and the research ideas are analyzed in thischapter.
In the second chapter,we directly give a smoothing function of the absolutevalue equations. And then,under the condition that the interval matrix [A I, A+I] is regular, we propose a smoothing Newton method for solving AVE.The convergence of the algorithm is proved.
In the third chapter, we transform the AVE into a semismooth functionequations Φ(x)=0based on Fischer-Burmeister function and generalized lin-ear complementary problem. And then, we give a smoothing function Φ (x) ofΦ(x), and also discuss the basic properties of it. Then we propose an imporved smoothing Newton method for solving AVE. Under the condition that the inter-val matrix [A—I, A+I] is regular, the imporved algorithm is global superlinear convergence to the unique solution of the absolute value equations. Numerical results of this chapter show that the algorithm is feasible.
In Chapter4, in order to avoid the non-differentiability of the absolute value function, we transform the absolute value equations into a unconstrained opti-mization problem. Then we propose a negative gradient descent algorithm. The feasibility and convergence of the algorithm are also proved. Numerical results show that the algorithm is feasible.
引文
[1]Alefeld G. and Mayer G., Interval Analysis, Theory and Applications[J]. Com-put.Appl.Math.,2000,121:421-464.
[2]Caccetta L., Qu B. and Zhou G. L., A globally and quadratically convergent method for absolute value equations [J]. Comput. Optim. Appl.,2009,48:45-58.
[3]Chen X., Qi L. and Sun D., Global and superlinear convergence of the smooth-ing Newton method and its application to general box constrained variational inequalities [J]. Math. Comput.,1998,67:519-540.
[4]Cottle R. W., Pang J. S., Stone, R. E., The Line Complementarity Problem[M]. Academic Press, New York,1992.
[5]Facchinei F. and Pang J. S., Finite dimensional variational inequalities and com-plementarity problems[M]. vol. I. Berlin:Springer.,2003.
[6]Facchinei F. and Kanzow C., A nonsmooth inexact Newton method for the so-lution of large-scale nonlinear complementarity problems [J]. Mathematical Pro-gramming., DOI10.1007/BF02614395,1997,76:493-512.
[7]Fang S.C., An iterative method for generalized complementarity problems[J]. IEEE Transactions on Automatica Control,1980, AC-25:1225-1227.
[8]韩继业,修乃华,戚厚铎,非线性互补理论与算法[M].上海：上海科学技术出版社,2006.
[9]Jing Y.F. and Huang T.Z., On a new iterative method for solving linear systems and comparison results [J]. Comput. Appl. Math.,2008,220:74-84.
[10]Kanzow C. and Pieper H., Jacobian smoothing methods for nonlinear complemen-tarity problems [J]. SIAM Journal of Optimization,1999,9:342-373.
[11]Liu C. H. and Liu H. W., A new semi-smooth Newton method for absolute value equations [J].Preprint.
[12]Mangasarian O. L. and Meyer R. R., Absolute value equations[J]. Linear Algebra Appl,2006,419:359-367.
[13] Mangasarian O. L., Absolute value programming[J]. Comput. Optim. Appl.,2007,36:43-53.
[14] Mangasarian O. L., A generalized Newton method for absolute value equations[J].Optim. Lett.,2009,3:101-108.
[15] Mangasarian O. L., Primal-dual bilinear programming solution of the absolutevalue equation[J]. Optim. Lett.,DOI10.1007/s11590-011-0347-6,2011.
[16] Mangasarian O. L., Absolute value equation solution via dual complementarity[J].Optim. Lett.,Online,2011.
[17] Mangasarian O. L., The linear complementarity problem as a seperable bilinearprogram[J]. Journal of Global Optimization,1995,3:153-161.
[18] Mangasarian O. L., Absolute value equation solution via concave minimization[J].Optimization Letters,2007,1(2):3-8.
[19] Mangasarian O. L., Locally unique solutions of quadratic programs,linear andnonlinear complementarity problems[J]. Mathematical Programming,1980,19:200-212.
[20] Mangasarian O. L., Solution of general linear complementarity problems vianondiferentiable concave minimization[J]. Acta Mathematica Vietnamica,1997,22(1):199-205.
[21] Mangasarian O. L., Characterization of linear complementarity problems as linearprograms[J]. Mathematical Programming.,1978,7:74-87.
[22] MATLAB. User’s Guide. The MathWorks,Inc.,Natick,MA01760,1994-2001.
[23] Mayer G., Epsilon-inflation in verification algorithms[J]. Comput. Appl. Math.,1995,60(1-2):147-169.
[24] Moore R.E., Methods and Applications of Interval Analysis[M]. SIAM Stud.Appl.Math.,2,Society for Industrial and Applied Mathematics,Philadelphta,1979.
[25] Noor M.A., Iqbal J.,Noor K.I., Al-Said E., On an iterative method for solvingabsolute value equations[J]. Optim. Lett., DOI10.1007/s11590-011-0332-0,2011.
[26] Noor M.A., Iqbal J., Khattri S., Al-Said E., A new iterative method for solvingabsolute value equations[J]. Int.J.Phy.Sci.,2011,6(7):1793-1797.
[27] Pang J.S., Inexact Newton method for the nonlinear complementarity problem[J].Mathematical Programming,1986,36(1):54-71.
[28] Qi L., Sun D., Smoothing functions and a smoothing Newton method for comple-mentarity and variational inequality problems[J]. J.Optim. Theory Appl.,2002,113:121-147.
[29] Qi L. and Sun J., A nonsmooth version of Newton’s method[J]. Math. Program.,1993,58:353-367.
[30] Qi L., A convergence analysis of some algorithms for solving nonsmooth equa-tions[J]. Math. Oper. Res.,1993,18:227-244.
[31] Rohn J., Systems of linear interval equations[J]. Linear Algebra Appl.,1989,126:39-78.
[32] Rohn J., A theorem of the alternatives for the equation Ax+B|x|=b[J]. LinearMultilinear Algebra,2004,52:421-426.
[33] Rohn J., An algorithm for computing all solutions of an absolute value equation[J].Optim. Lett., DOI10.1007/s11590-011-0305-3,2011.
[34] Rohn J., An algorithm for solving the absolute value equation[J]. Electronic Jour-nal of Linear Algebra,2009,18:589-599.
[35] Rohn J., On unique solvability of the absolute value equation[J]. Optim. Lett.,2009,3:603-606.
[36] Rohn J., A residual existence theorem for linear equations[J]. Optim. Lett.,2010,4(2):287-292.
[37]Rex G. and Rohn J., Sufficient conditions for regularity and singularity of interval matrices[J]. SIAM J. Matrix Anal.,1999,20:437-445.
[38]Rump S.M., New results on verified inclusions [J]. Accurate Scientific Computa-tions, Bad Neuenahr,1985,Lecture Notes in Comput. Sci.,235,Springer. Berlin.,1986,31-69.
[39]Rump S.M., On the solution of interval linear systems[J]. Computing.,1992,47(3-4):337-353.
[40]Sun D. and Han J., Newton and quasi-Newton methods for a class of nonsmooth equations and related problems [J]. SIAM J. Optim.,1997,7:463-480.
[41]Ujevic N., A new iterative method for solving linear systems[J]. Appl. Math. Com-put.,2006,179:725-730.
[42]袁亚湘,孙文瑜,最优化理论与方法[M].北京：科学出版社,1997.
[43]Zhang C. and Wei Q. J., Global and finite convergence of a generalized Newton method for absolute value equations[J]. J.Optim. Theory Appl.,2009,143:391-403.
[2]Caccetta L., Qu B. and Zhou G. L., A globally and quadratically convergent method for absolute value equations [J]. Comput. Optim. Appl.,2009,48:45-58.
[3]Chen X., Qi L. and Sun D., Global and superlinear convergence of the smooth-ing Newton method and its application to general box constrained variational inequalities [J]. Math. Comput.,1998,67:519-540.
[4]Cottle R. W., Pang J. S., Stone, R. E., The Line Complementarity Problem[M]. Academic Press, New York,1992.
[5]Facchinei F. and Pang J. S., Finite dimensional variational inequalities and com-plementarity problems[M]. vol. I. Berlin:Springer.,2003.
[6]Facchinei F. and Kanzow C., A nonsmooth inexact Newton method for the so-lution of large-scale nonlinear complementarity problems [J]. Mathematical Pro-gramming., DOI10.1007/BF02614395,1997,76:493-512.
[7]Fang S.C., An iterative method for generalized complementarity problems[J]. IEEE Transactions on Automatica Control,1980, AC-25:1225-1227.
[8]韩继业,修乃华,戚厚铎,非线性互补理论与算法[M].上海：上海科学技术出版社,2006.
[9]Jing Y.F. and Huang T.Z., On a new iterative method for solving linear systems and comparison results [J]. Comput. Appl. Math.,2008,220:74-84.
[10]Kanzow C. and Pieper H., Jacobian smoothing methods for nonlinear complemen-tarity problems [J]. SIAM Journal of Optimization,1999,9:342-373.
[11]Liu C. H. and Liu H. W., A new semi-smooth Newton method for absolute value equations [J].Preprint.
[12]Mangasarian O. L. and Meyer R. R., Absolute value equations[J]. Linear Algebra Appl,2006,419:359-367.
[13] Mangasarian O. L., Absolute value programming[J]. Comput. Optim. Appl.,2007,36:43-53.
[14] Mangasarian O. L., A generalized Newton method for absolute value equations[J].Optim. Lett.,2009,3:101-108.
[15] Mangasarian O. L., Primal-dual bilinear programming solution of the absolutevalue equation[J]. Optim. Lett.,DOI10.1007/s11590-011-0347-6,2011.
[16] Mangasarian O. L., Absolute value equation solution via dual complementarity[J].Optim. Lett.,Online,2011.
[17] Mangasarian O. L., The linear complementarity problem as a seperable bilinearprogram[J]. Journal of Global Optimization,1995,3:153-161.
[18] Mangasarian O. L., Absolute value equation solution via concave minimization[J].Optimization Letters,2007,1(2):3-8.
[19] Mangasarian O. L., Locally unique solutions of quadratic programs,linear andnonlinear complementarity problems[J]. Mathematical Programming,1980,19:200-212.
[20] Mangasarian O. L., Solution of general linear complementarity problems vianondiferentiable concave minimization[J]. Acta Mathematica Vietnamica,1997,22(1):199-205.
[21] Mangasarian O. L., Characterization of linear complementarity problems as linearprograms[J]. Mathematical Programming.,1978,7:74-87.
[22] MATLAB. User’s Guide. The MathWorks,Inc.,Natick,MA01760,1994-2001.
[23] Mayer G., Epsilon-inflation in verification algorithms[J]. Comput. Appl. Math.,1995,60(1-2):147-169.
[24] Moore R.E., Methods and Applications of Interval Analysis[M]. SIAM Stud.Appl.Math.,2,Society for Industrial and Applied Mathematics,Philadelphta,1979.
[25] Noor M.A., Iqbal J.,Noor K.I., Al-Said E., On an iterative method for solvingabsolute value equations[J]. Optim. Lett., DOI10.1007/s11590-011-0332-0,2011.
[26] Noor M.A., Iqbal J., Khattri S., Al-Said E., A new iterative method for solvingabsolute value equations[J]. Int.J.Phy.Sci.,2011,6(7):1793-1797.
[27] Pang J.S., Inexact Newton method for the nonlinear complementarity problem[J].Mathematical Programming,1986,36(1):54-71.
[28] Qi L., Sun D., Smoothing functions and a smoothing Newton method for comple-mentarity and variational inequality problems[J]. J.Optim. Theory Appl.,2002,113:121-147.
[29] Qi L. and Sun J., A nonsmooth version of Newton’s method[J]. Math. Program.,1993,58:353-367.
[30] Qi L., A convergence analysis of some algorithms for solving nonsmooth equa-tions[J]. Math. Oper. Res.,1993,18:227-244.
[31] Rohn J., Systems of linear interval equations[J]. Linear Algebra Appl.,1989,126:39-78.
[32] Rohn J., A theorem of the alternatives for the equation Ax+B|x|=b[J]. LinearMultilinear Algebra,2004,52:421-426.
[33] Rohn J., An algorithm for computing all solutions of an absolute value equation[J].Optim. Lett., DOI10.1007/s11590-011-0305-3,2011.
[34] Rohn J., An algorithm for solving the absolute value equation[J]. Electronic Jour-nal of Linear Algebra,2009,18:589-599.
[35] Rohn J., On unique solvability of the absolute value equation[J]. Optim. Lett.,2009,3:603-606.
[36] Rohn J., A residual existence theorem for linear equations[J]. Optim. Lett.,2010,4(2):287-292.
[37]Rex G. and Rohn J., Sufficient conditions for regularity and singularity of interval matrices[J]. SIAM J. Matrix Anal.,1999,20:437-445.
[38]Rump S.M., New results on verified inclusions [J]. Accurate Scientific Computa-tions, Bad Neuenahr,1985,Lecture Notes in Comput. Sci.,235,Springer. Berlin.,1986,31-69.
[39]Rump S.M., On the solution of interval linear systems[J]. Computing.,1992,47(3-4):337-353.
[40]Sun D. and Han J., Newton and quasi-Newton methods for a class of nonsmooth equations and related problems [J]. SIAM J. Optim.,1997,7:463-480.
[41]Ujevic N., A new iterative method for solving linear systems[J]. Appl. Math. Com-put.,2006,179:725-730.
[42]袁亚湘,孙文瑜,最优化理论与方法[M].北京：科学出版社,1997.
[43]Zhang C. and Wei Q. J., Global and finite convergence of a generalized Newton method for absolute value equations[J]. J.Optim. Theory Appl.,2009,143:391-403.