nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Mathematically Rigorous Global Optimization and Fuzzy Optimization

A Brief Comparison of Paradigms, Methods, Similarities, and Differences

verfasst von : Ralph Baker Kearfott

Erschienen in: Black Box Optimization, Machine Learning, and No-Free Lunch Theorems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Mathematically rigorous global optimization and fuzzy optimization have different philosophical underpinnings, goals, and applications. However, some of the tools used in implementations are similar or identical. We review, compare and contrast basic ideas and applications behind these areas, referring to some of the work in the very large literature base.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Black-Box and Data-Driven Computation

Nächstes Kapitel Optimization Under Uncertainty Explains Empirical Success of Deep Learning Heuristics

Our interval details are more comprehensive, since fuzzy technology is such a large field, and since our primary expertise lies in interval analysis.

Typically, through control of the rounding mode, as specified in the IEEE 754 standard for floating point arithmetic [19].

Most desktops and laptops with appropriate programming language support, and some supercomputers, adhere to this standard.

First observed in [39, pp. 90–93] and treated by many since then.

The clustering effect is actually in common to most basic branch and bound algorithms, whether or not interval technology is used. However, its cause is closely related to the interval dependency problem.

But with complicated interpretation of results in general settings.

This is not to say that mathematical implications of particular procedures are not highly analyzed.

An interval \(\mathbb {X}\) corresponds to a fuzzy set

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-66515-9_7/478260_1_En_7_IEq59_HTML.gif

as in Definition 5 with \(\mathcal {A} = \mathbb {X}\) and μ _A(x) = 1 if \(x\in \mathbb {X}\), μ _A(x) = 0 otherwise.

However, data, and even statistics, can sometimes be used in the design of membership functions.

The terms “degree of truth” and “degree of belief” are common in the literature concerning handling uncertain knowledge. Also, “belief functions,” like membership functions, are defined. See [53], for example. We do not guarantee that our definition of “degree of truth” is the same as that of all others.

The results of (1) and (2) are sharp to within measurement and rounding errors but are sometimes increasingly un-sharp when operations are combined.

See [42], etc.

For details and generalizations, see a text on interval analysis, such as [4, 43], or our work [24].

Under mild conditions on the interval extension of F′ and for most ways of computing v.

Various researchers refer to similar lists as code lists (Rall), directed acyclic graphs (DAGs, Neumaier), etc. Although, for a given problem, such lists are not unique, they may be generated automatically with computer language compilers or by other means.

To obtain a possibly better upper bound on the global optimum, we replace φ in Problem 10 by − φ and then form and solve a relaxation of the resulting problem. However, for mathematical rigor, computing an upper bound on φ is more complicated than computing a lower bound over \(\mathcal {D}\), since the region \(\mathcal {D}\) may not contain a feasible point.

Two-variable relaxations correspond to multiplication; the literature describes various relaxations to these.

Another group previously published similar ideas, with a slightly different perspective; see [15].

Notably, quadratics, since quadratic programs have been extensively studied.

Derived from μ _X and f or designed some other way, to take account of perceived goodness of values of φ.

Ackleh, A.S., Allen, E.J., Kearfott, R.B., Seshaiyer, P.: Classical and Modern Numerical Analysis: Theory, Methods, and Practice. Taylor and Francis, Boca Raton (2009)CrossRef

Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs. I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137–1158 (1998)CrossRef

Alefeld, G., Herzberger, J.: Nullstelleneinschließung mit dem Newton-Verfahren ohne Invertierung von Intervallmatrizen. (German) [Including zeros of nonlinear equations by the Newton method without inverting interval matrices]. Numer. Math. 19(1), 56–64 (1972)

Alefeld, G., Herzberger, J.: Introduction to Interval Computations. Academic Press, New York (1983). Transl. by Jon G. Rokne from the original German ‘Einführung in die Intervallrechnung’

Androulakis, I.P., Maranas, C.D., Floudas, C.A.: αbb: a global optimization method for general constrained nonconvex problems. J. Global Optim. 7(4), 337–363 (1995). https://doi.org/10.1007/BF01099647

Anguelov, R.: The algebraic structure of spaces of intervals: Contribution of Svetoslav Markov to interval analysis and its applications. BIOMATH 2 (2014). https://doi.org/10.11145/j.biomath.2013.09.257

Barreto, G.A., Coelho, R. (eds.): Fuzzy Information Processing—37th Conference of the North American Fuzzy Information Processing Society, NAFIPS 2018, Fortaleza, Brazil, July 4–6, 2018, Proceedings, Communications in Computer and Information Science, vol. 831. Springer, Berlin (2018). https://doi.org/10.1007/978-3-319-95312-0

Berz, M., Makino, K.: Taylor models web page (2020). https://bt.pa.msu.edu/index_TaylorModels.htm. Accessed 30 March 2020

Berz, M., Makino, K., Kim, Y.K.: Long-term stability of the Tevatron by verified global optimization. Nucl. Instrum. Methods Phys. Res., Sect. A 558(1), 1–10 (2006). https://doi.org/10.1016/j.nima.2005.11.035. http://www.sciencedirect.com/science/article/pii/S0168900205020383. Proceedings of the 8th International Computational Accelerator Physics Conference

10.

Bessiere, C.: Chapter 3 - constraint propagation. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming. Foundations of Artificial Intelligence, vol. 2, pp. 29–83. Elsevier, Amsterdam (2006). https://doi.org/10.1016/S1574-6526(06)80007-6. http://www.sciencedirect.com/science/article/pii/S1574652606800076

11.

Corliss, G.F., Rall, L.B.: Bounding derivative ranges. In: Pardalos, P.M., Floudas, C.A. (eds.) Encyclopedia of Optimization. Kluwer, Dordrecht (1999)

12.

Du, K.: Cluster problem in global optimization using interval arithmetic. Ph.D. thesis, University of Southwestern Louisiana (1994)

13.

Du, K., Kearfott, R.B.: The cluster problem in global optimization: the univariate case. Comput. Suppl. 9, 117–127 (1992)MATH

14.

Dwyer, P.S.: Matrix inversion with the square root method. Technometrics 6, 197–213 (1964)MathSciNetMATHCrossRef

15.

Epperly, T.G.W., Pistikopoulos, E.N.: A reduced space branch and bound algorithm for global optimization. J. Global Optim. 11(3), 287–311 (1997)MathSciNetMATHCrossRef

16.

Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (2003)MATHCrossRef

17.

Hansen, E.R.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (1983)

18.

IEEE: 1788-2015—IEEE Standard for Interval Arithmetic. IEEE Computer Society Press, 1109 Spring Street, Suite 300, Silver Spring (2015). https://doi.org/10.1109/IEEESTD.2015.7140721. http://ieeexplore.ieee.org/servlet/opac?punumber=7140719. Approved 11 June 2015 by IEEE-SA Standards Board. http://ieeexplore.ieee.org/servlet/opac?punumber=7140719

19.

IEEE Task P754: IEEE 754-2008, Standard for Floating-Point Arithmetic. IEEE, New York, NY, USA (2008). https://doi.org/10.1109/IEEESTD.2008.4610935. http://en.wikipedia.org/wiki/IEEE_754-2008; http://ieeexplore.ieee.org/servlet/opac?punumber=4610933

20.

Jaulin, L., Keiffer, M., Didrit, O., Walter, E.: Applied Interval Analysis. SIAM, Philadelphia (2001)CrossRef

21.

Karhbet, S., Kearfott, R.B.: Range bounds of functions over simplices, for branch and bound algorithms. Reliab. Comput. 25, 53–73 (2017). Special volume containing refereed papers from SCAN 2016, guest editors Vladik Kreinovich and Warwick Tucker

22.

Kearfott, R.B.: Preconditioners for the interval Gauss–Seidel method. SIAM J. Numer. Anal. 27(3), 804–822 (1990). https://doi.org/10.1137/0727047 MathSciNetMATHCrossRef

23.

Kearfott, R.B.: Decomposition of arithmetic expressions to improve the behavior of interval iteration for nonlinear systems. Computing 47(2), 169–191 (1991)MathSciNetMATHCrossRef

24.

Kearfott, R.B.: Rigorous Global Search: Continuous Problems. No. 13 in Nonconvex optimization and its applications. Kluwer Academic Publishers, Dordrecht (1996)

25.

Kearfott, R.B.: GlobSol User Guide. Optim. Methods Softw. 24(4–5), 687–708 (2009)MathSciNetMATHCrossRef

26.

Kearfott, R.B.: Erratum: Validated linear relaxations and preprocessing: some experiments. SIAM J. Optim. 21(1), 415–416 (2011)MathSciNetMATHCrossRef

27.

Kearfott, R.B., Batyrshin, I.Z., Reformat, M., Ceberio, M., Kreinovich, V. (eds.): Fuzzy Techniques: Theory and Applications - Proceedings of the 2019 Joint World Congress of the International Fuzzy Systems Association and the Annual Conference of the North American Fuzzy Information Processing Society IFSA/NAFIPS’2019 (Lafayette, Louisiana, USA, June 18–21, 2019). Advances in Intelligent Systems and Computing, vol. 1000. Springer, Berlin (2019). https://doi.org/10.1007/978-3-030-21920-8

28.

Kearfott, R.B., Castille, J.M., Tyagi, G.: Assessment of a non-adaptive deterministic global optimization algorithm for problems with low-dimensional non-convex subspaces. Optim. Methods Softw. 29(2), 430–441 (2014). https://doi.org/10.1080/10556788.2013.780058 MathSciNetMATHCrossRef

29.

Kearfott, R.B., Du, K.: The cluster problem in multivariate global optimization. J. Global Optim. 5, 253–265 (1994)MathSciNetMATHCrossRef

30.

Kearfott, R.B., Hongthong, S.: Validated linear relaxations and preprocessing: some experiments. SIAM J. Optim. 16(2), 418–433 (2005). https://doi.org/10.1137/030602186. http://epubs.siam.org/sam-bin/dbq/article/60218

31.

Kearfott, R.B., Hu, C.Y., Novoa III, M.: A review of preconditioners for the interval Gauss–Seidel method. Interval Comput. 1(1), 59–85 (1991). http://interval.louisiana.edu/reliable-computing-journal/1991/interval-computations-1991-1-pp-59-85.pdf MathSciNetMATH

32.

Kearfott, R.B., Muniswamy, S., Wang, Y., Li, X., Wang, Q.: On smooth reformulations and direct non-smooth computations in global optimization for minimax problems. J. Global Optim. 57(4), 1091–1111 (2013)MathSciNetMATHCrossRef

33.

Kreinovich, V.: Relations between interval and soft computing. In: Hu, C., Kearfott, R.B., de Korvin, A. (eds.) Knowledge Processing with Interval and Soft Computing, Advanced Information and Knowledge Processing, pp. 75–97. Springer, Berlin (2008). https://doi.org/10.1007/BFb0085718 CrossRef

34.

Liu, D.: A Bernstein-polynomial-based branch-and-bound algorithm for polynomial optimization over simplexes. Ph.D. thesis, Department of Mathematics, University of Louisiana, Lafayette, LA 70504-1010 USA (2021). (work in progress)

35.

Makino, K., Berz, M.: Efficient control of the dependency problem based on Taylor model methods. Reliab. Comput. 5(1), 3–12 (1999)MathSciNetMATHCrossRef

36.

McCormick, G.P.: Converting general nonlinear programming problems to separable nonlinear programming problems. Tech. Rep. T-267, George Washington University, Washington (1972)

37.

McCormick, G.P.: Computability of global solutions to factorable nonconvex programs. Math. Prog. 10(2), 147–175 (1976)MATHCrossRef

38.

Messine, F.: Deterministic global optimization using interval constraint propagation techniques. RAIRO-Oper. Res. 38(4), 277–293 (2004). https://doi.org/10.1051/ro:2004026 MathSciNetMATHCrossRef

39.

Moore, R.E.: Interval arithmetic and automatic error analysis in digital computing. Ph.D. Dissertation, Department of Mathematics, Stanford University, Stanford, CA, USA (1962). http://interval.louisiana.edu/Moores_early_papers/disert.pdf. Also published as Applied Mathematics and Statistics Laboratories Technical Report No. 25

40.

Moore, R.E.: Interval analysis. Prentice-Hall, Upper Saddle River (1966)MATH

41.

Moore, R.E.: Methods and Applications of Interval Analysis. SIAM, Philadelphia (1979)MATHCrossRef

42.

Moore, R.E., Kearfott, R.B., Cloud, M.J.: Introduction to Interval Analysis. SIAM, Philadelphia (2009). http://www.loc.gov/catdir/enhancements/fy0906/2008042348-b.html; http://www.loc.gov/catdir/enhancements/fy0906/2008042348-d.html; http://www.loc.gov/catdir/enhancements/fy0906/2008042348-t.html

43.

Neumaier, A.: Interval Methods for Systems of Equations. Encyclopedia of Mathematics and Its Applications, vol. 37. Cambridge University Press, Cambridge (1990)

44.

Neumaier, A.: Complete search in continuous global optimization and constraint satisfaction. In: Iserles, A. (ed.) Acta Numerica 2004, pp. 271–369. Cambridge University Press, Cambridge (2004)CrossRef

45.

Paulavčius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, Berlin (2014). https://doi.org/10.1007/978-1-4614-9093-7

46.

Paulavičius, R., Žilinskas, J.: Simplicial global optimization. J. Global Optim. 60(4), 801–802 (2014). http://EconPapers.repec.org/RePEc:spr:jglopt:v:60:y:2014:i:4:p:801-802 MATHCrossRef

47.

Ratschek, H., Rokne, J.G.: New Computer Methods for Global Optimization. Wiley, New York (1988)MATH

48.

Rump, S.M.: INTLAB–INTerval LABoratory. In: Csendes, T. (ed.) Developments in Reliable Computing: Papers Presented at the International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics, SCAN-98, in Szeged, Hungary, Reliable Computing, vol. 5(3), pp. 77–104. Kluwer Academic Publishers Group, Norwell and Dordrecht, (1999). http://www.ti3.tu-harburg.de/rump/intlab/ CrossRef

49.

Rump, S.M.: INTLAB—INTerval LABoratory (1999–2020). http://www.ti3.tu-harburg.de/rump/intlab/

50.

Rump, S.M., Kashiwagi, M.: Implementation and improvements of affine arithmetic. Nonlinear Theory and Its Applications, IEICE 6(3), 341–359 (2015). https://doi.org/10.1587/nolta.6.341 CrossRef

51.

Sahinidis, N.V.: BARON: A general purpose global optimization software package. J. Global Optim. 8(2), 201–205 (1996)MathSciNetMATHCrossRef

52.

Sahinidis, N.V.: BARON Wikipedia page (2020). https://en.wikipedia.org/wiki/BARON. Accessed 16 March 2020

53.

Smets, P.: The degree of belief in a fuzzy event. Inf. Sci. 25, 1–19 (1981)MathSciNetMATHCrossRef

54.

Stolfi, J., de Figueiredo, L.H.: An introduction to affine arithmetic. TEMA (São Carlos) 4(3), 297–312 (2003). https://doi.org/10.5540/tema.2003.04.03.0297. https://tema.sbmac.org.br/tema/article/view/352

55.

Sunaga, T.: Theory of interval algebra and its application to numerical analysis. RAAG Mem. 2, 29–46 (1958). http://www.cs.utep.edu/interval-comp/sunaga.pdf MATH

56.

Tang, J.F., Wang, D.W., Fung, R.Y.K., Yung, K.L.: Understanding of fuzzy optimization: Theories and methods. J. Syst. Sci. Complex. 17(1), 117 (2004). http://123.57.41.99/jweb_xtkxyfzx/EN/abstract/article_11437.shtml MathSciNetMATH

57.

Van Hentenryck, P.: Constraint Satisfaction in Logic Programming. MIT Press, Cambridge (1989)

58.

Van Hentenryck, P., McAllester, D., Kapur, D.: Solving polynomial systems using a branch and prune approach. SIAM J. Numer. Anal. 34(2), 797–827 (1997). https://doi.org/10.1137/S0036142995281504 MathSciNetMATHCrossRef

59.

Vellasco, M., Estevez, P. (eds.): 2018 IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2018, Rio de Janeiro, Brazil, July 8–13, 2018. IEEE, Piscataway (2018). http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=8466242

60.

Žilinskas, J., Bogle, D.: A survey of methods for the estimation ranges of functions using interval arithmetic. In: Models and Algorithms for Global Optimization: Essays Dedicated to Antanas Žilinskas on the Occasion of His 60th Birthday, pp. 97–108 (2007). https://doi.org/10.1007/978-0-387-36721-7_6

61.

Warmus, M.M.: Approximations and inequalities in the calculus of approximations. classification of approximate numbers. Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 9, 241–245 (1961). http://www.ippt.gov.pl/~zkulpa/quaphys/warmus.html MathSciNet

62.

Wikipedia: COPROD web page (2020). http://coprod.constraintsolving.com/. Accessed 17 March 2020

63.

Wikipedia: Interval arithmetic Wikipedia page (2020). https://en.wikipedia.org/wiki/Interval_arithmetic. Accessed 30 March 2020

64.

Young, R.C.: The algebra of many-valued quantities. Math. Ann. 104, 260–290 (1931)MathSciNetMATHCrossRef

65.

Zadeh, L.A.: Fuzzy sets. Inf. Control 8, 338–353 (1965)MATHCrossRef

66.

Žilinskas, J.: Branch and bound with simplicial partitions for global optimization. Math. Model. Anal. 13(1), 145–159 (2008). https://doi.org/10.3846/1392-6292.2008.13.145-159 MathSciNetMATHCrossRef

Titel: Mathematically Rigorous Global Optimization and Fuzzy Optimization
verfasst von: Ralph Baker Kearfott
Verlag: Springer International Publishing
Buch: Black Box Optimization, Machine Learning, and No-Free Lunch Theorems
Print ISBN: 978-3-030-66514-2

Electronic ISBN: 978-3-030-66515-9

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-66515-9_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner