×

Dual extragradient algorithms extended to equilibrium problems. (English) Zbl 1258.90088

Summary: We propose two iterative schemes for solving equilibrium problems which are called dual extragradient algorithms. In contrast with the primal extragradient methods [D. Q. Tran, M. L. Dung and V. H. Nguyen, Optimization 57, No. 6, 749–776 (2008; Zbl 1152.90564)] which require to solve two general strongly convex programs at each iteration, the dual extragradient algorithms proposed in this paper only need to solve, at each iteration, one general strongly convex program, one projection problem and one subgradient calculation. Moreover, we provide the worst case complexity bounds of these algorithms, which have not been done in the primal extragradient methods yet. An application to Nash-Cournot equilibrium models of electricity markets is presented and implemented to examine the performance of the proposed algorithms.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C60 Abstract computational complexity for mathematical programming problems

Citations:

Zbl 1152.90564

Software:

Ipopt
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blum E., Oettli W.: From optimization and variational inequality to equilibrium problems. Math. Student 63, 127–149 (1994) · Zbl 0888.49007
[2] Bruck R.E.: On the weak convergence of an Ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space. J. Math. Anal. Appl. 61, 159–164 (1977) · Zbl 0423.47023 · doi:10.1016/0022-247X(77)90152-4
[3] Chinchuluun, A., Pardalos, P.M., Migdalas, A., Pitsoulis, L. (eds): Pareto Optimality, Game Theory and Equilibria. Springer, Berlin (2008) · Zbl 1143.91004
[4] Cohen G.: Auxiliary problem principle and decomposition of optimization problems. J. Optim. Theory Appl. 32, 277–305 (1980) · Zbl 0417.49046 · doi:10.1007/BF00934554
[5] Cohen G.: Auxiliary principle extended to variational inequalities. J. Optim. Theory Appl. 59, 325–333 (1988) · Zbl 0628.90069 · doi:10.1007/BF00940305
[6] Contreras J., Klusch M., Krawczyk J.B.: Numerical solutions to Nash-Cournot equilibria in coupled constraint electricity markets. IEEE Trans. Power Syst. 19(1), 195–206 (2004) · doi:10.1109/TPWRS.2003.820692
[7] Facchinei F., Pang J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol I. II. Springer, New York (2003) · Zbl 1062.90002
[8] Flam S.D., Antipin A.S.: Equilibrium programming using proximal-like algorithms. Math. Program. 78, 29–41 (1997) · Zbl 0890.90150 · doi:10.1007/BF02614504
[9] Giannessi, F., Maugeri, A., Pardalos, P.M. (eds): Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models. Kluwer, Dordrecht (2004) · Zbl 0979.00025
[10] Konnov I.V.: Combined relaxation methods for variational inequalities. Springer-Verlag, Berlin (2001) · Zbl 0982.49009
[11] Konnov I.V., Kum S.: Descent methods for mixed variational inequalities in Hilbert spaces. Nonlinear Anal. 47, 561–572 (2001) · Zbl 1042.49514 · doi:10.1016/S0362-546X(01)00201-2
[12] Konnov I.V.: Generalized convexity and related topics. In: Konnov, I.V., Luc, D.T., Rubinov, (eds.) A.M. (eds) Combined Relaxation Methods for Generalized Monotone Variational Inequalities, pp. 3–331. Springer, Berlin (2007)
[13] Korpelevich G.M.: Extragradient method for finding saddle points and other problems. Matecon 12, 747–756 (1976) · Zbl 0342.90044
[14] Lalitha C.S.: A note on duality of generalized equilibrium problem. Optim. Lett. 4(1), 57–66 (2010) · Zbl 1206.90193 · doi:10.1007/s11590-009-0145-6
[15] Li S.J., Zhao P.: A method of duality for mixed vector equilibrium problem. Optim. Lett. 4(1), 85–96 (2010) · Zbl 1189.90189 · doi:10.1007/s11590-009-0141-x
[16] Maiorano, A., Song, Y.H., Trovato, M.: Dynamics of noncollusive oligopolistic electricity markets. In: Proceedings IEEE Power Engineering Society Winter Meeting, pp. 838–844, Singapore Jan (2000)
[17] Martinet B.: Régularisation d’inéquations variationelles par approximations successives. Revue Française d’Automatique et d’Informatique Recherche Opérationnelle 4, 154–159 (1970)
[18] Mastroeni G.: On auxiliary principle for equilibrium problems. Publicatione del Dipartimento di Mathematica dellUniversita di Pisa 3, 1244–1258 (2000)
[19] Mastroeni G.: Gap function for equilibrium problems. J. Global Optim. 27(4), 411–426 (2003) · Zbl 1061.90112 · doi:10.1023/A:1026050425030
[20] Moudafi A.: Proximal point algorithm extended to equilibrium problem. J. Nat. Geom. 15, 91–100 (1999) · Zbl 0974.65066
[21] Muu L.D., Oettli W.: Convergence of an adaptive penalty scheme for finding constrained equilibria. Nonlinear Anal. 18(12), 1159–1166 (1992) · Zbl 0773.90092 · doi:10.1016/0362-546X(92)90159-C
[22] Muu L.D., Quoc T.D.: Regularization algorithms for solving monotone Ky Fan inequalities with application to a Nash-Cournot equilibrium model. J. Optim. Theory Appl. 142(1), 185–204 (2009) · Zbl 1191.90084 · doi:10.1007/s10957-009-9529-0
[23] Nemirovskii A.S.: Effective iterative methods for solving equations with monotone operators. Ekon. Matem. Met. (Matecon) 17, 344–359 (1981)
[24] Nesterov Y.: Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. Ser. B 109(2–3), 319–344 (2007) · Zbl 1167.90014 · doi:10.1007/s10107-006-0034-z
[25] Nguyen V.H.: Lecture Notes on Equilibrium Problems. CIUF-CUD Summer School on Optimization and Applied Mathematics. Nha Trang, Vietnam (2002)
[26] Panicucci B., Pappalardo M., Passacantando M.: On solving generalized Nash equilibrium problems via optimization. Optim. Lett. 3(3), 419–435 (2009) · Zbl 1187.91011 · doi:10.1007/s11590-009-0122-0
[27] Pardalos, P.M, Rassias, T.M., Khan, A.A. (eds): Nonlinear Analysis and Variational Problems. Springer, Berlin (2010)
[28] Quoc T.D., Muu L.D.: Implementable quadratic regularization methods for solving pseudomonotone equilibrium problems. East West J. Math. 6(2), 101–123 (2004) · Zbl 1101.65064
[29] Quoc T.D., Muu L.D., Nguyen V.H.: Extragradient algorithms extended to equilibrium problems. Optimization 57(6), 749–776 (2008) · Zbl 1152.90564 · doi:10.1080/02331930601122876
[30] Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[31] Rockafellar R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056
[32] Taskar B., Lacoste-Julien S., Jordan M.I.: Structured prediction, dual extragradient and Bregman projections. J. Mach. Learn. Res. 7, 1627–1653 (2006) · Zbl 1222.62143
[33] Van N.T.T., Strodiot J.J., Nguyen V.H.: The interior proximal extragradient method for solving equilibrium problems. J. Global Optim. 44(2), 175–192 (2009) · Zbl 1192.90212 · doi:10.1007/s10898-008-9311-0
[34] Van N.T.T., Strodiot J.J., Nguyen V.H.: A bundle method for solving equilibrium problems. Math. Program. 116, 529–552 (2009) · Zbl 1155.49006 · doi:10.1007/s10107-007-0112-x
[35] Wachter A., Biegler L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[36] Zhu D.L., Marcotte P.: An extended descent framework for variational inequalities. J. Optim. Theory Appl. 80, 349–366 (1994) · Zbl 0798.49014 · doi:10.1007/BF02192941
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.