An extension of hybrid method without extrapolation step to equilibrium problems

Van Hieu Dang

doi:10.3934/jimo.2017015

Article Contents

2017, Volume 13, Issue 4: 1723-1741. Doi: 10.3934/jimo.2017015

This issue Previous Article Artificial intelligence combined with nonlinear optimization techniques and their application for yield curve optimization Next Article Structure analysis on the k-error linear complexity for 2ⁿ-periodic binary sequences

An extension of hybrid method without extrapolation step to equilibrium problems

Van Hieu Dang^,

Department of Mathematics, Vietnam National University, 334 - Nguyen Trai Street, Thanh Xuan, Ha Noi 100000, Viet Nam

* Corresponding author: dv.hieu83@gmail.com
* Corresponding author: dv.hieu83@gmail.com

Received: September 30, 2015

Published: November 2017

Abstract Full Text(HTML) Figure(0) / Table(7) Related Papers Cited by

Abstract

In this paper, we introduce a new hybrid algorithm for solving equilibrium problems. The algorithm combines the generalized gradient-like projection method and the hybrid (outer approximation) method. In this algorithm, only one optimization program is solved at each iteration without any extra-step dealing with the feasible set like as in the hybrid extragradient method and the hybrid Armijo linesearch method. A specially constructed half-space in the hybrid method is the reason for the absence of an optimization program in the proposed algorithm. The strongly convergent theorem is established and several numerical experiments are implemented to illustrate the convergence of the algorithm and compare it with others.

Keywords:

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

Citation:

Full Text(HTML)

Table 1. Results for given starting points in Example 1

$x_0$	Iter.				Time
$x_0$	Alg. 1	Alg. 3	Alg. 4	Alg. 5	Alg. 1	Alg. 3	Alg. 4	Alg. 5
(2, 5)	241	111	221	122	1.928	2.331	1.768	4.636
(5, 5)	192	108	215	122	2.880	2.700	2.580	3.294
(4, 4.5)	194	108	215	122	2.910	2.700	2.795	3.294
(-0.75, 0)	196	108	215	122	3.724	3.132	2.795	3.172

| Show Table

DownLoad: CSV

Table 2. Results for given starting points in Example 2

$x_0$	Iter.				Time
$x_0$	Alg. 1	Alg. 3	Alg. 4	Alg. 5	Alg. 1	Alg. 3	Alg. 4	Alg. 5
$x_0^1$	1918	1022	225	812	15.344	10.220	7.875	334.544
$x_0^2$	1470	524	173	924	10.290	8.384	5.709	370.524
$x_0^3$	1421	980	296	1043	12.789	32.34	10.360	617.456

| Show Table

DownLoad: CSV

Table 3. Results for different given parameter $\lambda$ in Example 2

$\tau$	Iter.			Time
$\tau$	Alg. 1	Alg. 3	Alg. 4	Alg. 1	Alg. 3	Alg. 4
$10^{-2}$	1423	572	351	25.614	20.020	15.093
$10^{-4}$	1341	655	373	22.797	20.960	16.039
$10^{-6}$	1093	635	367	18.581	17.145	15.414

| Show Table

DownLoad: CSV

Table 4. Numerical results for Example 3

$m$	Iter.				Time
$m$	Alg. 1	Alg. 3	Alg. 4	Alg. 5	Alg. 1	Alg. 3	Alg. 4	Alg. 5
$10$	521	212	183	312	17.193	13.356	17.934	37.440
$15$	674	406	366	467	31.004	32.074	25.254	135.897
$20$	912	388	348	Slow	127.680	111.356	98.136	-
$50$	Slow	-	-	-	-	-	-	-

| Show Table

DownLoad: CSV

Table 5. The parameters of the functions $c_j$ in Example 4

$j$	$\hat{\alpha}_j$	$\hat{\beta}_j$	$\hat{\gamma}_j$	$\tilde{\alpha}_j$	$\tilde{\beta}_j$	$\tilde{\gamma}_j$
1	0.0400	2.00	0.00	2.0000	1.0000	25.0000
2	0.0350	1.75	0.00	1.7500	1.0000	28.5714
3	0.1250	1.00	0.00	1.0000	1.0000	8.0000
4	0.0116	3.25	0.00	3.2500	1.0000	86.2069
5	0.0500	3.00	0.00	3.0000	1.0000	20.0000
6	0.0500	3.00	0.00	3.0000	1.0000	20.0000

| Show Table

DownLoad: CSV

Table 6. Results for given starting points in Example 4

$x_0$	Iter.				Time
$x_0$	Alg. 1	Alg. 3	Alg. 4	Alg. 5	Alg. 1	Alg. 3	Alg. 4	Alg. 5
$x_0^1$	1965	934	557	805	47.160	36.426	23.394	79.695
$x_0^2$	2001	1023	573	928	58.029	31.713	26.358	144.768
$x_0^3$	1877	1279	567	1011	46.925	48.602	24.948	105.144
$x_0^4$	1574	1089	598	873	39.350	34.848	24.518	139.680

| Show Table

DownLoad: CSV

Table 7. Results for given starting points in Example 5

$x_0$	Iter.		Time
$x_0$	Alg. 1	Alg. 3	Alg. 1	Alg. 3
$x_0^1$	2365	1565	2059.915	3428.915
$x_0^2$	2417	1437	2259.895	3463.170
$x_0^3$	2877	1729	2557.653	3577.301

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York, 2011. doi: 10.1007/978-1-4419-9467-7.
[2]	E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems, Math. Program., 63 (1994), 123-145.
[3]	L. C. Ceng, N. Hadjisavvas and N. C. Wong, Strong convergence theorem by a hybrid extragradient-like approximation method for variational inequalities and fixed point problems, J. Glob. Optim., 46 (2010), 635-646. doi: 10.1007/s10898-009-9454-7.
[4]	L. C. Ceng and J. C. Yao, An extragradient-like approximation method for variational inequality problems and fixed point problems, Appl. Math. Comput., 190 (2007), 205-215. doi: 10.1016/j.amc.2007.01.021.
[5]	Y. Censor, A. Gibali and S. Reich, The subgradient extragradient method for solving variational inequalities in Hilbert space, J. Optim. Theory Appl., 148 (2011), 318-335. doi: 10.1007/s10957-010-9757-3.
[6]	Y. Censor, A. Gibali and S. Reich, Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space, Optim. Methods Softw., 26 (2011), 827-845. doi: 10.1080/10556788.2010.551536.
[7]	P. L. Combettes and S. A. Hirstoaga, Equilibrium programming in Hilbert spaces, J. Nonlinear Convex Anal, 6 (2005), 117-136.
[8]	P. Daniele, F. Giannessi and A. Maugeri, Equilibrium Problems and Variational Models, Kluwer, 2003. doi: 10.1007/978-1-4613-0239-1.
[9]	K. Fan, A minimax inequality and applications, In: Shisha, O. (ed. ) Inequality, Ⅲ [Academic Press, New York, 1972], 103-113.
[10]	K. Goebel and S. Reich, Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings, Marcel Dekker, New York and Basel, 1984. doi: MR744194.
[11]	K. Goebel and W. A. Kirk, Topics in Metric Fixed Point Theory, Cambridge Studies in Advanced Math., vol. 28 and Cambridge University Press, Cambridge, 1990. doi: 10.1017/CBO9780511526152.
[12]	D. V. Hieu, P. K. Anh and L. D. Muu, Modified hybrid projection methods for finding common solutions to variational inequality problems, Comput. Optim. Appl., (2016), 1-22. doi: 10.1007/s10589-016-9857-6.
[13]	D. V. Hieu, A parallel hybrid method for equilibrium problems, variational inequalities and nonexpansive mappings in Hilbert space, J. Korean Math. Soc., 52 (2015), 373-388. doi: 10.4134/JKMS.2015.52.2.373.
[14]	D. V. Hieu, Parallel extragradient-proximal methods for split equilibrium problems, Math. Model. Anal., 21 (2016), 478-501. doi: 10.3846/13926292.2016.1183527.
[15]	D. V. Hieu, L. D. Muu and P. K. Anh, Parallel hybrid extragradient methods for pseudomonotone equilibrium problems and nonexpansive mappings, Numer. Algor., 73 (2016), 197-217. doi: 10.1007/s11075-015-0092-5.
[16]	D. V. Hieu, Parallel hybrid methods for generalized equilibrium problems and asymptotically strictly pseudocontractive mappings, J. Appl. Math. Comput., 73 (2016), 1-24. doi: 10.1007/s12190-015-0980-9.
[17]	H. Iiduka, Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping, Math. Program. Ser. A, 149 (2015), 131-165. doi: 10.1007/s10107-013-0741-1.
[18]	I. V. Konnov, Combined Relaxation Methods for Variational Inequalities, Springer, Berlin, 2001. doi: 10.1007/978-3-642-56886-2.
[19]	G. M. Korpelevich, The extragradient method for finding saddle points and other problems, Ekonomika i Matematicheskie Metody, 12 (1976), 747-756.
[20]	S. I. Lyashko, V. V. Semenov and T. A. Voitova, Low-cost modification of Korpelevich's methods for monotone equilibrium problems, Cybernetics and Systems Analysis, 47 (2011), 631-639. doi: 10.1007/s10559-011-9343-1.
[21]	Y. V. Malitsky and V. V. Semenov, A hybrid method without extrapolation step for solving variational inequality problems, J. Glob. Optim., 61 (2015), 193-202. doi: 10.1007/s10898-014-0150-x.
[22]	B. Martinet, R$\rm\acute{e}$gularisation d$\rm\acute{i}$n$\rm\acute{e}$quations variationelles par approximations successives, Rev. Fr. Autom. Inform. Rech. Op$\rm\acute{e}$r., Anal. Num$\acute{e}$r., 4 (1970), 154-158.
[23]	G. Mastroeni, On auxiliary principle for equilibrium problems, Chapter: Equilibrium Problems and Variational Models, 68 (2003), 289-298. doi: 10.1007/978-1-4613-0239-1_15.
[24]	B. Mordukhovich, B. Panicucci, M. Pappalardo and M. Passacantando, Hybrid proximal methods for equilibrium problems, Optim. Lett., 6 (2012), 1535-1550. doi: 10.1007/s11590-011-0348-5.
[25]	L. D. Muu and W. Oettli, Convergence of an adative penalty scheme for finding constrained equilibria, Nonlinear Anal. TMA, 18 (1992), 1159-1166. doi: 10.1016/0362-546X(92)90159-C.
[26]	N. Nadezhkina and W. Takahashi, Strong convergence theorem by a hybrid method for nonexpansive mappings and Lipschitz-continuous monotone mappings, SIAM J. Optim, 16 (2006), 1230-1241. doi: 10.1137/050624315.
[27]	T. T. V. Nguyen, J. J. Strodiot and V. H. Nguyen, Hybrid methods for solving simultaneously an equilibrium problem and countably many fixed point problems in a Hilbert space, J. Optim. Theory Appl., 160 (2014), 809-831. doi: 10.1007/s10957-013-0400-y.
[28]	T. P. D. Nguyen, J. J. Strodiot, V. H. Nguyen and T. T. V. Nguyen, A family of extragradient methods for solving equilibrium problems, J. Ind. Manag. Optim., 11 (2015), 619-630. doi: 10.3934/jimo.2015.11.619.
[29]	T. D. Quoc, L. D. Muu and N. V. Hien, Extragradient algorithms extended to equilibrium problems, Optimization, 57 (2008), 749-776. doi: 10.1080/02331930601122876.
[30]	T. D. Quoc, P. 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]	R. T. Rockafellar, Convex Analysis, Princeton, NJ: Princeton University Press, 1970. doi: MR0274683.
[32]	J. J. Strodiot, T. T. V. Nguyen and V. H. Nguyen, A new class of hybrid extragradient algorithms for solving quasi-equilibrium problems, J. Glob. Optim., 56 (2013), 373-397. doi: 10.1007/s10898-011-9814-y.
[33]	P. T. Vuong, J. J. Strodiot and V. H. Nguyen, Extragradient methods and linesearch algorithms for solving Ky Fan inequalities and fixed point problems, J. Optim. Theory Appl., 155 (2012), 605-627. doi: 10.1007/s10957-012-0085-7.
[34]	I. Yamada, The hybrid steepest descent method for the variational inequality problem over the intersection of fixed point sets of nonexpansive mappings, In: Butnariu, D., Censor, Y., Reich, S. (eds. ) Inherently Parallel Algorithms for Feasibility and Optimization and Their Applications, Elsevier, Amsterdam, 8 (2001), 473-504. doi: 10.1016/S1570-579X(01)80028-8.