×

zbMATH — the first resource for mathematics

A direct search quasi-Newton method for nonsmooth unconstrained optimization. (English) Zbl 1385.65042
Summary: A direct search quasi-Newton algorithm is presented for local minimization of Lipschitz continuous black-box functions. The method estimates the gradient via central differences using a maximal frame around each iterate. When nonsmoothness prevents progress, a global direction search is used to locate a descent direction. Almost sure convergence to Clarke stationary point(s) is shown, where convergence is independent of the accuracy of the gradient estimates. Numerical results show that the method is effective in practice.
MSC:
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C53 Methods of quasi-Newton type
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akbari, Z.; Yousefpour, R.; Reza Peyghami, M., A new nonsmooth trust region algorithm for locally Lipschitz unconstrained optimization problems, J. Optim. Theory Appl., 164, 733-754, (2015) · Zbl 1318.49054
[2] Appel, M. J.; Labarre, R.; Radulović, D., On accelerated random search, SIAM J. Optim., 14, 708-731, (2003) · Zbl 1061.65046
[3] Audet, C.; Dennis, J. E. Jr., Analysis of generalized pattern searches, SIAM J. Optim., 13, 889-903, (2003) · Zbl 1053.90118
[4] Audet, C.; Dennis, J. E. Jr., Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217, (2006) · Zbl 1112.90078
[5] Audet, C.; Dennis, J. E. Jr., OrthoMADS: a deterministic MADS instance with orthogonal directions, SIAM J. Optim., 20, 948-966, (2009) · Zbl 1187.90266
[6] Bagirov, A. M.; Karasözen, B.; Sezer, M., Discrete gradient method: derivative free method for nonsmooth optimization, J. Optim. Theory Appl., 137, 317-334, (2008) · Zbl 1165.90021
[7] Bagirov, A. M.; Ugon, J., Piecewise partially separable functions and a derivative-free algorithm for large scale nonsmooth optimization, J. Global Optim., 35, 163-195, (2006) · Zbl 1136.90515
[8] Burke, J. V.; Lewis, A. S.; Overton, M. L., A robust gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim., 15, 751-779, (2005) · Zbl 1078.65048
[9] Clarke, F. H., Optimization and nonsmooth analysis, Volume 5 of, (1990), SIAM: SIAM, Philadelphia · Zbl 0696.49002
[10] Coope, I. D.; Price, C. J., Frame based methods for unconstrained optimization, J. Optim. Theory Appl., 107, 261-274, (2000) · Zbl 0983.90074
[11] Custódio, A. L.; Dennis, J. E. Jr.; Vicente, L. N., Using simplex gradients of nonsmooth functions in direct search methods, IMA J. Numer. Anal., 28, 770-784, (2008) · Zbl 1156.65059
[12] Davis, C., Theory of positive linear dependence, Amer. J. Math., 76, 733-746, (1954) · Zbl 0058.25201
[13] Dennis, J. E. Jr.
[14] Gill, P. E.; Murray, W.; Wright, M. H., Practical optimization, (1981), Academic Press: Academic Press, London
[15] Hooke, R.; Jeeves, T. A., Direct search solution of numerical and statistical problems, Assoc. Computing Machinery J., 8, 212-229, (1960) · Zbl 0111.12501
[16] Lukšan, L.; Vlček, J.
[17] Makela, M., Survey of bundle methods for nonsmooth optimization, Optim. Methods Softw., 17, 1-29, (2002) · Zbl 1050.90027
[18] Moré, J. J.; Garbow, B. S.; Hillstrom, K. E., Testing unconstrained optimization software, ACM Trans. Math. Software, 7, 17-41, (1981) · Zbl 0454.65049
[19] Nelder, J. A.; Mead, R., A simplex method for function minimization, Comput. J., 7, 308-313, (1965) · Zbl 0229.65053
[20] Polak, E.; Roysett, J. O., Algorithms for finite and semi-infinite min-max-min problems using adaptive smoothing techniques, J. Optim. Theory Appl., 119, 421-457, (2003) · Zbl 1061.90116
[21] Price, C. J.; Coope, I. D., Frame based ray search algorithms in unconstrained optimization, J. Optim. Theory Appl., 116, 359-377, (2003) · Zbl 1045.90066
[22] Price, C. J.; Reale, M.; Robertson, B. L., A direct search method for smooth and nonsmooth unconstrained optimization, ANZIAM J., 48, C927-C948, (2008) · Zbl 1334.90132
[23] Price, C. J.; Robertson, B. L.; Reale, M., A hybrid Hooke and Jeeves - Direct method for non-smooth optimization, Adv. Model. Optim., 11, 43-61, (2009) · Zbl 1179.90313
[24] Robertson, B. L.; Price, C. J.; Reale, M., CARTopt: a random search method for nonsmooth unconstrained optimization, Comput. Optim. Appl., 56, 291-315, (2013) · Zbl 1312.90065
[25] Sun, L.-P., A quasi-Newton algorithm without calculating derivatives for unconstrained optimization, J. Comput. Math., 12, 380-386, (1994) · Zbl 0817.65046
[26] Tang, C. M.; Liu, S.; Jian, J. B.; Li, J. L., A feasible SQP-GS algorithm for nonconvex, nonsmooth constrained optimization, Numer. Algorithms, 65, 1-22, (2014) · Zbl 1285.65036
[27] Torczon, V., On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1-25, (1997) · Zbl 0884.65053
[28] Vicente, L. N.; Custodio, A. L., Analysis of direct searches for discontinuous functions, Math. Program. Ser. A, 133, 299-325, (2012) · Zbl 1245.90127
[29] Wright, M. H., Direct search methods: once scorned, now respectable, Numerical analysis 1995 (Dundee, 1995), Volume 344 of, 191-208, (1996), Longman: Longman, Harlow · Zbl 0844.65057
[30] Wu, T.; Sun, L.-P., A new quasi-Newton pattern search method based on symmetric rank-one update for unconstrained optimization, Comput. Math. Appl., 55, 1201-1214, (2008) · Zbl 1144.90513
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.