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.展开更多
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 (ⅲ).展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
Symmetric tensor decomposition is of great importance in applications.Several studies have employed a greedy approach,where the main idea is to first find a best rank-one approximation of a given tensor,and then repea...Symmetric tensor decomposition is of great importance in applications.Several studies have employed a greedy approach,where the main idea is to first find a best rank-one approximation of a given tensor,and then repeat the process to the residual tensor by subtracting the rank-one component.In this paper,we focus on finding a best rank-one approximation of a given orthogonally order-3 symmetric tensor.We give a geometric landscape analysis of a nonconvex optimization for the best rank-one approximation of orthogonally symmetric tensors.We show that any local minimizer must be a factor in this orthogonally symmetric tensor decomposition,and any other critical points are linear combinations of the factors.Then,we propose a gradient descent algorithm with a carefully designed initialization to solve this nonconvex optimization problem,and we prove that the algorithm converges to the global minimum with high probability for orthogonal decomposable tensors.This result,combined with the landscape analysis,reveals that the greedy algorithm will get the tensor CP low-rank decomposition.Numerical results are provided to verify our theoretical results.展开更多
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.展开更多
A Quasi-Newton method in Infinite-dimensional Spaces (QNIS) for solving operator equations is presellted and the convergence of a sequence generated by QNIS is also proved in the paper. Next, we suggest a finite-dimen...A Quasi-Newton method in Infinite-dimensional Spaces (QNIS) for solving operator equations is presellted and the convergence of a sequence generated by QNIS is also proved in the paper. Next, we suggest a finite-dimensional implementation of QNIS and prove that the sequence defined by the finite-dimensional algorithm converges to the root of the original operator equation providing that the later exists and that the Frechet derivative of the governing operator is invertible. Finally, we apply QNIS to an inverse problem for a parabolic differential equation to illustrate the efficiency of the finite-dimensional algorithm.展开更多
基金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.
基金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 (ⅲ).
文摘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.
基金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.
文摘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.
基金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.
文摘Symmetric tensor decomposition is of great importance in applications.Several studies have employed a greedy approach,where the main idea is to first find a best rank-one approximation of a given tensor,and then repeat the process to the residual tensor by subtracting the rank-one component.In this paper,we focus on finding a best rank-one approximation of a given orthogonally order-3 symmetric tensor.We give a geometric landscape analysis of a nonconvex optimization for the best rank-one approximation of orthogonally symmetric tensors.We show that any local minimizer must be a factor in this orthogonally symmetric tensor decomposition,and any other critical points are linear combinations of the factors.Then,we propose a gradient descent algorithm with a carefully designed initialization to solve this nonconvex optimization problem,and we prove that the algorithm converges to the global minimum with high probability for orthogonal decomposable tensors.This result,combined with the landscape analysis,reveals that the greedy algorithm will get the tensor CP low-rank decomposition.Numerical results are provided to verify our theoretical results.
基金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.
文摘A Quasi-Newton method in Infinite-dimensional Spaces (QNIS) for solving operator equations is presellted and the convergence of a sequence generated by QNIS is also proved in the paper. Next, we suggest a finite-dimensional implementation of QNIS and prove that the sequence defined by the finite-dimensional algorithm converges to the root of the original operator equation providing that the later exists and that the Frechet derivative of the governing operator is invertible. Finally, we apply QNIS to an inverse problem for a parabolic differential equation to illustrate the efficiency of the finite-dimensional algorithm.