IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v238y2014i2p497-504.html
   My bibliography  Save this article

Random sampling: Billiard Walk algorithm

Author

Listed:
  • Gryazina, Elena
  • Polyak, Boris

Abstract

Hit-and-Run is known to be one of the best random sampling algorithms, its mixing time is polynomial in dimension. However in practice, the number of steps required to obtain uniformly distributed samples is rather high. We propose a new random walk algorithm based on billiard trajectories. Numerical experiments demonstrate much faster convergence to the uniform distribution.

Suggested Citation

  • Gryazina, Elena & Polyak, Boris, 2014. "Random sampling: Billiard Walk algorithm," European Journal of Operational Research, Elsevier, vol. 238(2), pages 497-504.
    • Handle: RePEc:eee:ejores:v:238:y:2014:i:2:p:497-504
    DOI: 10.1016/j.ejor.2014.03.041
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171400280X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.03.041?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Boris Polyak & Elena Gryazina, 2011. "Randomized methods based on new Monte Carlo schemes for control and optimization," Annals of Operations Research, Springer, vol. 189(1), pages 343-356, September.
    2. Robert L. Smith, 1984. "Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions," Operations Research, INFORMS, vol. 32(6), pages 1296-1308, December.
    3. C. G. E. Boender & R. J. Caron & J. F. McDonald & A. H. G. Rinnooy Kan & H. E. Romeijn & R. L. Smith & J. Telgen & A. C. F. Vorst, 1991. "Shake-and-Bake Algorithms for Generating Uniform Points on the Boundary of Bounded Polyhedra," Operations Research, INFORMS, vol. 39(6), pages 945-954, December.
    4. Tervonen, Tommi & van Valkenhoef, Gert & Baştürk, Nalan & Postmus, Douwe, 2013. "Hit-And-Run enables efficient weight generation for simulation-based multiple criteria decision analysis," European Journal of Operational Research, Elsevier, vol. 224(3), pages 552-559.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Pavel Shcherbakov & Mingyue Ding & Ming Yuchi, 2021. "Random Sampling Many-Dimensional Sets Arising in Control," Mathematics, MDPI, vol. 9(5), pages 1-16, March.
    2. Xun Shen & Satoshi Ito, 2024. "Approximate Methods for Solving Chance-Constrained Linear Programs in Probability Measure Space," Journal of Optimization Theory and Applications, Springer, vol. 200(1), pages 150-177, January.
    3. Cyril Bachelard & Apostolos Chalkis & Vissarion Fisikopoulos & Elias Tsigaridas, 2023. "Randomized geometric tools for anomaly detection in stock markets," Post-Print hal-04223511, HAL.
    4. Cyril Bachelard & Apostolos Chalkis & Vissarion Fisikopoulos & Elias Tsigaridas, 2022. "Randomized geometric tools for anomaly detection in stock markets," Papers 2205.03852, arXiv.org, revised May 2022.
    5. Cyril Bachelard & Apostolos Chalkis & Vissarion Fisikopoulos & Elias Tsigaridas, 2024. "Randomized Control in Performance Analysis and Empirical Asset Pricing," Papers 2403.00009, arXiv.org.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Luca Anzilli & Silvio Giove, 2020. "Multi-criteria and medical diagnosis for application to health insurance systems: a general approach through non-additive measures," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 43(2), pages 559-582, December.
    2. Corrente, Salvatore & Figueira, José Rui & Greco, Salvatore, 2014. "The SMAA-PROMETHEE method," European Journal of Operational Research, Elsevier, vol. 239(2), pages 514-522.
    3. Luis V. Montiel & J. Eric Bickel, 2014. "A Generalized Sampling Approach for Multilinear Utility Functions Given Partial Preference Information," Decision Analysis, INFORMS, vol. 11(3), pages 147-170, September.
    4. van Valkenhoef, Gert & Tervonen, Tommi, 2016. "Entropy-optimal weight constraint elicitation with additive multi-attribute utility models," Omega, Elsevier, vol. 64(C), pages 1-12.
    5. Ru, Zice & Liu, Jiapeng & Kadziński, Miłosz & Liao, Xiuwu, 2023. "Probabilistic ordinal regression methods for multiple criteria sorting admitting certain and uncertain preferences," European Journal of Operational Research, Elsevier, vol. 311(2), pages 596-616.
    6. Serpil Sayin, 2003. "A Procedure to Find Discrete Representations of the Efficient Set with Specified Coverage Errors," Operations Research, INFORMS, vol. 51(3), pages 427-436, June.
    7. Aur'elien Hazan, 2016. "Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model," Papers 1601.00822, arXiv.org, revised Jan 2017.
    8. Silvia Angilella & Maria Rosaria Pappalardo, 2022. "Performance assessment of energy companies employing Hierarchy Stochastic Multi-Attribute Acceptability Analysis," Operational Research, Springer, vol. 22(1), pages 299-370, March.
    9. Costa, Ana Sara & Corrente, Salvatore & Greco, Salvatore & Figueira, José Rui & Borbinha, José, 2020. "A robust hierarchical nominal multicriteria classification method based on similarity and dissimilarity," European Journal of Operational Research, Elsevier, vol. 286(3), pages 986-1001.
    10. Francesca Abastante & Salvatore Corrente & Salvatore Greco & Isabella M. Lami & Beatrice Mecca, 2022. "The introduction of the SRF-II method to compare hypothesis of adaptive reuse for an iconic historical building," Operational Research, Springer, vol. 22(3), pages 2397-2436, July.
    11. Zhang, Zhiying & Liao, Huchang & Tang, Anbin, 2022. "Renewable energy portfolio optimization with public participation under uncertainty: A hybrid multi-attribute multi-objective decision-making method," Applied Energy, Elsevier, vol. 307(C).
    12. Angilella, Silvia & Corrente, Salvatore & Greco, Salvatore, 2015. "Stochastic multiobjective acceptability analysis for the Choquet integral preference model and the scale construction problem," European Journal of Operational Research, Elsevier, vol. 240(1), pages 172-182.
    13. Corrente, S. & Figueira, J.R. & Greco, S., 2021. "Pairwise comparison tables within the deck of cards method in multiple criteria decision aiding," European Journal of Operational Research, Elsevier, vol. 291(2), pages 738-756.
    14. Hazan, Aurélien, 2017. "Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 473(C), pages 589-602.
    15. Brunelli, Matteo & Corrente, Salvatore, 2024. "Modeling criteria and project interactions in portfolio decision analysis with the Choquet integral," Omega, Elsevier, vol. 126(C).
    16. Ciomek, Krzysztof & Kadziński, Miłosz & Tervonen, Tommi, 2017. "Heuristics for prioritizing pair-wise elicitation questions with additive multi-attribute value models," Omega, Elsevier, vol. 71(C), pages 27-45.
    17. Angilella, Silvia & Corrente, Salvatore & Greco, Salvatore & Słowiński, Roman, 2016. "Robust Ordinal Regression and Stochastic Multiobjective Acceptability Analysis in multiple criteria hierarchy process for the Choquet integral preference model," Omega, Elsevier, vol. 63(C), pages 154-169.
    18. van Valkenhoef, Gert & Tervonen, Tommi & Postmus, Douwe, 2014. "Notes on ‘Hit-And-Run enables efficient weight generation for simulation-based multiple criteria decision analysis’," European Journal of Operational Research, Elsevier, vol. 239(3), pages 865-867.
    19. Arcidiacono, Sally Giuseppe & Corrente, Salvatore & Greco, Salvatore, 2018. "GAIA-SMAA-PROMETHEE for a hierarchy of interacting criteria," European Journal of Operational Research, Elsevier, vol. 270(2), pages 606-624.
    20. A. B. Dieker & Santosh S. Vempala, 2015. "Stochastic Billiards for Sampling from the Boundary of a Convex Set," Mathematics of Operations Research, INFORMS, vol. 40(4), pages 888-901, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:238:y:2014:i:2:p:497-504. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.