线性不等式约束的广义非线性互补问题的仿射内点信赖域方法  

Affine Scaling Interior Trust-Region Method for Solving Generalized Complementarity Problems with Linear Inequality Constraints

作　　者：朱德通[1] 蔡力[2] 

机构地区：[1]上海师范大学商学院,上海200234 [2]上海师范大学数学系,上海200234

出　　处：《数学年刊（A辑）》2010年第1期13-34,共22页Chinese Annals of Mathematics

基　　金：国家自然科学基金(No.10871130);上海市重点学科建设基金(No.T0401)资助的项目

摘　　要：提供了一种新的非单调内点回代线搜索技术的仿射内点信赖域方法解线性不等式约束的广义非线性互补问题(GCP).基于广义互补问题构成的半光滑方程组的广义Jacobian矩阵,算法使用l_2范数作为半光滑方程组的势函数,形成的信赖域子问题为一个带椭球约束的线性化的二次模型.利用广义牛顿方程计算试探迭代步,通过内点映射回代技术确保迭代点是严格内点,保证了算法的整体收敛性.在合理的条件下,证明了信赖域算法在接近最优点时可转化为广义拟牛顿步,进而具有局部超线性收敛速率.非单调技术将克服高度非线性情况加速收敛进展.最后,数值结果表明了算法的有效性.This paper proposes a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the generalized complementarity problems （GCP） with linear inequality constraints. The proposed algorithm uses a generalized Jacobian of the function involved the semismooth equations reformulated from the GCP and adopts squared Euclidean norm of the semismooth equations as a merit function. Based on a simply constrained differentiable minimization reformulation, the trustregion subproblem is defined by minimizing the local quadratic approximation of the squared Euclidean norm of the semismooth systems adding the augmented quadratic affine scaling term subject only to an ellipsoidal constraint. The global convergence results are developed in a very general setting of computing trial steps by a generalized Newton-like method while the strict interior feasibility is augmented by an interior projective backtracking technique. The authors establish that close to a regular solution the trust-region algorithm turns into the generalized Newton method under some mild conditions, which is shown to converge locally q-superlinearly. A nonmonotonic backtracking criterion should bring about speeding up the convergence progress under some large curvature curves of the contours of merit function. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.

关 键 词：半光滑方程 信赖域方法 广义非线性互补问题 仿射内点 

分 类 号：O224[理学—运筹学与控制论]