We study decentralized smooth optimization problems over compact submanifolds.Recasting it as a composite optimization problem,we propose a decentralized Douglas-Rachford splitting algorithm(DDRS).When the proximal op...We study decentralized smooth optimization problems over compact submanifolds.Recasting it as a composite optimization problem,we propose a decentralized Douglas-Rachford splitting algorithm(DDRS).When the proximal operator of the local loss func-tion does not have a closed-form solution,an inexact version of DDRS(iDDRS),is also presented.Both algorithms rely on careful integration of the nonconvex Douglas-Rachford splitting algorithm with gradient tracking and manifold optimization.We show that our DDRS and iDDRS achieve the convergence rate of O(1/k).The main challenge in the proof is how to handle the nonconvexity of the manifold constraint.To address this issue,we utilize the concept of proximal smoothness for compact submanifolds.This ensures that the projection onto the submanifold exhibits convexity-like properties,which allows us to control the consensus error across agents.Numerical experiments on the principal component analysis are conducted to demonstrate the effectiveness of our decentralized DRS compared with the state-of-the-art ones.展开更多
The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a t...The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.展开更多
The method of recovering a low-rank matrix with an unknown fraction whose entries are arbitrarily corrupted is known as the robust principal component analysis （RPCA）. This RPCA problem, under some conditions, can b...The method of recovering a low-rank matrix with an unknown fraction whose entries are arbitrarily corrupted is known as the robust principal component analysis （RPCA）. This RPCA problem, under some conditions, can be exactly solved via convex optimization by minimizing a combination of the nuclear norm and the 11 norm. In this paper, an algorithm based on the Douglas-Rachford splitting method is proposed for solving the RPCA problem. First, the convex optimization problem is solved by canceling the constraint of the variables, and ~hen the proximity operators of the objective function are computed alternately. The new algorithm can exactly recover the low-rank and sparse components simultaneously, and it is proved to be convergent. Numerical simulations demonstrate the practical utility of the proposed algorithm.展开更多
In this paper,we present a novel Douglas-Rachford-splitting-based path following(DRS-PF)method that rapidly obtains the solution of linear programming(LP)with high accuracy.It originates from the fixed-point mapping a...In this paper,we present a novel Douglas-Rachford-splitting-based path following(DRS-PF)method that rapidly obtains the solution of linear programming(LP)with high accuracy.It originates from the fixed-point mapping associated with DRS on the log-barrier penalized LP.A path-following scheme is then proposed to simultaneously update the iterates and the penalty parameter for accelerating the overall procedure.Its global convergence towards an optimal solution to the original problem is established under mild assumptions.Numerical experiments show that DRS-PF outperforms the simplex and interior point methods implemented in the academic software(CLP,HiGHS,etc.)in terms of the geometric mean of the running time on a few typical benchmark data sets.In some cases,it is even reasonably competitive to the interior point method implemented in Gurobi,one of the most powerful software for LP.展开更多
文摘We study decentralized smooth optimization problems over compact submanifolds.Recasting it as a composite optimization problem,we propose a decentralized Douglas-Rachford splitting algorithm(DDRS).When the proximal operator of the local loss func-tion does not have a closed-form solution,an inexact version of DDRS(iDDRS),is also presented.Both algorithms rely on careful integration of the nonconvex Douglas-Rachford splitting algorithm with gradient tracking and manifold optimization.We show that our DDRS and iDDRS achieve the convergence rate of O(1/k).The main challenge in the proof is how to handle the nonconvexity of the manifold constraint.To address this issue,we utilize the concept of proximal smoothness for compact submanifolds.This ensures that the projection onto the submanifold exhibits convexity-like properties,which allows us to control the consensus error across agents.Numerical experiments on the principal component analysis are conducted to demonstrate the effectiveness of our decentralized DRS compared with the state-of-the-art ones.
基金Supported by the National Natural Science Foundation of China(Grant Nos.12061045,12061046,11661056,11771198,11771347,91730306,41390454,11401293)the China Postdoctoral Science Foundation(Grant No.2015M571989)the Jiangxi Province Postdoctoral Science Foundation(Grant No.2015KY51)。
文摘The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.
基金supported by the National Natural Science Foundation of China(No.61271014)the Specialized Research Fund for the Doctoral Program of Higher Education(No.20124301110003)the Graduated Students Innovation Fund of Hunan Province(No.CX2012B238)
文摘The method of recovering a low-rank matrix with an unknown fraction whose entries are arbitrarily corrupted is known as the robust principal component analysis （RPCA）. This RPCA problem, under some conditions, can be exactly solved via convex optimization by minimizing a combination of the nuclear norm and the 11 norm. In this paper, an algorithm based on the Douglas-Rachford splitting method is proposed for solving the RPCA problem. First, the convex optimization problem is solved by canceling the constraint of the variables, and ~hen the proximity operators of the objective function are computed alternately. The new algorithm can exactly recover the low-rank and sparse components simultaneously, and it is proved to be convergent. Numerical simulations demonstrate the practical utility of the proposed algorithm.
基金Research supported in part by the National Natural Science Foundation of China(Grant Nos.12331010,12288101)the Natural Science Foundation of Beijing,China(Grant No.Z230002)the National Key Research and Development Program of China(Grant No.2024YFA1012903).
文摘In this paper,we present a novel Douglas-Rachford-splitting-based path following(DRS-PF)method that rapidly obtains the solution of linear programming(LP)with high accuracy.It originates from the fixed-point mapping associated with DRS on the log-barrier penalized LP.A path-following scheme is then proposed to simultaneously update the iterates and the penalty parameter for accelerating the overall procedure.Its global convergence towards an optimal solution to the original problem is established under mild assumptions.Numerical experiments show that DRS-PF outperforms the simplex and interior point methods implemented in the academic software(CLP,HiGHS,etc.)in terms of the geometric mean of the running time on a few typical benchmark data sets.In some cases,it is even reasonably competitive to the interior point method implemented in Gurobi,one of the most powerful software for LP.
