A class of Dantzig-Wolfe type decomposition methods for variational inequality problems

• 成果类型: Article
• 署名作者: Luna, Juan Pablo; Sagastizabal, Claudia; Solodov, Mikhail
• 署名单位: Instituto Nacional de Matematica Pura e Aplicada (IMPA)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0599-7
• 发表日期: 2014
• 页码: 177-209
• 关键词: proximal point algorithms; generalized nash games; monotone-operators; splitting method; Column Generation; FRAMEWORK; equilibrium; inclusions; mappings; bundle

摘要

We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig-Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with certain types of set-valued or nonmonotone operators, as well as with various kinds of approximations in the subproblems of the functions and derivatives in the single-valued case. Also, subproblems may be solved approximately. Convergence is established under reasonable assumptions. We also report numerical experiments for computing variational equilibria of the game-theoretic models of electricity markets. Our numerical results illustrate that the decomposition approach allows to solve large-scale problem instances otherwise intractable if the widely used PATH solver is applied directly, without decomposition.