Prediction-correction method with BB step sizes

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

References

[1] Barzilai J, Borwein J W. Two-point step size gradient methods. IMA J Numer Anal, 1988, 8: 141–148

[2] Bertsekas D P, Gafni E M. Projection methods for variational inequalities with applications to the traffic assignment problem. Math Program Study, 1982, 17: 139–159

[3] Birgin E G, Chambouleyron I, Martinez J M. Estimation of the optical constants and the thickness of thin films using unconstrained optimization. J Comput Phys, 1999, 151: 862–880

[4] Dafermos S. Traffic equilibrium and variational inequalities. Transp Sci, 1980, 14: 42–54

[5] Dai Y H, Fletcher R. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer Math, 2005, 100: 21–47

[6] Dai Y H, Fletcher R. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math Program, 2006, 106: 403–421

[7] Dai Y H, Hager W W, Schittkowski K, Zhang H C. The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J Numer Anal, 2006, 26: 604–627

[8] Dai Y H, Yuan Y X. Alternate minimization gradient method. IMA J Numer Anal, 2003, 23: 377–393

[9] Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complemen-tarity Problems, Vol 1. Berlin: Springer-Verlag, 2003

[10] Goldstein A A. Convex programming in Hilbert space. Bull Amer Math Soc, 1964, 70: 709–710

[11] Hager W W, Mair B A, Zhang H C. An affine-scaling interior-point CBB method for box-constrained optimization. Math Program, 2009, 119: 1–32

[12] Hager W W, Zhang H C. A new active set algorithm for box constrained optimization. SIAM J Optim, 2006, 17: 526–557

[13] Harker P T, Pang J S. A damped-Newton method for the linear complementarity problem. Lect Appl Math, 1990, 26: 265–284

[14] Harker P T, Pang J S. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math Program, 1990, 48: 161–220

[15] He B S, Liao L Z. Improvements of some projection methods for monotone nonlinear variational inequalities. J Optim Theory Appl, 2002, 112: 111–128

[16] He H J, Han D R, Li Z B. Some projection methods with the BB step sizes for variational inequalities. J Comput Appl Math, 2012, 236: 2590–2604

[17] Korpelevich G M. An extragradient method for finding saddle points and other problems. Èkon Mat Metody, 1976, 12: 747–756

[18] Levitin E S, Polyak B T. Constrained minimization methods. USSR Comput Math Math Phys, 1966, 6: 1–50

[19] Liu W, Dai Y H. Minimization algorithms based on supervisor and searcher cooperation. J Optim Theory Appl, 2001, 111: 359–379

[20] Nagurney A, Ramanujam P. Transportation network policy modeling with goal targets and generalized penalty functions. Transp Sci, 1996, 30: 3–13

[21] Pang J S, Fukushima M. Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput Manag Sci, 2005, 2: 21–56

[22] Robbins H, Siegmund D. 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] Zhang H C, Hager W W. 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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature