[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Maximum-entropy sampling and the Boolean quadric polytope

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

Abstract

We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean quadric polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the use of a relaxation of BQP that imposes semidefiniteness and a small number of equality constraints gives excellent bounds on many benchmark instances. These bounds can be further tightened by imposing additional inequality constraints that are valid for the BQP. Duality information associated with the BQP-based bounds can be used to fix variables to 0/1 values, and also as the basis for the implementation of a “strong branching” strategy. A branch-and-bound algorithm using the BQP-based bounds solves some benchmark instances of MESP to optimality for the first time.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. The CVX system for convex programming [6] recognizes concavity of the objective in (2), but unfortunately does not process the resulting problem efficiently even when the SDPT3 solver is available.

  2. Recall that in (3) we index the rows and colums of Y, \(\widehat{C}\) and S beginning with zero.

References

  1. Anstreicher, K., Lee, J.: A masked spectral bound for maximum-entropy sampling. mODa 7–Advances in Model-Oriented Design and Analysis. Contributions to Statistics, pp. 1–10. Physica, Heidelberg (2004)

    Google Scholar 

  2. Anstreicher, K.M., Fampa, M., Lee, J., Williams, J.: Continuous relaxations for constrained maximum-entropy sampling. Integer Programming and Combinatorial Optimization (Vancouver, BC, 1996). Lecture Notes in Computer Science, vol. 1084, pp. 234–248. Springer, Berlin (1996)

    Chapter  Google Scholar 

  3. Anstreicher, K.M., Fampa, M., Lee, J., Williams, J.: Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems. Math. Program. 85(2), 221–240 (1999)

    Article  MathSciNet  Google Scholar 

  4. Burer, S., Lee, J.: Solving maximum-entropy sampling problems using factored masks. Math. Program. Ser. B 109, 263–281 (2007)

    Article  MathSciNet  Google Scholar 

  5. Graham, A.: Kronecker Products and Matrix Calculus: with Applications. Ellis Horwood, London (1981)

    MATH  Google Scholar 

  6. Grant, M., Boyd, S.: CVX: Matlab Software for Disciplined Convex Programming, Version 2.1. http://cvxr.com/cvx (2014). Accessed 10 Apr 2018

  7. Guttorp, P., Le, N., Sampson, P., Zidek, J.: Using entropy in the redesign of an environmental monitoring network. Tech. Rep. 116, The Department of Statistics, The University of British Columbia (1992)

  8. Helmberg, C.: Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21(3), 952–969 (2000)

    Article  MathSciNet  Google Scholar 

  9. Hoffman, A., Lee, J., Williams, J.: New upper bounds for maximum-entropy sampling. In: mODa 6–Advances in Model-Oriented Design and Analysis (Puchberg/Schneeberg. 2001), Contributions to Statistics, pp. 143–153. Physica, Heidelberg (2001)

    Chapter  Google Scholar 

  10. Ko, C.W., Lee, J., Queyranne, M.: An exact algorithm for maximum entropy sampling. Oper. Res. 43(4), 684–691 (1995)

    Article  MathSciNet  Google Scholar 

  11. Lee, J.: Constrained maximum-entropy sampling. Oper. Res. 46(5), 655–664 (1998)

    Article  Google Scholar 

  12. Lee, J.: Semidefinite programming in experimental design. In: Saigal, R., Wolkowicz, H., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming, International Series in Operations Research and Management Science, vol. 27, pp. 528–532. Kluwer Acad. Publ, Boston (2000)

    Google Scholar 

  13. Lee, J.: Maximum-entropy sampling. In: El-Shaarawi, A.H., Piegorsch, W.W. (eds.) Encyclopedia of Environmetrics, vol. 3, pp. 1229–1234. Wiley, Hoboken (2001)

    Google Scholar 

  14. Lee, J., Williams, J.: A linear integer programming bound for maximum-entropy sampling. Math. Program. Ser. B 94(2–3), 247–256 (2003)

    Article  MathSciNet  Google Scholar 

  15. Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. Ser. B 45, 139–172 (1989)

    Article  MathSciNet  Google Scholar 

  16. Rendl, F., Rinaldi, G., Wiegele, A.: Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121(2), 307–335 (2010)

    Article  MathSciNet  Google Scholar 

  17. Sherali, H., Adams, W.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1998)

    MATH  Google Scholar 

  18. Shewry, M., Wynn, H.P.: Maximum entropy sampling. J. Appl. Stat. 46, 165–170 (1987)

    Article  Google Scholar 

  19. Toh, K.C., Todd, M.J., Tutuncu, R.H.: On the implementation and usage of SDPT3—a MATLAB software package for semidefinite-quadratic-linear programming, version 4.0. In: Anjos, M., Lasserre, J. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research and Management Science, vol. 166, pp. 715–754. Springer, Berlin (2012)

    Google Scholar 

  20. Vandenberghe, L., Boyd, S., Wu, S.P.: Determinant maximization with linear matrix inequality constraints. SIAM J. Matrix Anal. Appl. 19(2), 499–533 (1998)

    Article  MathSciNet  Google Scholar 

  21. Wu, S., Zidek, J.V.: An entropy based review of selected NADP/NTN network sites for 1983–86. Atmos. Environ. 26A, 2089–2103 (1992)

    Article  Google Scholar 

Download references

Acknowledgements

I am grateful to Jon Lee for several very valuable conversations on the topic of this paper, and to Sam Burer for providing details of the computational results from [4].

Author information

Authors and Affiliations

  1. Department of Management Sciences, University of Iowa, Iowa City, IA, 52242, USA

    Kurt M. Anstreicher

Authors
  1. Kurt M. Anstreicher
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kurt M. Anstreicher.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Anstreicher, K.M. Maximum-entropy sampling and the Boolean quadric polytope. J Glob Optim 72, 603–618 (2018). https://doi.org/10.1007/s10898-018-0662-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-018-0662-x

Keywords

Mathematics Subject Classification

Search

Navigation