×

zbMATH — the first resource for mathematics

CARTopt: a random search method for nonsmooth unconstrained optimization. (English) Zbl 1312.90065
Summary: A random search algorithm for unconstrained local nonsmooth optimization is described. The algorithm forms a partition on \(\mathbb{R}^{n}\) using classification and regression trees (CART) from statistical pattern recognition. The CART partition defines desirable subsets where the objective function \(f\) is relatively low, based on previous sampling, from which further samples are drawn directly. Alternating between partition and sampling phases provides an effective method for nonsmooth optimization. The sequence of iterates \(\{z _{k }\}\) is shown to converge to an essential local minimizer of \(f\) with probability one under mild conditions. Numerical results are presented to show that the method is effective and competitive in practice.

MSC:
90C26 Nonconvex programming, global optimization
Software:
CARTopt; Matlab; minpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, M.J.; Labarre, R.; Radulovic, D., On accelerated random search, SIAM J. Optim., 14, 708-731, (2003) · Zbl 1061.65046
[2] Audet, C.; Dennis, J.E., Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217, (2006) · Zbl 1112.90078
[3] Brachetti, P.; Ciccoli, M.D.F.; Di Pillo, G.; Lucidi, S., A new version of the price’s algorithm for global optimization, J. Glob. Optim., 10, 165-184, (1997) · Zbl 0877.65038
[4] Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and Regression Trees. Wadsworth, Belmont (1984) · Zbl 0541.62042
[5] Burmen, Á.; Puhan, J.; Tuma, T., Grid restrained Nelder Mead algorithm, Comput. Optim. Appl., 34, 359-375, (2006) · Zbl 1152.90658
[6] Clarke, F.H.: Optimization and Nonsmooth Analysis. Classics in Applied Mathematics. SIAM, Philadelpha (1990) · Zbl 0696.49002
[7] Dorea, C.C.Y., Stopping rules for a random optimization method, SIAM J. Control Optim., 28, 841-850, (1990) · Zbl 0711.65043
[8] Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification. Wiley-Interscience, New York (2001)
[9] Hart, W.E., Sequential stopping rules for random optimization methods with applications to multistart local search, SIAM J. Optim., 9, 270-290, (1998) · Zbl 0959.65075
[10] Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer, Berlin (1981) · Zbl 0452.90038
[11] Loh, W., On Latin hypercube sampling, Ann. Stat., 24, 2058-2080, (1996) · Zbl 0867.62005
[12] Lukšan, L., Vlc̆ek, J.: Test problems for unconstrained optimization. Technical Report no. 8. Academy of Sciences of the Czech Republic, Institute of Computer Science (2003) · Zbl 0454.65049
[13] Martinez, W.L., Martinez, A.R.: Computational Statistics Handbook with MATLAB. Chapman & Hall/CRC Press, London/Boca Raton (2002) · Zbl 0986.62104
[14] Moré, J.J.; Garbow, B.S.; Hillstrom, K.E., Testing unconstrained optimization software, ACM Trans. Math. Softw., 7, 17-41, (1981) · Zbl 0454.65049
[15] Nelder, J.A.; Mead, R., A simplex method for function minimization, Comput. J., 7, 308-313, (1965) · Zbl 0229.65053
[16] Price, C.J.; Reale, M.; Robertson, B.L., A direct search method for smooth and nonsmooth unconstrained optimization, ANZIAM J., 48, c927-c948, (2006) · Zbl 1334.90132
[17] Price, C.J.; Robertson, B.L.; Reale, M., A hybrid Hooke and jeeves—direct method for nonsmooth optimization, Adv. Model. Optim., 11, 43-61, (2009) · Zbl 1179.90313
[18] Price, C.J.; Reale, M.; Robertson, B.L., A cover partitioning method for bound constrained global optimization, Optim. Methods Softw., 27, 1059-1072, (2012) · Zbl 1250.90071
[19] Rinnooy Kan, A.H.G.; Timmer, G.T., Stochastic global optimization methods. part I. clustering methods, Math. Program., 39, 27-56, (1987) · Zbl 0634.90066
[20] Robertson, B.L.; Price, C.J.; Reale, M., Nonsmooth optimization using classification and regression trees, Cairns, Australia, July 13-17, 2009 · Zbl 1162.94431
[21] Robertson, B.L.: Direct search methods for nonsmooth problems using global optimization techniques. Ph.D. Thesis, University of Canterbury, Christchurch, New Zealand (2010) · Zbl 1152.90658
[22] Schittkowski, K.: More Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 282. Springer, Berlin (1987) · Zbl 0658.90060
[23] Tang, Z.B., Adaptive partitioned random search to global optimization, IEEE Trans. Autom. Control, 39, 2235-2244, (1994) · Zbl 0846.90102
[24] Torn, A., Žilinskas, A.: Global Optimization. Lecture Notes in Computer Science, vol. 350. Springer, Berlin (1989) · Zbl 0752.90075
[25] Vicente, L.N.; Custódio, A.L., Analysis of direct searches for discontinuous functions, Math. Program., 133, 299-325, (2012) · Zbl 1245.90127
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.