首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 109 毫秒
1.
We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem, and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method, while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance rules is also discussed. Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000  相似文献   

2.
For the extended linear complementarity problem over an affine subspace, we first study some characterizations of (strong) column/row monotonicity and (strong) R 0-property. We then establish global s-type error bound for this problem with the column monotonicity or R 0-property, especially for the one with the nondegeneracy and column monotonicity, and give several equivalent formulations of such error bound without the square root term for monotone affine variational inequality. Finally, we use this error bound to derive some properties of the iterative sequence produced by smoothing methods for solving such a problem under suitable assumptions. Received: May 2, 1999 / Accepted: February 21, 2000?Published online July 20, 2000  相似文献   

3.
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  相似文献   

4.
The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied. Received June 30, 1995 / Revised version received October 9, 1998? Published online June 11, 1999  相似文献   

5.
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  相似文献   

6.
In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ 2n →ℜ 2n , u∈ℜ n is a parameter variable and x∈ℜ n is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z k =(u k ,x k )} such that the mapping H(·) is continuously differentiable at each z k and may be non-differentiable at the limiting point of {z k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999  相似文献   

7.
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  相似文献   

8.
The paper presents an interior embedding of nonlinear optimization problems. This embedding satisfies a sufficient condition for the success of pathfollowing algorithms with jumps being applied to one-parametric optimization problems.?The one-parametric problem obtained by the embedding is supposed to be regular in the sense of Jongen, Jonker and Twilt. This asumption is analyzed, and its genericity is proved in the space of the original optimization problems. Received May 20, 1997 / Revised version received October 6, 1998?Published online May 12, 1999  相似文献   

9.
Let VIP(F,C) denote the variational inequality problem associated with the mapping F and the closed convex set C. In this paper we introduce weak conditions on the mapping F that allow the development of a convergent cutting-plane framework for solving VIP(F,C). In the process we introduce, in a natural way, new and useful notions of generalized monotonicity for which first order characterizations are presented. Received: September 25, 1997 / Accepted: March 2, 1999?Published online July 20, 2000  相似文献   

10.
Smooth methods of multipliers for complementarity problems   总被引:2,自引:0,他引:2  
This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function, the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows that this class of algorithms is effective at solving many of the standard complementarity test problems. Received February 21, 1997 / Revised version received December 11, 1998? Published online May 12, 1999  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号