IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v201y2024i2d10.1007_s10957-024-02414-5.html
   My bibliography  Save this article

A Boosted-DCA with Power-Sum-DC Decomposition for Linearly Constrained Polynomial Programs

Author

Listed:
  • Hu Zhang

    (Shanghai Jiao Tong University)

  • Yi-Shuai Niu

    (Beijing Institute of Mathematical Sciences and Applications)

Abstract

This paper proposes a novel Difference-of-Convex (DC) decomposition for polynomials using a power-sum representation, achieved by solving a sparse linear system. We introduce the Boosted DCA with Exact Line Search ( $$\hbox {BDCA}_\text {e}$$ BDCA e ) for addressing linearly constrained polynomial programs within the DC framework. Notably, we demonstrate that the exact line search equates to determining the roots of a univariate polynomial in an interval, with coefficients being computed explicitly based on the power-sum DC decompositions. The subsequential convergence of $$\hbox {BDCA}_\text {e}$$ BDCA e to critical points is proven, and its convergence rate under the Kurdyka–Łojasiewicz property is established. To efficiently tackle the convex subproblems, we integrate the Fast Dual Proximal Gradient method by exploiting the separable block structure of the power-sum DC decompositions. We validate our approach through numerical experiments on the Mean–Variance–Skewness–Kurtosis portfolio optimization model and box-constrained polynomial optimization problems. Comparative analysis of $$\hbox {BDCA}_\text {e}$$ BDCA e against DCA, BDCA with Armijo line search, UDCA, and UBDCA with projective DC decomposition, alongside standard nonlinear optimization solvers FMINCON and FILTERSD, substantiates the efficiency of our proposed approach.

Suggested Citation

  • Hu Zhang & Yi-Shuai Niu, 2024. "A Boosted-DCA with Power-Sum-DC Decomposition for Linearly Constrained Polynomial Programs," Journal of Optimization Theory and Applications, Springer, vol. 201(2), pages 720-759, May.
  • Handle: RePEc:spr:joptap:v:201:y:2024:i:2:d:10.1007_s10957-024-02414-5
    DOI: 10.1007/s10957-024-02414-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-024-02414-5
    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/s10957-024-02414-5?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. Hoai Le Thi & Mahdi Moeini & Tao Pham Dinh & Joaquim Judice, 2012. "A DC programming approach for solving the symmetric Eigenvalue Complementarity Problem," Computational Optimization and Applications, Springer, vol. 51(3), pages 1097-1117, April.
    2. Pierre Frankel & Guillaume Garrigos & Juan Peypouquet, 2015. "Splitting Methods with Variable Metric for Kurdyka–Łojasiewicz Functions and General Convergence Rates," Journal of Optimization Theory and Applications, Springer, vol. 165(3), pages 874-900, June.
    3. Yisheng Song & Gaohang Yu, 2016. "Properties of Solution Set of Tensor Complementarity Problem," Journal of Optimization Theory and Applications, Springer, vol. 170(1), pages 85-96, July.
    4. 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.
    5. Tao Pham Dinh & Yi-Shuai Niu, 2011. "An efficient DC programming approach for portfolio decision with higher moments," Computational Optimization and Applications, Springer, vol. 50(3), pages 525-554, December.
    6. Carmo Brás & Gabriele Eichfelder & Joaquim Júdice, 2016. "Copositivity tests based on the linear complementarity problem," Computational Optimization and Applications, Springer, vol. 63(2), pages 461-493, March.
    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. Niu, Yi-Shuai & Júdice, Joaquim & Le Thi, Hoai An & Pham, Dinh Tao, 2019. "Improved dc programming approaches for solving the quadratic eigenvalue complementarity problem," Applied Mathematics and Computation, Elsevier, vol. 353(C), pages 95-113.
    2. Jie Wang & Shenglong Hu & Zheng-Hai Huang, 2018. "Solution Sets of Quadratic Complementarity Problems," Journal of Optimization Theory and Applications, Springer, vol. 176(1), pages 120-136, January.
    3. J. X. Cruz Neto & P. R. Oliveira & A. Soubeyran & J. C. O. Souza, 2020. "A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem," Annals of Operations Research, Springer, vol. 289(2), pages 313-339, June.
    4. 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.
    5. Shenglong Hu & Jie Wang & Zheng-Hai Huang, 2018. "Error Bounds for the Solution Sets of Quadratic Complementarity Problems," Journal of Optimization Theory and Applications, Springer, vol. 179(3), pages 983-1000, December.
    6. Zheng-Hai Huang & Yu-Fan Li & Yong Wang, 2023. "A fixed point iterative method for tensor complementarity problems with the implicit Z-tensors," Journal of Global Optimization, Springer, vol. 86(2), pages 495-520, June.
    7. Ge Li & Jicheng Li, 2023. "Improved Fixed Point Iterative Methods for Tensor Complementarity Problem," Journal of Optimization Theory and Applications, Springer, vol. 199(2), pages 787-804, November.
    8. Xue-Li Bai & Zheng-Hai Huang & Yong Wang, 2016. "Global Uniqueness and Solvability for Tensor Complementarity Problems," Journal of Optimization Theory and Applications, Springer, vol. 170(1), pages 72-84, July.
    9. Masoud Ahookhosh & Le Thi Khanh Hien & Nicolas Gillis & Panagiotis Patrinos, 2021. "A Block Inertial Bregman Proximal Algorithm for Nonsmooth Nonconvex Problems with Application to Symmetric Nonnegative Matrix Tri-Factorization," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 234-258, July.
    10. Ilyes Abid & Christian Urom & Jonathan Peillex & Majdi Karmani & Gideon Ndubuisi, 2025. "PGP for portfolio optimization: application to ESG index family," Annals of Operations Research, Springer, vol. 347(1), pages 405-417, April.
    11. Behzad Azmi & Marco Bernreuther, 2025. "On the forward–backward method with nonmonotone linesearch for infinite-dimensional nonsmooth nonconvex problems," Computational Optimization and Applications, Springer, vol. 91(3), pages 1263-1308, July.
    12. Orizon Pereira Ferreira & Yingchao Gao & Sándor Zoltán Németh & Petra Renáta Rigó, 2024. "Gradient projection method on the sphere, complementarity problems and copositivity," Journal of Global Optimization, Springer, vol. 90(1), pages 1-25, September.
    13. Rui Zhou & Daniel P. Palomar, 2020. "Solving High-Order Portfolios via Successive Convex Approximation Algorithms," Papers 2008.00863, arXiv.org.
    14. Darvay, Zsolt & Illés, Tibor & Rigó, Petra Renáta, 2022. "Predictor-corrector interior-point algorithm for P*(κ)-linear complementarity problems based on a new type of algebraic equivalent transformation technique," European Journal of Operational Research, Elsevier, vol. 298(1), pages 25-35.
    15. Hafner, Christian & Herwartz, Helmut, 2020. "Dynamic score driven independent component analysis," LIDAM Discussion Papers ISBA 2020031, Université catholique de Louvain, Institute of Statistics, Biostatistics and Actuarial Sciences (ISBA).
    16. Hoai An Thi & Thi Minh Tam Nguyen & Tao Pham Dinh, 2023. "On solving difference of convex functions programs with linear complementarity constraints," Computational Optimization and Applications, Springer, vol. 86(1), pages 163-197, September.
    17. Patrick Cheridito & Arnulf Jentzen & Florian Rossmannek, 2024. "Gradient Descent Provably Escapes Saddle Points in the Training of Shallow ReLU Networks," Journal of Optimization Theory and Applications, Springer, vol. 203(3), pages 2617-2648, December.
    18. Tong-tong Shang & Guo-ji Tang, 2023. "Structured tensor tuples to polynomial complementarity problems," Journal of Global Optimization, Springer, vol. 86(4), pages 867-883, August.
    19. Brás, Carmo P. & Fukushima, Masao & Iusem, Alfredo N. & Júdice, Joaquim J., 2015. "On the Quadratic Eigenvalue Complementarity Problem over a general convex cone," Applied Mathematics and Computation, Elsevier, vol. 271(C), pages 594-608.
    20. Franck Iutzeler & Jérôme Malick, 2018. "On the Proximal Gradient Algorithm with Alternated Inertia," Journal of Optimization Theory and Applications, Springer, vol. 176(3), pages 688-710, March.

    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:joptap:v:201:y:2024:i:2:d:10.1007_s10957-024-02414-5. 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.