The Peaceman-Rachford splitting method is efficient for minimizing a convex optimization problem with a separable objective function and linear constraints.However,its convergence was not guaranteed without extra requ...The Peaceman-Rachford splitting method is efficient for minimizing a convex optimization problem with a separable objective function and linear constraints.However,its convergence was not guaranteed without extra requirements.He et al.(SIAM J.Optim.24:1011-1040,2014)proved the convergence of a strictly contractive Peaceman-Rachford splitting method by employing a suitable underdetermined relaxation factor.In this paper,we further extend the so-called strictly contractive Peaceman-Rachford splitting method by using two different relaxation factors.Besides,motivated by the recent advances on the ADMM type method with indefinite proximal terms,we employ the indefinite proximal term in the strictly contractive Peaceman-Rachford splitting method.We show that the proposed indefinite-proximal strictly contractive Peaceman-Rachford splitting method is convergent and also prove the o(1/t)convergence rate in the nonergodic sense.The numerical tests on the l 1 regularized least square problem demonstrate the efficiency of the proposed method.展开更多
For solving minimization problems whose objective function is the sum of two functions without coupled variables and the constrained function is linear, the alternating direction method of multipliers (ADMM) has exh...For solving minimization problems whose objective function is the sum of two functions without coupled variables and the constrained function is linear, the alternating direction method of multipliers (ADMM) has exhibited its efficiency and its convergence is well understood. When either the involved number of separable functions is more than two, or there is a nonconvex function~ ADMM or its direct extended version may not converge. In this paper, we consider the multi-block sepa.rable optimization problems with linear constraints and absence of convexity of the involved component functions. Under the assumption that the associated function satisfies the Kurdyka- Lojasiewicz inequality, we prove that any cluster point of the iterative sequence generated by ADMM is a critical point, under the mild condition that the penalty parameter is sufficiently large. We also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.展开更多
The nonnegative tensor (matrix) factorization finds more and more applications in various disciplines including machine learning, data mining, and blind source separation, etc. In computation, the optimization probl...The nonnegative tensor (matrix) factorization finds more and more applications in various disciplines including machine learning, data mining, and blind source separation, etc. In computation, the optimization problem involved is solved by alternatively minimizing one factor while the others are fixed. To solve the subproblem efficiently, we first exploit a variable regularization term which makes the subproblem far from ill-condition. Second, an augmented Lagrangian alternating direction method is employed to solve this convex and well-conditioned regularized subproblem, and two accelerating skills are also implemented. Some preliminary numerical experiments are performed to show the improvements of the new method.展开更多
Determining whether a quantum state is separable or inseparable (entangled) is a problem of fundamental importance in quantum science and has attracted much attention since its first recognition by Einstein, Podolsk...Determining whether a quantum state is separable or inseparable (entangled) is a problem of fundamental importance in quantum science and has attracted much attention since its first recognition by Einstein, Podolsky and Rosen [Phys. Rev., 1935, 47: 777] and SchrSdinger [Naturwissenschaften, 1935, 23: 807-812, 823-828, 844-849]. In this paper, we propose a successive approximation method (SAM) for this problem, which approximates a given quantum state by a so-called separable state: if the given states is separable, this method finds its rank-one components and the associated weights; otherwise, this method finds the distance between the given state to the set of separable states, which gives information about the degree of entanglement in the system. The key task per iteration is to find a feasible descent direction, which is equivalent to finding the largest M-eigenvalue of a fourth-order tensor. We give a direct method for this problem when the dimension of the tensor is 2 and a heuristic cross-hill method for cases of high dimension. Some numerical results and experiences are presented.展开更多
Owing to its efficiency in solving some types of large-scale separable optimization problems with linear constraints, the convergence rate of the alternating direction method of multipliers(ADMM for short) has recentl...Owing to its efficiency in solving some types of large-scale separable optimization problems with linear constraints, the convergence rate of the alternating direction method of multipliers(ADMM for short) has recently attracted significant attention. In this paper, we consider the generalized ADMM(G-ADMM), which incorporates an acceleration factor and is more efficient. Instead of using a solution measure that depends on a bounded set and cannot be easily estimated, we propose using the original ?-optimal solution measure, under which we prove that the G-ADMM converges at a rate of O(1/t). The new bound depends on the penalty parameter and the distance between the initial point and the solution set, which is more reasonable than the previous bound.展开更多
Tensor canonical decomposition (shorted as CANDECOMP/PARAFAC or CP) decomposes a tensor as a sum of rank-one tensors, which finds numerous applications in signal processing, hypergraph analysis, data analysis, etc. ...Tensor canonical decomposition (shorted as CANDECOMP/PARAFAC or CP) decomposes a tensor as a sum of rank-one tensors, which finds numerous applications in signal processing, hypergraph analysis, data analysis, etc. Alternating least-squares (ALS) is one of the most popular numerical algorithms for solving it. While there have been lots of efforts for enhancing its efficiency, in general its convergence can not been guaranteed. In this paper, we cooperate the ALS and the trust-region technique from optimization field to generate a trust-region-based alternating least-squares (TRALS) method for CP. Under mild assumptions, we prove that the whole iterative sequence generated by TRALS converges to a stationary point of CP. This thus provides a reasonable way to alleviate the swamps, the notorious phenomena of ALS that slow down the speed of the algorithm. Moreover, the trust region itself, in contrast to the regularization alternating least-squares (RALS) method, provides a self-adaptive way in choosing the parameter, which is essential for the efficiency of the algorithm. Our theoretical result is thus stronger than that of RALS in [26], which only proved the cluster point of the iterative sequence generated by RALS is a stationary point. In order to accelerate the new algorithm, we adopt an extrapolation scheme. We apply our algorithm to the amino acid fluorescence data decomposition from chemometrics, BCM decomposition and rank-(Lr, Lr, 1) decomposition arising from signal processing, and compare it with ALS and RALS. The numerical results show that TRALS is superior to ALS and RALS, both from the number of iterations and CPU time perspectives.展开更多
基金supported by the Natural Science Foundation of Jiangsu Province (Grant No.BK20210267)supported by the National Natural Science Foundation of China (Grant No.11971239)+1 种基金the Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (Grant No.21KJA110002)supported by the National Natural Science Foundation of China (Grant Nos.12131004,11625105).
文摘The Peaceman-Rachford splitting method is efficient for minimizing a convex optimization problem with a separable objective function and linear constraints.However,its convergence was not guaranteed without extra requirements.He et al.(SIAM J.Optim.24:1011-1040,2014)proved the convergence of a strictly contractive Peaceman-Rachford splitting method by employing a suitable underdetermined relaxation factor.In this paper,we further extend the so-called strictly contractive Peaceman-Rachford splitting method by using two different relaxation factors.Besides,motivated by the recent advances on the ADMM type method with indefinite proximal terms,we employ the indefinite proximal term in the strictly contractive Peaceman-Rachford splitting method.We show that the proposed indefinite-proximal strictly contractive Peaceman-Rachford splitting method is convergent and also prove the o(1/t)convergence rate in the nonergodic sense.The numerical tests on the l 1 regularized least square problem demonstrate the efficiency of the proposed method.
文摘For solving minimization problems whose objective function is the sum of two functions without coupled variables and the constrained function is linear, the alternating direction method of multipliers (ADMM) has exhibited its efficiency and its convergence is well understood. When either the involved number of separable functions is more than two, or there is a nonconvex function~ ADMM or its direct extended version may not converge. In this paper, we consider the multi-block sepa.rable optimization problems with linear constraints and absence of convexity of the involved component functions. Under the assumption that the associated function satisfies the Kurdyka- Lojasiewicz inequality, we prove that any cluster point of the iterative sequence generated by ADMM is a critical point, under the mild condition that the penalty parameter is sufficiently large. We also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.
文摘The nonnegative tensor (matrix) factorization finds more and more applications in various disciplines including machine learning, data mining, and blind source separation, etc. In computation, the optimization problem involved is solved by alternatively minimizing one factor while the others are fixed. To solve the subproblem efficiently, we first exploit a variable regularization term which makes the subproblem far from ill-condition. Second, an augmented Lagrangian alternating direction method is employed to solve this convex and well-conditioned regularized subproblem, and two accelerating skills are also implemented. Some preliminary numerical experiments are performed to show the improvements of the new method.
文摘Determining whether a quantum state is separable or inseparable (entangled) is a problem of fundamental importance in quantum science and has attracted much attention since its first recognition by Einstein, Podolsky and Rosen [Phys. Rev., 1935, 47: 777] and SchrSdinger [Naturwissenschaften, 1935, 23: 807-812, 823-828, 844-849]. In this paper, we propose a successive approximation method (SAM) for this problem, which approximates a given quantum state by a so-called separable state: if the given states is separable, this method finds its rank-one components and the associated weights; otherwise, this method finds the distance between the given state to the set of separable states, which gives information about the degree of entanglement in the system. The key task per iteration is to find a feasible descent direction, which is equivalent to finding the largest M-eigenvalue of a fourth-order tensor. We give a direct method for this problem when the dimension of the tensor is 2 and a heuristic cross-hill method for cases of high dimension. Some numerical results and experiences are presented.
基金supported by a Project Funded by the Priority Academic Program Development of Jiangsu Higher Education InstitutionsNational Natural Science Foundation of China (Grant Nos. 11401315, 11625105, 11171159 and 11431102)the National Science Foundation from Jiangsu Province (Grant No. BK20140914)
文摘Owing to its efficiency in solving some types of large-scale separable optimization problems with linear constraints, the convergence rate of the alternating direction method of multipliers(ADMM for short) has recently attracted significant attention. In this paper, we consider the generalized ADMM(G-ADMM), which incorporates an acceleration factor and is more efficient. Instead of using a solution measure that depends on a bounded set and cannot be easily estimated, we propose using the original ?-optimal solution measure, under which we prove that the G-ADMM converges at a rate of O(1/t). The new bound depends on the penalty parameter and the distance between the initial point and the solution set, which is more reasonable than the previous bound.
文摘Tensor canonical decomposition (shorted as CANDECOMP/PARAFAC or CP) decomposes a tensor as a sum of rank-one tensors, which finds numerous applications in signal processing, hypergraph analysis, data analysis, etc. Alternating least-squares (ALS) is one of the most popular numerical algorithms for solving it. While there have been lots of efforts for enhancing its efficiency, in general its convergence can not been guaranteed. In this paper, we cooperate the ALS and the trust-region technique from optimization field to generate a trust-region-based alternating least-squares (TRALS) method for CP. Under mild assumptions, we prove that the whole iterative sequence generated by TRALS converges to a stationary point of CP. This thus provides a reasonable way to alleviate the swamps, the notorious phenomena of ALS that slow down the speed of the algorithm. Moreover, the trust region itself, in contrast to the regularization alternating least-squares (RALS) method, provides a self-adaptive way in choosing the parameter, which is essential for the efficiency of the algorithm. Our theoretical result is thus stronger than that of RALS in [26], which only proved the cluster point of the iterative sequence generated by RALS is a stationary point. In order to accelerate the new algorithm, we adopt an extrapolation scheme. We apply our algorithm to the amino acid fluorescence data decomposition from chemometrics, BCM decomposition and rank-(Lr, Lr, 1) decomposition arising from signal processing, and compare it with ALS and RALS. The numerical results show that TRALS is superior to ALS and RALS, both from the number of iterations and CPU time perspectives.