共查询到10条相似文献,搜索用时 109 毫秒
1.
Error bounds for proximal point subproblems and associated inexact proximal point algorithms 总被引:1,自引:0,他引: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.
Liqun Qi 《Journal of Global Optimization》2006,35(2):343-366
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.
Jan-J. Rückmann 《Mathematical Programming》1999,86(2):387-415
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.
A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities 总被引:17,自引:0,他引:17
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.
Walter Gómez Bofill 《Mathematical Programming》1999,86(3):649-659
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.
Conditions ensuring the applicability of cutting-plane methods for solving variational inequalities 总被引:1,自引:0,他引:1
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 相似文献