Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Continuous relaxations for Constrained Maximum-Entropy Sampling

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1084))

Abstract

We consider a new nonlinear relaxation for the Constrained Maximum Entropy Sampling Problem — the problem of choosing thes × s principal submatrix with maximal determinant from a givenn × n positive definite matrix, subject to linear constraints. We implement a branch-and-bound algorithm for the problem, using the new relaxation. The performance on test problems is far superior to a previous implementation using an eigenvalue-based relaxation.

Visiting the Dept. of Management Sciences, University of Iowa, supported by a Research Fellowship from CNPq-Brasilia-Brazil.

Supported in part by NSF grant DMI-9401424.

Supported in part by NSF grant DMI-9401424 and by the U. K. Center for Computational Sciences.

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov and D. Sorensen (1992), LAPACKUsers' Guide. SIAM, Philadelphia.

    Google Scholar 

  2. K.M. Anstreicher and M. Pampa (1996), A long-step path following algorithm for semidefinite programming problems. Working paper, Dept. of Management Sciences, University of Iowa, Iowa City.

    Google Scholar 

  3. D. Blackwell (1951), Comparison of experiments. InProceedings of the 2nd Berkeley Symposium, 93–102, University of California Press, Berkeley.

    Google Scholar 

  4. L. Boltzmann (1877), Beziehung zwischen dem zweiten Haupstatz der Wärmetheorie und der Wahrscheinlichkeitsrechnung resp. den Sätzen über das Wärmegleichgewicht (Complexionen-Theorie).Wien Ber. 762, p. 373.

    Google Scholar 

  5. W.F. Caselton, L. Kan and J.V. Zidek (1991), Quality data network designs based on entropy. InStatistics in the Environmental and Earth Science, P. Guttorp and A. Waiden, eds., Griffin, London.

    Google Scholar 

  6. W.F. Caselton and J. Zidek (1984), Optimal monitoring network designs.Stat. Prob. Lett.2, 223–227.

    Article  Google Scholar 

  7. CPLEX Optimization, Inc. (1994).Using the CPLEXCallable Library.

    Google Scholar 

  8. D. den Hertog, C. Roos, and T. Terlaky (1992), On the classical logarithmic barrier method for a class of smooth convex programming problems.JOTA73, 1–25.

    Article  Google Scholar 

  9. V. Fedorov, S. Leonov, M. Antonovsky and S. Pitovranov (1987), The experimental design of an observation network: software and examples. WP-87-05, International Institute for Applied Systems Analysis, Laxenburg, Austria.

    Google Scholar 

  10. V. Fedorov and W. Mueller (1989), Comparison of two approaches in the optimal design of an observation network.Statistics20, 339–351.

    Google Scholar 

  11. A.V. Fiacco and G.P. McCormick (1968),Nonlinear Programming, Sequential Unconstrained Minimization Techniques. John Wiley, New York; reprinted asClassics in Applied Mathematics Vol. 4, SIAM, Philadelphia, 1990.

    Google Scholar 

  12. P. Guttorp, N.D. Le, P.D. Sampson and J.V. Zidek (1992), Using Entropy in the redesign of an environmental monitoring network. Technical Report #116, Department of Statistics, The University of British Columbia, Vancouver, British Columbia.

    Google Scholar 

  13. R.A. Horn and C.R. Johnson (1985),Matrix Analysis. Cambridge University Press, Cambridge.

    Google Scholar 

  14. C.-W. Ko, J. Lee, and M. Queyranne (1995), An exact algorithm for maximum entropy sampling.Operations Research43, 684–691.

    Google Scholar 

  15. J. Lee (1995), Constrained maximum-entropy sampling. Working paper, Dept. of Mathematics, University of Kentucky, Lexington, KY.

    Google Scholar 

  16. C.E. Shannon (1948), The mathematical theory of communication.Bell Systems Technical Journal27, 379–423, 623–656.

    Google Scholar 

  17. M.C. Shewry and H.P. Wynn (1987), Maximum entropy sampling.Journal of Applied Statistics46, 165–170.

    Google Scholar 

  18. S. Wu and J.V. Zidek (1992), An entropy based review of selected NADP/NTN network sites for 1983–86.Atmospheric Environment26A, 2089–2103.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Management Sciences, University of Iowa, 52242, Iowa City, IA

    Kurt M. Anstreicher

  2. Dept. of Systems Engineering and Computer Sciences, COPPE, Federal University of Rio de Janeiro, CP 68511, 21945, Rio de Janeiro, RJ, Brazil

    Marcia Fampa

  3. Dept. of Mathematics, University of Kentucky, 40506-0027, Lexington, KY

    Jon Lee & Joy Williams

Authors
  1. Kurt M. Anstreicher

    You can also search for this author inPubMed Google Scholar

  2. Marcia Fampa

    You can also search for this author inPubMed Google Scholar

  3. Jon Lee

    You can also search for this author inPubMed Google Scholar

  4. Joy Williams

    You can also search for this author inPubMed Google Scholar

Editor information

William H. Cunningham S. Thomas McCormick Maurice Queyranne

Rights and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Anstreicher, K.M., Fampa, M., Lee, J., Williams, J. (1996). Continuous relaxations for Constrained Maximum-Entropy Sampling. In: Cunningham, W.H., McCormick, S.T., Queyranne, M. (eds) Integer Programming and Combinatorial Optimization. IPCO 1996. Lecture Notes in Computer Science, vol 1084. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61310-2_18

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp