IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i2p511-530.html
   My bibliography  Save this article

Sparse Solutions by a Quadratically Constrained ℓ q (0 < q < 1) Minimization Model

Author

Listed:
  • Shan Jiang

    (School of Management, Xiamen University, Xiamen 361005, China)

  • Shu-Cherng Fang

    (Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, North Carolina 27695)

  • Qingwei Jin

    (Department of Data Science and Engineering Management, School of Management, Zhejiang University, Hangzhou 310058, China)

Abstract

Finding sparse solutions to a system of equations and/or inequalities is an important topic in many application areas such as signal processing, statistical regression and nonparametric modeling. Various continuous relaxation models have been proposed and widely studied to deal with the discrete nature of the underlying problem. In this paper, we propose a quadratically constrained ℓ q (0 < q < 1) minimization model for finding sparse solutions to a quadratic system. We prove that solving the proposed model is strongly NP-hard. To tackle the computation difficulty, a first order necessary condition for local minimizers is derived. Various properties of the proposed model are studied for designing an active-set-based descent algorithm to find candidate solutions satisfying the proposed condition. In addition to providing a theoretical convergence proof, we conduct extensive computational experiments using synthetic and real-life data to validate the effectiveness of the proposed algorithm and to show the superior capability in finding sparse solutions of the proposed model compared with other known models in the literature. We also extend our results to a quadratically constrained ℓ q (0 < q < 1) minimization model with multiple convex quadratic constraints for further potential applications. Summary of Contribution: In this paper, we propose and study a quadratically constrained ℓ q minimization (0 < q < 1) model for finding sparse solutions to a quadratic system which has wide applications in sparse signal recovery, image processing and machine learning. The proposed quadratically constrained ℓ q minimization model extends the linearly constrained ℓ q and unconstrained ℓ 2 - ℓ q models. We study various properties of the proposed model in aim of designing an efficient algorithm. Especially, we propose an unrelaxed KKT condition for local/global minimizers. Followed by the properties studied, an active-set based descent algorithm is then proposed with its convergence proof being given. Extensive numerical experiments with synthetic and real-life Sparco datasets are conducted to show that the proposed algorithm works very effectively and efficiently. Its sparse recovery capability is superior to that of other known models in the literature.

Suggested Citation

  • Shan Jiang & Shu-Cherng Fang & Qingwei Jin, 2021. "Sparse Solutions by a Quadratically Constrained ℓ q (0 < q < 1) Minimization Model," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 511-530, May.
    • Handle: RePEc:inm:orijoc:v:33:y:2021:i:2:p:511-530
    DOI: 10.1287/ijoc.2020.1004
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.1004
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2020.1004?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. Vivek F. Farias & Srikanth Jagabathula & Devavrat Shah, 2013. "A Nonparametric Approach to Modeling Choice with Limited Data," Management Science, INFORMS, vol. 59(2), pages 305-322, December.
    2. Yan Li & Kristofer G. Reyes & Jorge Vazquez-Anderson & Yingfei Wang & Lydia M. Contreras & Warren B. Powell, 2018. "A Knowledge Gradient Policy for Sequencing Experiments to Identify the Structure of RNA Molecules Using a Sparse Additive Belief Model," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 750-767, November.
    3. Le Thi, H.A. & Pham Dinh, T. & Le, H.M. & Vo, X.T., 2015. "DC approximation approaches for sparse optimization," European Journal of Operational Research, Elsevier, vol. 244(1), pages 26-46.
    4. Han-Lin Li & Yao-Huei Huang & Shu-Cherng Fang, 2013. "A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment Problems," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 643-653, November.
    5. Kenneth J. Arrow & Leonid Hurwicz & Hirofumi Uzawa, 1961. "Constraint qualifications in maximization problems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 8(2), pages 175-191, June.
    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. Francisco Lozano & Jonathan Moreno, 2018. "¿Se comparte la misma idea al utilizar el término Neoclasicismo?," Revista Cuadernos de Economia, Universidad Nacional de Colombia, FCE, CID, vol. 37(73), February.
    2. Guang Li & Paat Rusmevichientong & Huseyin Topaloglu, 2015. "The d -Level Nested Logit Model: Assortment and Price Optimization Problems," Operations Research, INFORMS, vol. 63(2), pages 325-342, April.
    3. Zhen-Yu Chen & Xin-Li Liu & Li-Ping Yin, 2023. "Data-driven product configuration improvement and product line restructuring with text mining and multitask learning," Journal of Intelligent Manufacturing, Springer, vol. 34(4), pages 2043-2059, April.
    4. 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.
    5. Zhenzhen Yan & Karthik Natarajan & Chung Piaw Teo & Cong Cheng, 2022. "A Representative Consumer Model in Data-Driven Multiproduct Pricing Optimization," Management Science, INFORMS, vol. 68(8), pages 5798-5827, August.
    6. Ruxian Wang & Maqbool Dada & Ozge Sahin, 2019. "Pricing Ancillary Service Subscriptions," Management Science, INFORMS, vol. 65(10), pages 4712-4732, October.
    7. Donghun Lee, 2022. "Knowledge Gradient: Capturing Value of Information in Iterative Decisions under Uncertainty," Mathematics, MDPI, vol. 10(23), pages 1-20, November.
    8. Kameng Nip & Zhenbo Wang & Zizhuo Wang, 2021. "Assortment Optimization under a Single Transition Choice Model," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2122-2142, July.
    9. Barbier, Thibault & Anjos, Miguel F. & Cirinei, Fabien & Savard, Gilles, 2020. "Product-closing approximation for ranking-based choice network revenue management," European Journal of Operational Research, Elsevier, vol. 286(3), pages 1002-1017.
    10. Robin Bade, 1973. "Optimal Foreign Investment and International Trade," The Economic Record, The Economic Society of Australia, vol. 49(1), pages 62-75, March.
    11. Sanjay Dominik Jena & Andrea Lodi & Claudio Sole, 2021. "On the estimation of discrete choice models to capture irrational customer behaviors," Papers 2109.03882, arXiv.org.
    12. Paulo D. Waquil & THOMAS L. COX, 1995. "Spatial Equilibrium with Intermediate Products: Implementation and Validation in the Mercosur," Wisconsin-Madison Agricultural and Applied Economics Staff Papers 388, Wisconsin-Madison Agricultural and Applied Economics Department.
    13. Li, Han-Lin & Fang, Shu-Cherng & Huang, Yao-Huei & Nie, Tiantian, 2016. "An enhanced logarithmic method for signomial programming with discrete variables," European Journal of Operational Research, Elsevier, vol. 255(3), pages 922-934.
    14. Felipe Caro & Victor Martínez-de-Albéniz & Paat Rusmevichientong, 2014. "The Assortment Packing Problem: Multiperiod Assortment Planning for Short-Lived Products," Management Science, INFORMS, vol. 60(11), pages 2701-2721, November.
    15. Ningyuan Chen & Guillermo Gallego & Zhuodong Tang, 2019. "The Use of Binary Choice Forests to Model and Estimate Discrete Choices," Papers 1908.01109, arXiv.org, revised Apr 2024.
    16. Resul Aydemir & Mehmet Melih Değirmenci & Abdullah Bilgin, 2023. "Estimation of passenger sell-up rates in airline revenue management by considering the effect of fare class availability," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 22(6), pages 501-513, December.
    17. Antoine Désir & Vineet Goyal & Danny Segev & Chun Ye, 2020. "Constrained Assortment Optimization Under the Markov Chain–based Choice Model," Management Science, INFORMS, vol. 66(2), pages 698-721, February.
    18. Aydın Alptekinoğlu & John H. Semple, 2021. "Heteroscedastic Exponomial Choice," Operations Research, INFORMS, vol. 69(3), pages 841-858, May.
    19. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R, 2017. "On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization," Annals of Operations Research, Springer, vol. 258(2), pages 301-346, November.
    20. Hans Corsten & Michael Hopf & Benedikt Kasper & Clemens Thielen, 2018. "Assortment planning for multiple chain stores," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 875-912, 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:inm:orijoc:v:33:y:2021:i:2:p:511-530. 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.