×

zbMATH — the first resource for mathematics

A class of Dantzig-Wolfe type decomposition methods for variational inequality problems. (English) Zbl 1286.90112
Summary: 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, so 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.

MSC:
90C25 Convex programming
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
Software:
PLCP; PATH Solver; SQPlab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ben Amor, H; Desrosiers, J; Frangioni, A, On the choice of explicit stabilizing terms in column generation, Discret. Appl. Math., 157, 1167-1184, (2009) · Zbl 1169.90395
[2] Bonnans, J.F., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization: Theoretical and Practical Aspects, 2nd edn. Springer, Berlin (2006) · Zbl 1108.65060
[3] Briant, O; Lemaréchal, C; Meurdesoif, P; Michel, S; Perrot, N; Vanderbeck, F, Comparison of bundle and classical column generation, Math. Program., 113, 299-344, (2008) · Zbl 1152.90005
[4] Chen, G; Teboulle, M, A proximal-based decomposition method for convex minimization problems, Math. Program., 64, 81-101, (1994) · Zbl 0823.90097
[5] 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, 1318-1327, (2010) · Zbl 1226.90115
[6] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Inc., Boston (1992) · Zbl 0757.90078
[7] Crainic, TG; Frangioni, A; Gendron, B, Bundle-based relaxation methods for multi-commodity capacitated fixed charge metwork design problems, Discret. Appl. Math., 112, 73-99, (2001) · Zbl 1026.90010
[8] Dantzig, GB; Wolfe, P, The decomposition algorithm for linear programs, Econometric, 29, 767-778, (1961) · Zbl 0104.14305
[9] Dirkse, SP; Ferris, MC, The PATH solver: a non-monotone stabilization scheme for mixed complementarity problems, Optim. Methods Softw., 5, 123-156, (1995)
[10] Eckstein, J; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073
[11] Eckstein, J, Some saddle-function splitting methods for convex programming, Optim. Methods Softw., 4, 75-83, (1994)
[12] Facchinei, F; Kanzow, C, Generalized Nash equilibrium problems, Ann. Oper. Res., 175, 177-211, (2010) · Zbl 1185.91016
[13] Facchinei, F; Fischer, A; Piccialli, V, On generalized Nash games and variational inequalities, Oper. Res. Lett., 35, 159-164, (2007) · Zbl 1303.91020
[14] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[15] Ferris, MC; Munson, TS, Interfaces to PATH 3.0: design, implementation and usage, Comput. Optim. Appl., 12, 207-227, (1999) · Zbl 1040.90549
[16] Fuller, JD; Chung, W, Dantzig-Wolfe decomposition of variational inequalities, Comput. Econ., 25, 303-326, (2005) · Zbl 1161.91436
[17] He, B; Liao, LZ; Han, D; Yang, H, A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92, 103-118, (2002) · Zbl 1009.90108
[18] Hobbs, BF; Pang, JS, Nash-Cournot equilibria in electric power markets with piecewise linear demand functions and joint constraints, Oper. Res., 55, 113-127, (2007) · Zbl 1167.91356
[19] Jones, KL; Lustig, IJ; Farwolden, JM; Powell, WB, Multicommodity network flows: the impact of formulation on decomposition, Math. Program., 62, 95-117, (1993) · Zbl 0802.90039
[20] Josephy, N.H.: Newton’s Method for Generalized Equations. Technical Summary Report no. 1965. Mathematics Research Center, University of Wisconsin, Madison (1979)
[21] Kannan, A., Zavala, V.M.: A Game-Theoretical Dynamic Model for Electricity Markets. Argonne National Aboratory, Technical, Report ANL/MCS-P1792-1010 (2011) · Zbl 0358.90053
[22] Kannan, A., Shanbhag, U.V., Kim, H.M.: Addressing supply-side risk in uncertain power markets: stochastic generalized Nash models, scalable algorithms and error analysis. Optim. Methods Softw. www.tandfonline.com, doi:10.1080/10556788.2012.676756 · Zbl 1278.91077
[23] Kannan, A; Shanbhag, UV; Kim, HM, Strategic behavior in power markets under uncertainty, Energy Syst., 2, 115-141, (2011)
[24] Konnov, I.V.: Combined Relaxation Methods for Variational Inequalities. Lecture Notes in Economics and Mathematical Systems, vol. 495. Springer, Berlin (2001) · Zbl 0982.49009
[25] Kulkarni, AA; Shanbhag, UV, On the variational equilibrium as a refinement of the generalized Nash equilibrium, Automatica, 48, 45-55, (2012) · Zbl 1245.91006
[26] Kulkarni, A.A., Shanbhag, U.V.: Revisiting generalized Nash games and variational inequalities. J. Optim. Theory Appl. 154, 175-186 (2012) · Zbl 1261.90065
[27] Lotito, PA; Parente, LA; Solodov, MV, A class of variable metric decomposition methods for monotone variational inclusions, J. Convex Anal., 16, 857-880, (2009) · Zbl 1183.49011
[28] Luo, Z-Q; Tseng, P, Error bound and convergence analysis of matrix splitting algorithm for the affine variational inequality problems, SIAM J. Optim., 2, 43-54, (1992) · Zbl 0777.49010
[29] Martinet, B, Regularisation d’inequations variationelles par approximations successives, Revue Française d’Informatique et de Recherche Opérationelle, 4, 154-159, (1970) · Zbl 0215.21103
[30] Parente, LA; Lotito, PA; Solodov, MV, A class of inexact variable metric proximal point algorithms, SIAM J. Optim., 19, 240-260, (2008) · Zbl 1190.90216
[31] Pennanen, T, A splitting method for composite mappings, Numer. Funct. Anal. Optim, 23, 875-890, (2002) · Zbl 1054.49022
[32] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898, (1976) · Zbl 0358.90053
[33] Rockafellar, RT, Local boundedness of nonlinear, monotone operators, Mich. Math. J., 16, 397-407, (1969) · Zbl 0175.45002
[34] Rockafellar, RT, On the maximality of sums of nonlinear monotone operators, Trans. Am. Math. Soc., 149, 75-88, (1970) · Zbl 0222.47017
[35] Shanbhag, UV; Infanger, G; Glynn, PW, A complementarity framework for forward contracting under uncertainty, Oper. Res., 59, 810-834, (2011) · Zbl 1235.91074
[36] Solodov, MV; Ferris, MC (ed.); Mangasarian, OL (ed.); Pang, J-S (ed.), A class of globally convergent algorithms for pseudomonotone variational inequalities, 297-315, (2001), Dordrecht · Zbl 0987.65061
[37] Solodov, MV, A class of decomposition methods for convex optimization and monotone variational inclusions via the hybrid inexact proximal point framework, Optim. Methods Softw., 19, 557-575, (2004) · Zbl 1097.90041
[38] Solodov, M.V.: Constraint qualifications. In: Cochran, J.J., et al. (eds.) Wiley Encyclopedia of Operations Research and Management Science. Wiley, New York (2010) · Zbl 1169.90395
[39] Solodov, MV; Svaiter, BF, A unified framework for some inexact proximal point algorithms, Numer. Funct. Anal. Optim., 22, 1013-1035, (2001) · Zbl 1052.49013
[40] Solodov, MV; Tseng, P, Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 34, 1814-1830, (1996) · Zbl 0866.49018
[41] Spingarn, JE, Applications of the method of partial inverses to convex programming, Math. Program., 32, 199-223, (1985) · Zbl 0565.90058
[42] Tseng, P, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. Control Optim., 29, 119-138, (1991) · Zbl 0737.90048
[43] Tseng, P, Alternating projection-proximal methods for convex programming and variational inequalities, SIAM J. Optim., 7, 951-965, (1997) · Zbl 0914.90218
[44] Tseng, P, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim., 38, 431-446, (2000) · Zbl 0997.90062
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.