IDEAS home Printed from https://ideas.repec.org/a/spr/cejnor/v26y2018i2d10.1007_s10100-017-0499-2.html
   My bibliography  Save this article

Building a completely positive factorization

Author

Listed:
  • Immanuel M. Bomze

    (University of Vienna)

Abstract

A symmetric matrix of order n is called completely positive if it has a symmetric factorization by means of a rectangular matrix with n columns and no negative entries (a so-called cp factorization), i.e., if it can be interpreted as a Gram matrix of n directions in the positive orthant of another Euclidean space of possibly different dimension. Finding this factor therefore amounts to angle packing and finding an appropriate embedding dimension. Neither the embedding dimension nor the directions may be unique, and so many cp factorizations of the same given matrix may coexist. Using a bordering approach, and building upon an already known cp factorization of a principal block, we establish sufficient conditions under which we can extend this cp factorization to the full matrix. Simulations show that the approach is promising also in higher dimensions.

Suggested Citation

  • Immanuel M. Bomze, 2018. "Building a completely positive factorization," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(2), pages 287-305, June.
    • Handle: RePEc:spr:cejnor:v:26:y:2018:i:2:d:10.1007_s10100-017-0499-2
    DOI: 10.1007/s10100-017-0499-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10100-017-0499-2
    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/s10100-017-0499-2?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. Walter J. Gutjahr, 2010. "Stochastic Search in Metaheuristics," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 573-597, Springer.
    2. Xin Chen & Jiming Peng, 2015. "New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 725-738, March.
    3. Karthik Natarajan & Chung Piaw Teo & Zhichao Zheng, 2011. "Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation," Operations Research, INFORMS, vol. 59(3), pages 713-728, June.
    4. Bomze, Immanuel M., 2012. "Copositive optimization – Recent developments and applications," European Journal of Operational Research, Elsevier, vol. 216(3), pages 509-520.
    5. Anwa Zhou & Jinyan Fan, 2015. "Interiors of completely positive cones," Journal of Global Optimization, Springer, vol. 63(4), pages 653-675, December.
    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. Immanuel Bomze & Werner Schachinger & Gabriele Uchida, 2012. "Think co(mpletely)positive ! Matrix properties, examples and a clustered bibliography on copositive optimization," Journal of Global Optimization, Springer, vol. 52(3), pages 423-445, March.
    2. Li, Xiaobo & Natarajan, Karthik & Teo, Chung-Piaw & Zheng, Zhichao, 2014. "Distributionally robust mixed integer linear programs: Persistency models with applications," European Journal of Operational Research, Elsevier, vol. 233(3), pages 459-473.
    3. Jinyan Fan & Anwa Zhou, 2016. "Computing the distance between the linear matrix pencil and the completely positive cone," Computational Optimization and Applications, Springer, vol. 64(3), pages 647-670, July.
    4. Xuan Wang & Jiawei Zhang, 2015. "Process Flexibility: A Distribution-Free Bound on the Performance of k -Chain," Operations Research, INFORMS, vol. 63(3), pages 555-571, June.
    5. Immanuel M. Bomze & Vaithilingam Jeyakumar & Guoyin Li, 2018. "Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations," Journal of Global Optimization, Springer, vol. 71(3), pages 551-569, July.
    6. Wong, Man Hong & Zhang, Shuzhong, 2014. "On distributional robust probability functions and their computations," European Journal of Operational Research, Elsevier, vol. 233(1), pages 23-33.
    7. Bomze, Immanuel M. & Gabl, Markus, 2023. "Optimization under uncertainty and risk: Quadratic and copositive approaches," European Journal of Operational Research, Elsevier, vol. 310(2), pages 449-476.
    8. Riley Badenbroek & Etienne de Klerk, 2022. "An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1115-1125, March.
    9. O. I. Kostyukova & T. V. Tchemisova, 2022. "On strong duality in linear copositive programming," Journal of Global Optimization, Springer, vol. 83(3), pages 457-480, July.
    10. Immanuel M. Bomze & Werner Schachinger & Reinhard Ullrich, 2018. "The Complexity of Simple Models—A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 651-674, May.
    11. Areesh Mittal & Can Gokalp & Grani A. Hanasusanto, 2020. "Robust Quadratic Programming with Mixed-Integer Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 201-218, April.
    12. Badenbroek, Riley & de Klerk, Etienne, 2020. "An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix," Other publications TiSEM 876ff1ab-036c-4635-9688-1, Tilburg University, School of Economics and Management.
    13. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    14. Immanuel Bomze & Markus Gabl, 2021. "Interplay of non-convex quadratically constrained problems with adjustable robust optimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(1), pages 115-151, February.
    15. Jean-Baptiste Hiriart-Urruty & Hai Le, 2013. "A variational approach of the rank function," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(2), pages 207-240, July.
    16. Jinyan Fan & Anwa Zhou, 2017. "A semidefinite algorithm for completely positive tensor decomposition," Computational Optimization and Applications, Springer, vol. 66(2), pages 267-283, March.
    17. Sarah Yini Gao & David Simchi-Levi & Chung-Piaw Teo & Zhenzhen Yan, 2019. "Disruption Risk Mitigation in Supply Chains: The Risk Exposure Index Revisited," Operations Research, INFORMS, vol. 67(3), pages 831-852, May.
    18. 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.
    19. Long He & Ho-Yin Mak & Ying Rong & Zuo-Jun Max Shen, 2017. "Service Region Design for Urban Electric Vehicle Sharing Systems," Manufacturing & Service Operations Management, INFORMS, vol. 19(2), pages 309-327, May.
    20. Zhijian Lai & Akiko Yoshise, 2022. "Completely positive factorization by a Riemannian smoothing method," Computational Optimization and Applications, Springer, vol. 83(3), pages 933-966, December.

    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:cejnor:v:26:y:2018:i:2:d:10.1007_s10100-017-0499-2. 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.