A new class of penalized NCP-functions and its properties

In this paper, we consider a class of penalized NCP-functions, which includes several existing well-known NCP-functions as special cases. The merit function induced by this class of NCP-functions is shown to have bounded level sets and provide error bounds under mild conditions. A derivative free algorithm is also proposed, its global convergence is proved and numerical performance compared with those based on some existing NCP-functions is reported.     

A penalized Fischer-Burmeister NCP-function

We introduce a new NCP-function in order to reformulate the nonlinear complementarity problem as a nonsmooth system of equations. This new NCP-function turns out to have stronger theoretical properties than the widely used Fischer-Burmeister function and other NCP-functions suggested previously. Moreover, numerical experience indicates that a semismooth Newton method based on this new NCP-function performs considerably better than the corresponding method based on the Fischer-Burmeister function. Received: March 10, 1997 / Accepted: February 15, 2000?Published online May 12, 2000     

On NCP-Functions

In this paper we reformulate several NCP-functions for the nonlinear complementarity problem (NCP) from their merit function forms and study some important properties of these NCP-functions. We point out that some of these NCP-functions have all the nice properties investigated by Chen, Chen and Kanzow [2] for a modified Fischer-Burmeister function, while some other NCP-functions may lose one or several of these properties. We also provide a modified normal map and a smoothing technique to overcome the limitation of these NCP-functions. A numerical comparison for the behaviour of various NCP-functions is provided.     

Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems

In this paper, we propose a new family of NCP-functions and the corresponding merit functions, which are the generalization of some popular NCP-functions and the related merit functions. We show that the new NCP-functions and the corresponding merit functions possess a system of favorite properties. Specially, we show that the new NCP-functions are strongly semismooth, Lipschitz continuous, and continuously differentiable; and that the corresponding merit functions have SC¹$S{C}^1$ property (i.e., they are continuously differentiable and their gradients are semismooth) and LC¹$L{C}^1$ property (i.e., they are continuously differentiable and their gradients are Lipschitz continuous) under suitable assumptions. Based on the new NCP-functions and the corresponding merit functions, we investigate a derivative free algorithm for the nonlinear complementarity problem and discuss its global convergence. Some preliminary numerical results are reported.     

一类新的Lagrangian乘子法

本文提出了求解光滑不等式约束最优化问题新的乘子法,在增广Lagrangian函数中,使用了新的NCP函数的乘子法．该方法在增广Lagrangian函数和原问题之间存在很好的等价性;同时该方法具有全局收敛性,且在适当假设下,具有超线性收敛率．本文给出了一个有效选择参数C的方法．     

一类新的曲线搜索下的多步下降算法

提出一类新的曲线搜索下的多步下降算法,在较弱条件下证明了算法具有全局收敛性和线性收敛速率.算法利用前面多步迭代点的信息和曲线搜索技巧产生新的迭代点,收敛稳定,不用计算和存储矩阵,适于求解大规模优化问题.数值试验表明算法是有效的.     

A new smoothing Newton method for solving constrained nonlinear equations

In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well.     

A regularization semismooth Newton method based on the generalized Fischer–Burmeister function for -NCPs

We consider a regularization method for nonlinear complementarity problems with F being a P₀-function which replaces the original problem with a sequence of the regularized complementarity problems. In this paper, this sequence of regularized complementarity problems are solved approximately by applying the generalized Newton method for an equivalent augmented system of equations, constructed by the generalized Fischer–Burmeister (FB) NCP-functions φ_p with p>1. We test the performance of the regularization semismooth Newton method based on the family of NCP-functions through solving all test problems from MCPLIB. Numerical experiments indicate that the method associated with a smaller p, for example p[1.1,2], usually has better numerical performance, and the generalized FB functions φ_p with p[1.1,2) can be used as the substitutions for the FB function φ₂.     

伪Newton—B族的导出及其性质

本文对无约束优化问题提出了一类新的近似牛顿法（伪牛顿-B族）,此方法同样具有二次终止性,产生的矩阵序列保持正定对称传递性。并证明了算法的全局收敛性和超级性收敛性。     

Globally Convergent Broyden-Like Methods for Semismooth Equations and Applications to VIP, NCP and MCP

In this paper, we propose a general smoothing Broyden-like quasi-Newton method for solving a class of nonsmooth equations. Under appropriate conditions, the proposed method converges to a solution of the equation globally and superlinearly. In particular, the proposed method provides the possibility of developing a quasi-Newton method that enjoys superlinear convergence even if strict complementarity fails to hold. We pay particular attention to semismooth equations arising from nonlinear complementarity problems, mixed complementarity problems and variational inequality problems. We show that under certain conditions, the related methods based on the perturbed Fischer–Burmeister function, Chen–Harker–Kanzow–Smale smoothing function and the Gabriel–Moré class of smoothing functions converge globally and superlinearly.     

线性均衡约束最优化的一个广义投影强次可行方向法

本文讨论带线性均衡约束最优化问题,首先利用摄动技术和一个互补函数将问题等价转化为一般约束最优化问题,然后结合广义投影技术和强次可行方向法思想,建立了问题的一个新算法.算法在迭代过程中保证搜索方向不为零,从而使得每次迭代只需计算一次广义投影.在适当的条件下,证明了算法的全局收敛性,并对算法进行了初步的数值试验.     

基于增广Lagrange函数的RQP方法

Recursive quadratic programming is a family of techniques developd by Bartholomew-Biggs and other authors for solving nonlinear programming problems.This paperdescribes a new method for constrained optimization which obtains its search di-rections from a quadratic programming subproblem based on the well-known aug-mented Lagrangian function.It avoids the penalty parameter to tend to infinity.We employ the Fletcher‘s exact penalty function as a merit function and the use of an approximate directional derivative of the function that avoids the need toevaluate the second order derivatives of the problem functions.We prove that thealgorithm possesses global and superlinear convergence properties.At the sametime, numerical results are reported.     

An algorithm for a class of nonlinear complementarity problems with non-Lipschitzian functions

In this paper, we focus on solving a class of nonlinear complementarity problems with non-Lipschitzian functions. We first introduce a generalized class of smoothing functions for the plus function. By combining it with Robinson's normal equation, we reformulate the complementarity problem as a family of parameterized smoothing equations. Then, a smoothing Newton method combined with a new nonmonotone line search scheme is employed to compute a solution of the smoothing equations. The global and local superlinear convergence of the proposed method is proved under mild assumptions. Preliminary numerical results obtained applying the proposed approach to nonlinear complementarity problems arising in free boundary problems are reported. They show that the smoothing function and the nonmonotone line search scheme proposed in this paper are effective.     

A family of quasi-Newton methods for unconstrained optimization problems

ABSTRACT

In this paper, we present a class of approximating matrices as a function of a scalar parameter that includes the Davidon-Fletcher-Powell and Broyden-Fletcher-Goldfarb-Shanno methods as special cases. A powerful iterative descent method for finding a local minimum of a function of several variables is described. The new method maintains the positive definiteness of the approximating matrices. For a region in which the function depends quadratically on the variables, no more than n iterations are required, where n is the number of variables. A set of computational results that verifies the superiority of the new method are presented.     

To the Theory of the Alternating Triangle Iteration Method

We construct a new class of versions of the adaptive alternating triangle method whose optimization requires no a priori spectral information in contrast with the approaches known so far. The same estimate for the convergence rate is preserved as in the presence of a priori information.     

Quadratic and Superlinear Convergence of the Huschens Method for Nonlinear Least Squares Problems

This paper is concerned with quadratic and superlinear convergence of structured quasi-Newton methods for solving nonlinear least squares problems. These methods make use of a special structure of the Hessian matrix of the objective function. Recently, Huschens proposed a new kind of structured quasi-Newton methods and dealt with the convex class of the structured Broyden family, and showed its quadratic and superlinear convergence properties for zero and nonzero residual problems, respectively. In this paper, we extend the results by Huschens to a wider class of the structured Broyden family. We prove local convergence properties of the method in a way different from the proof by Huschens.     

大规模无约束优化的一族LBFGS类算法

尝试在有限存储类算法中利用目标函数值所提供的信息.首先利用插值条件构造了一个新的二次函数逼近目标函数,得到了一个新的弱割线方程,然后将此弱割线方程与袁[1]的弱割线方程相结合,给出了一族包括标准LBFGS的有限存储BFGS类算法,证明了这族算法的收敛性.从标准试验函数库CUTE中选择试验函数进行了数值试验,试验结果表明这族算法的数值表现都与标准LBFGS类似.     

新的滤子方法

本文定义了一种新的滤子方法,并提出了求解光滑不等式约束最优化问题的滤子QP-free非可行域方法.通过乘子和分片线性非线性互补函数,构造一个等价于原约束问题一阶KKT条件的非光滑方程组.在此基础上,通过牛顿-拟牛顿迭代得到满足KKT最优条件的解,在迭代中采用了滤子线搜索方法,证明了该算法是可实现,并具有全局收敛性.另外,在较弱条件下可以证明该方法具有超线性收敛性.     

A Kantorovich-type analysis for a fast iterative method for solving nonlinear equations

We revisit a fast iterative method studied by us in [I.K. Argyros, On a two-point Newton-like method of convergent order two, Int. J. Comput. Math. 88 (2) (2005) 219-234] to approximate solutions of nonlinear operator equations. The method uses only divided differences of order one and two function evaluations per step. This time we use a simpler Kantorovich-type analysis to establish the quadratic convergence of the method in the local as well as the semilocal case. Moreover we show that in some cases our method compares favorably, and can be used in cases where other methods using similar information cannot [S. Amat, S. Busquier, V.F. Candela, A class of quasi-Newton generalized Steffensen's methods on Banach spaces, J. Comput. Appl. Math. 149 (2) (2002) 397-406; D. Chen, On the convergence of a class of generalized Steffensen's iterative procedures and error analysis, Int. J. Comput. Math. 31 (1989) 195-203]. Numerical examples are provided to justify the theoretical results.     

Minimization by coordinate descent

We examine the minimization of anN-dimensional real-valued function using the coordinate descent method. We impose conditions on the function under which the method converges; furthermore, by specializing our class of functions, we obtain the rate of convergence. We also present some examples from classical approximation theory where this method applies. A computational example is also given.