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

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.