GLOBAL CONVERGENCE OF A CAUTIOUS PROJECTION BFGS ALGORITHM FOR NONCONVEX PROBLEMS WITHOUT GRADIENT LIPSCHITZ CONTINUITY

A cautious projection BFGS method is proposed for solving nonconvex unconstrained optimization problems.The global convergence of this method as well as a stronger general convergence result can be proven without a gradient Lipschitz continuity assumption,which is more in line with the actual problems than the existing modified BFGS methods and the traditional BFGS method.Under some additional conditions,the method presented has a superlinear convergence rate,which can be regarded as an extension and supplement of BFGS-type methods with the projection technique.Finally,the effectiveness and application prospects of the proposed method are verified by numerical experiments.

Convergence of Bregman Alternating Direction Method of Multipliers for Nonseparable Nonconvex Objective with Linear Constraints

In this paper, our focus lies on addressing a two-block linearly constrained nonseparable nonconvex optimization problem with coupling terms. The most classical algorithm, the alternating direction method of multipliers (ADMM), is employed to solve such problems typically, which still requires the assumption of the gradient Lipschitz continuity condition on the objective function to ensure overall convergence from the current knowledge. However, many practical applications do not adhere to the conditions of smoothness. In this study, we justify the convergence of variant Bregman ADMM for the problem with coupling terms to circumvent the issue of the global Lipschitz continuity of the gradient. We demonstrate that the iterative sequence generated by our approach converges to a critical point of the issue when the corresponding function fulfills the Kurdyka-Lojasiewicz inequality and certain assumptions apply. In addition, we illustrate the convergence rate of the algorithm.

A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization

The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered.This problem is an important component of many machine learning techniques with data parallelism,such as deep learning and federated learning.We propose a distributed primal-dual stochastic gradient descent(SGD)algorithm,suitable for arbitrarily connected communication networks and any smooth(possibly nonconvex)cost functions.We show that the proposed algorithm achieves the linear speedup convergence rate O(1/(√nT))for general nonconvex cost functions and the linear speedup convergence rate O(1/(nT)) when the global cost function satisfies the Polyak-Lojasiewicz(P-L)condition,where T is the total number of iterations.We also show that the output of the proposed algorithm with constant parameters linearly converges to a neighborhood of a global optimum.We demonstrate through numerical experiments the efficiency of our algorithm in comparison with the baseline centralized SGD and recently proposed distributed SGD algorithms.

Improved nonconvex optimization model for low-rank matrix recovery

Low-rank matrix recovery is an important problem extensively studied in machine learning, data mining and computer vision communities. A novel method is proposed for low-rank matrix recovery, targeting at higher recovery accuracy and stronger theoretical guarantee. Specifically, the proposed method is based on a nonconvex optimization model, by solving the low-rank matrix which can be recovered from the noisy observation. To solve the model, an effective algorithm is derived by minimizing over the variables alternately. It is proved theoretically that this algorithm has stronger theoretical guarantee than the existing work. In natural image denoising experiments, the proposed method achieves lower recovery error than the two compared methods. The proposed low-rank matrix recovery method is also applied to solve two real-world problems, i.e., removing noise from verification code and removing watermark from images, in which the images recovered by the proposed method are less noisy than those of the two compared methods.

THE GENERALIZED RIEMANN PROBLEM FOR A SCALAR NONCONVEX COMBUSTION MODEL-THE PERTURBATION ON INITIAL BINDING ENERGY

In this article, we study the generalized Riemann problem for a scalar non- convex Chapman-Jouguet combustion model in a neighborhood of the origin （t 〉 0） on the （x, t） plane. We focus our attention to the perturbation on initial binding energy. The solutions are obtained constructively under the entropy conditions. It can be found that the solutions are essentially different from the corresponding Riemann solutions for some cases. Especially, two important phenomena are observed： the transition from detonation to deflagration followed by a shock, which appears in the numerical simulations [7, 27]; the transition from deflagration to detonation （DDT）, which is one of the core problems in gas dynamic combustion.

Riemann problem for a simplest scalar nonconvex ZND combustion model with viscosity

In this paper, a simplest scalar nonconvex ZND combustion model with viscosity is considered. The existence of the global solution of the Riemann problem for the combustion model is obtained by using the fixed point theorem.

Generalized Nonconvex Low-Rank Algorithm for Magnetic Resonance Imaging (MRI) Reconstruction

In recent years,utilizing the low-rank prior information to construct a signal from a small amount of measures has attracted much attention.In this paper,a generalized nonconvex low-rank(GNLR) algorithm for magnetic resonance imaging(MRI)reconstruction is proposed,which reconstructs the image from highly under-sampled k-space data.In the algorithm,the nonconvex surrogate function replacing the conventional nuclear norm is utilized to enhance the low-rank property inherent in the reconstructed image.An alternative direction multiplier method(ADMM) is applied to solving the resulting non-convex model.Extensive experimental results have demonstrated that the proposed method can consistently recover MRIs efficiently,and outperforms the current state-of-the-art approaches in terms of higher peak signal-to-noise ratio(PSNR) and lower high-frequency error norm(HFEN) values.

Distributed optimization for discrete-time multiagent systems with nonconvex control input constraints and switching topologies

This paper addresses the distributed optimization problem of discrete-time multiagent systems with nonconvex control input constraints and switching topologies.We introduce a novel distributed optimization algorithm with a switching mechanism to guarantee that all agents eventually converge to an optimal solution point,while their control inputs are constrained in their own nonconvex region.It is worth noting that the mechanism is performed to tackle the coexistence of the nonconvex constraint operator and the optimization gradient term.Based on the dynamic transformation technique,the original nonlinear dynamic system is transformed into an equivalent one with a nonlinear error term.By utilizing the nonnegative matrix theory,it is shown that the optimization problem can be solved when the union of switching communication graphs is jointly strongly connected.Finally,a numerical simulation example is used to demonstrate the acquired theoretical results.

On the Global Convergence of the PERRY-SHANNO Method for Nonconvex Unconstrained Optimization Problems

In this paper, we prove the global convergence of the Perry-Shanno’s memoryless quasi-Newton (PSMQN) method with a new inexact line search when applied to nonconvex unconstrained minimization problems. Preliminary numerical results show that the PSMQN with the particularly line search conditions are very promising.

PERIODIC SOLUTIONS FOR HAMILTONIANSYSTEMS IN A NONCONVEX POTENTIAL WELL

Recently there has been a considerable amount of work on the existence of Tperiodic solutions for Hamiltonian systems with singular potentials, (see [1]—[7],[10], [11], [13], [14]). In this paper we will study the existence of T-periodic solutions for nonconservative second-order dynamical systems

Solving Fixed Point Problems in More General Nonconvex Sets Via an Interior Point Homotopy Method

In this paper,we are mainly devoted to solving fixed point problems in more general nonconvex sets via an interior point homotopy method.Under suitable conditions,a constructive proof is given to prove the existence of fixed points,which can lead to an implementable globally convergent algorithm.

Nonconvex Quadratic Programming Method for k－Coloring Problem：Algorithm and Computation

In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.

Nonconvex Constrained Consensus of Discrete-Time Heterogeneous Multi-Agent Systems with Arbitrarily Switching Topologies

This paper mainly focuses on the velocity-constrained consensus problem of discrete-time heterogeneous multi-agent systems with nonconvex constraints and arbitrarily switching topologies,where each agent has first-order or second-order dynamics.To solve this problem,a distributed algorithm is proposed based on a contraction operator.By employing the properties of the stochastic matrix,it is shown that all agents’position states could converge to a common point and second-order agents’velocity states could remain in corresponding nonconvex constraint sets and converge to zero as long as the joint communication topology has one directed spanning tree.Finally,the numerical simulation results are provided to verify the effectiveness of the proposed algorithms.

A Bregman-Style Improved ADMM and its Linearized Version in the Nonconvex Setting:Convergence and Rate Analyses

This work explores a family of two-block nonconvex optimization problems subject to linear constraints.We first introduce a simple but universal Bregman-style improved alternating direction method of multipliers(ADMM)based on the iteration framework of ADMM and the Bregman distance.Then,we utilize the smooth performance of one of the components to develop a linearized version of it.Compared to the traditional ADMM,both proposed methods integrate a convex combination strategy into the multiplier update step.For each proposed method,we demonstrate the convergence of the entire iteration sequence to a unique critical point of the augmented Lagrangian function utilizing the powerful Kurdyka–Łojasiewicz property,and we also derive convergence rates for both the sequence of merit function values and the iteration sequence.Finally,some numerical results show that the proposed methods are effective and encouraging for the Lasso model.

ERROR ANALYSIS FOR PARABOLIC OPTIMAL CONTROL PROBLEMS WITH MEASURE DATA IN A NONCONVEX POLYGONAL DOMAIN

This paper considers the finite element approximation to parabolic optimal control problems with measure data in a nonconvex polygonal domain.Such problems usually possess low regularity in the state variable due to the presence of measure data and the nonconvex nature of the domain.The low regularity of the solution allows the finite element approximations to converge at lower orders.We prove the existence,uniqueness and regularity results for the solution to the control problem satisfying the first order optimality condition.For our error analysis we have used piecewise linear elements for the approximation of the state and co-state variables,whereas piecewise constant functions are employed to approximate the control variable.The temporal discretization is based on the implicit Euler scheme.We derive both a priori and a posteriori error bounds for the state,control and co-state variables.Numerical experiments are performed to validate the theoretical rates of convergence.

Convergence of ADMM for multi-block nonconvex separable optimization models

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.

OPTIMALITY CONDITIONS FOR NONCONVEX BILEVEL PROGRAMMING PROBLEMS

In this paper, we derive an exact penalty function for nonconvex bilevel programming problem based on its KS form. Based on this exact penalty function a sufficient condition for KS to be partially calm is presented and a necessary optimality condition for nonconvex bilevel programming problems is given. Some existing results about the differentiability of the value function of the lower level programming problem are extended and a sufficient condition for CRCQ to hold for VS form of BLPP with linear lower level programming problem is also given.

Anefficient parallel and distributed solution to nonconvex penalized linear SVMs

Support vector machines(SVMs)have been recognized as a powerful tool to perform linear classification.When combined with the sparsity-inducing nonconvex penalty,SVMs can perform classification and variable selection simultaneously.However,the nonconvex penalized SVMs in general cannot be solved globally and efficiently due to their nondifferentiability,nonconvexity,and nonsmoothness.Existing solutions to the nonconvex penalized SVMs typically solve this problem in a serial fashion,which are unable to fully use the parallel computing power of modern multi-core machines.On the other hand,the fact that many real-world data are stored in a distributed manner urgently calls for a parallel and distributed solution to the nonconvex penalized SVMs.To circumvent this challenge,we propose an efficient alternating direction method of multipliers(ADMM)based algorithm that solves the nonconvex penalized SVMs in a parallel and distributed way.We design many useful techniques to decrease the computation and synchronization cost of the proposed parallel algorithm.The time complexity analysis demonstrates the low time complexity of the proposed parallel algorithm.Moreover,the convergence of the parallel algorithm is guaranteed.Experimental evaluations on four LIBSVM benchmark datasets demonstrate the efficiency of the proposed parallel algorithm.

Lyapunov stability and generalized invariance principle for nonconvex differential inclusions

This paper studies the system stability problems of a class of nonconvex differential inclusions. At first, a basic stability result is obtained by virtue of locally Lipschitz continuous Lyapunov functions. Moreover, a generalized invariance principle and related attraction conditions are proposed and proved to overcome the technical difficulties due to the absence of convexity. In the technical analysis, a novel set-valued derivative is proposed to deal with nonsmooth systems and nonsmooth Lyapunov functions. Additionally, the obtained results are consistent with the existing ones in the case of convex differential inclusions with regular Lyapunov functions. Finally, illustrative examples are given to show the effectiveness of the methods.