Previous Articles    

A STOCHASTIC MOVING BALLS APPROXIMATION METHOD OVER A SMOOTH INEQUALITY CONSTRAINT

Leiwu Zhang   

  1. Department of Mathematics, Nanjing University, Nanjing 210023, China
  • Received:2016-05-13 Revised:2019-08-07 Online:2020-05-15 Published:2020-05-15

Leiwu Zhang. A STOCHASTIC MOVING BALLS APPROXIMATION METHOD OVER A SMOOTH INEQUALITY CONSTRAINT[J]. Journal of Computational Mathematics, 2020, 38(3): 528-546.

We consider the problem of minimizing the average of a large number of smooth component functions over one smooth inequality constraint. We propose and analyze a stochastic Moving Balls Approximation (SMBA) method. Like stochastic gradient (SG) methods, the SMBA method’s iteration cost is independent of the number of component functions and by exploiting the smoothness of the constraint function, our method can be easily implemented. Theoretical and computational properties of SMBA are studied, and convergence results are established. Numerical experiments indicate that our algorithm dramatically outperforms the existing Moving Balls Approximation algorithm (MBA) for the structure of our problem.

CLC Number: 

[1] A. Auslender, R.Shefi and M. Teboulle, A Moving balls approximation method for a class of smooth constrained minimization problems. SIAM J. Optim., 20(2010), 3232-3259.

[2] A. Auslender, A very simple SQCQP method for a class of smooth convex constrained minimization problems with nice convergence results. Math. Program., 142(2013), 349-369.

[3] A. Beck and M. Teboulle, A fast iterative shrinkage-treshold algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(2009), 183-202.

[4] D. Bertsekas, Nonlinear Programming, 2nd ed., Athena Scientific, Belmont, MA, 1999.

[5] D. Blatt, A. O. Hero and H. Gauchman, A convergent incremental gradient method with a constant step size. SIAM Journal on Optimization, 18(2007), 29-51.

[6] D. Lan, Z. Lu and R. D. C. Monteiro, Primal-dual first-order methods with O(1/ε) iterationcomplexity for cone programming. Math. Program. Ser. A, 126(2011), 1-29.

[7] J. Jacod and P. Protter, Martingale convergence theorems. Springer berlin heidelberg, 2000.

[8] K. Lange, Numerical Analysis for Statisticians, 2nd edn. Statistics and Computing. Springer, New York, 2010.

[9] J. W. Liu, Z. K. Sun and X. L. Luo, Non-integer norm regularized logistic regression. The 26th Chinese Control and Decision Conference (2014 CCDC), Changsha, (2014), 1333-1338.

[10] J. Mairal, Optimization with first-order surrogate functions. International Conference on Machine Learning, 2013.

[11] R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive. variance reduction. Advances in Neural Information Processing Systems, 26(2013), 315-323.

[12] N. Le Roux, M. Schmidt and F. Bach, A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets. Advances in Neural Information Processing Systems, 2012.

[13] A. Nemirovski, A. Juditsky, G. Lan and A. Shapiro, Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(2009), 1574-1609.

[14] Y. Nesterov, Introductory Lectures on Convex Optimization. A Basic Course, Appl. Optim. 87, Kluwer Academic, Boston, MA, 2004.

[15] Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program. Ser. A, 103(2005), 127-152.

[16] M. Schmidt, N. Le Roux and F. Bach, Minimizing finite sums with the stochastic average gradient. Technical Report HAL 00860051, INRIA, Paris, France, 2013.

[17] R. Shefi and M. Teboulle, A dual method for minimizing a nonsmooth objective over one smooth inequality constraint. Math. Program. Ser. A, 126(2015), 1-28.

[18] P. Tseng, Approximation accuracy, gradientmethods, and error bound for structured convex optimization. Math. Program. Ser. B, 125(2010), 263-295.

[19] L. Xiao and T. Zhang, A proximal stochastic gradient method with progressive variance reduction. SIAM J. Optim., 4(2014), 2057-2075.

[20] H. Zou and T. Hastie, Regularization and variable selection via the elastic net. J. R. Stat. Soc. Ser. B(Stat. Method.) 67(2005), 301-320.
[1] Ning Du, Wanfang Shen. A FAST STOCHASTIC GALERKIN METHOD FOR A CONSTRAINED OPTIMAL CONTROL PROBLEM GOVERNED BY A RANDOM FRACTIONAL DIFFUSION EQUATION [J]. Journal of Computational Mathematics, 2018, 36(2): 259-275.
[2] Kun Xu, Zhaoli Guo. MULTIPLE TEMPERATURE GAS DYNAMIC EQUATIONS FOR NON-EQUILIBRIUM FLOWS [J]. Journal of Computational Mathematics, 2011, 29(6): 639-660.
Viewed
Full text


Abstract