求解摩擦接触问题的一个非内点光滑化算法

给出了一个求解三维弹性有摩擦接触问题的新算法,即基于NCP函数的非内点光滑化算法．首先通过参变量变分原理和参数二次规划法,将三维弹性有摩擦接触问题的分析归结为线性互补问题的求解;然后利用NCP函数,将互补问题的求解转换为非光滑方程组的求解;再用凝聚函数对其进行光滑化,最后用NEWTON法解所得到的光滑非线性方程组．方法具有易于理解及实现方便等特点．通过线性互补问题的数值算例及接触问题实例证实了该算法的可靠性与有效性．     

Finite termination of a Newton-type algorithm for a class of affine variational inequality problems

Many optimization problems can be reformulated as a system of equations. One may use the generalized Newton method or the smoothing Newton method to solve the reformulated equations so that a solution of the original problem can be found. Such methods have been powerful tools to solve many optimization problems in the literature. In this paper, we propose a Newton-type algorithm for solving a class of monotone affine variational inequality problems (AVIPs for short). In the proposed algorithm, the techniques based on both the generalized Newton method and the smoothing Newton method are used. In particular, we show that the algorithm can find an exact solution of the AVIP in a finite number of iterations under an assumption that the solution set of the AVIP is nonempty. Preliminary numerical results are reported.     

盒子型区域上变分不等式的一个光滑牛顿法(英文)

The box constrained variational inequality problem can be reformulated as a nonsmooth equation by using median operator.In this paper,we present a smoothing Newton method for solving the box constrained variational inequality problem based on a new smoothing approximation function.The proposed algorithm is proved to be well defined and convergent globally under weaker conditions.     

A non-interior-point smoothing method for variational inequality problem

In this paper, we focus on the variational inequality problem. Based on the Fischer-Burmeister function with smoothing parameters, the variational inequality problem can be reformulated as a system of parameterized smooth equations, a non-interior-point smoothing method is presented for solving the problem. The proposed algorithm not only has no restriction on the initial point, but also has global convergence and local quadratic convergence, moreover, the local quadratic convergence is established without a strict complementarity condition. Preliminary numerical results show that the algorithm is promising.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

P_0函数非线性互补问题的一步非内点连续方法的收敛性

本文对于Ｐ０函数非线性互补问题提出了一个基于Ｋａｎｚｏｗ光滑函数的一步非内点连续方法,在适当的假设条件下,证明了方法的全局线性及局部二次收敛性．特别,在方法的全局线性收敛性的分析中,不需要假定非线性互补问题的函数的Ｊａｃｏｂｉ阵是Ｌｉｐｓｃｈｉｔｚ连续的．文献中为了得到非内点连续方法的全局线性收敛性,这一假定是被广泛使用的．本文提出的方法在每一次迭代只须解一个线性方程式组．     

One-step smoothing Newton method for solving the mixed complementarity problem with a function

The mixed complementarity problem (denote by MCP(F)) can be reformulated as the solution of a smooth system of equations. In the paper, based on a perturbed mid function, we propose a new smoothing function, which has an important property, not satisfied by many other smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P₀ function are discussed. Then we presented a one-step smoothing Newton algorithm to solve the MCP with a P₀ function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the rate of convergence of the method is proved under some suitable assumptions.     

A non-interior continuation algorithm for the CP based on a generalized smoothing function

Based on the generalized CP-function proposed by Hu et al. [S.L. Hu, Z.H. Huang, J.S. Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math. 230 (2009) 69-82], we introduce a smoothing function which is a generalization of several popular smoothing functions. By which we propose a non-interior continuation algorithm for solving the complementarity problem. The proposed algorithm only needs to solve at most one system of linear equations at each iteration. In particular, we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions. The preliminary numerical results demonstrate that the algorithm is effective.     

A new non-interior continuation method for <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-NCP based on a SSPM-function

In this paper, we consider a new non-interior continuation method for the solution of nonlinear complementarity problem with P ₀-function (P ₀-NCP). The proposed algorithm is based on a smoothing symmetric perturbed minimum function (SSPM-function), and one only needs to solve one system of linear equations and to perform only one Armijo-type line search at each iteration. The method is proved to possess global and local convergence under weaker conditions. Preliminary numerical results indicate that the algorithm is effective.     

Boundedness and Regularity Properties of Semismooth Reformulations of Variational Inequalities

The Karush-Kuhn-Tucker (KKT) system of the variational inequality problem over a set defined by inequality and equality constraints can be reformulated as a system of semismooth equations via an nonlinear complementarity problem (NCP) function. We give a sufficient condition for boundedness of the level sets of the norm function of this system of semismooth equations when the NCP function is metrically equivalent to the minimum function; and a sufficient and necessary condition when the NCP function is the minimum function. Nonsingularity properties identified by Facchinei, Fischer and Kanzow, 1998, SIAM J. Optim. 8, 850–869, for the semismooth reformulation of the variational inequality problem via the Fischer-Burmeister function, which is an irrational regular pseudo-smooth NCP function, hold for the reformulation based on other regular pseudo-smooth NCP functions. We propose a new regular pseudo-smooth NCP function, which is piecewise linear-rational and metrically equivalent to the minimum NCP function. When it is used to the generalized Newton method for solving the variational inequality problem, an auxiliary step can be added to each iteration to reduce the value of the merit function by adjusting the Lagrangian multipliers only. This work is supported by the Research Grant Council of Hong Kong This paper is dedicated to Alex Rubinov on the occasion of his 65th Birthday     

解可分离结构变分不等式的一种新的交替方向法

交替方向法是求解可分离结构变分不等式问题的经典方法之一, 它将一个大型的变分不等式问题分解成若干个小规模的变分不等式问题进行迭代求解. 但每步迭代过程中求解的子问题仍然摆脱不了求解变分不等式子问题的瓶颈. 从数值计算上来说, 求解一个变分不等式并不是一件容易的事情.因此, 本文提出一种新的交替方向法, 每步迭代只需要求解一个变分不等式子问题和一个强单调的非线性方程组子问题. 相对变分不等式问题而言, 我们更容易、且有更多的有效算法求解一个非线性方程组问题. 在与经典的交替方向法相同的假设条件下, 我们证明了新算法的全局收敛性. 进一步的数值试验也验证了新算法的有效性.     

A New Decomposition Method for Variational Inequalities with Linear Constraints

We propose a new decomposition method for solving a class of monotone variational inequalities with linear constraints. The proposed method needs only to solve a well-conditioned system of nonlinear equations, which is much easier than a variational inequality, the subproblem in the classic alternating direction methods. To make the method more flexible and practical, we solve the sub-problems approximately. We adopt a self-adaptive rule to adjust the parameter, which can improve the numerical performance of the algorithm. Under mild conditions, the underlying mapping be monotone and the solution set of the problem be nonempty, we prove the global convergence of the proposed algorithm. Finally, we report some preliminary computational results, which demonstrate the promising performance of the new algorithm.     

A non-interior continuation algorithm for solving the convex feasibility problem

In this paper, a specific class of convex feasibility problems are considered and a non-interior continuation algorithm based on a smoothing function to solve this class of problems is introduced. The proposed algorithm solves at most one system of linear equations at each iteration. Under some weak assumptions, we show that the algorithm is globally linearly and locally quadratically convergent. Preliminary numerical results are also reported, which verify the favorable theoretical properties of the proposed algorithm.     

Convergence of a non-interior continuation algorithm for the monotone SCCP

It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.     

Solving Variational Inequality Problems with Linear Constraints by a Proximal Decomposition Algorithm

The alternating direction method solves large scale variational inequality problems with linear constraints via solving a series of small scale variational inequality problems with simple constraints. The algorithm is attractive if the subproblems can be solved efficiently and exactly. However, the subproblem is itself variational inequality problem, which is structurally also difficult to solve. In this paper, we develop a new decomposition algorithm, which, at each iteration, just solves a system of well-conditioned linear equations and performs a line search. We allow to solve the subproblem approximately and the accuracy criterion is the constructive one developed recently by Solodov and Svaiter. Under mild assumptions on the problem's data, the algorithm is proved to converge globally. Some preliminary computational results are also reported to illustrate the efficiency of the algorithm.     

A non-interior continuation method for generalized linear complementarity problems

In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP) introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions, it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results are also reported. Received September 3, 1997 / Revised version received April 27, 1999?Published online July 19, 1999     

Global Method for Monotone Variational Inequality Problems with Inequality Constraints

We consider optimization methods for monotone variational inequality problems with nonlinear inequality constraints. First, we study the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed, and some desirable properties of the merit function are obtained. Through the merit function, the original variational inequality problem is reformulated as simple bounded minimization. Under certain assumptions, we show that any stationary point of the optimization problem is a solution of the problem considered. Finally, we propose a descent method for the variational inequality problem and prove its global convergence.     

基于一个新的NCP函数的光滑牛顿法求解非线性互补问题

本文研究了非线性互补的光滑化问题.利用一个新的光滑NCP函数将非线性互补问题转化为等价的光滑方程组,并在此基础上建立了求解P0-函数非线性互补问题的一个完全光滑化牛顿法,获得了算法的全局收敛性和局部二次收敛性的结果.并给出数值实验验证了理论分析的正确性.     

Numerical comparisons based on four smoothing functions for absolute value equation

The system of absolute value equation, denoted by AVE, is a non-differentiable NP-hard problem. Many approaches have been proposed during the past decade and most of them focus on reformulating it as complementarity problem and then solve it accordingly. Another approach is to recast the AVE as a system of nonsmooth equations and then tackle with the nonsmooth equations. In this paper, we follow this path. In particular, we rewrite it as a system of smooth equations and propose four new smoothing functions along with a smoothing-type algorithm to solve the system of equations. The main contribution of this paper focuses on numerical comparisons which suggest a better choice of smoothing function along with the smoothing-type algorithm.