×

Generating \(\alpha \)-dense curves in non-convex sets to solve a class of non-smooth constrained global optimization. (English) Zbl 1458.90527

Summary: This paper deals with the dimensionality reduction approach to study multi-dimensional constrained global optimization problems where the objective function is non-differentiable over a general compact set \(D\) of \(\mathbb{R}^n\) and Hölderian. The fundamental principle is to provide explicitly a parametric representation \(x_i=\ell_i(t)\), \(1\leq i\leq n\) of \(\alpha \)-dense curve \(\ell_{\alpha }\) in the compact \(D\), for \(t\) in an interval \(\mathbb{I}\) of \(\mathbb{R} \), which allows to convert the initial problem to a one dimensional Hölder unconstrained one. Thus, we can solve the problem by using an efficient algorithm available in the case of functions depending on a single variable. A relation between the parameter \(\alpha\) of the curve \(\ell_{\alpha }\) and the accuracy of attaining the optimal solution is given. Some concrete \(\alpha\) dense curves in a non-convex feasible region \(D\) are constructed. The numerical results show that the proposed approach is efficient.

MSC:

90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ammar, H. and Cherruault, Y. (1993). Approximation of a several variables function by a one variable function and application to global optimization.Mathematical and Computer Modelling, 18(2), 17-21.doi: 10.1016/0895-7177(93)90003-h · Zbl 0797.41029
[2] Butz, A. R. (1968). Space filling curves and mathematical programming.Information and control, 12(4), 313-330.doi: 10.1016/s0019-9958(68)90367-7 · Zbl 0187.12702
[3] Delgado, P. M. and Galperin, E. A. (2006). Global optimization over general compact sets by the beta algorithm: A MAPLE Code.Computers and Mathematics with Applications, 52(1-2), 33-54. doi: 10.1016/j.camwa.2006.08.003 · Zbl 1161.90463
[4] Gourdin, E., Jaumard, B. and Ellaia, R. (1996). Global Optimization of H¨older function.Journal of Global Optimization, 8(4), 323-348.doi: 10.1007/bf02403997 · Zbl 0848.90110
[5] Guettal, D. and Ziadi, A. (2012). Reducing Transformation and Global Optimization.Applied Mathematics and Computation, 218(10), 5848-5860.doi: 10.1016/j.amc.2011.11.053 · Zbl 1256.65054
[6] Hanjoul, P., Hansen, P., Peeters, D. and Thisse, J. F. (1990). Uncapacitated plant location under alternative space price policies.Management Science, 36(1), 41-57.doi: 10.1287/mnsc.36.1.41 · Zbl 0694.90045
[7] Horst, R. and Pardalos, P. M. (1995). Handbook of Global Optimization.Nonconvex Optimization and Its Applications, 2. Springer-Verlag, Boston.doi: 10.1007/978-1-4615-2025-2 · Zbl 0805.00009
[8] Horst, R. and Tuy, H. (1993).Global Optimization, Deterministic Approaches. Springer-Verlag, Berlin.doi: 10.1007/978-3-662-03199-5 · Zbl 0867.90105
[9] Kiatsupaibul, S., Smith, L. R. and Zabinsky, Z. B. (2016). Solving infinite horizon optimization problems through analysis of a one-dimensional global optimization problem.Journal of Global Optimization, 66(4), 711-727.doi: 10.1007/s10898-016-0423-7 · Zbl 1370.90191
[10] Lera, D. and Sergeyev, Y. D. (2002). Global Minimization Algorithms for H¨older FunctionsBIT Numerical Mathematics, 42(1), 119-133.doi: 10.1023/a:1021926320198 · Zbl 1003.65064
[11] Lera, D. and Sergeyev, Y. D. (2010). Lipschitz and H¨older global optimization using space-filling curves.Applied Numerical Mathematics, 60(1-2), 115-129.doi: 10.1016/j.apnum.2009.10.004 · Zbl 1201.65101
[12] Hou, Z. E. and Duan, F. J. (2007). The approximation algorithm for solving a sort of non-smooth programming.Applied Mathematics and Computation, 186(2), 1511-1519.doi: 10.1016/j.amc.2006.06.129 · Zbl 1144.65040
[13] Mishra, S. H. (2006). Some new test functions for global optimization and performance of repulsive particle swarm method. Available at SSRN, 1-12.doi: 10.2139/ssrn.926132
[14] Mora, G. and Cherruault, Y. (1997). Characterization and generation ofα-dense curves.Computers and Mathematics with Applications, 33(9), 83-91.doi: 10.1016/s0898-1221(97)00067-9 · Zbl 0893.90177
[15] Pinter, J. D. (1996). Global Optimization in Action, Continuous and Lipschitz Optimization: Algorithm, Implementations and Applications. Book Series of theNonconvex Optimization and Its Application. Kluwer Academic Publisher, Dordrecht. Springer: New York.doi: 10.1007/978-14757-2502-5 · Zbl 0842.90110
[16] Piyavskii, S. A. (1972). An algorithm for finding the absolute extremum of a function. USSR Computational Mathematics and Mathematical Physics, 12(4), 57-67.doi: 10.1016/00415553(72)90115-2 · Zbl 0282.65052
[17] Rahal, M. and Ziadi, A. (2008). A new extension of Piyavskii’s method to H¨older functions of several variables.Applied Mathematics and Computation, 197(2), 478-488.doi: 10.1016/j.amc.2007.07.067 · Zbl 1154.65050
[18] Sagan, H. (1994).Space-filling curves. Springer-Verlag, New York.doi: 10.1007/978-1-4612-0871-6 · Zbl 0806.01019
[19] Sergeyev, Y. D., Strongin, R. G. and Lera, D. (2013).Introduction to Global Optimization Exploiting Space-Filling-Curves. Springer Briefs in Optimization. Springer, New York.doi: 10.1007/9781-4614-8042-6 · Zbl 1278.90005
[20] Strongin, R. G. (1992). Algorithms for multi-extremal programming problems employing the set of joint space-filling curves.Journal of Global Optimization, 2(4), 357—378.doi: 10.1007/bf00122428 · Zbl 0767.90080
[21] T¨orn, A. and ˇZilinska, A. (1989).Global optimization. Lecture Notes in Computer Sciences, 350. Springer-Verlag.https://doi.org/10.1007/3-540-50871-6 · Zbl 0752.90075
[22] Vanderbei, R. J. (1999). Extension of Piyavskii’s algorithm to continuous global optimization. Journal of Global Optimization, 14(2), 205-216.doi: 10.1023/a:1008395413111 · Zbl 0946.90065
[23] Ziadi, A. and Cherruault, Y. (1998). Generation ofα-dense curves in a cube ofRn.Kybernetes, 27(4), 416-425.doi: 10.1108/eum0000000004524 · Zbl 0933.65067
[24] Ziadi, A. and Cherruault, Y. (2000). Generation ofα-dense curves and application to global optimization.Kybernetes, 29(1), 71-82.doi: 10.1108/03684920010308871 · Zbl 0978.90090
[25] Ziadi, A., Cherruault, Y. and Mora, G.(2000). The existence ofα-dense curves with minimal lenght in a metric space.Kybernetes, 29(2), 219-230.doi: 10.1108/03684920010312803 · Zbl 0978.90091
[26] Ziadi, A., Cherruault, Y. and Mora, G. (2001). Global optimization: A new variant of the Alienor method.Computers and Mathematics with Applications, 41(1-2), 63-71.doi: 10.1016/S08981221(01)85006-9 · Zbl 0980.90069
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.