IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v87y2018i1d10.1007_s00186-017-0608-y.html
   My bibliography  Save this article

Norm bounds and underestimators for unconstrained polynomial integer minimization

Author

Listed:
  • Sönke Behrends

    (University of Göttingen)

  • Ruth Hübner

    (University of Göttingen)

  • Anita Schöbel

    (University of Göttingen)

Abstract

We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.

Suggested Citation

  • Sönke Behrends & Ruth Hübner & Anita Schöbel, 2018. "Norm bounds and underestimators for unconstrained polynomial integer minimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 87(1), pages 73-107, February.
    • Handle: RePEc:spr:mathme:v:87:y:2018:i:1:d:10.1007_s00186-017-0608-y
    DOI: 10.1007/s00186-017-0608-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00186-017-0608-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00186-017-0608-y?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. NESTEROV, Yu., 2000. "Squared functional systems and optimization problems," LIDAM Reprints CORE 1472, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. R. C. Jeroslow, 1973. "There Cannot be any Algorithm for Integer Programming with Quadratic Constraints," Operations Research, INFORMS, vol. 21(1), pages 221-224, February.
    3. Omprakash K. Gupta & A. Ravindran, 1985. "Branch and Bound Experiments in Convex Nonlinear Integer Programming," Management Science, INFORMS, vol. 31(12), pages 1533-1546, December.
    4. Lawrence J. Watters, 1967. "Letter to the Editor—Reduction of Integer Polynomial Programming Problems to Zero-One Linear Programming Problems," Operations Research, INFORMS, vol. 15(6), pages 1171-1174, December.
    5. Jesús A. De Loera & Raymond Hemmecke & Matthias Köppe & Robert Weismantel, 2006. "Integer Polynomial Optimization in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 147-153, February.
    6. Laurent, M., 2009. "Sums of squares, moment matrices and optimization over polynomials," Other publications TiSEM 9fef820b-69d2-43f2-a501-e, Tilburg University, School of Economics and Management.
    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. Meng-Meng Zheng & Zheng-Hai Huang & Sheng-Long Hu, 2022. "Unconstrained minimization of block-circulant polynomials via semidefinite program in third-order tensor space," Journal of Global Optimization, Springer, vol. 84(2), pages 415-440, October.
    2. Sönke Behrends & Anita Schöbel, 2020. "Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares," Journal of Optimization Theory and Applications, Springer, vol. 186(3), pages 911-935, September.
    3. Hübner, Ruth & Schöbel, Anita, 2014. "When is rounding allowed in integer nonlinear optimization?," European Journal of Operational Research, Elsevier, vol. 237(2), pages 404-410.
    4. Claudia D’Ambrosio & Andrea Lodi, 2013. "Mixed integer nonlinear programming tools: an updated practical overview," Annals of Operations Research, Springer, vol. 204(1), pages 301-320, April.
    5. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.
    6. Buchheim, Christoph & Crama, Yves & Rodríguez-Heck, Elisabeth, 2019. "Berge-acyclic multilinear 0–1 optimization problems," European Journal of Operational Research, Elsevier, vol. 273(1), pages 102-107.
    7. Hamidur Rahman & Ashutosh Mahajan, 2020. "On the facet defining inequalities of the mixed-integer bilinear covering set," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(3), pages 545-575, December.
    8. Xiao Wang & Xinzhen Zhang & Guangming Zhou, 2020. "SDP relaxation algorithms for $$\mathbf {P}(\mathbf {P}_0)$$P(P0)-tensor detection," Computational Optimization and Applications, Springer, vol. 75(3), pages 739-752, April.
    9. Jenny Carolina Saldana Cortés, 2011. "Programación semidefinida aplicada a problemas de cantidad económica de pedido," Documentos CEDE 8735, Universidad de los Andes, Facultad de Economía, CEDE.
    10. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.
    11. Laurent, Monique & Vargas, Luis Felipe, 2022. "Finite convergence of sum-of-squares hierarchies for the stability number of a graph," Other publications TiSEM 3998b864-7504-4cf4-bc1d-f, Tilburg University, School of Economics and Management.
    12. Wang, Wei & Xu, Huifu & Ma, Tiejun, 2023. "Optimal scenario-dependent multivariate shortfall risk measure and its application in risk capital allocation," European Journal of Operational Research, Elsevier, vol. 306(1), pages 322-347.
    13. Polyxeni-Margarita Kleniati & Panos Parpas & Berç Rustem, 2010. "Partitioning procedure for polynomial optimization," Journal of Global Optimization, Springer, vol. 48(4), pages 549-567, December.
    14. Laurent, M. & Rostalski, P., 2012. "The approach of moments for polynomial equations," Other publications TiSEM f08f3cd2-b83e-4bf1-9322-a, Tilburg University, School of Economics and Management.
    15. Kato, Naohiro & Kuriki, Satoshi, 2013. "Likelihood ratio tests for positivity in polynomial regressions," Journal of Multivariate Analysis, Elsevier, vol. 115(C), pages 334-346.
    16. Jie Wang & Victor Magron, 2021. "Exploiting term sparsity in noncommutative polynomial optimization," Computational Optimization and Applications, Springer, vol. 80(2), pages 483-521, November.
    17. Tomohiko Mizutani & Makoto Yamashita, 2013. "Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables," Journal of Global Optimization, Springer, vol. 56(3), pages 1073-1100, July.
    18. Sturm, J.F. & Zhang, S., 2001. "On Cones of Nonnegative Quadratic Functions," Discussion Paper 2001-26, Tilburg University, Center for Economic Research.
    19. Marcia Fampa & Jon Lee & Wendel Melo, 2016. "A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space," Computational Optimization and Applications, Springer, vol. 65(1), pages 47-71, September.
    20. Fook Wai Kong & Polyxeni-Margarita Kleniati & Berç Rustem, 2012. "Computation of Correlated Equilibrium with Global-Optimal Expected Social Welfare," Journal of Optimization Theory and Applications, Springer, vol. 153(1), pages 237-261, April.

    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:spr:mathme:v:87:y:2018:i:1:d:10.1007_s00186-017-0608-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.