A class of Benders decomposition methods for variational inequalities
- PDF / 389,716 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 206 Views
A class of Benders decomposition methods for variational inequalities Juan Pablo Luna1 · Claudia Sagastizábal2 · Mikhail Solodov3 Received: 31 January 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract We develop new variants of Benders decomposition methods for variational inequality problems. The construction is done by applying the general class of Dantzig–Wolfe decomposition of Luna et al. (Math Program 143(1–2):177–209, 2014) to an appropriately defined dual of the given variational inequality, and then passing back to the primal space. As compared to previous decomposition techniques of the Benders kind for variational inequalities, the following improvements are obtained. Instead of rather specific single-valued monotone mappings, the framework includes a rather broad class of multi-valued maximally monotone ones, and single-valued nonmonotone. Subproblems’ solvability is guaranteed instead of assumed, and approximations of the subproblems’ mapping are allowed (which may lead, in particular, to further decomposition of subproblems, which may otherwise be not possible). In addition, with a certain suitably chosen approximation, variational inequality subproblems become simple bound-constrained optimization problems, thus easier to solve. Keywords Variational inequalities · Benders decomposition · Dantzig–Wolfe decomposition · Stochastic Nash games Mathematics Subject Classification 90C33 · 65K10 · 49J53
B
Mikhail Solodov [email protected] Juan Pablo Luna [email protected] Claudia Sagastizábal [email protected]
1
COPPE-UFRJ, Engenharia de Produção, Cidade Universitária, Rio de Janeiro, RJ 21941-972, Brazil
2
IMECC - UNICAMP, Rua Sergio Buarque de Holanda, 651, Campinas, SP 13083-859, Brazil
3
IMPA – Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ 22460-320, Brazil
123
J. P. Luna et al.
1 Introduction In applications, feasible sets of optimization or variational problems frequently have some special structure, amenable to decomposition, which opens the potential to handle larger problems’ instances and to better computational performance. In this direction, two major classes of techniques are the Dantzig–Wolfe decomposition [8] and Benders decomposition [3]; see also [4, Chapter 11.1]. To outline the main ideas, it is sufficient to discuss the cases of two linear programs (LPs), structured as specified below. More precisely, consider ⎧ ⎨ min x f (x) s.t. H (x) ≤ 0 ⎩ g(x) ≤ 0, and
(1)
min x f (x) + r (y) s.t. g(x) + h(y) ≤ 0,
(2)
where all functions are affine with appropriate dimensions. In the case of (1), suppose the function g has a special structure such that (1) is (much) easier to solve if the constraint H (x) ≤ 0 were to be removed. In the case of (2), suppose the problem becomes (much) easier to solve if we fix the value of the variable y. For example, those two cases occur when the Jacobian matrix g defining the linear function g has the following block-separable structure: ⎡ ⎢ ⎢ g (x)
Data Loading...
