Skip to main content
SpringerLink
Log in

Solving Quantified Problems Using Interval Methods

  • Chapter
  • First Online:
Interval Methods for Solving Nonlinear Constraint Satisfaction, Optimization and Similar Problems

Part of the book series: Studies in Computational Intelligence ((SCI,volume 805))

  • 342 Accesses

Abstract

This chapter reviews three types of quantified problems that can be solved using interval methods: global optimization, seeking Pareto-sets of multicriteria problems and seeking game solutions. All these problems can be solved by instances of the B&BT algorithm; in all cases the algorithm has a significant second phase. Similarities and differences between the instances of the B&BT algorithm are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
eBook
USD 16.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Aumann, R.J.: Acceptable points in general cooperative games. In: A.W. Tuckar, R.D. Luce (eds.) Contributions to the Theory of Games IV. Princeton University Press (1959)

    Google Scholar 

  2. Barichard, V., Hao, J.K.: Population and interval constraint propagation algorithm. Lecture Notes in Computer Science, vol. 2632, pp. 88–101 (2003)

    Google Scholar 

  3. Berner, S.: New results on verified global optimization. Computing 57(4), 323–343 (1996)

    Google Scholar 

  4. Caprani, O., Godthaab, B., Madsen, K.: Use of a real-valued local minimum in parallel interval global optimization. Interval Comput. 2, 71–82 (1993)

    Google Scholar 

  5. Clark, K., Kay, S., Sefton, M.: When are Nash equilibria self-enforcing? An experimental analysis. Int. J. Game Theory 29(4), 495–515 (2001)

    Google Scholar 

  6. Fernandez, J., Toth, B.: Obtaining an outer approximation of the efficient set of nonlinear biobjective problems. J. Glob. Optim. 38, 315–331 (2007)

    Google Scholar 

  7. Goldsztejn, A., Domes, F., Chevalier, B.: First order rejection tests for multiple-objective optimization. J. Glob. Optim. 58(4), 653–672 (2014)

    Google Scholar 

  8. Hansen, E., Walster, W.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (2004)

    Google Scholar 

  9. Jaulin, L., Kieffer, M., Didrit, O., Walter, É.: Applied Interval Analysis. Springer, London (2001)

    Google Scholar 

  10. Jaulin, L., Walter, É.: Set inversion via interval analysis for nonlinear bounded-error estimation. Automatica 29(4), 1053–1064 (1993)

    Google Scholar 

  11. Kearfott, R.B.: An interval branch and bound algorithm for bound constrained optimization problems. J. Glob. Optim. 2(3), 259–280 (1992)

    Google Scholar 

  12. Kearfott, R.B.: Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht (1996)

    Google Scholar 

  13. Kearfott, R.B.: On proving existence of feasible points in equality constrained optimization problems. Math. Program. 83(1–3), 89–100 (1998)

    Google Scholar 

  14. Kubica, B.J.: Advanced interval tools for computing solutions of continuous games. Vychislennyie Tiehnologii (Computational Technologies) 23(1), 3–18 (2018)

    Google Scholar 

  15. Kubica, B.J., Malinowski, K.: An interval global optimization algorithm combining symbolic rewriting and componentwise Newton method applied to control a class of queueing systems. Reliab. Comput. 11(5), 393–411 (2005)

    Google Scholar 

  16. Kubica, B.J., Malinowski, K.: Optimization of performance of queuing systems with long-tailed service times. Prace Naukowe Politechniki Warszawskiej. Elektronika 156, 237–245 (2006)

    Google Scholar 

  17. Kubica, B.J., Niewiadomska-Szynkiewicz, E.: An improved interval global optimization algorithm and its application to price management problem. In: PARA 2006 Proceedings. Lecture Notes in Computer Science, vol. 4699, pp. 1055–1064 (2007)

    Google Scholar 

  18. Kubica, B.J., Woźniak, A.: Interval componentwise Newton operator in computing the Pareto-front of constrained multicriterial problems. In: Proceedings of KKA 2008 Conference (2008)

    Google Scholar 

  19. Kubica, B.J., Woźniak, A.: Interval methods for computing the Pareto-front of a multicriterial problem. In: PPAM 2007 Proceedings. Lecture Notes in Computer Science, vol. 4967, pp. 1382–1391 (2009)

    Google Scholar 

  20. Kubica, B.J., Woźniak, A.: An interval method for seeking the Nash equilibria of non-cooperative games. In: PPAM 2009 Proceedings. Lecture Notes in Computer Science, vol. 6068, pp. 446–455 (2010)

    Google Scholar 

  21. Kubica, B.J., Woźniak, A.: A multi-threaded interval algorithm for the Pareto-front computation in a multi-core environment. In: PARA 2008 Proceedings. Lecture Notes in Computer Science, vol. 6126/6127. Accepted for Publication (2010)

    Google Scholar 

  22. Kubica, B.J., Woźniak, A.: Optimization of the multi-threaded interval algorithm for the Pareto-set computation. J. Telecommun. Inf. Technol. 1, 70–75 (2010)

    Google Scholar 

  23. Kubica, B.J., Woźniak, A.: Applying an interval method for a four agent economy analysis. In: PPAM 2011 (9th International Conference on Parallel Processing and Applied Mathematics) Proceedings. Lecture Notes in Computer Science, vol. 7204, pp. 477–483 (2012)

    Google Scholar 

  24. Kubica, B.J., Woźniak, A.: Using the second-order information in Pareto-set computations of a multi-criteria problem. In: PARA 2010 Proceedings. Lecture Notes in Computer Science, vol. 7134, pp. 137–147 (2012)

    Google Scholar 

  25. Kubica, B.J., Woźniak, A.: Tuning the interval algorithm for seeking Pareto sets of multi-criteria problems. In: PARA 2012 Proceedings. Lecture Notes in Computer Science, vol. 7782, pp. 504–517 (2013)

    Google Scholar 

  26. Kubica, B.J., Woźniak, A.: Interval methods for computing strong Nash equilibria of continuous games. Decis. Mak. Manuf. Serv. 9(1), 63–78 (2015). SING10 Proceedings

    Google Scholar 

  27. Lera, D., Sergeyev, Y.D.: Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants. Commun. Nonlinear Sci. Numer. Simul. 23(1), 328–342 (2015)

    Google Scholar 

  28. Lyudvin, D.Y., Shary, S.P.: Testing implementations of PPS-methods for interval linear systems. Reliab. Comput. 19(2), 176–196 (2013). SCAN 2012 Proceedings

    Google Scholar 

  29. Martin, B.: Rigorous algorithms for nonlinear biobjective optimization. Ph.D. thesis, Université de Nantes (2014)

    Google Scholar 

  30. Martin, B., Goldsztejn, A., Granvilliers, L., Jermann, C.: Constraint propagation using dominance in interval branch & bound for nonlinear biobjective optimization. Eur. J. Oper. Res. 260(3), 934–948 (2017)

    Google Scholar 

  31. Martínez, J., Casado, L.G., García, I., Sergeyev, Y.D., Toth, B.: On an efficient use of gradient information for accelerating interval global optimization algorithms. Numer. Algorithms 37(1–4), 61–69 (2004)

    Google Scholar 

  32. Miettinen, K.: Nonlinear Multiobjective Optimization, vol. 12. Kluwer Academic Publishers, Dordrecht (1999)

    Google Scholar 

  33. Moore, R.E., Kearfott, R.B., Cloud, M.J.: Introduction to Interval Analysis. SIAM, Philadelphia (2009)

    Google Scholar 

  34. Nash, J.F.: Equilibrium points in \(n\)-person games. Proc. Natl. Assoc. Sci. 36, 48–49 (1950)

    Google Scholar 

  35. Pal, L.: Global optimization algorithms for bound constrained problems. Ph.D. thesis, University of Szeged (2010)

    Google Scholar 

  36. Ratz, D., Csendes, T.: On the selection of subdivision directions in interval branch-and-bound methods for global optimization. J. Glob. Optim. 7, 183–207 (1995)

    Google Scholar 

  37. Ruetsch, G.R.: An interval algorithm for multi-objective optimization. Struct. Multidiscip. Optim. 30(1), 27–37 (2005)

    Google Scholar 

  38. Shary, S.P.: A surprising approach in interval global optimization. Reliab. Comput. 7(6), 497–505 (2001)

    Google Scholar 

  39. Shary, S.P.: Randomized algorithms in interval global optimization. Numer. Anal. Appl. 1(4), 376–389 (2008)

    Google Scholar 

  40. Shary, S.P.: Finite-dimensional Interval Analysis. Institute of Computational Technologies, SB RAS, Novosibirsk (2013)

    Google Scholar 

  41. Toth, B., Casado, L.G.: Multi-dimensional pruning from the Baumann point in an interval global optimization algorithm. J. Glob. Optim. 38(2), 215–236 (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Informatics, Warsaw University of Life Sciences, Warsaw, Poland

    Bartłomiej Jacek Kubica

Authors
  1. Bartłomiej Jacek Kubica
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bartłomiej Jacek Kubica .

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Kubica, B.J. (2019). Solving Quantified Problems Using Interval Methods. In: Interval Methods for Solving Nonlinear Constraint Satisfaction, Optimization and Similar Problems. Studies in Computational Intelligence, vol 805. Springer, Cham. https://doi.org/10.1007/978-3-030-13795-3_6

Download citation

Publish with us

Policies and ethics

Search

Navigation