Fully asynchronous distributed optimization with linear convergence over directed networks

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.

On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems

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.

LINEAR CONVERGENCE OF THE LZI ALGORITHM FOR WEAKLY POSITIVE TENSORS

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.

Local Linear Convergence of an ADMM-Type Splitting Framework for Equality Constrained Optimization

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.

ON THE LINEAR CONVERGENCE OF PC-METHOD FOR ACLASS OF LINEAR VARIATIONAL INEQUALITIES

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.

GLOBAL LINEAR AND QUADRATIC ONE-STEP SMOOTHING NEWTON METHOD FOR VERTICAL LINEAR COMPLEMENTARITY PROBLEMS

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 (ⅲ).

New Estimates for the Rate of Convergence of the Method of Subspace Corrections

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.

Inertial Subgradient Extragradient Algorithm for Solving Variational Inequality Problems with Pseudomonotonicity

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.

A Coordinate Gradient Descent Method for Nonsmooth Nonseparable Minimization

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.

Non-interior Continuation Algorithm for Solving System of Inequalities over Symmetric Cones

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.

Convergence of a Non-interior Continuation Algorithm for the Monotone SCCP

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.

LINEARLY CONVERGENT FIRST-ORDER ALGORITHMS FOR SEMIDEFINITE PROGRAMMING

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.

Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor

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.

An Improved Feasible QP-free Algorithm for Inequality Constrained Optimization

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.

A Method with Parameter for Solving the Spectral Radius of Nonnegative Tensor

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.

Gradient Descent for Symmetric Tensor Decomposition

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.

A Numerical Algorithm for Arbitrary Real-Order Hankel Transform

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 AND ITS APPLICATION FOR SOLVING A PARABOLIC INVERSE PROBLEM

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.