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

Nurullah Yilmaz; Ahmet Sahiner

doi:10.3934/naco.2020004

Article Contents

2020, Volume 10, Issue 3: 317-330. Doi: 10.3934/naco.2020004

This issue Previous Article On fractional quadratic optimization problem with two quadratic constraints Next Article

$ H_{\infty} $

observer-based control for large-scale systems with sparse observer communication network

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

Nurullah Yilmaz and
Ahmet Sahiner^,

Department of Mathematics, Suleyman Demirel University, Isparta, Turkey

^* Corresponding author: Ahmet Sahiner
^* Corresponding author: Ahmet Sahiner

Received: May 2019

Revised: October 2019

Published: June 2020

This study has been supported by the Teaching Staff Training Project Units of Suleyman Demirel University (OYP-05545-DR-13)

Abstract / Introduction Full Text(HTML) Figure(3) / Table(6) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

FullText(HTML)

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) $

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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} $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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} $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.