We study distributed optimization problems over a directed network,where nodes aim to minimize the sum of local objective functions via directed communications with neighbors.Many algorithms are designed to solve it f...We study distributed optimization problems over a directed network,where nodes aim to minimize the sum of local objective functions via directed communications with neighbors.Many algorithms are designed to solve it for synchronized or randomly activated implementation,which may create deadlocks in practice.In sharp contrast,we propose a fully asynchronous push-pull gradient(APPG) algorithm,where each node updates without waiting for any other node by using possibly delayed information from neighbors.Then,we construct two novel augmented networks to analyze asynchrony and delays,and quantify its convergence rate from the worst-case point of view.Particularly,all nodes of APPG converge to the same optimal solution at a linear rate of O(λ^(k)) if local functions have Lipschitz-continuous gradients and their sum satisfies the Polyak-?ojasiewicz condition(convexity is not required),where λ ∈(0,1) is explicitly given and the virtual counter k increases by one when any node updates.Finally,the advantage of APPG over the synchronous counterpart and its linear speedup efficiency are numerically validated via a logistic regression problem.展开更多
This paper aims to investigate sign-based methods for unconstrained optimisation problems,which utilise the sign of gradients,instead of full gradients,to reduce the communication cost in distributed optimisation.The ...This paper aims to investigate sign-based methods for unconstrained optimisation problems,which utilise the sign of gradients,instead of full gradients,to reduce the communication cost in distributed optimisation.The methods introduced in this paper also provide an avenue to conquer the issue that classical sign gradient descent with a constant step size generally oscillates around the minimum value of the objective function.To this end,two sign-based algorithms are proposed and analysed.The first one,called ES-GD,is demonstrated to be linearly convergent to the optimal value if the objective function is strongly convex,smooth and separable.For the second variant,called ES-SGD,where the gradient estimates do not need to be unbiased,the algorithm is shown to converge linearly at the same rate as ES-GD to the optimal value under the same assumptions on the objective function.Numerical experiments are conducted to validate the theoretical results.展开更多
We consider a class of nonsmooth convex optimization problems where the objective function is the composition of a strongly convex differentiable function with a linear mapping,regularized by the sum of both l1-norm a...We consider a class of nonsmooth convex optimization problems where the objective function is the composition of a strongly convex differentiable function with a linear mapping,regularized by the sum of both l1-norm and l2-norm of the optimization variables.This class of problems arise naturally from applications in sparse group Lasso,which is a popular technique for variable selection.An effective approach to solve such problems is by the Proximal Gradient Method(PGM).In this paper we prove a local error bound around the optimal solution set for this problem and use it to establish the linear convergence of the PGM method without assuming strong convexity of the overall objective function.展开更多
We define weakly positive tensors and study the relations among essentially positive tensors, weakly positive tensors, and primitive tensors. In particular, an explicit linear convergence rate of the Liu-Zhou-Ibrahim...We define weakly positive tensors and study the relations among essentially positive tensors, weakly positive tensors, and primitive tensors. In particular, an explicit linear convergence rate of the Liu-Zhou-Ibrahim（LZI） algorithm for finding the largest eigenvalue of an irreducible nonnegative tensor, is established for weakly positive tensors. Numerical results are given to demonstrate linear convergence of the LZI algorithm for weakly positive tensors.展开更多
We establish local convergence results for a generic algorithmic framework for solving a wide class of equality constrained optimization problems.The framework is based on applying a splitting scheme to the augmented ...We establish local convergence results for a generic algorithmic framework for solving a wide class of equality constrained optimization problems.The framework is based on applying a splitting scheme to the augmented Lagrangian function that includes as a special case the well-known alternating direction method of multipliers(ADMM).Our local convergence analysis is free of the usual restrictions on ADMM-like methods,such as convexity,block separability or linearity of constraints.It offers a much-needed theoretical justification to the widespread practice of applying ADMM-like methods to nonconvex optimization problems.展开更多
This paper studies the linear convergence properties of a class of the projection and contraction methods for the affine variational inequalities, and proposes a necessary and sufficient condition under which PC-Metho...This paper studies the linear convergence properties of a class of the projection and contraction methods for the affine variational inequalities, and proposes a necessary and sufficient condition under which PC-Method has a globally linear convergence rate.展开更多
A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solve...A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solves only one linear system of equations and does only one line search at each iteration; (ⅱ) It is well_defined for the vertical linear complementarity problem with vertical block P 0 matrix and any accumulation point of iteration sequence is its solution.Moreover, the iteration sequence is bounded for the vertical linear complementarity problem with vertical block P 0+R 0 matrix; (ⅲ) It has both global linear and local quadratic convergence without strict complementarity. Many existing smoothing Newton methods do not have the property (ⅲ).展开更多
We discuss estimates for the rate of convergence of the method of successive subspace corrections in terms of condition number estimate for the method of parallel subspace corrections.We provide upper bounds and in a ...We discuss estimates for the rate of convergence of the method of successive subspace corrections in terms of condition number estimate for the method of parallel subspace corrections.We provide upper bounds and in a special case,a lower bound for preconditioners defined via the method of successive subspace corrections.展开更多
This paper presents a coordinate gradient descent approach for minimizing the sum of a smooth function and a nonseparable convex function.We find a search direction by solving a subproblem obtained by a second-order a...This paper presents a coordinate gradient descent approach for minimizing the sum of a smooth function and a nonseparable convex function.We find a search direction by solving a subproblem obtained by a second-order approximation of the smooth function and adding a separable convex function.Under a local Lipschitzian error bound assumption,we show that the algorithm possesses global and local linear convergence properties.We also give some numerical tests(including image recovery examples) to illustrate the efficiency of the proposed method.展开更多
As a basic mathematical structure,the system of inequalities over symmetric cones and its solution can provide an effective method for solving the startup problem of interior point method which is used to solve many o...As a basic mathematical structure,the system of inequalities over symmetric cones and its solution can provide an effective method for solving the startup problem of interior point method which is used to solve many optimization problems.In this paper,a non-interior continuation algorithm is proposed for solving the system of inequalities under the order induced by a symmetric cone.It is shown that the proposed algorithm is globally convergent and well-defined.Moreover,it can start from any point and only needs to solve one system of linear equations at most at each iteration.Under suitable assumptions,global linear and local quadratic convergence is established with Euclidean Jordan algebras.Numerical results indicate that the algorithm is efficient.The systems of random linear inequalities were tested over the second-order cones with sizes of 10,100,,1 000 respectively and the problems of each size were generated randomly for 10 times.The average iterative numbers show that the proposed algorithm can generate a solution at one step for solving the given linear class of problems with random initializations.It seems possible that the continuation algorithm can solve larger scale systems of linear inequalities over the secondorder cones quickly.Moreover,a system of nonlinear inequalities was also tested over Cartesian product of two simple second-order cones,and numerical results indicate that the proposed algorithm can deal with the nonlinear cases.展开更多
In order to solve variational inequality problems of pseudomonotonicity and Lipschitz continuity in Hilbert spaces, an inertial subgradient extragradient algorithm is proposed by virtue of non-monotone stepsizes. More...In order to solve variational inequality problems of pseudomonotonicity and Lipschitz continuity in Hilbert spaces, an inertial subgradient extragradient algorithm is proposed by virtue of non-monotone stepsizes. Moreover, weak convergence and R-linear convergence analyses of the algorithm are constructed under appropriate assumptions. Finally, the efficiency of the proposed algorithm is demonstrated through numerical implementations.展开更多
Biot’s model is a multiphysics model that describes the interaction of a poroelastic material with its interstitial fluid flow.In this study,we focus on investigating the convergence behavior of a global-in-time iter...Biot’s model is a multiphysics model that describes the interaction of a poroelastic material with its interstitial fluid flow.In this study,we focus on investigating the convergence behavior of a global-in-time iterative decoupled algorithm based on a three-field formulation.During each iteration,the algorithm involves solving a reaction-diffusion subproblem across the entire temporal domain,followed by resolving a Stokes subproblem over the same time interval.This algorithm is recognized for its "partially parallel-in-time" property,enabling the implementation of a parallel procedure when addressing the Stokes subproblem.We establish its global convergence with a new technique by confirming that the limit of the sequence of numerical solutions of the global-in-time algorithm is the numerical solution of the fully coupled algorithm.Numerical experiments validate the theoretical predictions and underline the efficiency gained by implementing the parallel procedure within the proposed globalin-time algorithm.展开更多
The Hankel transform is widely used to solve various engineering and physics problems,such as the representation of electromagnetic field components in the medium,the representation of dynamic stress intensity factors...The Hankel transform is widely used to solve various engineering and physics problems,such as the representation of electromagnetic field components in the medium,the representation of dynamic stress intensity factors,vibration of axisymmetric infinite membrane and displacement intensity factors which all involve this type of integration.However,traditional numerical integration algorithms cannot be used due to the high oscillation characteristics of the Bessel function,so it is particularly important to propose a high precision and efficient numerical algorithm for calculating the integral of high oscillation.In this paper,the improved Gaver-Stehfest(G-S)inverse Laplace transform method for arbitrary real-order Bessel function integration is presented by using the asymptotic characteristics of the Bessel function and the accumulation of integration,and the optimized G-S coefficients are given.The effectiveness of the algorithm is verified by numerical examples.Compared with the linear transformation accelerated convergence algorithm,it shows that the G-S inverse Laplace transform method is suitable for arbitrary real order Hankel transform,and the time consumption is relatively stable and short,which provides a reliable calculation method for the study of electromagnetic mechanics,wave propagation,and fracture dynamics.展开更多
It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we pr...It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.展开更多
In this paper, we consider two different formulations （one is smooth and the other one is nonsmooth） for solving linear matrix inequalities （LMIs）, an important class of semidefinite programming （SDP）, under a c...In this paper, we consider two different formulations （one is smooth and the other one is nonsmooth） for solving linear matrix inequalities （LMIs）, an important class of semidefinite programming （SDP）, under a certain Slater constraint qualification assumption. We then propose two first-order methods, one based on subgradient method and the other based on Nesterov＇s optimal method, and show that they converge linearly for solving these formulations. Moreover, we introduce an accelerated prox-level method which converges linearly uniformly for both smooth and non-smooth problems without requiring the input of any problem parameters. Finally, we consider a special case of LMIs, i.e., linear system of inequalities, and show that a linearly convergent algorithm can be obtained under a much weaker assumption.展开更多
In this paper,we propose a variable metric extrapolation proximal iterative hard thresholding(VMEPIHT)method for nonconvex\ell_0-norm sparsity regularization problem which has wide applications in signal and image pro...In this paper,we propose a variable metric extrapolation proximal iterative hard thresholding(VMEPIHT)method for nonconvex\ell_0-norm sparsity regularization problem which has wide applications in signal and image processing,machine learning and so on.The VMEPIHT method is based on the forward-backward splitting(FBS)method,and variable metric strategy is employed in the extrapolation step to speed up the algorithm.The proposed method’s convergence,linear convergence rate and superlinear convergence rate are shown under appropriate assumptions.Finally,we conduct numerical experiments on compressed sensing problem and CT image reconstruction problem to confirm the efficiency of the proposed method,compared with other state-of-the-art methods.展开更多
Consider the problem of computing the largest eigenvalue for nonnegative tensors. In this paper, we establish the Q-linear convergence of a power type algorithm for this problem under a weak irreducibility condition. ...Consider the problem of computing the largest eigenvalue for nonnegative tensors. In this paper, we establish the Q-linear convergence of a power type algorithm for this problem under a weak irreducibility condition. Moreover, we present a convergent algorithm for calculating the largest eigenvalue for any nonnegative tensors.展开更多
In this paper, an improved feasible QP-free method is proposed to solve nonlinear inequality constrained optimization problems. Here, a new modified method is presented to obtain the revised feasible descent direction...In this paper, an improved feasible QP-free method is proposed to solve nonlinear inequality constrained optimization problems. Here, a new modified method is presented to obtain the revised feasible descent direction. In view of the computational cost, the most attractive feature of the new algorithm is that only one system of linear equations is required to obtain the revised feasible descent direction. Thereby, per single iteration, it is only necessary to solve three systems of linear equations with the same coefficient matrix. In particular, without the positive definiteness assumption on the Hessian estimate, the proposed algorithm is still global convergence. Under some suitable conditions, the superlinear convergence rate is obtained.展开更多
This paper develops distributed algorithms for solving Sylvester equations.The authors transform solving Sylvester equations into a distributed optimization problem,unifying all eight standard distributed matrix struc...This paper develops distributed algorithms for solving Sylvester equations.The authors transform solving Sylvester equations into a distributed optimization problem,unifying all eight standard distributed matrix structures.Then the authors propose a distributed algorithm to find the least squares solution and achieve an explicit linear convergence rate.These results are obtained by carefully choosing the step-size of the algorithm,which requires particular information of data and Laplacian matrices.To avoid these centralized quantities,the authors further develop a distributed scaling technique by using local information only.As a result,the proposed distributed algorithm along with the distributed scaling design yields a universal method for solving Sylvester equations over a multi-agent network with the constant step-size freely chosen from configurable intervals.Finally,the authors provide three examples to illustrate the effectiveness of the proposed algorithms.展开更多
In this paper,a method with parameter is proposed for finding the spectral radius of weakly irreducible nonnegative tensors.What is more,we prove this method has an explicit linear convergence rate for indirectly posi...In this paper,a method with parameter is proposed for finding the spectral radius of weakly irreducible nonnegative tensors.What is more,we prove this method has an explicit linear convergence rate for indirectly positive tensors.Interestingly,the algorithm is exactly the NQZ method(proposed by Ng,Qi and Zhou in Finding the largest eigenvalue of a non-negative tensor SIAM J Matrix Anal Appl 31:1090–1099,2009)by taking a specific parameter.Furthermore,we give a modified NQZ method,which has an explicit linear convergence rate for nonnegative tensors and has an error bound for nonnegative tensors with a positive Perron vector.Besides,we promote an inexact power-type algorithm.Finally,some numerical results are reported.展开更多
基金Supported by National Natural Science Foundation of China(62033006,62203254)。
文摘We study distributed optimization problems over a directed network,where nodes aim to minimize the sum of local objective functions via directed communications with neighbors.Many algorithms are designed to solve it for synchronized or randomly activated implementation,which may create deadlocks in practice.In sharp contrast,we propose a fully asynchronous push-pull gradient(APPG) algorithm,where each node updates without waiting for any other node by using possibly delayed information from neighbors.Then,we construct two novel augmented networks to analyze asynchrony and delays,and quantify its convergence rate from the worst-case point of view.Particularly,all nodes of APPG converge to the same optimal solution at a linear rate of O(λ^(k)) if local functions have Lipschitz-continuous gradients and their sum satisfies the Polyak-?ojasiewicz condition(convexity is not required),where λ ∈(0,1) is explicitly given and the virtual counter k increases by one when any node updates.Finally,the advantage of APPG over the synchronous counterpart and its linear speedup efficiency are numerically validated via a logistic regression problem.
基金supported by the National Natural Science Foundation of China under Grants 62473292 and 62088101.
文摘This paper aims to investigate sign-based methods for unconstrained optimisation problems,which utilise the sign of gradients,instead of full gradients,to reduce the communication cost in distributed optimisation.The methods introduced in this paper also provide an avenue to conquer the issue that classical sign gradient descent with a constant step size generally oscillates around the minimum value of the objective function.To this end,two sign-based algorithms are proposed and analysed.The first one,called ES-GD,is demonstrated to be linearly convergent to the optimal value if the objective function is strongly convex,smooth and separable.For the second variant,called ES-SGD,where the gradient estimates do not need to be unbiased,the algorithm is shown to converge linearly at the same rate as ES-GD to the optimal value under the same assumptions on the objective function.Numerical experiments are conducted to validate the theoretical results.
基金This work was partially supported by the National Natural Science Foundation of China(Nos.61179033,DMS-1015346)。
文摘We consider a class of nonsmooth convex optimization problems where the objective function is the composition of a strongly convex differentiable function with a linear mapping,regularized by the sum of both l1-norm and l2-norm of the optimization variables.This class of problems arise naturally from applications in sparse group Lasso,which is a popular technique for variable selection.An effective approach to solve such problems is by the Proximal Gradient Method(PGM).In this paper we prove a local error bound around the optimal solution set for this problem and use it to establish the linear convergence of the PGM method without assuming strong convexity of the overall objective function.
基金Acknowledgments. This first author＇s work was supported by the National Natural Science Foundation of China （Grant No. 10871113）. This second author＇s work was supported by the Hong Kong Research Grant Council.
文摘We define weakly positive tensors and study the relations among essentially positive tensors, weakly positive tensors, and primitive tensors. In particular, an explicit linear convergence rate of the Liu-Zhou-Ibrahim（LZI） algorithm for finding the largest eigenvalue of an irreducible nonnegative tensor, is established for weakly positive tensors. Numerical results are given to demonstrate linear convergence of the LZI algorithm for weakly positive tensors.
基金This work was supported in part by Shenzhen Fundamental Research Fund(Nos.JCYJ-20170306141038939,KQJSCX-20170728162302784,ZDSYS-201707251409055)via the Shenzhen Research Institute of Big DataThe work of Jun-Feng Yang was supported by the National Natural Science Foundation of China(Nos.11771208,11922111,11671195).
文摘We establish local convergence results for a generic algorithmic framework for solving a wide class of equality constrained optimization problems.The framework is based on applying a splitting scheme to the augmented Lagrangian function that includes as a special case the well-known alternating direction method of multipliers(ADMM).Our local convergence analysis is free of the usual restrictions on ADMM-like methods,such as convexity,block separability or linearity of constraints.It offers a much-needed theoretical justification to the widespread practice of applying ADMM-like methods to nonconvex optimization problems.
文摘This paper studies the linear convergence properties of a class of the projection and contraction methods for the affine variational inequalities, and proposes a necessary and sufficient condition under which PC-Method has a globally linear convergence rate.
文摘A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solves only one linear system of equations and does only one line search at each iteration; (ⅱ) It is well_defined for the vertical linear complementarity problem with vertical block P 0 matrix and any accumulation point of iteration sequence is its solution.Moreover, the iteration sequence is bounded for the vertical linear complementarity problem with vertical block P 0+R 0 matrix; (ⅲ) It has both global linear and local quadratic convergence without strict complementarity. Many existing smoothing Newton methods do not have the property (ⅲ).
文摘We discuss estimates for the rate of convergence of the method of successive subspace corrections in terms of condition number estimate for the method of parallel subspace corrections.We provide upper bounds and in a special case,a lower bound for preconditioners defined via the method of successive subspace corrections.
基金supported by NSFC Grant 10601043,NCETXMUSRF for ROCS,SEM+2 种基金supported by RGC 201508HKBU FRGssupported by the Hong Kong Research Grant Council
文摘This paper presents a coordinate gradient descent approach for minimizing the sum of a smooth function and a nonseparable convex function.We find a search direction by solving a subproblem obtained by a second-order approximation of the smooth function and adding a separable convex function.Under a local Lipschitzian error bound assumption,we show that the algorithm possesses global and local linear convergence properties.We also give some numerical tests(including image recovery examples) to illustrate the efficiency of the proposed method.
基金Supported by National Natural Science Foundation of China (No.10871144)the Seed Foundation of Tianjin University (No.60302023)
文摘As a basic mathematical structure,the system of inequalities over symmetric cones and its solution can provide an effective method for solving the startup problem of interior point method which is used to solve many optimization problems.In this paper,a non-interior continuation algorithm is proposed for solving the system of inequalities under the order induced by a symmetric cone.It is shown that the proposed algorithm is globally convergent and well-defined.Moreover,it can start from any point and only needs to solve one system of linear equations at most at each iteration.Under suitable assumptions,global linear and local quadratic convergence is established with Euclidean Jordan algebras.Numerical results indicate that the algorithm is efficient.The systems of random linear inequalities were tested over the second-order cones with sizes of 10,100,,1 000 respectively and the problems of each size were generated randomly for 10 times.The average iterative numbers show that the proposed algorithm can generate a solution at one step for solving the given linear class of problems with random initializations.It seems possible that the continuation algorithm can solve larger scale systems of linear inequalities over the secondorder cones quickly.Moreover,a system of nonlinear inequalities was also tested over Cartesian product of two simple second-order cones,and numerical results indicate that the proposed algorithm can deal with the nonlinear cases.
文摘In order to solve variational inequality problems of pseudomonotonicity and Lipschitz continuity in Hilbert spaces, an inertial subgradient extragradient algorithm is proposed by virtue of non-monotone stepsizes. Moreover, weak convergence and R-linear convergence analyses of the algorithm are constructed under appropriate assumptions. Finally, the efficiency of the proposed algorithm is demonstrated through numerical implementations.
基金support by National NSF of China No.123B2016supported by the National NSF of China No.11971221+4 种基金the Shenzhen Sci-Tech Fund Nos.RCJC20200714114556020,JCYJ20170818153840322 and JCYJ20190809150413261Guangdong Provincial Key Laboratory of Computational Science and Material Design No.2019B030301001Guang-Dong Basic and Applied Basic Research Foundation 2023B1515250005supported in part by NIH-RCMI grant through U54MD013376,the affiliated project award from the Center for Equitable Artificial Intelligence and Machine Learning Systems(CEAMLS)at Morgan State University(project ID 02232301)the National Science Foundation award 1831950.
文摘Biot’s model is a multiphysics model that describes the interaction of a poroelastic material with its interstitial fluid flow.In this study,we focus on investigating the convergence behavior of a global-in-time iterative decoupled algorithm based on a three-field formulation.During each iteration,the algorithm involves solving a reaction-diffusion subproblem across the entire temporal domain,followed by resolving a Stokes subproblem over the same time interval.This algorithm is recognized for its "partially parallel-in-time" property,enabling the implementation of a parallel procedure when addressing the Stokes subproblem.We establish its global convergence with a new technique by confirming that the limit of the sequence of numerical solutions of the global-in-time algorithm is the numerical solution of the fully coupled algorithm.Numerical experiments validate the theoretical predictions and underline the efficiency gained by implementing the parallel procedure within the proposed globalin-time algorithm.
基金Supported by the National Natural Science Foundation of China(42064004,12062022,11762017,11762016)
文摘The Hankel transform is widely used to solve various engineering and physics problems,such as the representation of electromagnetic field components in the medium,the representation of dynamic stress intensity factors,vibration of axisymmetric infinite membrane and displacement intensity factors which all involve this type of integration.However,traditional numerical integration algorithms cannot be used due to the high oscillation characteristics of the Bessel function,so it is particularly important to propose a high precision and efficient numerical algorithm for calculating the integral of high oscillation.In this paper,the improved Gaver-Stehfest(G-S)inverse Laplace transform method for arbitrary real-order Bessel function integration is presented by using the asymptotic characteristics of the Bessel function and the accumulation of integration,and the optimized G-S coefficients are given.The effectiveness of the algorithm is verified by numerical examples.Compared with the linear transformation accelerated convergence algorithm,it shows that the G-S inverse Laplace transform method is suitable for arbitrary real order Hankel transform,and the time consumption is relatively stable and short,which provides a reliable calculation method for the study of electromagnetic mechanics,wave propagation,and fracture dynamics.
基金supported by the National Natural Science Foundation of China (Grants No.10571134 and 10871144)the Natural Science Foundation of Tianjin (Grant No.07JCYBJC05200)
文摘It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.
文摘In this paper, we consider two different formulations （one is smooth and the other one is nonsmooth） for solving linear matrix inequalities （LMIs）, an important class of semidefinite programming （SDP）, under a certain Slater constraint qualification assumption. We then propose two first-order methods, one based on subgradient method and the other based on Nesterov＇s optimal method, and show that they converge linearly for solving these formulations. Moreover, we introduce an accelerated prox-level method which converges linearly uniformly for both smooth and non-smooth problems without requiring the input of any problem parameters. Finally, we consider a special case of LMIs, i.e., linear system of inequalities, and show that a linearly convergent algorithm can be obtained under a much weaker assumption.
基金supported by the National Natural Science Foundation of China(No.11901368).
文摘In this paper,we propose a variable metric extrapolation proximal iterative hard thresholding(VMEPIHT)method for nonconvex\ell_0-norm sparsity regularization problem which has wide applications in signal and image processing,machine learning and so on.The VMEPIHT method is based on the forward-backward splitting(FBS)method,and variable metric strategy is employed in the extrapolation step to speed up the algorithm.The proposed method’s convergence,linear convergence rate and superlinear convergence rate are shown under appropriate assumptions.Finally,we conduct numerical experiments on compressed sensing problem and CT image reconstruction problem to confirm the efficiency of the proposed method,compared with other state-of-the-art methods.
文摘Consider the problem of computing the largest eigenvalue for nonnegative tensors. In this paper, we establish the Q-linear convergence of a power type algorithm for this problem under a weak irreducibility condition. Moreover, we present a convergent algorithm for calculating the largest eigenvalue for any nonnegative tensors.
基金Supported by National Natural Science Foundation of China (Grant Nos. 11061011 and 71061002)Guangxi Fund for Distinguished Young Scholars (2012GXSFFA060003)
文摘In this paper, an improved feasible QP-free method is proposed to solve nonlinear inequality constrained optimization problems. Here, a new modified method is presented to obtain the revised feasible descent direction. In view of the computational cost, the most attractive feature of the new algorithm is that only one system of linear equations is required to obtain the revised feasible descent direction. Thereby, per single iteration, it is only necessary to solve three systems of linear equations with the same coefficient matrix. In particular, without the positive definiteness assumption on the Hessian estimate, the proposed algorithm is still global convergence. Under some suitable conditions, the superlinear convergence rate is obtained.
基金supported in part by the National Natural Science Foundation of China under Grant Nos.62103003,72171171,62073035,61973002in part by the Anhui Provincial Natural Science Foundation under Grant No.2008085J32。
文摘This paper develops distributed algorithms for solving Sylvester equations.The authors transform solving Sylvester equations into a distributed optimization problem,unifying all eight standard distributed matrix structures.Then the authors propose a distributed algorithm to find the least squares solution and achieve an explicit linear convergence rate.These results are obtained by carefully choosing the step-size of the algorithm,which requires particular information of data and Laplacian matrices.To avoid these centralized quantities,the authors further develop a distributed scaling technique by using local information only.As a result,the proposed distributed algorithm along with the distributed scaling design yields a universal method for solving Sylvester equations over a multi-agent network with the constant step-size freely chosen from configurable intervals.Finally,the authors provide three examples to illustrate the effectiveness of the proposed algorithms.
基金the Ph.D.Candidate Research Innovation Fund of Nankai University.Qing-Zhi Yang’s work was supported by the National Natural Science Foundation of China(No.11271206)Doctoral Fund of Chinese Ministry of Education(No.20120031110024).
文摘In this paper,a method with parameter is proposed for finding the spectral radius of weakly irreducible nonnegative tensors.What is more,we prove this method has an explicit linear convergence rate for indirectly positive tensors.Interestingly,the algorithm is exactly the NQZ method(proposed by Ng,Qi and Zhou in Finding the largest eigenvalue of a non-negative tensor SIAM J Matrix Anal Appl 31:1090–1099,2009)by taking a specific parameter.Furthermore,we give a modified NQZ method,which has an explicit linear convergence rate for nonnegative tensors and has an error bound for nonnegative tensors with a positive Perron vector.Besides,we promote an inexact power-type algorithm.Finally,some numerical results are reported.
