IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i5p580-d513530.html
   My bibliography  Save this article

Random Sampling Many-Dimensional Sets Arising in Control

Author

Listed:
  • Pavel Shcherbakov

    (Institute of Control Sciences, Russian Academy of Science, 117997 Moscow, Russia)

  • Mingyue Ding

    (Department of Biomedical Engineering, Huazhong University of Science and Technology, Wuhan 430074, China)

  • Ming Yuchi

    (Department of Biomedical Engineering, Huazhong University of Science and Technology, Wuhan 430074, China)

Abstract

Various Monte Carlo techniques for random point generation over sets of interest are widely used in many areas of computational mathematics, optimization, data processing, etc. Whereas for regularly shaped sets such sampling is immediate to arrange, for nontrivial, implicitly specified domains these techniques are not easy to implement. We consider the so-called Hit-and-Run algorithm, a representative of the class of Markov chain Monte Carlo methods, which became popular in recent years. To perform random sampling over a set, this method requires only the knowledge of the intersection of a line through a point inside the set with the boundary of this set. This component of the Hit-and-Run procedure, known as boundary oracle, has to be performed quickly when applied to economy point representation of many-dimensional sets within the randomized approach to data mining, image reconstruction, control, optimization, etc. In this paper, we consider several vector and matrix sets typically encountered in control and specified by linear matrix inequalities. Closed-form solutions are proposed for finding the respective points of intersection, leading to efficient boundary oracles; they are generalized to robust formulations where the system matrices contain norm-bounded uncertainty.

Suggested Citation

  • Pavel Shcherbakov & Mingyue Ding & Ming Yuchi, 2021. "Random Sampling Many-Dimensional Sets Arising in Control," Mathematics, MDPI, vol. 9(5), pages 1-16, March.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:5:p:580-:d:513530
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/5/580/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/5/580/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Gryazina, Elena & Polyak, Boris, 2014. "Random sampling: Billiard Walk algorithm," European Journal of Operational Research, Elsevier, vol. 238(2), pages 497-504.
    3. Yurii Nesterov, 2018. "Lectures on Convex Optimization," Springer Optimization and Its Applications, Springer, edition 2, number 978-3-319-91578-4, September.
    4. Ravindran Kannan & Hariharan Narayanan, 2012. "Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming," Mathematics of Operations Research, INFORMS, vol. 37(1), pages 1-20, February.
    5. Boris Polyak & Pavel Shcherbakov, 2017. "Why Does Monte Carlo Fail to Work Properly in High-Dimensional Optimization Problems?," Journal of Optimization Theory and Applications, Springer, vol. 173(2), pages 612-627, May.
    Full references (including those not matched with items on IDEAS)

    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. Cyril Bachelard & Apostolos Chalkis & Vissarion Fisikopoulos & Elias Tsigaridas, 2024. "Randomized Control in Performance Analysis and Empirical Asset Pricing," Papers 2403.00009, arXiv.org.
    2. Cyril Bachelard & Apostolos Chalkis & Vissarion Fisikopoulos & Elias Tsigaridas, 2023. "Randomized geometric tools for anomaly detection in stock markets," Post-Print hal-04223511, HAL.
    3. 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.
    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. Shota Takahashi & Mituhiro Fukuda & Mirai Tanaka, 2022. "New Bregman proximal type algorithms for solving DC optimization problems," Computational Optimization and Applications, Springer, vol. 83(3), pages 893-931, December.
    6. 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.
    7. Corrente, Salvatore & Figueira, José Rui & Greco, Salvatore, 2014. "The SMAA-PROMETHEE method," European Journal of Operational Research, Elsevier, vol. 239(2), pages 514-522.
    8. Stephen Baumert & Archis Ghate & Seksan Kiatsupaibul & Yanfang Shen & Robert L. Smith & Zelda B. Zabinsky, 2009. "Discrete Hit-and-Run for Sampling Points from Arbitrary Distributions Over Subsets of Integer Hyperrectangles," Operations Research, INFORMS, vol. 57(3), pages 727-739, June.
    9. A. Scagliotti & P. Colli Franzone, 2022. "A piecewise conservative method for unconstrained convex optimization," Computational Optimization and Applications, Springer, vol. 81(1), pages 251-288, January.
    10. Xin Jiang & Lieven Vandenberghe, 2022. "Bregman primal–dual first-order method and application to sparse semidefinite programming," Computational Optimization and Applications, Springer, vol. 81(1), pages 127-159, January.
    11. 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.
    12. Dimitris Bertsimas & Allison O'Hair, 2013. "Learning Preferences Under Noise and Loss Aversion: An Optimization Approach," Operations Research, INFORMS, vol. 61(5), pages 1190-1199, October.
    13. Qi Fan & Jiaqiao Hu, 2018. "Surrogate-Based Promising Area Search for Lipschitz Continuous Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 677-693, November.
    14. Reuven Rubinstein, 2009. "The Gibbs Cloner for Combinatorial Optimization, Counting and Sampling," Methodology and Computing in Applied Probability, Springer, vol. 11(4), pages 491-549, December.
    15. Jing Voon Chen & Julia L. Higle & Michael Hintlian, 2018. "A systematic approach for examining the impact of calibration uncertainty in disease modeling," Computational Management Science, Springer, vol. 15(3), pages 541-561, October.
    16. Huiyi Cao & Kamil A. Khan, 2023. "General convex relaxations of implicit functions and inverse functions," Journal of Global Optimization, Springer, vol. 86(3), pages 545-572, July.
    17. 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.
    18. Francisco García Riesgo & Sergio Luis Suárez Gómez & Enrique Díez Alonso & Carlos González-Gutiérrez & Jesús Daniel Santos, 2021. "Fully Convolutional Approaches for Numerical Approximation of Turbulent Phases in Solar Adaptive Optics," Mathematics, MDPI, vol. 9(14), pages 1-20, July.
    19. Kiatsupaibul, Seksan & J. Hayter, Anthony & Liu, Wei, 2017. "Rank constrained distribution and moment computations," Computational Statistics & Data Analysis, Elsevier, vol. 105(C), pages 229-242.
    20. Liam Madden & Stephen Becker & Emiliano Dall’Anese, 2021. "Bounds for the Tracking Error of First-Order Online Optimization Methods," Journal of Optimization Theory and Applications, Springer, vol. 189(2), pages 437-457, May.

    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:gam:jmathe:v:9:y:2021:i:5:p:580-:d:513530. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.