Article Contents
Article Contents

# On a new smoothing technique for non-smooth, non-convex optimization

• * Corresponding author: Ahmet Sahiner
This study has been supported by the Teaching Staff Training Project Units of Suleyman Demirel University (OYP-05545-DR-13)
• In many global optimization techniques, the local search methods are used for different issues such as to obtain a new initial point and to find the local solution rapidly. Most of these local search methods base on the smoothness of the problem. In this study, we propose a new smoothing approach in order to smooth out non-smooth and non-Lipschitz functions playing a very important role in global optimization problems. We illustrate our smoothing approach on well-known test problems in the literature. The numerical results show the efficiency of our method.

Mathematics Subject Classification: Primary: 65D10, 90C26; Secondary: 49J52, 26A27.

 Citation:

• Figure 1.  (a) The green and solid graph is the graph of $q_1(t)$, the blue and dashed one is the graph of $\tilde{q}_{1}(t,0.5)$, the red and dotted one is the graph of $\tilde{q}_{1}(t,1)$. (b) The green and solid graph is the graph of $q_{1/2}(t)$, the blue and dashed one is the graph of $\tilde{q}_{1/2}(t,0.5)$, the red and dotted one is the graph of $\tilde{q}_{1/2}(t,1)$

Figure 2.  (a) The graph of the function $f(x,y)$, (b) The graph of $\tilde{f}(x,\beta)$

Figure 3.  (a) The graph of the function $F_{\lambda}(x)$, (b) the graph of the function $\tilde{F}_{\lambda}(x,\beta)$

Table 1.  The values of $a_j$, $b_j$ and $p_j$ in Example 1

 $j$ $1$ $2$ $3$ $4$ $5$ $a_j$ $3$ $2$ $3$ $3.5$ $5$ $b^j$ $(4,3)$ $(-2,-3)$ $(-3,3)$ $(4,-4)$ $(0,0)$ $p_j$ $2$ $2$ $2$ $1$ $\frac{2}{3}$

Table 2.  Table of minimization process of the Example 1

 $\beta$ $k$ $\bar{x}_k$ $\tilde{f}(\bar{x}_k,\beta)$ $f(\bar{x}_k)$ $x_k^*$ $f(x_k^*)$ $10^{-4}$ $1$ $(3.9999, 2.9998)$ $-4.4178$ $-4.4178$ $(3.9944,2.9777)$ $-4.4193$ $2$ $(4.0000, -4.0000)$ $-4.4704$ $-4.4708$ $(4.0000,-3.9808)$ $-4.4064$ $3$ $(-0.0000, -0.0000)$ $-5.7907$ $-5.8048$ $(-0.0000, 0.0000)$ $-5.8048$ $10^{-6}$ $1$ $(3.9829,2.9846)$ $-4.2006$ $-4.4188$ $(3.9944, 2.9777)$ $-4.4193$ $2$ $(4.0000,-4.0000)$ $-4.4673$ $-4.4706$ $(4.0000,-4.0000)$ $-4.4706$ $3$ $(-0.0000, 0.0000)$ $-5.8040$ $-5.8042$ $(0.0000,-0.0000)$ $-5.8047$

Table 3.  The values of $a_j$, $b_j$ and $p_j$ in Example 2

 $j$ $1$ $2$ $3$ $4$ $5$ $6$ $a_j$ $1.8$ $1.2$ $4.8$ $3.5$ $2.8$ $2.1$ $b^j$ $-7$ $2$ $-3.5$ $6$ $-1$ $4$ $p_j$ $2$ $2$ $1$ $1$ $\frac{2}{5}$ $\frac{1}{2}$

Table 4.  Table of minimization process of the Example 2

 $\beta$ $k$ $\bar{x}_k$ $\tilde{F}_{\lambda}(\bar{x}_k,\beta)$ $F_{\lambda}(\bar{x}_k)$ $f(\bar{x}_k)$ $x_k^*$ $f(x_k^*)$ $10^{-4}$ $1$ $4.0001$ $-5.0017$ $-5.0320$ $-5.0320$ $4.0000$ $-5.0504$ $2$ $6.0000$ $-5.7891$ $-5.7893$ $-5.7893$ $6.0000$ $-5.7893$ $3$ $-3.5000$ $-7.0153$ $-7.0156$ $-7.0156$ $-3.5000$ $-7.0156$ $10^{-6}$ $1$ $-0.9998$ $-5.2906$ $-5.3361$ $-5.3361$ $-1.0000$ $-5.4260$ $2$ $3.9999$ $-2.5950$ $-2.5966$ $-2.5966$ $4.0000$ $-2.5967$ $3$ $-3.5000$ $-7.0132$ $-7.0156$ $-7.0156$ $-3.5000$ $-7.0156$

Table 5.  The list of non-smooth test problems

 Problem No. Function Name Dimension $n$ Region Global minimum 2 Problem 1 in [14] $1$ $[-10,10]$ $1$ 3 Problem 2 in [14] $1$ $[-10,10]$ $1$ 4 Problem 3 in [14] $2$ $[-10,10]$ $2$ 5, 6, 7, 8, 9, 10, 11 Problem 7 in [14] $2,3,4,5,10,15,20$ $[-10,10]$ $0$

Table 6.  The numerical results for the non-smooth test problems

 Problem AFA GDA No. $x_0$ $f^*$ f.eval Time(sec) $f^*$ f.eval Time(sec) $2$ $10$ $1.0000$ $106$ $0.0155$ $1.0000$ $362$ $0.1552$ $3$ $10$ $1.0000$ $219$ $0.0178$ $1.0000$ $524$ $0.3779$ $4$ $(10,10)$ $2.0000$ $539$ $0.2676$ $2.0000$ $1136$ $2.4738$ $5$ $(5,5)$ $1.0000$ $367$ $0.2432$ $0.0000$ $1212$ $2.9559$ $6$ $(5,5,5)$ $2.9806e-005$ $471$ $0.2458$ $0.0000$ $1678$ $5.1616$ $7$ $(5,\dots,5)$ $2.9986e-005$ $614$ $0.2771$ $0.0000$ $2614$ $7.5685$ $8$ $(5,\dots,5)$ $4.9992e-005$ $733$ $0.3065$ $2e-004$ $3484$ $10.0016$ $9$ $(5,\dots,5)$ $9.9991e-005$ $2270$ $0.4037$ $6e-004$ $10344$ $37.5289$ $10$ $(5,\dots,5)$ $1.4982e-006$ $3278$ $0.4986$ $8e-004$ $14390$ $55.3796$ $11$ $(5,\dots,5)$ $1.6520e-013$ $8262$ $0.7262$ $5e-004$ $42446$ $118.4403$
•  [1] A. M. Bagirov, A. Al Nuaimat and N. Sultanova, Hyperbolic smoothing function method for minimax problems, Optimization, 62 (2013), 759-782.  doi: 10.1080/02331934.2012.675335. [2] D. Bertsekas, Nondifferentiable optimization via approximation, Mathematical Programming Study, 3 (1975), 1-25.  doi: 10.1007/BFb0120696. [3] B. C. Cetin, J. Barhen and J. W. Burdick, Terminal repeller unconstrained subenergy tunneling (TRUST) for fast global optimization, J. Optimiz. Theory Appl., 77 (1993), 97-126.  doi: 10.1007/BF00940781. [4] C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problem, Comput. Optim. Appl., 5 (1996), 91-138.  doi: 10.1007/BF00249052. [5] X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Math. Program. Ser. B, 134 (2012), 71-99.  doi: 10.1007/s10107-012-0569-0. [6] X. Chen, M. K. Ng and C. Zhang, Non-lipschitz $l_p$-regularization and box constrained model for image processing, IEEE Trans. Image. Process., 21 (2012), 4709-4721.  doi: 10.1109/TIP.2012.2214051. [7] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983. [8] V. F. Demyanov and V. N. Malozemov, Introduction to Minimax, 2$^{nd}$ edition, Dover, New York 1990. [9] V. F. Demyanov and A. M. Rubinov, Constructive Nonsmooth Analysis, Verlag Peter Lang, Frankfurt, 1995. [10] R. P. Ge, A filled function method for finding global minimizer of a function of several variables, Math. Program., 46 (1990), 191-204.  doi: 10.1007/BF01585737. [11] R. P. Ge, The theory of filled function method for finding global minimizer of a nonlinearly constrained minimization problem, J. Comput. Math., 5 (1987), 1-9. [12] J. H. Holland,  Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975. [13] D. R. Jones, C. D. Perttunen and B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79 (1993), 157-181.  doi: 10.1007/BF00941892. [14] A. Ketfi-Cherif and A. Ziadi, Global descent method for constrained continuous global optimization, Appl. Math. Comput., 244 (2014), 209-221.  doi: 10.1016/j.amc.2014.06.089. [15] S. Kirkpatrick, Jr. C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680. [16] D. E. Kvasov and M. S. Mukhametzhanov, Metaheuristic vs. deterministic global optimization algorithms: The univariate case, Appl. Math. Comput., 318 (2018), 245-259.  doi: 10.1016/j.amc.2017.05.014. [17] D. E. Kvasov and Y. D. Sergeyev, Deterministic approaches for solving practical black-box global optimization problems, Adv. Eng. Softw., 80 (2015), 58-66.  doi: 10.1016/j.advengsoft.2014.09.014. [18] J. Lee and D. Skipper, Virtuous smoothing for global optimization, J. Glob. Optim., 69 (2017), 677-697.  doi: 10.1007/s10898-017-0533-x. [19] A. V. Levy and A. Montalvo, The tunneling algorithm for the global minimization of functions, SIAM J. Sci. Stat. Comput., 6 (1985), 15-29.  doi: 10.1137/0906002. [20] S. J. Lian, Smoothing approximation to $l_1$ exact penalty for inequality constrained optimization, Appl. Math. Comput., 219 (2012), 3113-3121.  doi: 10.1016/j.amc.2012.09.042. [21] H. Lin, Y. Wang, Y. Gao and X. Wang, A filled function method for global optimization with inequality constraints, Comput. Appl. Math., 37 (2018), 1524-1536.  doi: 10.1007/s40314-016-0407-8. [22] S. Ma, Y. Yang and H. Liu, A parameter free filled function for unconstrained global optimization, Appl. Math. Comput., 215 (2010), 3610-3619.  doi: 10.1016/j.amc.2009.10.057. [23] C. K. Ng, D. Li and L. S. Zhang, Global descent method for global optimization, SIAM J. Optim., 20 (2010), 3161-3184.  doi: 10.1137/090749815. [24] M. Nikolova, C. K. Ng and C. P. Tam, Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction, IEEE T. Image Process., 19 (2010), 3073-3088.  doi: 10.1109/TIP.2010.2052275. [25] A. Ozmen, E. Kropat and G.-W. Weber, Spline regression models for complex multi-modal regulatory networks, Optim. Method Softw., 29 (2014), 515-534.  doi: 10.1080/10556788.2013.821611. [26] A. Ozmen and G. W. Weber, RMARS: Robustification of multivariate adaptive regression spline under polyhedral uncertainty, J. Comput. Appl. Math., 259 (2014), 914-924.  doi: 10.1016/j.cam.2013.09.055. [27] R. Paulavicius, J. Zilinskas and A. Grothey, Parallel branch and bound for global optimization with combination of Lipschitz bounds, Optim. Method Softw., 26 (2011), 487-498.  doi: 10.1080/10556788.2010.551537. [28] R. Paulavicius, Y. D. Sergeyev, D. E. Kvasov and J. Zilinskas, Globally-biased DISIMPL algorithm for expensive global optimization, J. Glob. Optim., 59 (2014), 545-567.  doi: 10.1007/s10898-014-0180-4. [29] R. Paulavicius, C. Lakhdar and J. Zilinskas, Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants, J. Glob. Optim., 79 (2018), 5-20.  doi: 10.1007/s10898-016-0485-6. [30] S. S. Rao, K. Sundararaju, B. G. Prakash and C. Balakrishna, A fuzzy goal programming approach for structural optimization, AIAA Journal, 30 (1992), 1425-1432.  doi: 10.2514/3.11079. [31] M. Resener, S. Haffner, L. A. Pereira and P. M. Pardalos, Optimization techniques applied to planning of electric power distribution systems: A bibliographic survey, Energy Syst., 9 (2018), 473-509.  doi: 10.1007/s12667-018-0276-x. [32] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, Berlin, 1998. [33] A. Sahiner, N. Yilmaz and O. Demirozer, Mathematical modeling and application of filled function method in entomology, Int. Journal Pest. Manage., 60 (2014), 232-237.  doi: 10.1080/09670874.2014.958879. [34] A. Sahiner, G. Kapusuz and N. Yilmaz, A new smoothing approach to exact penalty functions for inequality constrained optimization problems, Numer. Algebra Cont. Optim., 6 (2016), 161-173.  doi: 10.3934/naco.2016006. [35] Y. D. Sergeyev, R. G. Strongin and D. Lera, Introduction to Global Optimization Exploiting Space-Filling Curves, Springer, New York, 2013. [36] Y. D. Sergeyev, D. E. Kvasov and M. S. Mukhametzhanov, On the efficiency of nature-inspired metaheuristics in expensive global optimization with limited budget, Sci. Rep., 8 (2018), 1-9.  doi: 10.1038/s41598-017-18940-4. [37] Y. Shi and R. Eberhart, A modified particle swarm optimizer, In Proceedings of IEEE International Conference on Evolutionary Computation, (1998), 69–73. [38] R. G. Strogin and Y. D. Sergeyev, Global Optimization with Nonconvex Constraints: Sequential and Paralel Algorithms, Kluwer Academic Publishers, Dordecht, 2000. [39] H. Tuy, Cutting plane methods for global optimization, In: Encyclopedia of Optimization (eds. C. Floudas and P. Pardalos), 2$^{nd}$ Edition, Springer, New York, (2009), 590–594. [40] Y. Wang, W. Fang and T. Wu, A cut-peak function method for global optimization, J. Comput. Appl. Math., 230 (2009), 135-142.  doi: 10.1016/j.cam.2008.10.069. [41] F. Wei, Y. Wang and H. Lin, A new filled function method with two parameters for global optimization, J. Optim. Theory Appl., 163 (2014), 510-527.  doi: 10.1007/s10957-013-0515-1. [42] Z. Y. Wu, F. S. Bai, H. W. J. Lee and Y. J. Yang, A filled function method for constrained global optimization, J. Glob. Optim., 39 (2007), 495-507.  doi: 10.1007/s10898-007-9152-2. [43] Z. Y. Wu, D. Li and S. Zhang, Global descent methods for unconstrained global optimization, J. Glob. Optim., 50 (2011), 379-396.  doi: 10.1007/s10898-010-9587-8. [44] A. E. Xavier, Penalizacao Hiperbolica: Um Novo Metodo para Resolutato de Problemas de Otimizao, M. Sc. Thesis, COPPE–Federal University of Rio de Janeiro, 1982. [45] A. E. Xavier, The hyperbolic smoothing clustering method, Patt. Recog., 43 (2010), 731-737.  doi: 10.1016/j.patcog.2009.06.018. [46] A. E. Xavier and A. A. F. Oliveira, Optimal covering of plane domains by circles via hyperbolic smoothing, J. Glob. Optim., 31 (2005), 493-504.  doi: 10.1007/s10898-004-0737-8. [47] L. Xu, J. Lee and D. Skipper, More virtuous smoothing, SIAM J. Optim., 29 (2019) 1240–1259. doi: 10.1137/18M1172831. [48] Y. T. Xu, Y. Zhang and S. G. Wang, A modified tunneling function method for non-smooth global optimization and its application in artificial neural network, Appl. Math. Model., 39 (2015), 6438-6450.  doi: 10.1016/j.apm.2015.01.059. [49] Y. Yang and Y. Shang, A new filled function method for unconstrained global optimization, Appl. Math. Comput., 173 (2006), 501-512.  doi: 10.1016/j.amc.2005.04.046. [50] H. Yin, An adaptive smoothing method for continuous minimax problems, Asia-Pac. J. Oper. Res., 32 (2015), 1-19.  doi: 10.1142/S0217595915400011. [51] I. Zang, A smoothing out technique for min-max optimization, Math. Program., 19 (1980), 61-77.  doi: 10.1007/BF01581628. [52] L. S. Zhang, C. K. Ng, D. Li and W. W. Tian, A new filled function method for global optimization, J. Glob. Optim., 28 (2004), 17-43.  doi: 10.1023/B:JOGO.0000006653.60256.f6. [53] A. Zhigljavsky and A. Zilinskas, Stochastic Global Optimization, Springer, New York, 2008. [54] J. Zilinskas, Branch and bound with simplicial partitions for global optimization, Math. Model. Anal., 13 (2008), 145-159.  doi: 10.3846/1392-6292.2008.13.145-159.

Figures(3)

Tables(6)