非线性规划的QP-free方法

数学物理学报 ›› 2011, Vol. 31 ›› Issue (1): 103-116.

非线性规划的QP-free方法

姜爱萍

上海大学悉尼工商学院上海 201800

收稿日期:2008-11-29 修回日期:2010-01-13 出版日期:2011-02-25 发布日期:2011-02-25
基金资助:
上海市优秀青年教师科研专项(B.37-0115-08-007)、上海大学创新基金(A.10-0115-09-900)、上海市自然科学基金(09ZR1411000)和国家自然科学基金(70502020)资助

QP-free Method for Nonlinear Programming Problems

JIANG Ai-Ping

Sydney Institute of Language and Commerce, Shanghai University, Shanghai |201800

Received:2008-11-29 Revised:2010-01-13 Online:2011-02-25 Published:2011-02-25
Supported by:
上海市优秀青年教师科研专项(B.37-0115-08-007)、上海大学创新基金(A.10-0115-09-900)、上海市自然科学基金(09ZR1411000)和国家自然科学基金(70502020)资助

摘要/Abstract

摘要：

该文提出一种QP-free可行域方法用来解满足光滑不等式约束的最优化问题.此方法把QP-free方法和3-1线性互补函数相结合一个等价于原约束问题的一阶KKT条件的方程组,并在此基础上给出解这个方程组的迭代算法. 这个方法的每一步迭代都可以看作是对求KKT条件解的牛顿或拟牛顿迭代的扰动,且在该方法中每一步的迭代均具有可行性. 该方法是可实行的且具有全局性, 且不需要严格互补条件、聚点的孤立性和积极约束函数梯度的线性独立等假设. 在与文献[2]中相同的适当条件下,此方法还具有超线性收敛性. 数值检验结果表示,该文提出的QP-free可行域方法是切实有效的方法.

关键词: 滤子, QP-free方法, , 约束函数, NCP函数, 收敛性

Abstract:

In this paper, A QP-free feasible method is proposed to obtain the local convergence under some weaker conditions for the minimization of a smooth function subject to smooth inequalities. Based on the solutions of linear systems of equation reformulation of the KKT optimality conditions, this method uses the 3-1 NCP function^[1]. The method is iterative, which means each iteration can be viewed as a perturbation of a Newton or Quasi Newton on both the primal and dual variables for the solution of the equalities in the KKT first order conditions of optimality, and the feasibility of all iterations is ensured in this method. In particular, this method is implementable and
globally convergent without assuming the strict complementarity condition, the isolation of the accumulation point and the linear
independence of the gradients of active constrained functions. The method has also superlinear convergence rate under some mild
conditions which are the same as those in[2]. Some preliminary numerical results indicate that this new QP-free feasible method is quite promising.

Key words: Filter, QP-free method, Constrained function, Convergence, NCP function

中图分类号:

90C30

姜爱萍. 非线性规划的QP-free方法[J]. 数学物理学报, 2011, 31(1): 103-116.

JIANG Ai-Ping. QP-free Method for Nonlinear Programming Problems[J]. Acta mathematica scientia,Series A, 2011, 31(1): 103-116.

参考文献

[1] Han J Y, Xiu N H, Qi H D. Nonlinear Omplementary Theory and Algorithm. Shanghai: Shanghai Science and Technology Press, 2006

[2] Qi H, Qi L. A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization. SIAM J Optim, 2000, 11: 113--132

[3] Ferris M C, Pang J S. Engineering and economic applications of complementarity problems. SIAM Review, 1997, 39: 669--713

[4] Fukushima M. Merit Functions for Variational and Complementarity Problems//Di Pillo G, Giannessi F, eds. Nonlinear Optimization and Applications. New York: Plenum Press, 1996: 155--170

[5] Harker P T, Pang J S. Finite-dimensional variational and nonlinear complementarity problems: a survey of theory, algorithm and applications. Mathematical Programming, 1990, 48: 161--220

[6] Pang J S. Complementarity Problems//Horst R, Pardalos P, eds. Handbook of Global Optimization. Boston: Kluwer Academic Publishers, 1995: 271--338

[7] Facchinei F, Kanzow C. A nonsmooth inexact Newton method for the solution of large nonlinear complementarity problems. Mathematics Programming, 1997, 76: 493--512

[8] Herskovits J N. A two-stage feasible direction algorithm for nonlinear constrained optimization. Math Programming, 1986, 36: 19--38

[9] Herskovits J N. Feasible direction interior-point technique for nonlinear optimization. J Optim Theory Appl, 1998, 99: 121--146

[10] Panier E R, Tits A L, Herskovits J N. A QP-free, globally, locally superlinear convergent method for the inequality constrained optimization problems. SIAM J Control Optim, 1988, 36: 788--811

[11] Sun D. A regularization Newton method for solving nonlinear complementarity problems. Applied Mathematics and Optimization, 1999, 40: 315--339

[12] Urban T, Tits A L, Lawrence C T. A Primal-dual Interior-point Method for Nonvex Optimization with Multiple Logarithmic Barrier
Parameters and with Strong Convergence Properties. Maryland: Department of Electrical Engineering and Institute for Systems Research,
University of Maryland, College Park, 1998

[13] Panier E R, Tits A L. A superlinear convergent feasible method for the solution of inequality constrained optimization problems. SIAM
J Control Optim, 1987, 25: 934--950

[14] Clarke F H. Optimization and Nonsmooth Analysis. Philadelphia: SIAM, 1990

[15] Chen X, Qi L, Yang Y F. Lagrangian globalization methods for nonlinear complementarity problem. Optim Theory Appl, 2002, 112: 77--95

[16] Pu D, Zhang J. An inexact generalized Newton method for second order C-differentiable optimization. J of Computational and Applied Mathematics, 1998, 93: 107--122

[17] Qi L. Convergence analysis of some method for solving nonsmooth equations. Marhematics of Operations Research, 1993, 18: 227--243

[18] Schittkowski K. More Test Examples for Nonlinear Programming Codes. New York: Springer-Verlag, 1988