IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v205y2025i2d10.1007_s10957-025-02656-x.html
   My bibliography  Save this article

A Jacobian-Free Method for the Nearest Doubly Stochastic Matrix Problem

Author

Listed:
  • Jianghua Yin

    (Guangxi Minzu University)

  • Yaobiao Li

    (Guangxi Minzu University)

  • Chunming Tang

    (Guangxi University)

Abstract

In this paper, we consider the nearest doubly stochastic matrix problem, which encompasses many important real-world applications. Theoretically, we show that the problem under consideration can be equivalently reformulated as the system of nonsmooth monotone equations, the mapping of which is Lipschitz continuous. To the best of our knowledge, this is the first theoretical result, showing that the underlying mapping owns the Lipschitz continuity and monotonicity. Moreover, the scale of the system is significantly smaller than that of the KKT optimality conditions for the original problem. Based on a scaling memoryless DFP formula, a Jacobian-free method with a modified Armijo line search is proposed for solving such a system. By the aid of the Lipschitz continuity and monotonicity of the underlying mapping, the global convergence and iteration complexity for the proposed method are established. Importantly, we illustrate for the first time that the Armijo line search mentioned above is superior to the original one in terms of iteration complexity. This also opens the door to improve the iteration complexity of Jacobian-free methods by designing an appropriate line search. Furthermore, the local linear rate of convergence established in this paper is new compared with existing Jacobian-free methods for solving nonsmooth monotone equations. Finally, numerical results illustrating the practical behavior of the presented method are reported.

Suggested Citation

  • Jianghua Yin & Yaobiao Li & Chunming Tang, 2025. "A Jacobian-Free Method for the Nearest Doubly Stochastic Matrix Problem," Journal of Optimization Theory and Applications, Springer, vol. 205(2), pages 1-25, May.
    • Handle: RePEc:spr:joptap:v:205:y:2025:i:2:d:10.1007_s10957-025-02656-x
    DOI: 10.1007/s10957-025-02656-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-025-02656-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/s10957-025-02656-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. Henry Wolkowicz, 1994. "Measures for Symmetric Rank-One Updates," Mathematics of Operations Research, INFORMS, vol. 19(4), pages 815-830, November.
    2. Naomi Graham & Hao Hu & Jiyoung Im & Xinxin Li & Henry Wolkowicz, 2022. "A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2125-2143, July.
    3. Jiayun Rao & Na Huang, 2023. "A derivative-free scaling memoryless DFP method for solving large scale nonlinear monotone equations," Journal of Global Optimization, Springer, vol. 87(2), pages 641-677, November.
    4. Avinoam Perry, 1977. "A Class of Conjugate Gradient Algorithms with a Two-Step Variable Metric Memory," Discussion Papers 269, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    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. Lennart Sinjorgo & Renata Sotirov, 2024. "On Solving MAX-SAT Using Sum of Squares," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 417-433, March.
    2. M. Fatemi, 2016. "An Optimal Parameter for Dai–Liao Family of Conjugate Gradient Methods," Journal of Optimization Theory and Applications, Springer, vol. 169(2), pages 587-605, May.
    3. Hao Hu & Xinxin Li & Jiageng Wu, 2023. "A note on the SDP relaxation of the minimum cut problem," Journal of Global Optimization, Springer, vol. 87(2), pages 857-876, November.
    4. C. X. Kou & Y. H. Dai, 2015. "A Modified Self-Scaling Memoryless Broyden–Fletcher–Goldfarb–Shanno Method for Unconstrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 165(1), pages 209-224, April.
    5. Andrei, Neculai, 2010. "Accelerated scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization," European Journal of Operational Research, Elsevier, vol. 204(3), pages 410-420, August.
    6. Zexian Liu & Hongwei Liu & Yu-Hong Dai, 2020. "An improved Dai–Kou conjugate gradient algorithm for unconstrained optimization," Computational Optimization and Applications, Springer, vol. 75(1), pages 145-167, January.
    7. André Uschmajew & Bart Vandereycken, 2022. "A Note on the Optimal Convergence Rate of Descent Methods with Fixed Step Sizes for Smooth Strongly Convex Functions," Journal of Optimization Theory and Applications, Springer, vol. 194(1), pages 364-373, July.
    8. Jiayun Rao & Na Huang, 2023. "A derivative-free scaling memoryless DFP method for solving large scale nonlinear monotone equations," Journal of Global Optimization, Springer, vol. 87(2), pages 641-677, November.
    9. Johannes Brust & Jennifer B. Erway & Roummel F. Marcia, 2017. "On solving L-SR1 trust-region subproblems," Computational Optimization and Applications, Springer, vol. 66(2), pages 245-266, 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:205:y:2025:i:2:d:10.1007_s10957-025-02656-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.