基于平方函数空间变换的凸二次规划问题的微分方程方法
|
摘要
凸二次规划是数学规划中的一个重要分支,它在经济,市场均衡,管理,军事等各个领域均有重要应用。求解凸二次规划问题有很多有效的算法,如拟牛顿法,内点法,投影法,Langrange方法及Lemke方法等。
本文旨在研究求解凸二次规划问题的微分方程方法,包括求解凸二次规划问题的一阶微分方程方法和二阶微分方程方法的理论及相应的数值实现。其原因有三:一是很多优化问题的神经网络方法都由微分方程系统来刻画;二是可以把有效的微分方程数值解法用于求解凸二次规划问题;三是二阶导数的微分方程方法是二次收敛的。
本文首先将一般的凸二次规划问题转化为等价的优化问题,然后基于一具体的空间变换利用微分方程进行求解。首先我们对凸二次规划问题建立了一阶微分方程系统,随后我们利用牛顿方法建立了二阶微分方程系统;对于这两个微分方程系统,我们证明了它们具有如下性质:凸二次规划问题的KKT点是它们的渐近稳定平衡点,且当初始点可行时,解轨迹将全部落于可行域中。其次我们还证明了该微分方程系统欧拉离散迭代格式的收敛性。我们还给出了算法,并证明了基于二阶导数的微分方程系统的算法具有二阶收敛速度。最后用两个离散迭代格式计算了几个例子,数值结果验证了微分方程方法的有效性,也表明基于二阶导数的微分方程系统的算法具有较快的收敛速度。
The convex quadratic programming is an important branch of mathematical programming. It has important applications in economic, equilibrium market management, military and other fields. There are many effective algorithms to solve quadratic programming problems, including Newton methods, interior point methods, projection methods, Wolfe algorithms, Lagrange methods and Lemke methods.
The aim of this dissertation is to study differential equation approaches to convex quadratic programming, including theories and numerical implementations of both first order and second order differential equation approaches. There are three reasons for selecting such a subject: First, this may provide a theoretical support to some neural network methods as there are many neural network for optimization problems characterized by systems of differential equations; Next, effective numerical algorithms for differential equations can be applied to solving convex quadratic programming; At last, the convergence rate of second order derivatives differential equation method is quadratic.
For convex quadratic programming, using space transformation, we construct differential equation systems based on first order derivatives and second order derivatives. The two systems are proved to have the properties: the KKT point of a convex quadratic programming is an asymptotically stable equilibrium point of the system and the whole solution trajectory is in the feasible domain of the problem if it starts from a feasible point. Moreover, we demonstrate the convergence theorems for the discrete schemes of the two differential systems, including the locally quadratic convergence rate of the discrete algorithm for second order derivatives based on these two discrete methods and the numerical results show that the differential equation algorithms based on second order derivatives are faster than that on first order derivatives.
本文旨在研究求解凸二次规划问题的微分方程方法,包括求解凸二次规划问题的一阶微分方程方法和二阶微分方程方法的理论及相应的数值实现。其原因有三:一是很多优化问题的神经网络方法都由微分方程系统来刻画;二是可以把有效的微分方程数值解法用于求解凸二次规划问题;三是二阶导数的微分方程方法是二次收敛的。
本文首先将一般的凸二次规划问题转化为等价的优化问题,然后基于一具体的空间变换利用微分方程进行求解。首先我们对凸二次规划问题建立了一阶微分方程系统,随后我们利用牛顿方法建立了二阶微分方程系统;对于这两个微分方程系统,我们证明了它们具有如下性质:凸二次规划问题的KKT点是它们的渐近稳定平衡点,且当初始点可行时,解轨迹将全部落于可行域中。其次我们还证明了该微分方程系统欧拉离散迭代格式的收敛性。我们还给出了算法,并证明了基于二阶导数的微分方程系统的算法具有二阶收敛速度。最后用两个离散迭代格式计算了几个例子,数值结果验证了微分方程方法的有效性,也表明基于二阶导数的微分方程系统的算法具有较快的收敛速度。
The convex quadratic programming is an important branch of mathematical programming. It has important applications in economic, equilibrium market management, military and other fields. There are many effective algorithms to solve quadratic programming problems, including Newton methods, interior point methods, projection methods, Wolfe algorithms, Lagrange methods and Lemke methods.
The aim of this dissertation is to study differential equation approaches to convex quadratic programming, including theories and numerical implementations of both first order and second order differential equation approaches. There are three reasons for selecting such a subject: First, this may provide a theoretical support to some neural network methods as there are many neural network for optimization problems characterized by systems of differential equations; Next, effective numerical algorithms for differential equations can be applied to solving convex quadratic programming; At last, the convergence rate of second order derivatives differential equation method is quadratic.
For convex quadratic programming, using space transformation, we construct differential equation systems based on first order derivatives and second order derivatives. The two systems are proved to have the properties: the KKT point of a convex quadratic programming is an asymptotically stable equilibrium point of the system and the whole solution trajectory is in the feasible domain of the problem if it starts from a feasible point. Moreover, we demonstrate the convergence theorems for the discrete schemes of the two differential systems, including the locally quadratic convergence rate of the discrete algorithm for second order derivatives based on these two discrete methods and the numerical results show that the differential equation algorithms based on second order derivatives are faster than that on first order derivatives.
引文
[1]黄红选,韩继业.数学规划.北京:清华大学出版社.2006.
[2]周华任.运筹学解题指导.北京:清华大学出版社.2006.
[3]姜健飞,胡良剑,唐俭.数值分析及其MATLAB实验.2004.
[4]Evtushenko Yu G.and Zhandan V G.Newtons' steepest descent for linear programming.Sov.Math.Dokl,1974,15(2):420-423.
[5]Arrow K J and Hurwice L.Reduction of constrained maxima to saddle point problems.Proceedings of the 3rd Berkeley Symposium on Mathematical Statistics and Probability,J.Neyman(ed.),University of California Press,Berkeley,1956,1-26.
[6]Fiacco A V and McCormick G P.Nonsmooth Optimization:Sequential Unconstrained Minimization Techniques,John Wiely,New York,(1968)
[7]李庆扬,王能超,易大义.数值分析.北京:清华大学出版社.2004.
[8]廖晓晞.稳定性的理论、方法和应用.华中理工大学出版社.1998.
[9]Evtushenko Yu G.Two numerical methods of solving nonlinear programming problems.Sov Math Dokl,1974,15(2):420-423.
[10]Evtushenko Yu G.Numerical optimization techniques.Optimization Software,Inc.Publication Division,New York,1985
[11]袁亚湘.非线性规划数值方法.上海:上海科学技术出版社.1993.
[12]袁亚湘,孙文瑜.最优化理论与方法.科学出版社.1997.
[13]Evtushenko Yu G.and Zhandan V G.Barrier-projection methods for nonlinear programming.Comp Math Phys.1994,34(5):579-590.
[14]Evtushenko Yu G and Zhandan V G.Stable barrier-projection and barrier-Newton methods In nonlinear programming.Optimization Methods and Software,1994(30:237-256
[15]Evtushenko Yu nonlinear programming.Algorithmation for Continuous,Optimization E.Spedicato(ed.),Kluwer AcademicPublishers.1994,255-285
[16]Evtushenko Yu G and Zhandan V G.Space-transformation technique:the state of art.Non-linear optim G and Zhandan V G.Stable barrier-projection and barrier-Newton methods In ization and application.1996:101-123.
[17]Pan P Q.New ODE methods for equality constrained optimization(1)-equation.Journal of Computational Mathematics.1992,10(1):77-92
[18]黄启昌.常微分方程.北京:高等教育出版社.1983..
[19]胡运全.运筹学习题集.北京:清华大学出版社.1995.
[20]Botsaris C A.Differential gradient methods.Journal Mathematical Analysis & Application.1978(9):177-198.
[21]Cichocki A and Unbehauen R.Neueal networks for solving.Optimization and Signal Processing.Chichester:Wiley,1993
[22]Evtushenko Yu G and Zhandan V G.Dual barrier-projection methods In nonlinear programming WSSIAA,1995,(5):51-56..
[23]王高雄,周之铭,朱思铭,王寿松.常微分方程.1983.
[24]Evtushenko Yu G and Zhandan V G.Stable barrier-projection and barrier-Newton methods In nonlinear programming.Computational optimization and application,1994,3(4):289-303.4
[25]孙文瑜,徐成贤,朱德通.最优化方法.高等教育出版社,2004.
[26]Evtushenko Yu G and Zhandan V G,Cherenkov A P.The use of Newton's method for linear programming.Comput.Maths.Math.Phys.1995,35(6):673-686.
[27]Golikov A I,Evtushenko Yu G.A new method for solving systems of linear equalities and inequalities.Doklady mathematics.2001,64(3):370-373.
[28]Hopfied J J.Neurons with graded response have collective computational properties like those of two-state neurons.Process Natl.Academice Science.1984,81:3088-3092.
[29]Tank D W and Hopfied J J Simple neural's optimization networks:an A/D convertor,signal decision circuit and a linear programming circuit.IEEE Trans.Circuits,System 1986,33:533-541.
[30]周丽美.非线性最优化微分方程方法的研究.(博士学位论文)大连:大连理工大学.2004.
[31]金丽.基于二阶导数的非凸约束优化的微分方程方法.(博士学位论文)大连:大连理工大学.2006.
[32]Zhang L W.Li Q,Zhang X.Two differential systems for solving nonlinear programming problems.OR Transaction.2000,4(4):33-46.
[33]Zhang L W.A modified version to the differential system of Evtushenko and Zhadan for solving nonlinear programming.In Yuan Ya-Xiang(ed.),Numerical Linear Algebra and Optimization,Science Press,Beijing,New York,199:161-168.
[35]Fiacco A V,McCormick G.p.Sequential Unconstrained Minimization Techniques.In:Wiely J.Nonlinear Programming.New York,1968.
[36]Yamadhita H.A differential equation approach to nonlinear programming.Math.Prog.1980,18:115-168.
[37]Pan P Q.New ODE methods for equality constrained optimization(1)-equations.J.Computational Mathematics.1992,10(1):77-92.
[38]Botsaris C A.Differential gradient methods.Journal Mathematical Analysis & Application.1978,(9):177-198.
[39]Amaya J A.A differential equations approach to function minimization.Review of Mathmatical Application.1987,(9):1-7.
[40]Rodriguez-Vazquez A,Dominguez-Castro R.Nonlinear switched-Capacitor neural networks for optimization problems.IEEE Trans on Circuits and System.1990,37(3):384-397.
[41]Osowski S.Neural network for nonlinear programming with linear equality constrains.Inter J of Circuit Theory and Applications.1992,20:93-98.
[42]Brown A A,Bartholomew-Biggs M C.ODE versus SQP methods for constrained optimization.The Hatfield polytechnic optimization center.Technical report 1987:No.179.
[43]Brown A A,Bartholomew-Biggs M C.ODE versus SQP methods for constrained optimization.Journal of Optimization Theory & Application.1989,62:371-386.
[44]Tanable K.An algorithm for constrained maximization in nonlinear programming.Journal of the Operations Research Society of Japan.1947,(17):184-201.
[45]Smirnov G V.Convergence of barrier-projection methods of optimization via vector Lyapunov functions.Optimization Methods and Software 1994(3):153-162.
[46]Zhang S W,Constantinides A G.Lagrange programming neural network.IEEE Trans on Circuits and Systems.1992,(39):441-452.
[47]Zhang S W,Zhu X N,Zou L H.Second-order neural nets for constrained optimization.IEEE Trans.on Neural Networks.1992,(3)6:1021-1-24.
[48]Zhou Z F.An ODE method of solving nonlinear programming.Computers Mathematics and Application.1997,34(1):97-102.
[49]Kennedy M P,Chua L O.Neural network for nonlinear programming.IEEE Transaction on Circuits and Systems.1988,35:554-562.
[50]Lillo W E,Loh M H,Hui S.On solving constrained optimization problems with neural networks:a penalty method approach.IEEE Transanctions on Neural Networks.1993,4:931-940.
[51]Cichocki A,Unbehauen R.Swithed-capacitor nerural networks for differential optimization.Inter J of Circuit Theory and Applications.1991,19:161-187.
[52]Lillo W E,Loh M H,Hui S.et al.Neural networks for constrained optimization problems.Inter J of Circuit and Applications.1993,21:385-399.
[53]黄远灿,孙圣和,韩京轻.基于Lagrange乘子法的非线性规划神经网络.电子学报.1998,26:24-28.
[54]黄远灿.一种新型的Lagrange非线性规划神经网络.电子学报.2002,30:27-29.
[55]Maa C Y,Shanblatt M A.Linear and quadratic programming neural network analysis.IEEE Trans.On Neurons Networks.1992,3:580-594.
[56]Hopfied J J.Neurons with graded response have collective computational properties like those of two-state neurons.Process Natl.Academic Science.1984,81:3088-3092.
[57]Hopfied J J.,Tank D W.Neural computation of decision in optimization problems.Bio;Cybern 1985,52:141-152.
[58]Tank D W,Hopfield J J.Simple neurat's optimization networks:an A/D convertor,signal decision circuit and a linear programming circuit.IEEE Trans.Circuits System.,1986 33:533-541.
[59]Evtushenko Y G.Numerical Optimization Techniques.In:Optimization Software.New York:Inc.Publication Division,1985.
[60]Ortega J M,Rheinboldt W C.Iterative solution of nonlinear in several variables.New York:Academic Press,1970.
[2]周华任.运筹学解题指导.北京:清华大学出版社.2006.
[3]姜健飞,胡良剑,唐俭.数值分析及其MATLAB实验.2004.
[4]Evtushenko Yu G.and Zhandan V G.Newtons' steepest descent for linear programming.Sov.Math.Dokl,1974,15(2):420-423.
[5]Arrow K J and Hurwice L.Reduction of constrained maxima to saddle point problems.Proceedings of the 3rd Berkeley Symposium on Mathematical Statistics and Probability,J.Neyman(ed.),University of California Press,Berkeley,1956,1-26.
[6]Fiacco A V and McCormick G P.Nonsmooth Optimization:Sequential Unconstrained Minimization Techniques,John Wiely,New York,(1968)
[7]李庆扬,王能超,易大义.数值分析.北京:清华大学出版社.2004.
[8]廖晓晞.稳定性的理论、方法和应用.华中理工大学出版社.1998.
[9]Evtushenko Yu G.Two numerical methods of solving nonlinear programming problems.Sov Math Dokl,1974,15(2):420-423.
[10]Evtushenko Yu G.Numerical optimization techniques.Optimization Software,Inc.Publication Division,New York,1985
[11]袁亚湘.非线性规划数值方法.上海:上海科学技术出版社.1993.
[12]袁亚湘,孙文瑜.最优化理论与方法.科学出版社.1997.
[13]Evtushenko Yu G.and Zhandan V G.Barrier-projection methods for nonlinear programming.Comp Math Phys.1994,34(5):579-590.
[14]Evtushenko Yu G and Zhandan V G.Stable barrier-projection and barrier-Newton methods In nonlinear programming.Optimization Methods and Software,1994(30:237-256
[15]Evtushenko Yu nonlinear programming.Algorithmation for Continuous,Optimization E.Spedicato(ed.),Kluwer AcademicPublishers.1994,255-285
[16]Evtushenko Yu G and Zhandan V G.Space-transformation technique:the state of art.Non-linear optim G and Zhandan V G.Stable barrier-projection and barrier-Newton methods In ization and application.1996:101-123.
[17]Pan P Q.New ODE methods for equality constrained optimization(1)-equation.Journal of Computational Mathematics.1992,10(1):77-92
[18]黄启昌.常微分方程.北京:高等教育出版社.1983..
[19]胡运全.运筹学习题集.北京:清华大学出版社.1995.
[20]Botsaris C A.Differential gradient methods.Journal Mathematical Analysis & Application.1978(9):177-198.
[21]Cichocki A and Unbehauen R.Neueal networks for solving.Optimization and Signal Processing.Chichester:Wiley,1993
[22]Evtushenko Yu G and Zhandan V G.Dual barrier-projection methods In nonlinear programming WSSIAA,1995,(5):51-56..
[23]王高雄,周之铭,朱思铭,王寿松.常微分方程.1983.
[24]Evtushenko Yu G and Zhandan V G.Stable barrier-projection and barrier-Newton methods In nonlinear programming.Computational optimization and application,1994,3(4):289-303.4
[25]孙文瑜,徐成贤,朱德通.最优化方法.高等教育出版社,2004.
[26]Evtushenko Yu G and Zhandan V G,Cherenkov A P.The use of Newton's method for linear programming.Comput.Maths.Math.Phys.1995,35(6):673-686.
[27]Golikov A I,Evtushenko Yu G.A new method for solving systems of linear equalities and inequalities.Doklady mathematics.2001,64(3):370-373.
[28]Hopfied J J.Neurons with graded response have collective computational properties like those of two-state neurons.Process Natl.Academice Science.1984,81:3088-3092.
[29]Tank D W and Hopfied J J Simple neural's optimization networks:an A/D convertor,signal decision circuit and a linear programming circuit.IEEE Trans.Circuits,System 1986,33:533-541.
[30]周丽美.非线性最优化微分方程方法的研究.(博士学位论文)大连:大连理工大学.2004.
[31]金丽.基于二阶导数的非凸约束优化的微分方程方法.(博士学位论文)大连:大连理工大学.2006.
[32]Zhang L W.Li Q,Zhang X.Two differential systems for solving nonlinear programming problems.OR Transaction.2000,4(4):33-46.
[33]Zhang L W.A modified version to the differential system of Evtushenko and Zhadan for solving nonlinear programming.In Yuan Ya-Xiang(ed.),Numerical Linear Algebra and Optimization,Science Press,Beijing,New York,199:161-168.
[35]Fiacco A V,McCormick G.p.Sequential Unconstrained Minimization Techniques.In:Wiely J.Nonlinear Programming.New York,1968.
[36]Yamadhita H.A differential equation approach to nonlinear programming.Math.Prog.1980,18:115-168.
[37]Pan P Q.New ODE methods for equality constrained optimization(1)-equations.J.Computational Mathematics.1992,10(1):77-92.
[38]Botsaris C A.Differential gradient methods.Journal Mathematical Analysis & Application.1978,(9):177-198.
[39]Amaya J A.A differential equations approach to function minimization.Review of Mathmatical Application.1987,(9):1-7.
[40]Rodriguez-Vazquez A,Dominguez-Castro R.Nonlinear switched-Capacitor neural networks for optimization problems.IEEE Trans on Circuits and System.1990,37(3):384-397.
[41]Osowski S.Neural network for nonlinear programming with linear equality constrains.Inter J of Circuit Theory and Applications.1992,20:93-98.
[42]Brown A A,Bartholomew-Biggs M C.ODE versus SQP methods for constrained optimization.The Hatfield polytechnic optimization center.Technical report 1987:No.179.
[43]Brown A A,Bartholomew-Biggs M C.ODE versus SQP methods for constrained optimization.Journal of Optimization Theory & Application.1989,62:371-386.
[44]Tanable K.An algorithm for constrained maximization in nonlinear programming.Journal of the Operations Research Society of Japan.1947,(17):184-201.
[45]Smirnov G V.Convergence of barrier-projection methods of optimization via vector Lyapunov functions.Optimization Methods and Software 1994(3):153-162.
[46]Zhang S W,Constantinides A G.Lagrange programming neural network.IEEE Trans on Circuits and Systems.1992,(39):441-452.
[47]Zhang S W,Zhu X N,Zou L H.Second-order neural nets for constrained optimization.IEEE Trans.on Neural Networks.1992,(3)6:1021-1-24.
[48]Zhou Z F.An ODE method of solving nonlinear programming.Computers Mathematics and Application.1997,34(1):97-102.
[49]Kennedy M P,Chua L O.Neural network for nonlinear programming.IEEE Transaction on Circuits and Systems.1988,35:554-562.
[50]Lillo W E,Loh M H,Hui S.On solving constrained optimization problems with neural networks:a penalty method approach.IEEE Transanctions on Neural Networks.1993,4:931-940.
[51]Cichocki A,Unbehauen R.Swithed-capacitor nerural networks for differential optimization.Inter J of Circuit Theory and Applications.1991,19:161-187.
[52]Lillo W E,Loh M H,Hui S.et al.Neural networks for constrained optimization problems.Inter J of Circuit and Applications.1993,21:385-399.
[53]黄远灿,孙圣和,韩京轻.基于Lagrange乘子法的非线性规划神经网络.电子学报.1998,26:24-28.
[54]黄远灿.一种新型的Lagrange非线性规划神经网络.电子学报.2002,30:27-29.
[55]Maa C Y,Shanblatt M A.Linear and quadratic programming neural network analysis.IEEE Trans.On Neurons Networks.1992,3:580-594.
[56]Hopfied J J.Neurons with graded response have collective computational properties like those of two-state neurons.Process Natl.Academic Science.1984,81:3088-3092.
[57]Hopfied J J.,Tank D W.Neural computation of decision in optimization problems.Bio;Cybern 1985,52:141-152.
[58]Tank D W,Hopfield J J.Simple neurat's optimization networks:an A/D convertor,signal decision circuit and a linear programming circuit.IEEE Trans.Circuits System.,1986 33:533-541.
[59]Evtushenko Y G.Numerical Optimization Techniques.In:Optimization Software.New York:Inc.Publication Division,1985.
[60]Ortega J M,Rheinboldt W C.Iterative solution of nonlinear in several variables.New York:Academic Press,1970.