A hybrid Newton method for solving the variational inequality problem via the D-gap function

The variational inequality problem (VIP) can be reformulated as an unconstrained minimization problem through the D-gap function. It is proved that the D-gap function has bounded level sets for the strongly monotone VIP. A hybrid Newton-type method is proposed for minimizing the D-gap function. Under some conditions, it is shown that the algorithm is globally convergent and locally quadratically convergent. Received May 6, 1997 / Revised version received October 30, 1998?Published online June 11, 1999     

一类变分不等式问题的信赖域算法

基于J.M.Peng研究一类变分不等式问题（简记为VIP）时所提出的价值函数，本文提出了求解强单调的VIP的一个新的信赖域算法。和已有的处理VIP的信赖域方法不同的是：它在每步迭代时，不必求解带信赖域界的子问题，仅解一线性方程组而求得试验步。这样，计算的复杂性一般来说可降低。在通常的假设条件下，文中还证明了算法的整体收敛性。最后，在梯度是半光滑和约束是矩形域的假设下，该算法还是超线性收敛的。     

Convergence and Error Bound of a Method for Solving Variational Inequality Problems via the Generalized D-Gap Function

The variational inequality problem (VIP) can be reformulated as an unconstrained minimization problem through the generalized D-gap function. Recently, a hybrid Newton-type method was proposed by Peng and Fukushima for minimizing a special form of the generalized D-gap function. In this paper, the hybrid Newton-type algorithm is extended to minimize the general form g of the generalized D-gap function. It is shown that the algorithm has nice convergence properties. Under some reasonable conditions, it is proved that the algorithm is locally and globally convergent. Moreover, it is proved that the function g has bounded level sets for strongly monotone VIP. An error bound of the algorithm is obtained.     

D-Gap Functions for Nonsmooth Variational Inequality Problems

We study the Clarke generalized gradient of the D-gap functions for the variational inequality problem (VIP) defined by a locally Lipschitz, but not necessarily differentiable, function in an Euclidean space. Using these results, we study the relationship between minimizing sequences and stationary sequences of the D-gap function, regardless of the existence of solutions of (VIP).     

Unconstrained optimization reformulations of equilibrium problems

We generalize the D-gap function developed in the literature for variational inequalities to a general equilibrium problem （EP）. Through the D-gap function, the equilibrium problem is cast as an unconstrained minimization problem. We give conditions under which any stationary point of the D-gap function is a solution of EP and conditions under which it provides a global error bound for EP. Finally, these results are applied to box-constrained EP and then weaker conditions are established to obtain the desired results for box-constrained EP.     

Theoretical and numerical investigation of the D-gap function for box constrained variational inequalities

The D-gap function, recently introduced by Peng and further studied by Yamashita et al., allows a smooth unconstrained minimization reformulation of the general variational inequality problem. This paper is concerned with the D-gap function for variational inequality problems over a box or, equivalently, mixed complementarity problems. The purpose of this paper is twofold. First we investigate theoretical properties in depth of the D-gap function, such as the optimality of stationary points, bounded level sets, global error bounds and generalized Hessians. Next we present a nonsmooth Gauss-Newton type algorithm for minimizing the D-gap function, and report extensive numerical results for the whole set of problems in the MCPLIB test problem collection. The work of this author was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports and Culture, Japan.     

Error bound results for generalized D-gap functions of nonsmooth variational inequality problems

Solving a variational inequality problem can be equivalently reformulated into solving a unconstraint optimization problem where the corresponding objective function is called a merit function. An important class of merit function is the generalized D-gap function introduced in [N. Yamashita, K. Taji, M. Fukushima, Unconstrained optimization reformulations of variational inequality problems, J. Optim. Theory Appl. 92 (1997) 439-456] and Yamashita and Fukushima (1997) [17]. In this paper, we present new fractional local/global error bound results for the generalized D-gap functions of nonsmooth variational inequality problems, which gives an effective estimate on the distance between a specific point to the solution set, in terms of the corresponding function value of the generalized D-gap function. Numerical examples and a simple application to the free boundary problem are also presented to illustrate the significance of our error bound results.     

Merit functions and error bounds for constrained mixed set-valued variational inequalities via generalized f-projection operators

In this paper, we introduce and investigate a constrained mixed set-valued variational inequality (MSVI) in Hilbert spaces. We prove the solution set of the constrained MSVI is a singleton under strict monotonicity. We also propose four merit functions for the constrained MSVI, that is, the natural residual, gap function, regularized gap function and D-gap function. We further use these functions to obtain error bounds, i.e. upper estimates for the distance to solutions of the constrained MSVI under strong monotonicity and Lipschitz continuity. The approach exploited in this paper is based on the generalized f-projection operator due to Wu and Huang, but not the well-known proximal mapping.     

Some Methods Based on the D-Gap Function for Solving Monotone Variational Inequalities

The D-gap function has been useful in developing unconstrained descent methods for solving strongly monotone variational inequality problems. We show that the D-gap function has certain properties that are useful also for monotone variational inequality problems with bounded feasible set. Accordingly, we develop two unconstrained methods based on them that are similar in spirit to a feasible method of Zhu and Marcotte based on the regularized-gap function. We further discuss a third method based on applying the D-gap function to a regularized problem. Preliminary numerical experience is also reported.     

An algorithm based on the generalized D-gap function for equilibrium problems

The equilibrium problem (EP) can be reformulated as an unconstrained minimization problem through the generalized D-gap function. In this paper, we propose an algorithm for minimizing the problem and analyze some convergence properties of the proposed algorithm. Under some reasonable conditions, we show that the iteration sequence generated by the algorithm is globally convergent and converges to a solution to the EP and the generalized D-gap function provides a global error bound for the algorithm.     

Equivalent Optimization Formulations and Error Bounds for Variational Inequality Problems

We investigate whether some merit functions for variational inequality problems (VIP) provide error bounds for the underlying VIP. Under the condition that the involved mapping F is strongly monotone, but not necessarily Lipschitz continuous, we prove that the so-called regularized gap function provides an error bound for the underlying VIP. We give also an example showing that the so-called D-gap function might not provide error bounds for a strongly monotone VIP.This research was supported by United College and by a direct grant of the Chinese University of Hong Kong. The authors thank the referees for helpful comments and suggestions.     

On the coerciveness of some merit functions for complementarity problems over symmetric cones

One of the popular solution methods for the complementarity problem over symmetric cones is to reformulate it as the global minimization of a certain merit function. An important question to be answered for this class of methods is under what conditions the level sets of the merit function are bounded (the coerciveness of the merit function). In this paper, we introduce the generalized weak-coerciveness of a continuous transformation. Under this condition, we prove the coerciveness of some merit functions, such as the natural residual function, the normal map, and the Fukushima-Yamashita function for complementarity problems over symmetric cones. We note that this is a much milder condition than strong monotonicity, used in the current literature.     

Neural networks for solving second-order cone constrained variational inequality problem

In this paper, we consider using the neural networks to efficiently solve the second-order cone constrained variational inequality (SOCCVI) problem. More specifically, two kinds of neural networks are proposed to deal with the Karush-Kuhn-Tucker (KKT) conditions of the SOCCVI problem. The first neural network uses the Fischer-Burmeister (FB) function to achieve an unconstrained minimization which is a merit function of the Karush-Kuhn-Tucker equation. We show that the merit function is a Lyapunov function and this neural network is asymptotically stable. The second neural network is introduced for solving a projection formulation whose solutions coincide with the KKT triples of SOCCVI problem. Its Lyapunov stability and global convergence are proved under some conditions. Simulations are provided to show effectiveness of the proposed neural networks.     

On the Lorentz Cone Complementarity Problems in Infinite-Dimensional Real Hilbert Space

In this article, we consider the Lorentz cone complementarity problems in infinite-dimensional real Hilbert space. We establish several results that are standard and important when dealing with complementarity problems. These include proving the same growth of the Fishcher–Burmeister merit function and the natural residual merit function, investigating property of bounded level sets under mild conditions via different merit functions, and providing global error bounds through the proposed merit functions. Such results are helpful for further designing solution methods for the Lorentz cone complementarity problems in Hilbert space.     

确定平板层流边界层速度分布的一种方法

用积分关系式方法求解平板层流边界层问题.首先,设定速度分布试函数,使之满足最基本的边界条件.试函数中的待定系数则利用已有的数值解的一些结果予以确定.它类似于彭一川(1992)提出的的方法,但比后者简便得多.按照彭一川的方法,决定试函数中的待定参数时,需求解一个三次代数方程,而本文方法则只需求解线性代数方程,精度也比彭一川的方法略高.     

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

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.     

On merit functions for <Emphasis Type="Italic">p</Emphasis>-order cone complementarity problem

Merit function approach is a popular method to deal with complementarity problems, in which the complementarity problem is recast as an unconstrained minimization via merit function or complementarity function. In this paper, for the complementarity problem associated with p-order cone, which is a type of nonsymmetric cone complementarity problem, we show the readers how to construct merit functions for solving p-order cone complementarity problem. In addition, we study the conditions under which the level sets of the corresponding merit functions are bounded, and we also assert that these merit functions provide an error bound for the p-order cone complementarity problem. These results build up a theoretical basis for the merit method for solving p-order cone complementarity problem.     

New NCP-Functions and Their Properties

Recently, Luo and Tseng proposed a class of merit functions for the nonlinear complementarity problem (NCP) and showed that it enjoys several interesting properties under some assumptions. In this paper, adopting a similar idea to that of Luo and Tseng, we present new merit functions for the NCP, which can be decomposed into component functions. We show that these merit functions not only share many properties with the one proposed by Luo and Tseng but also enjoy additional favorable properties owing to their decomposable structure. In particular, we present fairly mild conditions under which these merit functions have bounded level sets.     

A nonmonotone derivative-free algorithm for nonlinear complementarity problems based on the new generalized penalized Fischer–Burmeister merit function

In this paper, we propose a new generalized penalized Fischer–Burmeister merit function, and show that the function possesses a system of favorite properties. Moreover, for the merit function, we establish the boundedness of level set under a weaker condition. We also propose a derivative-free algorithm for nonlinear complementarity problems with a nonmonotone line search. More specifically, we show that the proposed algorithm is globally convergent and has a locally linear convergence rate. Numerical comparisons are also made with the merit function used by Chen (J Comput Appl Math 232:455–471, 2009), which confirm the superior behaviour of the new merit function.     

A one-parametric class of merit functions for the second-order cone complementarity problem

We investigate a one-parametric class of merit functions for the second-order cone complementarity problem (SOCCP) which is closely related to the popular Fischer–Burmeister (FB) merit function and natural residual merit function. In fact, it will reduce to the FB merit function if the involved parameter τ equals 2, whereas as τ tends to zero, its limit will become a multiple of the natural residual merit function. In this paper, we show that this class of merit functions enjoys several favorable properties as the FB merit function holds, for example, the smoothness. These properties play an important role in the reformulation method of an unconstrained minimization or a nonsmooth system of equations for the SOCCP. Numerical results are reported for some convex second-order cone programs (SOCPs) by solving the unconstrained minimization reformulation of the KKT optimality conditions, which indicate that the FB merit function is not the best. For the sparse linear SOCPs, the merit function corresponding to τ=2.5 or 3 works better than the FB merit function, whereas for the dense convex SOCPs, the merit function with τ=0.1, 0.5 or 1.0 seems to have better numerical performance.