Prediction-correction method with BB step sizes

doi:10.1007/s11464-018-0739-3

Front. Math. China

2018, Vol. 13

Issue (6) : 1325-1340 https://doi.org/10.1007/s11464-018-0739-3

RESEARCH ARTICLE

Prediction-correction method with BB step sizes

Xiaomei DONG¹, Xingju CAI¹, Deren HAN²(

)

¹. Jiangsu Key Laboratory for NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China
². School of Mathematics and Systems Science, Beihang University, Beijing 100191, China

Download: PDF(530 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

In the prediction-correction method for variational inequality (VI) problems, the step size selection plays an important role for its performance. In this paper, we employ the Barzilai-Borwein (BB) strategy in the prediction step, which is effcient for many optimization problems from a computational point of view. To guarantee the convergence, we adopt the line search technique, and relax the conditions to accept the BB step sizes as large as possible. In the correction step, we utilize a longer step length to calculate the next iteration point. Finally, we present some preliminary numerical results to show the effciency of the algorithms.

Keywords BB step sizes projection method prediction-correction method line search

Corresponding Author(s): Deren HAN

Issue Date: 02 January 2019

Cite this article:

Xiaomei DONG,Xingju CAI,Deren HAN. Prediction-correction method with BB step sizes[J]. Front. Math. China, 2018, 13(6): 1325-1340.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-018-0739-3
https://academic.hep.com.cn/fmc/EN/Y2018/V13/I6/1325

1	JBarzilai, J WBorwein. Two-point step size gradient methods. IMA J Numer Anal, 1988, 8: 141–148 https://doi.org/10.1093/imanum/8.1.141
2	D PBertsekas, E MGafni. Projection methods for variational inequalities with applications to the traffic assignment problem. Math Program Study, 1982, 17: 139–159 https://doi.org/10.1007/BFb0120965
3	E GBirgin, IChambouleyron, J MMartinez. Estimation of the optical constants and the thickness of thin films using unconstrained optimization. J Comput Phys, 1999, 151: 862–880 https://doi.org/10.1006/jcph.1999.6224
4	SDafermos. Traffic equilibrium and variational inequalities. Transp Sci, 1980, 14: 42–54 https://doi.org/10.1287/trsc.14.1.42
5	Y HDai, RFletcher. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer Math, 2005, 100: 21–47 https://doi.org/10.1007/s00211-004-0569-y
6	Y HDai, RFletcher. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math Program, 2006, 106: 403–421 https://doi.org/10.1007/s10107-005-0595-2
7	Y HDai, W WHager, KSchittkowski, H CZhang. The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J Numer Anal, 2006, 26: 604–627 https://doi.org/10.1093/imanum/drl006
8	Y HDai, Y XYuan. Alternate minimization gradient method. IMA J Numer Anal, 2003, 23: 377–393 https://doi.org/10.1093/imanum/23.3.377
9	FFacchinei, J SPang. Finite-Dimensional Variational Inequalities and Complemen-tarity Problems, Vol 1. Berlin: Springer-Verlag, 2003
10	A AGoldstein. Convex programming in Hilbert space. Bull Amer Math Soc, 1964, 70: 709–710 https://doi.org/10.1090/S0002-9904-1964-11178-2
11	W WHager, B AMair, H CZhang. An affine-scaling interior-point CBB method for box-constrained optimization. Math Program, 2009, 119: 1–32 https://doi.org/10.1007/s10107-007-0199-0
12	W WHager, H CZhang. A new active set algorithm for box constrained optimization. SIAM J Optim, 2006, 17: 526–557 https://doi.org/10.1137/050635225
13	P THarker, J SPang. A damped-Newton method for the linear complementarity problem. Lect Appl Math, 1990, 26: 265–284
14	P THarker, J SPang. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math Program, 1990, 48: 161–220 https://doi.org/10.1007/BF01582255
15	B SHe, L ZLiao. Improvements of some projection methods for monotone nonlinear variational inequalities. J Optim Theory Appl, 2002, 112: 111–128 https://doi.org/10.1023/A:1013096613105
16	H JHe, D RHan, Z BLi. Some projection methods with the BB step sizes for variational inequalities. J Comput Appl Math, 2012, 236: 2590–2604 https://doi.org/10.1016/j.cam.2011.12.017
17	G MKorpelevich. An extragradient method for finding saddle points and other problems. Èkon Mat Metody, 1976, 12: 747–756
18	E SLevitin, B TPolyak. Constrained minimization methods. USSR Comput Math Math Phys, 1966, 6: 1–50 https://doi.org/10.1016/0041-5553(66)90114-5
19	WLiu, Y HDai. Minimization algorithms based on supervisor and searcher cooperation. J Optim Theory Appl, 2001, 111: 359–379 https://doi.org/10.1023/A:1011986402461
20	ANagurney, PRamanujam. Transportation network policy modeling with goal targets and generalized penalty functions. Transp Sci, 1996, 30: 3–13 https://doi.org/10.1287/trsc.30.1.3
21	J SPang, MFukushima. Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput Manag Sci, 2005, 2: 21–56 https://doi.org/10.1007/s10287-004-0010-0
22	HRobbins, DSiegmund. A convergence theorem for non negative almost super-martingales and some applications. In: Rustagi J, ed. Optimizing Methods in Statistics. New York: Academic Press, 1971, 235–257
23	H CZhang, W WHager. PACBB: a projected adaptive cyclic Barzilai-Borwein method for box constrained optimization. In: Hager WW, Huang S J, Pardalos P M, Prokopyev O A, eds. Multiscale Optimization Method and Applications: Nonconvex Optimization and Its Applications. New York: Springer, 2006, 387–392 https://doi.org/10.1007/0-387-29550-X_21

[1]	Hongyu ZHANG, Yiju WANG, . A new CQ method for solving split feasibility problem[J]. Front. Math. China, 2010, 5(1): 37-46.
[2]	ZHOU Qunyan, SUN Wenyu. Adaptive nonmonotone line search method for unconstrained optimization[J]. Front. Math. China, 2008, 3(1): 133-148.

Viewed

Full text

Abstract

Cited

Shared

Discussed