×

zbMATH — the first resource for mathematics

A class of Benders decomposition methods for variational inequalities. (English) Zbl 1446.90156
Summary: 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 the first author et al. [Math. Program. 143, No. 1–2 (A), 177–209 (2014; Zbl 1286.90112)] 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.
MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K10 Numerical optimization and variational techniques
49J53 Set-valued and variational analysis
Software:
PLCP; SQPlab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Attouch, H.; Théra, M., A general duality principle for the sum of two operators, J. Convex Anal., 3, 1, 1-24 (1996) · Zbl 0861.47028
[2] Auslender, A.; Teboulle, M., Lagrangian duality and related multiplier methods for variational inequality problems, SIAM J. Optim., 10, 4, 1097-1115 (2000) · Zbl 0996.49005
[3] Benders, JF, Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 1, 238-252 (1962) · Zbl 0109.38302
[4] Bonnans, J.; Gilbert, J.; Lemaréchal, C.; Sagastizábal, C., Numerical Optimization: Theoretical and Practical Aspects (2006), Berlin: Springer, Berlin · Zbl 1108.65060
[5] Burachik, RS; Iusem, AN, Set-Valued Mappings and Enlargements of Monotone Operators, Springer Optimization and Its Applications (2008), New York: Springer, New York
[6] Çelebi, E.; Fuller, JD, Master problem approximations in Dantzig-Wolfe decomposition of variational inequality problems with applications to two energy market models, Comput. Oper. Res., 40, 11, 2724-2739 (2013) · Zbl 1348.90581
[7] Chung, W.; Fuller, JD, Subproblem approximation in Dantzig-Wolfe decomposition of variational inequality models with an application to a multicommodity economic equilibrium model, Oper. Res., 58, 5, 1318-1327 (2010) · Zbl 1226.90115
[8] Dantzig, GB; Wolfe, P., The decomposition algorithm for linear programs, Econom.: J. Econom. Soc., 29, 4, 767-778 (1961) · Zbl 0104.14305
[9] Eckstein, J.; Ferris, MC, Smooth methods of multipliers for complementarity problems, Math. Program., 86, 65-90 (1999) · Zbl 0978.90094
[10] Facchinei, F.; Pang, JS, Finite-Dimensional Variational Inequalities and Complementarity Problems (2007), Berlin: Springer, Berlin
[11] Fuller, JD; Chung, W., Dantzig-Wolfe decomposition of variational inequalities, Comput. Econ., 25, 4, 303-326 (2005) · Zbl 1161.91436
[12] Fuller, JD; Chung, W., Benders decomposition for a class of variational inequalities, Eur. J. Oper. Res., 185, 1, 76-91 (2008) · Zbl 1141.90034
[13] Gabriel, SA; Fuller, JD, A Benders decomposition method for solving stochastic complementarity problems with an application in energy, Comput. Econ., 35, 4, 301-329 (2010) · Zbl 1189.91105
[14] Luna, JP; Sagastizábal, C.; Solodov, M., A class of Dantzig-Wolfe type decomposition methods for variational inequality problems, Math. Program., 143, 1-2, 177-209 (2014) · Zbl 1286.90112
[15] Luna, JP; Sagastizábal, C.; Solodov, M., An approximation scheme for a class of risk-averse stochastic equilibrium problems, Math. Program., 157, 2, 451-481 (2016) · Zbl 1414.91293
[16] Mosco, U., Dual variational inequalities, J. Math. Anal. Appl., 40, 202-206 (1972) · Zbl 0262.49003
[17] Rahmaniani, R.; Crainic, TG; Gendreau, M.; Rei, W., The Benders decomposition algorithm: a literature review, Eur. J. Oper. Res., 259, 3, 801-817 (2017) · Zbl 1402.90158
[18] Rockafellar, RT, On the maximality of sums of nonlinear monotone operators, Trans. Am. Math. Soc., 149, 75-88 (1970) · Zbl 0222.47017
[19] Sagastizábal, CA; Solodov, MV, Parallel variable distribution for constrained optimization, Comput. Optim. Appl., 22, 1, 111-131 (2002) · Zbl 1007.90063
[20] Solodov, MV; Cochran, JJ, Constraint qualifications, Wiley Encyclopedia of Operations Research and Management Science (2010), New York: Wiley, New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.