×

A smoothing direct search method for Monte Carlo-based bound constrained composite nonsmooth optimization. (English) Zbl 1461.65138

Summary: We propose and analyze a smoothing direct search algorithm for finding a minimizer of a nonsmooth nonconvex function over a box constraint set, where the objective function values cannot be computed directly but are approximated by Monte Carlo simulation. In the algorithm, we adjust the stencil size, the sample size, and the smoothing parameter simultaneously so that the stencil size goes to zero faster than the smoothing parameter and the square root of the sample size goes to infinity faster than the reciprocal of the stencil size. We prove that with probability one any accumulation point of the sequence generated by the algorithm is a Clarke stationary point. We report on numerical results from statistics and financial applications.

MSC:

65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
90C30 Nonlinear programming
65C05 Monte Carlo methods

Software:

IMFIL; OR-Library; KELLEY; BFO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. G. Altonji, H. Ichimura, and T. Otsu, Estimating derivatives in nonseparable models with limited dependent variables, Econometrica, 80 (2012), pp. 1701–1719. · Zbl 1274.62647
[2] C. Audet and J. E. Dennis, Analysis of generalized pattern searches, SIAM J. Optim., 13 (2003), pp. 889–903. · Zbl 1053.90118
[3] C. Audet and J. E. Dennis, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17 (2006), pp. 188–217. · Zbl 1112.90078
[4] C. Audet and J. E. Dennis, A progressive barrier for derivative-free nonlinear programming, SIAM J. Optim., 20 (2009), pp. 445–472. · Zbl 1187.90266
[5] J. E. Beasley, OR-Library: Distributing test problems by electronic mail, J. Oper. Res. Soc., 41 (1990), pp. 1069–1072.
[6] R. W. Blundell and J. L. Powell, Censored regression quantiles with endogenous regressors, J. Econometrics, 141 (2007), pp. 65–83. · Zbl 1418.62420
[7] V. V. Buldygin and I. U. V. Kozachenko, Metric Characterization of Random Variables and Random Processes, American Mathematical Society, Providence, RI, 2000. · Zbl 0998.60503
[8] J. V. Burke, X. Chen, and H. Sun, Compute Clarke Subgradients of Expectation of Measurable Composite Affine Max Function via Smoothing, 2018, manuscript.
[9] D. Chafaï, O. Guédon, G. Lecué, and A. Pajor, Interactions Between Compressed Sensing Random Matrices and High Dimensional Geometry, Société Mathématique de France, 2012, .
[10] X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134 (2012), pp. 71–99. · Zbl 1266.90145
[11] X. Chen and C. T. Kelley, Optimization with hidden constraints and embedded Monte Carlo computations, Optim. Eng., 17 (2016), pp. 157–175. · Zbl 1364.65119
[12] X. Chen, T. K. Pong, and R. J.-B. Wets, Two-stage stochastic variational inequalities: An ERM-solution procedure, Math. Program., 165 (2017), pp. 71–112. · Zbl 1386.90157
[13] V. K. Chopra, Mean-variance revisited: Near-optimal portfolios and sensitivity to input variations, J. Investing, 2 (1993), pp. 51–59.
[14] F. H. Clarke, Optimization and Nonsmooth Analysis, Classics Appl. Math. 5, SIAM, Philadelphia, 1990. · Zbl 0696.49002
[15] A. R. Conn, K. Scheinberg, and L. N. Vicente, Introduction to Derivative-Free Optimization, MPS-SIAM Ser. Optim., SIAM, Philadelphia, 2009. · Zbl 1163.49001
[16] J. E. Dennis and V. Torczon, Direct search methods on parallel machines, SIAM J. Optim., 1 (1991), pp. 448–474. · Zbl 0754.90051
[17] J. Duchi, Lecture Notes for Statistics 311/Electrical Engineering 377: Information Theory and Statistics, (2016).
[18] A. Dvoretzky, J. Kiefer, and J. Wolfowitz, Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator, Ann. Math. Stat., 27 (1956), pp. 642–669. · Zbl 0073.14603
[19] B. Efron and R. J. Tibshirani, An Introduction to the Bootstrap, CRC Press, New York, 1994. · Zbl 0835.62038
[20] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. · Zbl 1062.90001
[21] S. Foss, D. Korshunov, and S. Zachary, An Introduction to Heavy-Tailed and Subexponential Distributions, Springer, New York, 2011. · Zbl 1250.62025
[22] G. M. Frankfurter, H. E. Phillips, and J. P. Seagle, Portfolio selection: The effects of uncertain means, variances, and covariances, J. Financ. Quant. Anal., 6 (1971), pp. 1251–1262.
[23] R. Garmanjani and L. N. Vicente, Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization, IMA J. Numer. Anal., 33 (2012), pp. 1008–1028. · Zbl 1272.65050
[24] J. C. Hull, Options, Futures, and Other Derivatives, Pearson, New York, 1988.
[25] P. Jorion, Bayes-Stein estimation for portfolio analysis, J. Financ. Quant. Anal., 21 (1986), pp. 279–292.
[26] R. L. Karandikar and M. Vidyasagar, Rates of uniform convergence of empirical means with mixing processes, Statist. Probab. Lett., 58 (2002), pp. 297–307. · Zbl 1016.60036
[27] C. T. Kelley, Iterative Methods for Optimization, Front. Appl. Math. 18, SIAM, Philadelphia, 1999. · Zbl 0934.90082
[28] C. T. Kelley, Implicit Filtering, Software Environ. Tools 23, SIAM, Philadelphia, 2011.
[29] S. Kim, R. Pasupathy, and S. G. Henderson, A guide to sample average approximation, in Handbook of Simulation Optimization, M. C. Fu, ed., Springer, New York, 2015, pp. 207–243.
[30] R. W. Klein and V. S. Bawa, The effect of estimation risk on optimal portfolio choice, J. Financ. Econom., 3 (1976), pp. 215–231.
[31] T. G. Kolda, R. M. Lewis, and V. Torczon, Stationarity results for generating set search for linearly constrained optimization, SIAM J. Optim., 17 (2006), pp. 943–968. · Zbl 1126.90076
[32] T. G. Kolda, R. M. Lewis, and V. J. Torczon, Optimization by direct search: New perspectives on some classical and modern methods, SIAM Rev., 45 (2003), pp. 385–482. · Zbl 1059.90146
[33] H. J. Kushner and G. G. Yin, Stochastic Approximation and Recursive Algorithms and Applications, Springer-Verlag, New York, 2003. · Zbl 1026.62084
[34] G. Lan, An optimal method for stochastic composite optimization, Math. Program., 133 (2012), pp. 365–397. · Zbl 1273.90136
[35] Y.-F. Liu, S. Ma, Y.-H. Dai, and S. Zhang, A smoothing SQP framework for a class of composite \(l_q\) minimization over polyhedron, Math. Program., 158 (2016), pp. 467–500. · Zbl 1346.90684
[36] H. Markowitz, Portfolio selection, J. Finance, 7 (1952), pp. 77–91.
[37] H. Markowitz, The optimization of a quadratic function subject to linear constraints, Naval Res. Logist. Q., 3 (1956), pp. 111–133.
[38] P. Massart, The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality, Ann. Probab., 18 (1990), pp. 1269–1283. · Zbl 0713.62021
[39] R. O. Michaud, The Markowitz optimization enigma: Is optimized optimal?, Financial Analysts J., 45 (1989), pp. 43–54.
[40] A. M. Mood, Introduction to the Theory of Statistics, McGraw-Hill, New York, 1950. · Zbl 0039.13901
[41] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Appl. Optim. 87, Kluwer Academic Publishers, London, 2004. · Zbl 1086.90045
[42] Y. Nesterov and V. Spokoiny, Random gradient-free minimization of convex functions, Found. Comput. Math., 17 (2017), pp. 527–566. · Zbl 1380.90220
[43] J. Nocedal and S. Wright, Numerical Optimization, 2nd ed., Springer Ser. Oper. Res., Springer, New York, 2006. · Zbl 1104.65059
[44] J.-S. Pang, A new and efficient algorithm for a class of portfolio selection problems, Oper. Res., 28 (1980), pp. 754–767. · Zbl 0451.90011
[45] R. Pasupathy, On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization, Oper. Res., 58 (2010), pp. 889–901. · Zbl 1228.90069
[46] R. Pasupathy, P. Glynn, S. Ghosh, and F. S. Hahemi, On sampling rates in simulation-based recursions, SIAM J. Optim., 28 (2018), pp. 45–73. · Zbl 1380.93168
[47] M. Porcelli and P. L. Toint, BFO, a trainable derivative-free Brute Force Optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables, ACM Trans. Math. Software, 44 (2017), pp. 1–25. · Zbl 1484.65136
[48] S. Sankaran, C. Audet, and A. L. Marsden, A method for stochastic constrained optimization using derivative-free surrogate pattern search and collocation, J. Comput. Phys., 229 (2010), pp. 4664–4682, . · Zbl 1193.65100
[49] A. Shapiro, D. Dentcheva, and A. Ruszczyński, Lectures on Stochastic Programming, MPS-SIAM Ser. Optim., SIAM, Philadelphia, 2009.
[50] W. F. Sharpe, The Sharpe ratio, J. Portfolio Manag, 21 (1994), pp. 49–58.
[51] R. J. Smith and R. W. Blundell, An exogeneity test for a simultaneous equation Tobit model with an application to labor supply, Econometrica, 54 (1986), pp. 679–685. · Zbl 0606.62136
[52] T. A. Sriver, J. W. Chrissis, and M. A. Abramson, Pattern search ranking and selection algorithms for mixed variable simulation-based optimization, European J. Oper. Res., 198 (2009), pp. 878–890. · Zbl 1176.90269
[53] L. Taylor and T. Otsu, Estimation of nonseparable models with censored dependent variables and endogenous regressors, Econom. Rev., to appear.
[54] J. L. Teugels, The class of subexponential distributions, Ann. Probab., 3 (1975), pp. 1000–1011. · Zbl 0374.60022
[55] A. Toth, J. A. Ellis, T. Evans, S. Hamilton, C. T. Kelley, R. Pawlowski, and S. Slattery, Local improvement results for Anderson acceleration with inaccurate function evaluations, SIAM J. Sci. Comput., 39 (2017), pp. S47–S65, . · Zbl 1422.65079
[56] R. Vershynin, Introduction to the non-asymptotic analysis of random matrices, in Compressed Sensing: Theory and Applications, Y. C. Eldar and G. Kutyniok, eds., Cambridge University Press, Cambridge, 2012, pp. 210–268.
[57] M. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint, (2017).
[58] J. Willert, X. Chen, and C. T. Kelley, Newton’s method for Monte Carlo-based residuals, SIAM J. Numer. Anal., 53 (2015), pp. 1738–1757, . · Zbl 1317.65121
[59] B. Yu, Rates of convergence for empirical processes of stationary mixing sequences, Ann. Probab., 22 (1994), pp. 94–116. · Zbl 0802.60024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.