非内点组合同伦方法解变分不等式.pdf

A Non-interior bined Homotopy Method for Solving
Variational Inequalities ∗
Shang Yu Feng 1,2, Yu Bo 1
of Applied Mathematics, Dalian University of Technology, Dalian, 116024
and Research Section of Mathematics, Aviation University of Air force, Changchun, 130022
Abstract. In this paper, we present a new homotopy method for variational inequalities in unbounded
sets. Compared to the method in [J. Global Optim. 31(2005), 121-131], such a method requires no assump-
tion that the initial interior point exists. To this end, based on a smooth perturbation of the constraints, we
construct a new framework of homotopy to solve problems of this type. Next, under some assumption, the
existence of solution path is proved, so we obtain a globally convergent algorithm. Lastly, several numerical
results illustrating the method are given.
Key words. Variational inequality, Homotopy method, Global convergence.
1 Introduction
Consider the Finite-dimensional Variational Inequality Problem(VI(X, F )): find a vector x∗∈
X ⊂ Rn such that
(x − x∗)T F (x∗) ≥ 0, ∀x ∈ X. ()
where F is a mapping from Rn to itself and X is a feasible set which is a nonempty, closed and
convex subset of Rn and defined as follows:
n
X = {x ∈ R : gi(x) ≤ 0, i = 1, . . . , m}, ()
where gi(x), i = 1, · · · , m, are assumed to be convex.
This problem arises in several equilibrium models in economics, operations research and
transportation science, and serves as a unified formulation of several important mathematical
problems. Up to now, there are a great many approaches which have been developed in recent
years to the variational inequality problem(VIP)s. We refer to prehensive monograph
on the theory, algorithms and applications for finite dimensional variational inequality and
complementarity problems found in [1, 2]. The best known of those methods are those which
are based on a Karush-Kuhn-Tucker (KKT-) conditions of VI(X, F ) as follows:
* T