×

zbMATH — the first resource for mathematics

Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints. (English) Zbl 1342.90151
Summary: The well known DIRECT (DIviding RECTangles) algorithm for global optimization requires bound constraints on variables and does not naturally address additional linear or nonlinear constraints. A feasible region defined by linear constraints may be covered by simplices, therefore simplicial partitioning may tackle linear constraints in a very subtle way. In this paper we demonstrate this advantage of simplicial partitioning by applying a recently proposed deterministic simplicial partitions based DISIMPL algorithm for optimization problems defined by general linear constraints (Lc-DISIMPL). An extensive experimental investigation reveals advantages of this approach to such problems comparing with different constraint-handling methods, proposed for use with DIRECT. Furthermore the Lc-DISIMPL algorithm gives very competitive results compared to a derivative-free particle swarm algorithm (PSwarm) which was previously shown to give very promising results. Moreover, DISIMPL guarantees the convergence to the global solution, whereas the PSwarm algorithm sometimes fails to converge to the global minimum.

MSC:
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baker, C.A., Watson, L.T., Grossman, B., Mason, W.H., Haftka, R.T.: Parallel global aircraft configuration design space exploration. In: Tentner A. (ed.) High Performance Computing Symposium 2000, pp. 54-66. Society for Computer Simulation International (2000)
[2] Bartholomew-Biggs, MC; Parkhurst, SC; Wilson, SP, Using DIRECT to solve an aircraft routing problem, Comput. Optim. Appl., 21, 311-323, (2002) · Zbl 1017.90133
[3] Carter, RG; Gablonsky, JM; Patrick, A; Kelley, CT; Eslinger, OJ, Algorithms for noisy problems in gas transmission pipeline optimization, Optim. Eng., 2, 139-157, (2001) · Zbl 1079.90624
[4] Chiter, L, DIRECT algorithm: a new definition of potentially optimal hyperrectangles, Appl. Math. Comput., 179, 742-749, (2006) · Zbl 1102.65067
[5] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to derivative-free optimization, vol. 8, SIAM (2009). doi:10.1137/1.9780898718768 · Zbl 1163.49001
[6] Cox, SE; Haftka, RT; Baker, CA; Grossman, B; Mason, WH; Watson, LT, A comparison of global optimization methods for the design of a high-speed civil transport, J. Global Optim., 21, 415-432, (2001) · Zbl 1014.90072
[7] De Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Computational geometry. Springer, Berlin, Heidelberg (2000). doi:10.1007/978-3-662-04245-8_1 · Zbl 0939.68134
[8] Delaunay, B, Sur la sphere vide. izv. akad. nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7, 1-2, (1934)
[9] Serafino, D; Liuzzi, G; Piccialli, V; Riccio, F; Toraldo, G, A modified dividing rectangles algorithm for a problem in astrophysics, J. Optim. Theory Appl., 151, 175-190, (2011) · Zbl 1226.90082
[10] Evtushenko, Y; Posypkin, M, A deterministic approach to global box-constrained optimization, Optim. Lett., 7, 819-829, (2013) · Zbl 1269.90082
[11] Evtushenko, YG, Numerical methods for finding global extrema (case of a non-uniform mesh), USSR Comput. Math. Math. Phys., 11, 38-54, (1971) · Zbl 0258.90045
[12] Finkel, D.E.: Direct optimization algorithm user guide. Center for Research in Scientific Computation, North Carolina State University 2 (2003) · Zbl 0956.90045
[13] Finkel, D.E.: Global optimization with the Direct algorithm. Ph.D. thesis, North Carolina State University (2005)
[14] Finkel, DE; Kelley, CT, Additive scaling and the DIRECT algorithm, J. Global Optim., 36, 597-608, (2006) · Zbl 1142.90488
[15] Fletcher, R.: Practical Methods of Optimization, vol. 37. Wiley, New York (1987) · Zbl 0905.65002
[16] Gablonsky, J.M.: Modifications of the Direct algorithm. Ph.D. thesis, North Carolina State University (2001) · Zbl 1039.90049
[17] Gablonsky, JM; Kelley, CT, A locally-biased form of the DIRECT algorithm, J. Global Optim., 21, 27-37, (2001) · Zbl 1039.90049
[18] He, J; Watson, LT; Ramakrishnan, N; Shaffer, CA; Verstak, A; Jiang, J; Bae, K; Tranter, WH, Dynamic data structures for a DIRECT search algorithm, Comput. Optim. Appl., 23, 5-25, (2002) · Zbl 1036.90055
[19] Hendrix, E.M., Casado, L.G., Amaral, P.: Global optimization simplex bisection revisited based on considerations by reiner horst. Computational Science and Its Applications-ICCSA 2012, pp. 159-173. Springer, Berlin, Heidelberg (2012). doi:10.1007/978-3-642-31137-6_12
[20] Horst, R., Pardalos, P.M. (eds.): Handbook of Global Optimization, vol. 1. Kluwer Academic Publishers, Dordrecht (1995) · Zbl 0805.00009
[21] Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic Publishers, Nonconvex Optimization and Its Application (1995) · Zbl 0836.90134
[22] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Berlin (1996) · Zbl 0867.90105
[23] Huyer, W; Neumaier, A, Global optimization by multilevel coordinate search, J. Global Optim., 14, 331-355, (1999) · Zbl 0956.90045
[24] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032
[25] Kvasov, DE; Sergeyev, YD, A univariate global search working with a set of Lipschitz constants for the first derivative, Optim. Lett., 3, 303-318, (2009) · Zbl 1173.90544
[26] Kvasov, DE; Sergeyev, YD, Lipschitz gradients for global optimization in a one-point-based partitioning scheme, J. Comput. Appl. Math., 236, 4042-4054, (2012) · Zbl 1246.65091
[27] Lera, D; Sergeyev, YD, Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives, SIAM J. Optim., 23, 508-529, (2013) · Zbl 1270.90049
[28] Liuzzi, G; Lucidi, S; Piccialli, V, A direct-based approach exploiting local minimizations for the solution for large-scale global optimization problems, Comput. Optim. Appl., 45, 353-375, (2010) · Zbl 1187.90275
[29] Liuzzi, G; Lucidi, S; Piccialli, V, A partition-based global optimization algorithm, J. Global Optim., 48, 113-128, (2010) · Zbl 1230.90153
[30] Murty, KG; Kabadi, SN, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39, 117-129, (1987) · Zbl 0637.90078
[31] Neumaier, A.: MCS: global optimization by multilevel coordinate search. http://www.mat.univie.ac.at/neum/software/mcs/ · Zbl 0956.90045
[32] Pardalos, PM; Schnitger, G, Checking local optimality in constrained quadratic programming is NP-hard, Oper. Res. Lett., 7, 33-35, (1988) · Zbl 0644.90067
[33] Paulavičius, R; Sergeyev, YD; Kvasov, DE; Žilinskas, J, Globally-biased disimpl algorithm for expensive global optimization, J. Global Optim., 59, 545-567, (2014) · Zbl 1297.90130
[34] Paulavičius, R; Žilinskas, J, Analysis of different norms and corresponding Lipschitz constants for global optimization in multidimensional case, Inf. Technol. Control, 36, 383-387, (2007)
[35] Paulavičius, R; Žilinskas, J, Influence of Lipschitz bounds on the speed of global optimization, Technol. Econ. Dev. Econ., 18, 54-66, (2012)
[36] Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. SpringerBriefs in Optimization. Springer, New York (2014). doi:10.1007/978-1-4614-9093-7 · Zbl 1401.90017
[37] Paulavičius, R; Žilinskas, J, Simplicial Lipschitz optimization without the Lipschitz constant, J. Global Optim., 59, 23-40, (2014) · Zbl 1300.90031
[38] Paulavičius, R; Žilinskas, J; Grothey, A, Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds, Optim. Lett., 4, 173-183, (2010) · Zbl 1189.90203
[39] Pintér, J.D.: Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications). Kluwer Academic Publishers, Dordrecht (1996) · Zbl 0842.90110
[40] Piyavskii, SA, An algorithm for finding the absolute extremum of a function, Zh. Vychisl. Mat. mat. Fiz, 12, 888-896, (1972) · Zbl 0249.65046
[41] Rios, L.M., Sahinidis, N.V.: Derivative-free optimization: a review of algorithms and comparison of software implementations. J. Global Optim. 56(3), 1247-1293 (2012). doi:10.1007/s10898-012-9951-y · Zbl 1272.90116
[42] Sergeyev, YD; Kvasov, DE, Global search based on efficient diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16, 910-937, (2006) · Zbl 1097.65068
[43] Sergeyev, YD; Kvasov, DE; Cochran, JJ (ed.); Cox, LA (ed.); Keskinocak, P (ed.); Kharoufeh, JP (ed.); Smith, JC (ed.), Lipschitz global optimization, No. 4, 2812-2828, (2011), New York
[44] Sergeyev, YD; Pugliese, P; Famularo, D, Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints, Math. Program., 96, 489-512, (2003) · Zbl 1023.90049
[45] Vaz, A.I.F.: PSwarm solver home page (2010). http://www.norg.uminho.pt/aivaz/pswarm/. Accessed 12 Dec 2013
[46] Vaz, AIF; Vicente, L, Pswarm: a hybrid solver for linearly constrained global derivative-free optimization, Optim. Methods Softw., 24, 669-685, (2009) · Zbl 1177.90327
[47] Žilinskas, J, Branch and bound with simplicial partitions for global optimization, Math. Model. Anal., 13, 145-159, (2008) · Zbl 1146.49029
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.