Skip to main content
SpringerLink
Log in

Testing pseudoconvexity via interval computation

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

We study the problem of checking pseudoconvexity of a twice differentiable function on an interval domain. Based on several characterizations of pseudoconvexity of a real function, we propose sufficient conditions for verifying pseudoconvexity on a domain formed by a Cartesian product of real intervals. We carried out numerical experiments to show which methods perform well from two perspectives—the computational complexity and effectiveness of recognizing pseudoconvexity.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, \(\alpha \)BB, for general twice-differentiabe constrained NLPs-II. Implementation and computational results. Comput. Chem. Eng. 22(9), 1159–1179 (1998)

    Article  Google Scholar 

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

    Article  Google Scholar 

  3. Ahmadi, A.A., Olshevsky, A., Parrilo, P.A., Tsitsiklis, J.N.: NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137(1–2), 453–476 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  4. Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \(\alpha \)BB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7(4), 337–363 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  5. Avriel, M., Schaible, S.: Second order characterizations of pseudoconvex functions. Math. Program. 14(1), 170–185 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  6. Crouzeix, J.: On second order conditions for quasiconvexity. Math. Program. 18(1), 349–352 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  7. Crouzeix, J., Ferland, J.A.: Criteria for quasi-convexity and pseudo-convexity: relationships and comparisons. Math. Program. 23(1), 193–205 (1982)

    Article  MATH  Google Scholar 

  8. Crouzeix, J.P.: Characterizations of generalized convexity and generalized monotonicity: a survey. In: Crouzeix, J.P., Martinez-Legaz, J.E., Volle, M. (eds.) Generalized Convexity, Generalized Monotonicity: Recent Results, Nonconvex Optimization and Its Applications, vol. 27, pp. 237–256. Springer, Berlin (1998)

    Chapter  Google Scholar 

  9. Ferland, J.A.: Mathematical programming problems with quasi-convex objective functions. Math. Program. 3(1), 296–301 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  10. Ferland, J.A.: Matrix criteria for pseudo-convex functions in the class \(C^2\). Linear Algebra Appl. 21(1), 47–57 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  11. Floudas, C.A.: Deterministic Global Optimization: Theory, Methods and Applications (Nonconvex Optimization and its Applications), vol. 37. Kluwer, Dordrecht (2000)

    Google Scholar 

  12. Hadjisavvas, N., Komlósi, S., Schaible, S. (eds.): Handbook of Generalized Convexity and Generalized Monotonicity. Springer, New York (2005)

    MATH  Google Scholar 

  13. Hansen, E.R., Walster, G.W.: Global Optimization Using Interval Analysis, 2nd edn. Marcel Dekker, New York (2004)

    MATH  Google Scholar 

  14. Hendrix, E.M.T., Gazdag-Tóth, B.: Introduction to Nonlinear and Global Optimization, Optimization and Its Applications, vol. 37. Springer, New York (2010)

    Book  MATH  Google Scholar 

  15. Hertz, D.: The extreme eigenvalues and stability of real symmetric interval matrices. IEEE Trans. Automat. Contr. 37(4), 532–535 (1992)

    Article  MathSciNet  Google Scholar 

  16. Hladík, M.: On the efficient Gerschgorin inclusion usage in the global optimization \(\alpha \)BB method. J. Glob. Optim. 61(2), 235–253 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  17. Hladík, M.: An extension of the \(\alpha \)BB-type underestimation to linear parametric Hessian matrices. J. Glob. Optim. 64(2), 217–231 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  18. Hladík, M., Daney, D., Tsigaridas, E.: Bounds on real eigenvalues and singular values of interval matrices. SIAM J. Matrix Anal. Appl. 31(4), 2116–2129 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  19. Hladík, M., Daney, D., Tsigaridas, E.P.: Characterizing and approximating eigenvalue sets of symmetric interval matrices. Comput. Math. Appl. 62(8), 3152–3163 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Hladík, M., Daney, D., Tsigaridas, E.P.: A filtering method for the interval eigenvalue problem. Appl. Math. Comput. 217(12), 5236–5242 (2011)

    MathSciNet  MATH  Google Scholar 

  21. Kearfott, R.B.: Interval computations, rigour and non-rigour in deterministic continuous global optimization. Optim. Methods Softw. 26(2), 259–279 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kreinovich, V., Lakeyev, A., Rohn, J., Kahl, P.: Computational Complexity and Feasibility of Data Processing and Interval Computations. Kluwer, Dordrecht (1998)

    Book  MATH  Google Scholar 

  23. Mereau, P., Paquet, J.G.: Second order conditions for pseudo-convex functions. SIAM J. Appl. Math. 27, 131–137 (1974)

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

  25. Nemirovskii, A.: Several NP-hard problems arising in robust stability analysis. Math. Control Signals Syst. 6(2), 99–105 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  26. Neumaier, A.: Interval Methods for Systems of Equations. Cambridge University Press, Cambridge (1990)

    MATH  Google Scholar 

  27. Neumaier, A.: Complete search in continuous global optimization and constraint satisfaction. Acta Numer. 13, 271–369 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  28. Rohn, J.: Checking positive definiteness or stability of symmetric interval matrices is NP-hard. Comment. Math. Univ. Carol. 35(4), 795–797 (1994). http://uivtx.cs.cas.cz/~rohn/publist/74.pdf

  29. Rohn, J.: Positive definiteness and stability of interval matrices. SIAM J. Matrix Anal. Appl. 15(1), 175–184 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  30. Rohn, J.: Checking Properties of Interval Matrices. Technical report 686, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague (1996). http://hdl.handle.net/11104/0123221

  31. Rohn, J.: A Handbook of Results on Interval Linear Problems. Technical report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague (2012). http://www.nsc.ru/interval/Library/InteBooks/!handbook.pdf

  32. Rump, S.M.: INTLAB—INTerval LABoratory. In: Csendes, T. (ed.) Developments in Reliable Computing, pp. 77–104. Kluwer Academic Publishers, Dordrecht (1999). http://www.ti3.tu-harburg.de/rump/

  33. Skjäl, A., Westerlund, T.: New methods for calculating \(\alpha \)BB-type underestimators. J. Glob. Optim. 58(3), 411–427 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author was supported by the Czech Science Foundation Grant P402-13-10660S.

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, 118 00, Prague, Czech Republic

    Milan Hladík

Authors
  1. Milan Hladík
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Milan Hladík.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hladík, M. Testing pseudoconvexity via interval computation. J Glob Optim 71, 443–455 (2018). https://doi.org/10.1007/s10898-017-0537-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-017-0537-6

Keywords

Search

Navigation