垂直线性互补问题的一步全局线性和局部二次收敛光滑Newton法

基于凝聚函数,提出一个求解垂直线性互补问题的光滑Newton法.该算法具有以下优点:(i)每次迭代仅需解一个线性系统和实施一次线性搜索;(ⅱ)算法对垂直分块P0矩阵的线性互补问题有定义且迭代序列的每个聚点都是它的解.而且,对垂直分块P₀+R₀矩阵的线性互补问题,算法产生的迭代序列有界且其任一聚点都是它的解;(ⅲ)在无严格互补条件下证得算法即具有全局线性收敛性又具有局部二次收敛性.许多已存在的求解此问题的光滑Newton法都不具有性质(ⅲ).     

垂直线性互补问题的一种光滑算法

文中给出了垂直线性互补问题的一个新的光滑价值函数,不同于光滑化方法中的价值函数,它不包含任何必须趋向零的参数,因此算法中不涉及参数调整步骤,而且具有良好的强制性.基此价值函数,提出了求解垂直线性互补问题的一种阻尼Newton类算法,并证明了该算法对竖块P0+R0矩阵的垂直线性互补问题具有全局收敛性;当解满足相当于BD-正则条件时,算法具有局部二次收敛性;在不增加额外校正步骤(算法的每个迭代步只求解一个Newton方程)的情形下,算法对竖块P-矩阵垂直线性互补问题(无须假设严格互补),具有有限步收敛性.数值实验结果令人满意.     

非线性互补问题的一种不可行非内点连续方法

基于 Chen- Mangasarian光滑函数的一个子类 ,针对单调非线性互补问题给出了一种不可行非内点连续方法预估校正算法 ,并在适当的条件下 ,证明了算法具有全局线性收敛性和局部二次收敛性。     

处理退化问题的一类SQP算法

本文对不等式优化问题提出了一个修正的序列二次规划算法(SQP).该算法适用于退化问题一积极约束梯度线性相关且严格互补条件不成立,并且算法是可行的,具有整体收敛与超线性收敛性.     

大规模非线性互补问题的共轭梯度法

提出求解大规模非线性互补问题NCP(F)的PRP型共轭梯度法,算法自然满足充分下降条件.当F是可微P_0+R_0函数且F'(χ)在水平集上全局Lipschitz连续条件下,证明了算法的全局收敛性.数值结果表明算法的有效性.     

线性互补问题在宽邻域下的局部二次收敛算法

艾文宝(2004)的宽邻域算法弥补了内点法在理论和实践表现之间的差异.基于这个算法的优越性,将其推广到线性互补问题中.新算法在一次迭代中,采用两个方向的线性组合作为新方向,并以满步长到达下一个点.可以证明,该算法具有O(n~(1/2)L)的理论复杂度,这是迄今为止最好的复杂度结果.同时,在假设线性互补问题存在严格互补解的前提下,证明算法具有局部二次收敛性.最后,数值实验说明算法是有效的.     

超线性与二次收敛序列线性方程组算法

本文,在无严格互补条件下,对非线性不等式约束最优化问题提出了一个新的序列线性方程组(简称SSLE)算法．算法有两个重要特征:首先,每次迭代,只须求解一个线性方程组或一个广义梯度投影阵,且线性方程组可以无解．其次,初始点可以任意选取．在无严格互补条件下,算法仍有全局收敛性、强收敛性、超线性收敛性及二次收敛性．文章的最后,还对算法进行了初步的数值实验．     

一个求解单调线性互补问题的高阶不可行内点算法

本文通过使用相同的矩阵因子，给出了一个求解单调线性互补问题的r-阶Mehrotra型宽城不可行内点算法，其中嵌入Wright的快速步与安全步算法．所给算法的迭代复杂性为O（n~((r 1)/r)L）．在考虑的问题有一个严格互补解的条件下，所给算法具有2阶Q-超线性收敛性．     

非线性均衡问题一个超线性收敛的光滑逼近SQP算法

研究非线性均衡问题,引入一个磨光算子将原问题转化为光滑问题,并用此光滑问题来逼近原来的问题而求解.在每步迭代中,通过转轴运算,求解一个线性约束二次规划问题和显式修正方向来得到主方向,并通过一个显式公式来得到高阶修正方向使得算法避免Maratos效应.在不需要上层互补条件下证明了算法具有全局收敛性和强收敛性且具有超线性收敛速度.     

一类带非单调搜索的SQP算法

本文给出了一个SQP新算法，其特点是使用了非单调搜索，并不再使用严格互补条件，使得算法在一定阶段后具有十分简洁的形式并保持整体收敛与超线性收敛性．     

Smoothing Trust Region Methods for Nonlinear Complementarity Problems with P 0-Functions

By using the Fischer–Burmeister function to reformulate the nonlinear complementarity problem (NCP) as a system of semismooth equations and using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing trust region algorithm for solving the NCP with P ₀ functions. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, local Q-superlinear/Q-quadratic convergence of the algorithm is established without the strict complementarity condition. This work was partially supported by the Research Grant Council of Hong Kong and the National Natural Science Foundation of China (Grant 10171030).     

NCP Functions Applied to Lagrangian Globalization for the Nonlinear Complementarity Problem

Based on NCP functions, we present a Lagrangian globalization (LG) algorithm model for solving the nonlinear complementarity problem. In particular, this algorithm model does not depend on some specific NCP function. Under several theoretical assumptions on NCP functions we prove that the algorithm model is well-defined and globally convergent. Several NCP functions applicable to the LG-method are analyzed in details and shown to satisfy these assumptions. Furthermore, we identify not only the properties of NCP functions which enable them to be used in the LG method but also their properties which enable the strict complementarity condition to be removed from the convergence conditions of the LG method. Moreover, we construct a new NCP function which possesses some favourable properties.     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

Superlinear／Quadratic One-step Smoothing Newton Methodf or P0-NCP

We propose a one-step smoothing Newton method for solving the non-linear complementarity problem with P0-function (P0-NCP) based on the smoothing symmetric perturbed Fisher function(for short, denoted as the SSPF-function). The proposed algorithm has to solve only one linear system of equations and performs only one line search per iteration. Without requiring any strict complementarity assumption at the P0-NCP solution, we show that the proposed algorithm converges globally and superlinearly under mild conditions. Furthermore, the algorithm has local quadratic convergence under suitable conditions. The main feature of our global convergence results is that we do not assume a priori the existence of an accumulation point. Compared to the previous literatures, our algorithm has stronger convergence results under weaker conditions.     

Predictor-Corrector Smoothing Newton Method,Based on a New Smoothing Function,for Solving the Nonlinear Complementarity Problem with a P 0 Function

By smoothing a perturbed minimum function, we propose in this paper a new smoothing function. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. We investigate the boundedness of the iteration sequence generated by noninterior continuation/smoothing methods under the assumption that the solution set of the NCP is nonempty and bounded. Based on the new smoothing function, we present a predictor-corrector smoothing Newton algorithm for solving the NCP with a P ₀ function, which is shown to be globally linearly and locally superlinearly convergent under suitable assumptions. Some preliminary computational results are reported.     

A smoothing inexact Newton method for nonlinear complementarity problems

In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP.     

A Null Space Approach for Solving Nonlinear Complementarity Problems

In this work, null space techniques are employed to tackle nonlinear complementarity problems （NCPs）. NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm.     

A self-adaptive trust region method for the extended linear complementarity problems

By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global convergence is obtained under mild conditions and the local superlinear convergence rate is also established under strict complementarity conditions. This work is supported by National Natural Science Foundation of China (No. 10671126) and Shanghai Leading Academic Discipline Project (S30501).     

非线性互补问题的一种新的光滑价值函数及牛顿类算法

A new smooth merit function was constructed for nonlinear complementarity problems (NCPs). Like as the merit function based on the famous FischerBurmeister function, the stationary point of the merit function is the solution of NCP when the function is only a P0-function, and the merit function has good coercive property. A damped Newton-type algorithm which based on the merit function was presented. The global and local superlinear or quadratic convergence results were obtained under suitable conditions. Furthermore, the finite termination property was obtained for affine case with P-matrix without using the hybrid switch technique or additional step as corrector Newton step as usual. Numerical results suggest that the method is promising.