利用KKT-系统求解非线性约束优化问题的两类新方法
|
摘要
非线性约束优化问题(CNLP)是运筹学的重要分支之一，它广泛应用于自然科学、工程和经济领域中通过求解CNLP的KKT-点来得到CNLP的局部极小点的方法是最近较流行的求解CNLP的数值方法之一。这类方法的一般特点是首先把KKT-系统等价地转化为光滑的无约束(或具有简单约束)的最优化问题，然后利用经典最优化方法来求解KKT-点。本文研究的算法也是基于这种思想，但构造目标函数的方法不同，具体内容如下：
1.通过构造仅在第一象限定义的NCP-函数，将非线性约束优化问题的KKT-系统等价地转化为带非负约束的光滑优化问题，这里借鉴了处理非线性互补问题的不可行点算法的思想，引入了辅助变量，简化了约束条件利用Qi等提出的效率较高的信赖域方法提供了具体求解KKT-点的算法，并在适当的条件下证明了算法的全局收敛性和局部超线性(二次)收敛性。
2.在研究以往NCP-函数的基础上总结出了一个构造NCP-函数的方法，利用该方法构造出来的NCP-函数具有良好的性质.在第三章中，根据该方法构造了两个新的NCP-函数，第一个NCP-函数具有四个象限收敛速度相近的性质，而第二个NCP-函数具有Lipschistz连续性、强半光滑，较好的强制性等良好性质.利用后一个NCP-函数给出了CNLP的KKT-系统新的非负约束优化等价形式并结合Qi等提出的信赖域方法进行了求解.在较弱的条件下得到了全局收敛性和局部超线性(二次)收敛性。数值试验表明此该算法具有较好适应性和稳定性，实际计算效果也令人满意。
The constrained nonlinear programming problems(CNLP) is a very important component part in operations research.It has wide application in natural science, en-gineering and economics. In recent years, the method that a local minimum of CNLP is obtained by solving KKT-systems for CNLP becomes one of the efficient numerical methods for CNLP. The main idea of the method is to reformulate the KKT-systems for CNLP as an unconstrained (or simply constrained) smooth minimization problem equivalently. Then a KKT-point for CNLP is obtained by using classical numerical methods for the problem. In this thesis, enlightened by the idea, author equivalently transformed the KKT-systems for CNLP into some new simply constrained smooth minimization problems different from that in literature. The details arc as follows:
1.Firstly.author constructed a new NCP-function that is only defined in first quad-rant, then equivalently reformulated the KKT-systems for CNLP as a smooth mini-mization problem with non-negative constraints. As in the infeasible method for non-linear complementarity problem, an additional variable was introduced in order to getting simple constraints- An efficient trust region algorithm for solving KKT point for CNLP was provided via using the method proposed by Qi etc[15]. The global convergence and local superlinear (or quadratic) convergence for the algorithm were shown under suitable conditions.
2. Futhermorc. a new method that to construct NCP-functions was proposed. By using the method, author obtained a new NCP-function with many useful properties, such as Lipschitz continuity. Strong semismoothness. good coercivity etc. A new refor-mulation was constructed by using it, and a similar algorithm as above was provided on the reformulation- The global convergence and local superlinear (or quadratic) con-vergence were obtained under weaker assumptions than above. Numerical results show that the algorithm is robust and efficient.
1.通过构造仅在第一象限定义的NCP-函数，将非线性约束优化问题的KKT-系统等价地转化为带非负约束的光滑优化问题，这里借鉴了处理非线性互补问题的不可行点算法的思想，引入了辅助变量，简化了约束条件利用Qi等提出的效率较高的信赖域方法提供了具体求解KKT-点的算法，并在适当的条件下证明了算法的全局收敛性和局部超线性(二次)收敛性。
2.在研究以往NCP-函数的基础上总结出了一个构造NCP-函数的方法，利用该方法构造出来的NCP-函数具有良好的性质.在第三章中，根据该方法构造了两个新的NCP-函数，第一个NCP-函数具有四个象限收敛速度相近的性质，而第二个NCP-函数具有Lipschistz连续性、强半光滑，较好的强制性等良好性质.利用后一个NCP-函数给出了CNLP的KKT-系统新的非负约束优化等价形式并结合Qi等提出的信赖域方法进行了求解.在较弱的条件下得到了全局收敛性和局部超线性(二次)收敛性。数值试验表明此该算法具有较好适应性和稳定性，实际计算效果也令人满意。
The constrained nonlinear programming problems(CNLP) is a very important component part in operations research.It has wide application in natural science, en-gineering and economics. In recent years, the method that a local minimum of CNLP is obtained by solving KKT-systems for CNLP becomes one of the efficient numerical methods for CNLP. The main idea of the method is to reformulate the KKT-systems for CNLP as an unconstrained (or simply constrained) smooth minimization problem equivalently. Then a KKT-point for CNLP is obtained by using classical numerical methods for the problem. In this thesis, enlightened by the idea, author equivalently transformed the KKT-systems for CNLP into some new simply constrained smooth minimization problems different from that in literature. The details arc as follows:
1.Firstly.author constructed a new NCP-function that is only defined in first quad-rant, then equivalently reformulated the KKT-systems for CNLP as a smooth mini-mization problem with non-negative constraints. As in the infeasible method for non-linear complementarity problem, an additional variable was introduced in order to getting simple constraints- An efficient trust region algorithm for solving KKT point for CNLP was provided via using the method proposed by Qi etc[15]. The global convergence and local superlinear (or quadratic) convergence for the algorithm were shown under suitable conditions.
2. Futhermorc. a new method that to construct NCP-functions was proposed. By using the method, author obtained a new NCP-function with many useful properties, such as Lipschitz continuity. Strong semismoothness. good coercivity etc. A new refor-mulation was constructed by using it, and a similar algorithm as above was provided on the reformulation- The global convergence and local superlinear (or quadratic) con-vergence were obtained under weaker assumptions than above. Numerical results show that the algorithm is robust and efficient.
引文
[1]袁亚湘，孙文瑜.最优化理论与方法[M]北京: 科学出版社，1997.
[2]陈宝林.最优化理论与算法[M].北京：清华大学出版社，2005.
[3] F.Facchinei und J.S.Pang. Finite-dimensional variational inequalities and complementarity prob-lems [M].Springer-Verlag.New York.Berlin.Heidelberg. 2003.
[4] L.Qi. Convergence analysis of some algorithms for solving nonsmoth equations [2\.Math.Oper. Res.-1993.18:pp. 227-244.
[5]L.Qi and J.Sun. A nonsmooth version of Newton's method [J].Math.programming 1993.58:pp. 353-368.
[6] A.Fischer. Solution of monotone complementarity problems with locally Lipschitaian functions [J].Math.Programrning.l997,76: pp. 513-532.
[7] F.Wang,K.Zhang and X.Tan. A fractional programming algorithm based on conic quasi-Newton trust region method for unconstrained minimization [J].Applied Mathematics and Computa-tion.2006,181:pp. 1061-1067.
[8] Y.Ji.S.Qu. Y.Wang and H.Li. A conic trust region method for optimization with nonlinear equality and inequality constrains via active-set strategy [J],Applied Mathematics and Com-putation.2006.183:pp. 217-231.
[9] C.J.Wang. Dogleg paths and trust region methods with back tracking technique for uncon-strained optimization [J].Applied Mathematics and Computation. 2006. 177:pp. 159-169.
[10] J.Z.Zhang and C.X. Xu. A class ot indefinite dogleg path methods for unconstrained minimiza-tion [J].SIAM Journal on Optimization.l999.9:pp. 616-667.
[11] J.T.Mo.C.Y.Lui and S.C.Yan. A nonmonotone trust- region method based on nonincreasing technique of weighted average of the successive function values [Z],Journal of Computational and Applied Mathematic3.2006.doi: 10.1016/j.cain.2006.10.070
[12] L.Grippo. F.Lampariello and S.Luctdi. A nonmonotone line search technique for Newton ' s method [J].SlAM J. Numer. Anal..l986.23:pp. 707-716.
[13] J.Nocedal and Y. Yuan . Combing trust region method and line search techniques [R].Illinois USA :Department of Computer Science, Northwestern University. 1991.
[14]钟守楠，高飞．纪昌明.遗传信赖域方法[J].数学杂志2001.21:pp.468-472
[15] H.D.Qi.L.Q.Qi and D.F.Snn. Soring Karush-Ku hn-Tucker systems via trust region and the con-jugate gradient methods [J].SIAM,J.Optim..2003,14:pp. 439-463.
[16]乌力吉.互补问题的乘子法[D].呼和浩特：内蒙古大学博士论文，2004
[17] Glsac, Complementarity problems [M].Berlin:Springer-Yerlag. 1992.
[18] M.C.Ferris and J.S.Pang. Engineering and ecnomic applications of complementarity prob-lems [J].SIAM J. Review.1997,39:pp- 669-713.
[19] R. W .Cottle. J.S.Pang and R.E.Stone. The linear complementarity problem [Z].Computer Science, and Scientific Computing.San Diego:Academic Press.CA. 1990.
[20] 修乃华，高自友.互补问题算法的新进展[J].数学进展 1999,28:pp.193-210.
[21] 陈国庆，曹兵.箱式约束变分不等式的一种新NCP-函数及其广义牛顿法[J].计算数学 2002.24:pp.91-104.
[22] D.Sun and L.Qi. On NCP-functions [J].Computational Optimization and Applications. 1999.13: pp. 201-220.
[23] A.Fischer and H.Jiang. Merit functions for complementarity and related problems:A sur-vey [J].Computational Optimization and Applications.2000.17-pp. 159-182.
[24] B. Chen and N.Xiu. A global and local quadratic noninterior continuation smoothing method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions [J].SIAM J. Optim..l999.9:pp. 605 623.
[25] C.Kanzow and H.Pieper. Jacobian smoothing methods for general nonlinear complementarity problems [J].SIAM J. Optim.. 1999.9:pp. 342-373.
[26] B.Chen and P. T.Harker. A non-hiterior-point continuation method for linear complementarity problems [J].SIAM J. Matrix Anal. Appl.1993.14:pp- 1168-1190.
[27] C.Kanzow. Some noninterior continuation methods for linear complementarity prob-lems [J].SIAM J.Matrix Anal. AppL. 1996.17:pp- 851-868.
[28] P.M. Pardalos. Y. Ye. C.G.Han and J.A.Kaliski. Solution of Po-matrix linear cornplementarity problems using a potential reduction algorithm [J].SIAM J. Matrix Anal. AppL. 1993.14:pp. 1048-1060.
[29] T.De Luca. F.Facchinei and C. Kanzow. A theorctial and numerical comparison of some semis-mooth algorithm for complementarity problems [3].Compid. Optim. AppL. 2000.16:pp. 173-205.
[30] J.S.Pang and L.Qi Nonsmooth equations: motivation and algorithm [J].SIAM j. Op-tim.. 1993,3:pp. 443-165.
[31] F.Facchinei,A.Fischer,and CKanzow. A sernismooth Newton method for variational inequali-ties:The ca.se of box constraints [Z].in Complementarity and Variational Problems: State, of the Art, Proc.Appl.Math., 92. M.C.Ferris and J.S.Pang, eds..SIAM. Philadelphia. 1997. pp. 76-90.
[32] F.Facchinei.A.Fischer.and C.Kanzow. Regularity properties of a semismooth reformulation of variational inequalities [J].SIAM J.Optim.. 1998,8:pp. 850-869.
[33] F.Facchinei,A.Fischer,and C.Kanzow,and J.M.Peng. A simply constrained optimization re-formulation of KKT systems arising from variational inequalities [J]Appl.Math.Optim.. 1999.40:pp. 19-37.
[34] J.M.Peng. Global method for monotone variational inequality problems with inequality con-straints [J]J.0ptin.Theory ,AppL1997.95:pp. 419-430.
[35] L.Qi and H.Jiang. Semismooth Karush-Kuhn- Tucker equations and convergence analysis of Xew-ton and quasi-Newton methods for solving these equations [J].Math.Oper.Res..1997.22:pp. 301-325.
[36] C.Kanzow and H.D.Qi. A QP-free constrained Newton-type method for variational inequality problems [J]- Math.Prograrn.. 1999.85: pp. 81-106.
[37] Y. Yuan. On the truncated conjugate gradient method [J].Math.Program..2000.87: pp. 561-573.
[38] J.J.More and J.J.Sorensen. Computing a trust region step [J].SIAM J.Sci.Stat.Comput.. 1983,4: pp. 553-572.
[39]李飞.求解变分不等式问题的连续化方法及其灵敏性分析[D].西安:西安交通大学博士学位论文，2000.
[40] Y.J.Wang.N.H.Xiu.and J.Z.Zhang. Modified extragrdient method for variational inequalities and verification of solution existence [J]. J.Omput.Appl.Math.. 2003,119(1):pp. 167-183.
[41]刘光中.凸分析与极值问题[M].北京：高等教育出版社，1987.
[42]白富生.非线性规划中的精确罚函数[D].上海:上海大学博士学位论文，2003
[43] A.V.Fiacco and G.P.McCormick. The sequential unconstrained minimization technique for nonlinear programming .a primal-dual method [J]. Management Science. 1964,10:pp. 360-366.
[44] S.P.Han and O.L.Mnngasarian. Exact penalty functions in nonlinear programming [J].Moth. programming. 1979.17:pp. 251-269.
[45] 唐振先.序列二次规划中B_k的正定性研究[D].长沙：湖南大学硕士学位论文，2005.
[46] S.P.Han. A globally convergent method for nonlinear programming [J].Journal of Optimization Theory and Apptication.1977.22:pp. 297-309.
[47] 屈彪.非线性最优化问题中若干重要算法的理论研究[D].大连:大连理工大学博士学位论文，2002.
[48] P.H.Calamai and J.J.More. Projected gradient methods for linearly constrained problems [J]. Math.Programming. 1987.39:pp. 93-116.
[2]陈宝林.最优化理论与算法[M].北京：清华大学出版社，2005.
[3] F.Facchinei und J.S.Pang. Finite-dimensional variational inequalities and complementarity prob-lems [M].Springer-Verlag.New York.Berlin.Heidelberg. 2003.
[4] L.Qi. Convergence analysis of some algorithms for solving nonsmoth equations [2\.Math.Oper. Res.-1993.18:pp. 227-244.
[5]L.Qi and J.Sun. A nonsmooth version of Newton's method [J].Math.programming 1993.58:pp. 353-368.
[6] A.Fischer. Solution of monotone complementarity problems with locally Lipschitaian functions [J].Math.Programrning.l997,76: pp. 513-532.
[7] F.Wang,K.Zhang and X.Tan. A fractional programming algorithm based on conic quasi-Newton trust region method for unconstrained minimization [J].Applied Mathematics and Computa-tion.2006,181:pp. 1061-1067.
[8] Y.Ji.S.Qu. Y.Wang and H.Li. A conic trust region method for optimization with nonlinear equality and inequality constrains via active-set strategy [J],Applied Mathematics and Com-putation.2006.183:pp. 217-231.
[9] C.J.Wang. Dogleg paths and trust region methods with back tracking technique for uncon-strained optimization [J].Applied Mathematics and Computation. 2006. 177:pp. 159-169.
[10] J.Z.Zhang and C.X. Xu. A class ot indefinite dogleg path methods for unconstrained minimiza-tion [J].SIAM Journal on Optimization.l999.9:pp. 616-667.
[11] J.T.Mo.C.Y.Lui and S.C.Yan. A nonmonotone trust- region method based on nonincreasing technique of weighted average of the successive function values [Z],Journal of Computational and Applied Mathematic3.2006.doi: 10.1016/j.cain.2006.10.070
[12] L.Grippo. F.Lampariello and S.Luctdi. A nonmonotone line search technique for Newton ' s method [J].SlAM J. Numer. Anal..l986.23:pp. 707-716.
[13] J.Nocedal and Y. Yuan . Combing trust region method and line search techniques [R].Illinois USA :Department of Computer Science, Northwestern University. 1991.
[14]钟守楠，高飞．纪昌明.遗传信赖域方法[J].数学杂志2001.21:pp.468-472
[15] H.D.Qi.L.Q.Qi and D.F.Snn. Soring Karush-Ku hn-Tucker systems via trust region and the con-jugate gradient methods [J].SIAM,J.Optim..2003,14:pp. 439-463.
[16]乌力吉.互补问题的乘子法[D].呼和浩特：内蒙古大学博士论文，2004
[17] Glsac, Complementarity problems [M].Berlin:Springer-Yerlag. 1992.
[18] M.C.Ferris and J.S.Pang. Engineering and ecnomic applications of complementarity prob-lems [J].SIAM J. Review.1997,39:pp- 669-713.
[19] R. W .Cottle. J.S.Pang and R.E.Stone. The linear complementarity problem [Z].Computer Science, and Scientific Computing.San Diego:Academic Press.CA. 1990.
[20] 修乃华，高自友.互补问题算法的新进展[J].数学进展 1999,28:pp.193-210.
[21] 陈国庆，曹兵.箱式约束变分不等式的一种新NCP-函数及其广义牛顿法[J].计算数学 2002.24:pp.91-104.
[22] D.Sun and L.Qi. On NCP-functions [J].Computational Optimization and Applications. 1999.13: pp. 201-220.
[23] A.Fischer and H.Jiang. Merit functions for complementarity and related problems:A sur-vey [J].Computational Optimization and Applications.2000.17-pp. 159-182.
[24] B. Chen and N.Xiu. A global and local quadratic noninterior continuation smoothing method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions [J].SIAM J. Optim..l999.9:pp. 605 623.
[25] C.Kanzow and H.Pieper. Jacobian smoothing methods for general nonlinear complementarity problems [J].SIAM J. Optim.. 1999.9:pp. 342-373.
[26] B.Chen and P. T.Harker. A non-hiterior-point continuation method for linear complementarity problems [J].SIAM J. Matrix Anal. Appl.1993.14:pp- 1168-1190.
[27] C.Kanzow. Some noninterior continuation methods for linear complementarity prob-lems [J].SIAM J.Matrix Anal. AppL. 1996.17:pp- 851-868.
[28] P.M. Pardalos. Y. Ye. C.G.Han and J.A.Kaliski. Solution of Po-matrix linear cornplementarity problems using a potential reduction algorithm [J].SIAM J. Matrix Anal. AppL. 1993.14:pp. 1048-1060.
[29] T.De Luca. F.Facchinei and C. Kanzow. A theorctial and numerical comparison of some semis-mooth algorithm for complementarity problems [3].Compid. Optim. AppL. 2000.16:pp. 173-205.
[30] J.S.Pang and L.Qi Nonsmooth equations: motivation and algorithm [J].SIAM j. Op-tim.. 1993,3:pp. 443-165.
[31] F.Facchinei,A.Fischer,and CKanzow. A sernismooth Newton method for variational inequali-ties:The ca.se of box constraints [Z].in Complementarity and Variational Problems: State, of the Art, Proc.Appl.Math., 92. M.C.Ferris and J.S.Pang, eds..SIAM. Philadelphia. 1997. pp. 76-90.
[32] F.Facchinei.A.Fischer.and C.Kanzow. Regularity properties of a semismooth reformulation of variational inequalities [J].SIAM J.Optim.. 1998,8:pp. 850-869.
[33] F.Facchinei,A.Fischer,and C.Kanzow,and J.M.Peng. A simply constrained optimization re-formulation of KKT systems arising from variational inequalities [J]Appl.Math.Optim.. 1999.40:pp. 19-37.
[34] J.M.Peng. Global method for monotone variational inequality problems with inequality con-straints [J]J.0ptin.Theory ,AppL1997.95:pp. 419-430.
[35] L.Qi and H.Jiang. Semismooth Karush-Kuhn- Tucker equations and convergence analysis of Xew-ton and quasi-Newton methods for solving these equations [J].Math.Oper.Res..1997.22:pp. 301-325.
[36] C.Kanzow and H.D.Qi. A QP-free constrained Newton-type method for variational inequality problems [J]- Math.Prograrn.. 1999.85: pp. 81-106.
[37] Y. Yuan. On the truncated conjugate gradient method [J].Math.Program..2000.87: pp. 561-573.
[38] J.J.More and J.J.Sorensen. Computing a trust region step [J].SIAM J.Sci.Stat.Comput.. 1983,4: pp. 553-572.
[39]李飞.求解变分不等式问题的连续化方法及其灵敏性分析[D].西安:西安交通大学博士学位论文，2000.
[40] Y.J.Wang.N.H.Xiu.and J.Z.Zhang. Modified extragrdient method for variational inequalities and verification of solution existence [J]. J.Omput.Appl.Math.. 2003,119(1):pp. 167-183.
[41]刘光中.凸分析与极值问题[M].北京：高等教育出版社，1987.
[42]白富生.非线性规划中的精确罚函数[D].上海:上海大学博士学位论文，2003
[43] A.V.Fiacco and G.P.McCormick. The sequential unconstrained minimization technique for nonlinear programming .a primal-dual method [J]. Management Science. 1964,10:pp. 360-366.
[44] S.P.Han and O.L.Mnngasarian. Exact penalty functions in nonlinear programming [J].Moth. programming. 1979.17:pp. 251-269.
[45] 唐振先.序列二次规划中B_k的正定性研究[D].长沙：湖南大学硕士学位论文，2005.
[46] S.P.Han. A globally convergent method for nonlinear programming [J].Journal of Optimization Theory and Apptication.1977.22:pp. 297-309.
[47] 屈彪.非线性最优化问题中若干重要算法的理论研究[D].大连:大连理工大学博士学位论文，2002.
[48] P.H.Calamai and J.J.More. Projected gradient methods for linearly constrained problems [J]. Math.Programming. 1987.39:pp. 93-116.