IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v70y2018i1d10.1007_s10898-017-0594-x.html
   My bibliography  Save this article

Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications

Author

Listed:
  • Davood Hajinezhad

    (Iowa State University)

  • Qingjiang Shi

    (Nanjing University of Aeronautics and Astronautics)

Abstract

In this paper, we study a class of nonconvex nonsmooth optimization problems with bilinear constraints, which have wide applications in machine learning and signal processing. We propose an algorithm based on the alternating direction method of multipliers, and rigorously analyze its convergence properties (to the set of stationary solutions). To test the performance of the proposed method, we specialize it to the nonnegative matrix factorization problem and certain sparse principal component analysis problem. Extensive experiments on real and synthetic data sets have demonstrated the effectiveness and broad applicability of the proposed methods.

Suggested Citation

  • Davood Hajinezhad & Qingjiang Shi, 2018. "Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications," Journal of Global Optimization, Springer, vol. 70(1), pages 261-288, January.
    • Handle: RePEc:spr:jglopt:v:70:y:2018:i:1:d:10.1007_s10898-017-0594-x
    DOI: 10.1007/s10898-017-0594-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-017-0594-x
    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/s10898-017-0594-x?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. P. Tseng, 2001. "Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization," Journal of Optimization Theory and Applications, Springer, vol. 109(3), pages 475-494, June.
    2. Shen, Haipeng & Huang, Jianhua Z., 2008. "Sparse principal component analysis via regularized low rank matrix approximation," Journal of Multivariate Analysis, Elsevier, vol. 99(6), pages 1015-1034, July.
    3. Li, Baibing & Martin, Elaine B. & Morris, A. Julian, 2002. "On principal component analysis in L1," Computational Statistics & Data Analysis, Elsevier, vol. 40(3), pages 471-474, September.
    4. Hui Zou & Trevor Hastie, 2005. "Addendum: Regularization and variable selection via the elastic net," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 67(5), pages 768-768, November.
    5. Hui Zou & Trevor Hastie, 2005. "Regularization and variable selection via the elastic net," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 67(2), pages 301-320, April.
    6. J. N. R. Jeffers, 1967. "Two Case Studies in the Application of Principal Component Analysis," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 16(3), pages 225-236, November.
    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. Zhiqing Meng & Min Jiang & Rui Shen & Leiyan Xu & Chuangyin Dang, 2021. "An objective penalty function method for biconvex programming," Journal of Global Optimization, Springer, vol. 81(3), pages 599-620, November.
    2. Utsav Sadana & Erick Delage, 2023. "The Value of Randomized Strategies in Distributionally Robust Risk-Averse Network Interdiction Problems," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 216-232, January.
    3. Temadher A. Almaadeed & Saeid Ansary Karbasy & Maziar Salahi & Abdelouahed Hamdi, 2022. "On Indefinite Quadratic Optimization over the Intersection of Balls and Linear Constraints," Journal of Optimization Theory and Applications, Springer, vol. 194(1), pages 246-264, July.
    4. Dolgopolik, Maksim V., 2021. "The alternating direction method of multipliers for finding the distance between ellipsoids," Applied Mathematics and Computation, Elsevier, vol. 409(C).

    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. Amir Beck & Yakov Vaisbourd, 2016. "The Sparse Principal Component Analysis Problem: Optimality Conditions and Algorithms," Journal of Optimization Theory and Applications, Springer, vol. 170(1), pages 119-143, July.
    2. Shuichi Kawano, 2021. "Sparse principal component regression via singular value decomposition approach," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 15(3), pages 795-823, September.
    3. Rosember Guerra-Urzola & Niek C. Schipper & Anya Tonne & Klaas Sijtsma & Juan C. Vera & Katrijn Deun, 2023. "Sparsifying the least-squares approach to PCA: comparison of lasso and cardinality constraint," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 17(1), pages 269-286, March.
    4. Seong-Yun Hong & Seonggook Moon & Sang-Hyun Chi & Yoon-Jae Cho & Jeon-Young Kang, 2022. "Local Sparse Principal Component Analysis for Exploring the Spatial Distribution of Social Infrastructure," Land, MDPI, vol. 11(11), pages 1-16, November.
    5. Mitzi Cubilla-Montilla & Ana Belén Nieto-Librero & M. Purificación Galindo-Villardón & Carlos A. Torres-Cubilla, 2021. "Sparse HJ Biplot: A New Methodology via Elastic Net," Mathematics, MDPI, vol. 9(11), pages 1-15, June.
    6. Jung, Yoon Mo & Whang, Joyce Jiyoung & Yun, Sangwoon, 2020. "Sparse probabilistic K-means," Applied Mathematics and Computation, Elsevier, vol. 382(C).
    7. Thomas Despois & Catherine Doz, 2022. "Identifying and interpreting the factors in factor models via sparsity : Different approaches," Working Papers halshs-03626503, HAL.
    8. Thomas Despois & Catherine Doz, 2023. "Identifying and interpreting the factors in factor models via sparsity: Different approaches," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 38(4), pages 533-555, June.
    9. Nicholson, William B. & Matteson, David S. & Bien, Jacob, 2017. "VARX-L: Structured regularization for large vector autoregressions with exogenous variables," International Journal of Forecasting, Elsevier, vol. 33(3), pages 627-651.
    10. David Degras, 2021. "Sparse group fused lasso for model segmentation: a hybrid approach," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 15(3), pages 625-671, September.
    11. Mihee Lee & Haipeng Shen & Jianhua Z. Huang & J. S. Marron, 2010. "Biclustering via Sparse Singular Value Decomposition," Biometrics, The International Biometric Society, vol. 66(4), pages 1087-1095, December.
    12. Carrizosa, Emilio & Guerrero, Vanesa, 2014. "Biobjective sparse principal component analysis," Journal of Multivariate Analysis, Elsevier, vol. 132(C), pages 151-159.
    13. Anshul Verma & Orazio Angelini & Tiziana Di Matteo, 2019. "A new set of cluster driven composite development indicators," Papers 1911.11226, arXiv.org, revised Mar 2020.
    14. Petra P. Šimović & Claire Y. T. Chen & Edward W. Sun, 2023. "Classifying the Variety of Customers’ Online Engagement for Churn Prediction with a Mixed-Penalty Logistic Regression," Computational Economics, Springer;Society for Computational Economics, vol. 61(1), pages 451-485, January.
    15. Hyun Hak Kim, 2013. "Forecasting Macroeconomic Variables Using Data Dimension Reduction Methods: The Case of Korea," Working Papers 2013-26, Economic Research Institute, Bank of Korea.
    16. Nerea González-García & Ana Belén Nieto-Librero & Purificación Galindo-Villardón, 2023. "CenetBiplot: a new proposal of sparse and orthogonal biplots methods by means of elastic net CSVD," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 17(1), pages 5-19, March.
    17. Yanming Li & Bin Nan & Ji Zhu, 2015. "Multivariate sparse group lasso for the multivariate multiple linear regression with an arbitrary group structure," Biometrics, The International Biometric Society, vol. 71(2), pages 354-363, June.
    18. Murat Genç, 2022. "A new double-regularized regression using Liu and lasso regularization," Computational Statistics, Springer, vol. 37(1), pages 159-227, March.
    19. Petra Posedel v{S}imovi'c & Davor Horvatic & Edward W. Sun, 2021. "Classifying variety of customer's online engagement for churn prediction with mixed-penalty logistic regression," Papers 2105.07671, arXiv.org, revised Jul 2021.
    20. Michoel, Tom, 2016. "Natural coordinate descent algorithm for L1-penalised regression in generalised linear models," Computational Statistics & Data Analysis, Elsevier, vol. 97(C), pages 60-70.

    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:jglopt:v:70:y:2018:i:1:d:10.1007_s10898-017-0594-x. 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.