IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v45y2020i1p86-98.html
   My bibliography  Save this article

Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube

Author

Listed:
  • Etienne de Klerk

    (Tilburg University, 5037 AB Tilburg, Netherlands; Delft University of Technology, 2600 AA Delft, Netherlands;)

  • Monique Laurent

    (Tilburg University, 5037 AB Tilburg, Netherlands; Centrum Wiskunde & Informatica (CWI), 1098 XG Amsterdam, Netherlands)

Abstract

We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre, and a related hierarchy by de Klerk, Hess, and Laurent. For polynomial optimization over the hypercube, we show a refined convergence analysis for the first hierarchy. We also show lower bounds on the convergence rate for both hierarchies on a class of examples. These lower bounds match the upper bounds and thus establish the true rate of convergence on these examples. Interestingly, these convergence rates are determined by the distribution of extremal zeroes of certain families of orthogonal polynomials.

Suggested Citation

  • Etienne de Klerk & Monique Laurent, 2020. "Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 86-98, February.
    • Handle: RePEc:inm:ormoor:v:45:y:2020:i:1:p:86-98
    DOI: 10.1287/moor.2018.0983
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2018.0983
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2018.0983?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
    ---><---

    References listed on IDEAS

    as
    1. de Klerk, Etienne & Laurent, Monique, 2018. "Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing," Other publications TiSEM 78f8f496-dc89-413e-864d-f, Tilburg University, School of Economics and Management.
    2. Etienne de Klerk & Jean B. Lasserre & Monique Laurent & Zhao Sun, 2017. "Bound-Constrained Polynomial Optimization Using Only Elementary Calculations," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 834-853, August.
    3. de Klerk, E. & Laurent, M., 2010. "Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube," Other publications TiSEM 619d9658-77df-4b5e-9868-0, Tilburg University, School of Economics and Management.
    4. Haemers, W.H., 1995. "Interlacing eigenvalues and graphs," Other publications TiSEM 35c08207-2c5c-4387-aaf5-2, Tilburg University, School of Economics and Management.
    5. Etienne de Klerk & Monique Laurent, 2018. "Comparison of Lasserre’s Measure-Based Bounds for Polynomial Optimization to Bounds Obtained by Simulated Annealing," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1317-1325, November.
    6. de Klerk, Etienne & Hess, Roxana & Laurent, Monique, 2017. "Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization," Other publications TiSEM 66281fb7-02b8-4d87-930b-0, Tilburg University, School of Economics and Management.
    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. Slot, Lucas & Laurent, Monique, 2023. "Sum-of-squares hierarchies for binary polynomial optimization," Other publications TiSEM 338b9ae7-ffde-4b57-a5ba-4, Tilburg University, School of Economics and Management.

    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. de Klerk, Etienne & Laurent, Monique, 2018. "Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube," Other publications TiSEM a939e3b3-0361-42c9-8263-0, Tilburg University, School of Economics and Management.
    2. de Klerk, Etienne & Laurent, Monique, 2019. "A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis," Other publications TiSEM d956492f-3e25-4dda-a5e2-e, Tilburg University, School of Economics and Management.
    3. Etienne de Klerk & Monique Laurent, 2018. "Comparison of Lasserre’s Measure-Based Bounds for Polynomial Optimization to Bounds Obtained by Simulated Annealing," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1317-1325, November.
    4. Riley Badenbroek & Etienne Klerk, 2022. "Simulated Annealing for Convex Optimization: Rigorous Complexity Analysis and Practical Perspectives," Journal of Optimization Theory and Applications, Springer, vol. 194(2), pages 465-491, August.
    5. de Klerk, Etienne & Badenbroek, Riley, 2022. "Simulated annealing with hit-and-run for convex optimization: complexity analysis and practical perspectives," Other publications TiSEM 323b4588-65e0-4889-a555-9, Tilburg University, School of Economics and Management.
    6. Kirschner, Felix & de Klerk, Etienne, 2023. "Construction of multivariate polynomial approximation kernels via semidefinite programming," Other publications TiSEM 9b1d01ec-074f-404f-a8d0-6, Tilburg University, School of Economics and Management.
    7. Jiang, Guisheng & Yu, Guidong & Sun, Wei & Ruan, Zheng, 2018. "The least eigenvalue of graphs whose complements have only two pendent vertices," Applied Mathematics and Computation, Elsevier, vol. 331(C), pages 112-119.
    8. van Dam, E.R. & Haemers, W.H., 1995. "A characterization of distance-regular graphs with diameter three," Research Memorandum FEW 695, Tilburg University, School of Economics and Management.
    9. Haemers, W.H., 1996. "Disconnected Vertex Sets and Equidistant Code Pairs," Other publications TiSEM 88f23503-c117-4689-876b-1, Tilburg University, School of Economics and Management.
    10. Haemers, W.H. & Spence, E., 2000. "The Pseudo-Geometric Graphs for Generalised Quadrangles of Order (3,t)," Other publications TiSEM 5ff99d9d-636d-43b2-80ef-c, Tilburg University, School of Economics and Management.
    11. Haemers, W.H. & Spence, E., 2001. "The pseudo-geometric graphs for generalized quadrangles of order (3,t)," Other publications TiSEM 792e7c74-c02a-4bd4-a2d2-5, Tilburg University, School of Economics and Management.
    12. Rosanna Grassi & Paolo Bartesaghi & Stefano Benati & Gian Paolo Clemente, 2021. "Multi-Attribute Community Detection in International Trade Network," Networks and Spatial Economics, Springer, vol. 21(3), pages 707-733, September.
    13. Bussemaker, F.C. & Haemers, W.H. & Spence, E., 1999. "The Search for Pseudo Orthogonal Latin Squares of Order Six," Other publications TiSEM eaa43e8f-0be1-4b54-a567-f, Tilburg University, School of Economics and Management.
    14. Haemers, W.H., 1997. "Disconnected vertex sets and equidistant code pairs," Other publications TiSEM 7e670383-93b5-4e6a-b9da-3, Tilburg University, School of Economics and Management.
    15. Brouwer, A.E. & Haemers, W.H., 2004. "Eigenvalues and Perfect Matchings," Other publications TiSEM 9283486e-34f6-4a28-9315-a, Tilburg University, School of Economics and Management.
    16. E. R. van Dam & R. Sotirov, 2015. "On Bounding the Bandwidth of Graphs with Symmetry," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 75-88, February.
    17. Shankar Bhamidi & Steven N. Evans & Arnab Sen, 2012. "Spectra of Large Random Trees," Journal of Theoretical Probability, Springer, vol. 25(3), pages 613-654, September.
    18. van Dam, E.R. & Haemers, W.H., 1998. "Graphs with constant mu and mu-bar," Other publications TiSEM 3cba5bf4-ad2f-465d-a9a2-a, Tilburg University, School of Economics and Management.
    19. Haemers, W.H., 1996. "Disconnected Vertex Sets and Equidistant Code Pairs," Research Memorandum 728, Tilburg University, School of Economics and Management.
    20. Monique Laurent & Zhao Sun, 2014. "Handelman’s hierarchy for the maximum stable set problem," Journal of Global Optimization, Springer, vol. 60(3), pages 393-423, November.

    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:inm:ormoor:v:45:y:2020:i:1:p:86-98. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.