\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A linesearch projection algorithm for solving equilibrium problems without monotonicity in Hilbert spaces

  • *Corresponding author: Rong Hu

    *Corresponding author: Rong Hu 

This work was supported by National Natural Science Foundation of China (11471230 and 11771067)

Abstract Full Text(HTML) Figure(6) / Table(10) Related Papers Cited by
  • We propose a linesearch projection algorithm for solving non-monotone and non-Lipschitzian equilibrium problems in Hilbert spaces. It is proved that the sequence generated by the proposed algorithm converges strongly to a solution of the equilibrium problem under the assumption that the solution set of the associated Minty equilibrium problem is nonempty. Compared with existing methods, we do not employ Fejér monotonicity in the strategy of proving the convergence. This comes from projecting a fixed point instead of the current point onto a subset of the feasible set at each iteration. Moreover, employing an Armijo-linesearch without subgradient has a great advantage in CPU-time. Some numerical experiments demonstrate the efficiency and strength of the presented algorithm.

    Mathematics Subject Classification: Primary: 65K15, 90C33; Secondary: 65J15.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Results for Algorithm 1 and PA with $ \theta = 0.05, \delta = 0.01 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $

    Figure 2.  Results for Algorithm 1 with different $ \theta $ ($ \delta = 0.01 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $)

    Figure 3.  Results for Algorithm 1 with different $ \beta_k $ ($ \theta = 0.1 $ and $ \delta = 0.01 $)

    Figure 4.  Results for Algorithm 1 with different $ \beta_k $ ($ \theta = 0.1 $ and $ \delta = 0.01 $)

    Figure 5.  Results for Algorithm 1 with different $ \delta $ ($ \theta = 0.1 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $)

    Figure 6.  Results for Algorithm 2, PA-BM and PA-YH with $ \delta = 0.01 $, $ \theta = 0.95 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $

    Table 1.  The parameters of cost functions of the generating units

    Gen. $ \alpha_{j}^{0} $ $ \beta_{j}^{0} $ $ \gamma_{j}^{0} $ $ \alpha_{j}^{1} $ $ \beta_{j}^{1} $ $ \gamma_{j}^{1} $
    1 0.0400 2.00 0.00 2.00 1.00 25.0000
    2 0.0350 1.75 0.00 1.75 1.00 28.5714
    3 0.1250 1.00 0.00 1.00 1.00 8.0000
    4 0.0116 3.25 0.00 3.25 1.00 86.2069
    5 0.0500 3.00 0.00 3.00 1.00 20.0000
    6 0.0500 3.00 0.00 3.00 1.00 20.0000
     | Show Table
    DownLoad: CSV

    Table 2.  The lower and upper bounds of the power generation of the generating units and companies

    Com. Gen. $ x_{\min }^{g} $ $ x_{\max }^{g} $ $ x_{\min }^{c} $ $ x_{\max }^{c} $
    1 1 0 80 0 80
    2 2 0 80 0 130
    2 3 0 50 0 130
    3 4 0 55 0 125
    3 5 0 30 0 125
    3 6 0 40 0 125
     | Show Table
    DownLoad: CSV

    Table 3.  Results for Algorithm 1 and PA with $ \theta $ ($ \delta = 0.01 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $)

    $ \theta $ Number of iterations CPU-time(s)
    Algorithm 1 PA Algorithm 1 PA
    0.05 836 1661 41.8707 732.9239
    0.1 546 734 24.3050 99.7314
    0.2 322 431 13.8061 45.3339
    0.25 286 346 18.9073 42.1359
    0.5 150 263 9.4381 32.6042
    0.6 162 207 4.4148 12.8857
    0.7 171 191 4.5864 12.8545
    0.85 183 149 4.6020 8.2369
    0.95 187 184 4.9608 12.1681
    0.99 222 159 7.3944 15.1945
     | Show Table
    DownLoad: CSV

    Table 4.  Results for Algorithm 1 and PA with different $ \beta_k $ ($ \theta = 0.1 $ and $ \delta = 0.01 $)

    $ \beta_k $ Number of iterations CPU-time(s)
    Algorithm 1 PA Algorithm 1 PA
    0.1 688 998 67.1116 281.2386
    0.2 617 966 33.6650 215.6090
    0.3 560 840 26.2082 134.1921
    0.4 548 755 22.8853 103.7563
    0.5 546 734 22.1365 94.7706
    0.6 530 728 22.3081 90.5274
    0.7 530 729 20.0461 90.7302
    0.8 521 732 19.2817 91.1826
    0.9 518 737 18.9853 91.0266
    1.0 508 742 19.1725 94.7394
     | Show Table
    DownLoad: CSV

    Table 5.  Results for Algorithm 1 with different $ \beta_k $ ($ \theta = 0.1 $ and $ \delta = 0.01 $)

    $ \beta_k $ Number of iterations CPU-time(s)
    $ \frac{k+1}{k+3} $ 56 4.8048
    $ \frac{k+1}{2k+3} $ 43 1.7160
    $ \frac{k+1}{3k+3} $ 37 1.4976
    $ \frac{k+1}{4k+3} $ 33 1.3728
    $ \frac{k+1}{5k+3} $ 30 1.1388
    0.1 688 64.7092
    0.3 560 42.6819
    0.5 546 39.0627
    0.7 530 36.5354
    1.0 508 33.6182
     | Show Table
    DownLoad: CSV

    Table 6.  Results for Algorithm 1 with different $ \theta $ ($ \delta = 0.01 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $)

    $ \theta $ Number of iterations CPU-time(s)
    0.1 546 40.8411
    0.3 249 17.2381
    0.5 150 9.5005
    0.8 175 10.7485
    0.99 222 15.0853
     | Show Table
    DownLoad: CSV

    Table 7.  Results for Algorithm 1 with different $ \delta $ ($ \theta = 0.1 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $)

    $ \delta $ Number of iterations CPU-time(s)
    0.01 546 24.8822
    0.05 546 20.3893
    0.1 546 21.7309
    0.25 546 20.0773
    0.5 546 19.2037
     | Show Table
    DownLoad: CSV

    Table 8.  Results for Algorithm 2, PA-BM and PA-YH with different initial point $ x^0 $ ($ \theta = 0.95 $, $ \delta = 0.01 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $)

    $ x^0 $ Number of iterations CPU-time(s)
    Algorithm 2 PA-BM PA-YH Algorithm 2 PA-BM PA-YH
    $ (0, 0)^T $ 6 8 41 0.7176 0.4056 2.9796
    $ (0, 1)^T $ 5 7 5 0.2808 0.2184 0.1560
    $ (1, 0)^T $ 5 8 74 0.1560 0.1872 1.4664
    $ (1, 1)^T $ 1 1 1 0.0156 0.0156 0.0156
    $ (0.3, 0.5)^T $ 5 6 36 0.0468 0.1248 0.6708
    $ (0.7, 0.1)^T $ 5 8 74 0.1404 0.1872 1.6536
     | Show Table
    DownLoad: CSV

    Table 9.  Results for Algorithm 2, PA-BM and PA-YH with different $ \beta_k $ ($ x^0 = (0, 0)^T $, $ \theta = 0.5 $ and $ \delta = 0.01 $)

    $ \beta_k $ Number of iterations CPU-time(s)
    Algorithm 2 PA-BM PA-YH Algorithm 2 PA-BM PA-YH
    0.05 17 106 64 1.3728 5.6316 3.1200
    0.10 17 58 64 0.3588 1.3728 1.2948
    0.15 17 42 64 0.3276 1.0296 1.8252
    0.20 17 34 64 0.3276 0.8736 1.4820
    0.25 17 30 64 0.4836 0.5772 1.5756
    0.30 17 27 64 0.4368 0.6084 1.6536
    0.35 17 24 64 0.2964 0.5148 1.9500
    0.40 17 23 64 0.3900 0.5928 1.3572
    0.45 17 22 64 0.3900 0.6084 1.8408
    0.50 17 21 64 0.2652 0.5772 1.7316
     | Show Table
    DownLoad: CSV

    Table 10.  Results for Algorithm 2, PA-BM and PA-YH with different $ \theta $ ($ x^0 = (0, 0)^T $, $ \delta = 0.01 $ and $ \beta_k = 0.5, \forall k \in \mathbb{N} $)

    $ \theta $ Number of iterations CPU-time(s)
    Algorithm 2 PA-BM PA-YH Algorithm 2 PA-BM PA-YH
    0.05 199 237 383 11.3725 12.6985 20.5609
    0.10 98 117 214 4.6800 6.2400 5.7252
    0.20 47 57 123 1.0452 1.4352 2.9172
    0.25 37 45 104 1.1388 1.2012 2.4024
    0.50 17 21 64 1.3104 1.2324 2.7612
    0.60 13 17 56 0.8580 0.4524 1.5912
    0.70 11 14 50 0.2340 0.2496 1.3728
    0.85 8 10 45 0.1872 0.2808 1.4820
    0.95 6 8 41 0.1716 0.1560 0.9204
    0.99 5 7 57 0.0624 0.1560 1.6536
     | Show Table
    DownLoad: CSV
  • [1] P. N. Anh, A hybrid extragradient method extended to fixed point problems and equilibrium problems, Optimization, 62 (2013), 271-283.  doi: 10.1080/02331934.2011.607497.
    [2] P. N. Anh, A hybrid extragradient method for pseudomonotone equilibrium problems and fixed point problems, Bull. Malays. Math. Sci. Soc., 36 (2013), 107-116. 
    [3] P. N. Anh and L. T. H. An, The subgradient extragradient method extended to equilibrium problems, Optimization, 64 (2015), 225-248.  doi: 10.1080/02331934.2012.745528.
    [4] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2011. doi: 10.1007/978-1-4419-9467-7.
    [5] J. Y. Bello-CruzR. Díaz Millán and H. M. Phan, Conditional extragradient algorithms for solving variational inequalities, Pacific J. Optim., 15 (2019), 331-357. 
    [6] G. BigiM. CastellaniM. Pappalardo and M. Passacantando, Existence and solution methods for equilibria, Eur. J. Oper. Res., 227 (2013), 1-11.  doi: 10.1016/j.ejor.2012.11.037.
    [7] G. Bigi and M. Passacantando, Auxiliary problem principles for equilibria, Optimization, 66 (2017), 1955-1972.  doi: 10.1080/02331934.2016.1227808.
    [8] E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems, Math. Student., 63 (1994), 123-145. 
    [9] R. S. Burachik and R. Díaz Millán, A projection algorithm for non-monotone variational inequalities, Set-Valued Var. Anal., 28 (2020), 149-166.  doi: 10.1007/s11228-019-00517-0.
    [10] Y. CensorA. Gibali and S. Reich, Strong convergence of subgradient extragradient methods for variational inequality problem in Hilbert space, Optim. Methods Softw., 26 (2011), 827-845.  doi: 10.1080/10556788.2010.551536.
    [11] L. M. DengR. Hu and Y. P. Fang, Projection extragradient algorithms for solving nonmonotone and non-Lipschitzian equilibrium problems in Hilbert spaces, Numer. Algor., 86 (2021), 191-221.  doi: 10.1007/s11075-020-00885-x.
    [12] B. V. Dinh and L. D. Muu, A projection algorithm for solving pseudomonotone equilibrium problems and it's application to a class of bilevel equilibria, Optimization, 64 (2015), 559-575.  doi: 10.1080/02331934.2013.773329.
    [13] B. V. Dinh and D. S. Kim, Projection algorithms for solving nonmonotone equilibrium problems in Hilbert space, J. Comput. Appl. Math., 302 (2016), 106-117.  doi: 10.1016/j.cam.2016.01.054.
    [14] K. Fan, A minimax inequality and applications, Inequalities, Academic Press, New York, 3 (1972), 103-113. 
    [15] S. D. Flam and A. S. Antipin, Equilibrium programming using proximal-like algorithms, Math. Program., 78 (1997), 29-41.  doi: 10.1016/S0025-5610(96)00071-8.
    [16] N. Hadjisavvas and S. Schaible, Quasimonotone variational inequalities in Banach spaces, J. Optim. Theory Appl., 90 (1996), 95-111.  doi: 10.1007/BF02192248.
    [17] D. V. Hieu, P. K. Quy, L. T. Hong and L. V. Vy, Accelerated hybrid methods for solving pseudomonotone equilibrium problems, Adv. Comput. Math., 46 (2020), Paper No. 58, 24 pp. doi: 10.1007/s10444-020-09778-y.
    [18] A. N. Iusem and W. Sosa, New existence results for equilibrium problems, Nonlinear Anal. TMA., 52 (2003), 621-635.  doi: 10.1016/S0362-546X(02)00154-2.
    [19] A. N. Iusem and W. Sosa, On the proximal point method for equilibrium problem in Hilbert spaces, Optimization, 59 (2010), 1259-1274.  doi: 10.1080/02331931003603133.
    [20] I. V. Konnov, Application of the proximal point method to nonmonotone equilibrium problems, J. Optim. Theory Appl., 119 (2003), 317-333.  doi: 10.1023/B:JOTA.0000005448.12716.24.
    [21] G. M. Korpelevich, The extragradient method for finding saddle points and other problems, Ekon. Mat. Metody., 12 (1976), 747-756. 
    [22] J.-L. Lions and G. Stampacchia, Variational inequalities, Comm. Pure Appl. Math., 20 (1967), 493-519.  doi: 10.1002/cpa.3160200302.
    [23] C. Martinez-Yanes and H.-K. Xu, Strong convergence of the CQ method for fixed point iteration processes, Nonlinear Anal. TMA., 64 (2006), 2400-2411.  doi: 10.1016/j.na.2005.08.018.
    [24] G. Mastroeni, Gap functions for equilibrium problems, J. Glob. Optim., 27 (2003), 411-426.  doi: 10.1023/A:1026050425030.
    [25] G. Mastroeni, On auxiliary principle for equilibrium problems, Equilibrium Problems and Variational Models, Nonconvex Optim. Appl., Kluwer Acad. Publ., Norwell, MA, 68 (2003), 289-298.  doi: 10.1007/978-1-4613-0239-1_15.
    [26] A. Moudafi, On the convergence of splitting proximal methods for equilibrium problems in Hilbert spaces, J. Math. Anal. Appl., 359 (2009), 508-513.  doi: 10.1016/j.jmaa.2009.06.005.
    [27] L.D. Muu and W. Oettli, Convergence of an adaptive penalty scheme for finding constrained equilibria, Nonlinear Anal. TMA., 18 (1992), 1159-1166.  doi: 10.1016/0362-546X(92)90159-C.
    [28] L. D. Muu and T. D. Quoc, Regularization algorithms for solving monotone Ky Fan inequalities with application to a Nash-Cournot equilibrium model, J. Optim. Theory Appl., 142 (2009), 185-204.  doi: 10.1007/s10957-009-9529-0.
    [29] K. NakajoK. Shimoji and W. Takahashi, Strong convergence to common fixed points of families of nonexpansive mappings in Banach spaces, J. Nonlinear Convex Anal., 8 (2007), 11-34. 
    [30] T. D. QuocP. N. Anh and L. D. Muu, Dual extragradient algorithms extended to equilibrium problems, J. Glob. Optim., 52 (2012), 139-159.  doi: 10.1007/s10898-011-9693-2.
    [31] T. D. Quoc and L. D. Muu, Iterative methods for solving monotone equilibrium problems via dual gap functions, Comput. Optim. Appl., 51 (2012), 709-728.  doi: 10.1007/s10589-010-9360-4.
    [32] R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28 Princeton University Press, Princeton, N.J., 1970
    [33] P. Santos and S. Scheimberg, An inexact subgradient algorithm for equilibrium problems, Comput. Appl. Math., 30 (2011), 91-107. 
    [34] S. Scheimberg and P. S. M. Santos, A relaxed projectionmethod for finite dimensional equilibrium problems, Optimization, 60 (2011), 1193-1208.  doi: 10.1080/02331934.2010.527974.
    [35] J. J. StrodiotP. T. Vuong and T. T. V. Nguyen, A class of shrinking projection extragradient methods for solving non-monotone equilibrium problems in Hilbert spaces, J. Glob. Optim., 64 (2016), 159-178.  doi: 10.1007/s10898-015-0365-5.
    [36] D. Q. TranM. L. Dung and V. H. Nguyen, Extragradient algorithms extended to equilibrium problems, Optimization, 57 (2008), 749-776.  doi: 10.1080/02331930601122876.
    [37] F. Q. Xia and N. J. Huang, A projection-proximal point algorithm for solving generalized variational inequalities, J. Optim Theory Appl., 150 (2011), 98-117.  doi: 10.1007/s10957-011-9825-3.
    [38] M. Ye and Y. He, A double projection method for solving variational inequalities without monotonicity, Comput. Optim. Appl., 60 (2015), 141-150.  doi: 10.1007/s10589-014-9659-7.
    [39] L. C. Zeng and J. Y. Yao, Modified combined relaxation method for general monotone equilibrium problems in Hilbert spaces, J. Optim. Theory Appl., 131 (2006), 469-483.  doi: 10.1007/s10957-006-9162-0.
  • 加载中

Figures(6)

Tables(10)

SHARE

Article Metrics

HTML views(1584) PDF downloads(143) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return