This paper addresses the distributed nonconvex optimization problem, where both the global cost function and local inequality constraint function are nonconvex. To tackle this issue, the p-power transformation and pen...This paper addresses the distributed nonconvex optimization problem, where both the global cost function and local inequality constraint function are nonconvex. To tackle this issue, the p-power transformation and penalty function techniques are introduced to reframe the nonconvex optimization problem. This ensures that the Hessian matrix of the augmented Lagrangian function becomes local positive definite by choosing appropriate control parameters. A multi-timescale primal-dual method is then devised based on the Karush-Kuhn-Tucker(KKT) point of the reformulated nonconvex problem to attain convergence. The Lyapunov theory guarantees the model's stability in the presence of an undirected and connected communication network. Finally, two nonconvex optimization problems are presented to demonstrate the efficacy of the previously developed method.展开更多
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...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.展开更多
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 recov...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.展开更多
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 nu...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.展开更多
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 w...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.展开更多
The margin maximization problem in digital subscriber line（DSL） systems is investigated.The particle swarm optimization（PSO） theory is applied to the nonconvex margin optimization problem with the target power and...The margin maximization problem in digital subscriber line（DSL） systems is investigated.The particle swarm optimization（PSO） theory is applied to the nonconvex margin optimization problem with the target power and rate constraints.PSO is a new evolution algorithm based on the social behavior of swarms, which can solve discontinuous, nonconvex and nonlinear problems efficiently.The proposed algorithm can converge to the global optimal solution, and numerical example demonstrates that the proposed algorithm can guarantee the fast convergence within a few iterations.展开更多
This paper considers the NP (Non-deterministic Polynomial)-hard problem of finding a minimum value of a quadratic program (QP), subject to m non-convex inhomogeneous quadratic constraints. One effective algorithm is p...This paper considers the NP (Non-deterministic Polynomial)-hard problem of finding a minimum value of a quadratic program (QP), subject to m non-convex inhomogeneous quadratic constraints. One effective algorithm is proposed to get a feasible solution based on the optimal solution of its semidefinite programming (SDP) relaxation problem.展开更多
We propose two nonmonotone retraction-based proximal gradient methods for solving a class of nonconvex nonsmooth optimization problems over the Stiefel manifold.The proposed methods are equipped with the descent direc...We propose two nonmonotone retraction-based proximal gradient methods for solving a class of nonconvex nonsmooth optimization problems over the Stiefel manifold.The proposed methods are equipped with the descent direction obtained by a proximal mapping restricted in tangent space of the manifold and the BarzilaiBorwein stepsizes determined by two recent iteration points and the corresponding descent directions.By employing,respectively,the Grippo-Lampariello-Lucidi nonmonotone line search strategy and the Dai-Fletcher nonmonotone line search strategy,our proposed methods are proved to be globally convergent.Analysis on the iteration complexity for obtaining an?-stationary solution is provided.Numerical results on the sparse principle component analysis problems demonstrate the efficiency of our methods.展开更多
Early fault detection for spiral bevel gears is crucial to ensure normal operation and prevent accidents.The harmonic components,excited by the time-varying mesh stiffness,always appear in measured vibration signal.Ho...Early fault detection for spiral bevel gears is crucial to ensure normal operation and prevent accidents.The harmonic components,excited by the time-varying mesh stiffness,always appear in measured vibration signal.How to extract the periodical impulses that indicate gear localized fault buried in the intensive noise and interfered by harmonics is a challenging task.In this paper,a novel Periodical Sparse-Assisted Decoupling(PSAD)method is proposed as an optimization problem to extract fault feature from noisy vibration signal.The PSAD method decouples the impulsive fault feature and harmonic components based on the sparse representation method.The sparsity within and across groups property and the periodicity of the fault feature are incorporated into the regularizer as the prior information.The nonconvex penalty is employed to highlight the sparsity of fault features.Meanwhile,the weight factor based on2norm of each group is constructed to strengthen the amplitude of fault feature.An iterative algorithm with Majorization-Minimization(MM)is derived to solve the optimization problem.Simulation study and experimental analysis confirm the performance of the proposed PSAD method in extracting and enhancing defect impulses from noisy signal.The suggested method surpasses other comparative methods in extracting and enhancing fault features.展开更多
The problem of nonconvex and nonsmooth optimization(NNO)has been extensively studied in the machine learning community,leading to the development of numerous fast and convergent numerical algorithms.Existing algorithm...The problem of nonconvex and nonsmooth optimization(NNO)has been extensively studied in the machine learning community,leading to the development of numerous fast and convergent numerical algorithms.Existing algorithms typically employ unified iteration schemes and require explicit solutions to subproblems for ensuring convergence.However,these inflexible iteration schemes overlook task-specific details and may encounter difficulties in providing explicit solutions to subproblems.In contrast,there is evidence suggesting that practical applications can benefit from approximately solving subproblems;however,many existing works fail to establish the theoretical validity of such approximations.In this paper,the authors propose a hybrid inexact proximal alternating method(hiPAM),which addresses a general NNO problem with coupled terms while overcoming all aforementioned challenges.The proposed hiPAM algorithm offers a flexible yet highly efficient approach by seamlessly integrating any efficient methods for approximate subproblem solving that cater to specificities.Additionally,the authors have devised a simple yet implementable stopping criterion that generates a Cauchy sequence and ultimately converges to a critical point of the original NNO problem.The proposed numerical experiments using both simulated and real data have demonstrated that hiPAM represents an exceedingly efficient and robust approach to NNO problems.展开更多
This work discusses a class of two-block nonconvex optimization problems with linear equality,inequality and box constraints.Based on the ideas of alternating direction method with multipliers(ADMM),sequential quadrat...This work discusses a class of two-block nonconvex optimization problems with linear equality,inequality and box constraints.Based on the ideas of alternating direction method with multipliers(ADMM),sequential quadratic programming(SQP)and Armijo line search technique,we propose a novel monotone splitting SQP algorithm.First,the discussed problem is transformed into an optimization problem with only linear equality and box constraints by introduction of slack variables.Second,the idea of ADMM is used to decompose the traditional quadratic programming(QP)subproblem.In particular,the QP subproblem corresponding to the introduction of the slack variable is simple,and it has an explicit optimal solution without increasing the computational cost.Third,the search direction is generated by the optimal solutions of the subproblems,and the new iteration point is yielded by an Armijo line search with augmented Lagrange function.Fourth,the multiplier is updated by a novel approach that is different from the ADMM.Furthermore,the algorithm is extended to the associated optimization problem where the box constraints can be replaced by general nonempty closed convex sets.The global convergence of the two proposed algorithms is analyzed under weaker assumptions.Finally,some preliminary numerical experiments and applications in mid-to-large-scale economic dispatch problems for power systems are reported,and these show that the proposed algorithms are promising.展开更多
In this paper, we consider the convergence of the generalized alternating direction method of multipliers（GADMM） for solving linearly constrained nonconvex minimization model whose objective contains coupled functio...In this paper, we consider the convergence of the generalized alternating direction method of multipliers（GADMM） for solving linearly constrained nonconvex minimization model whose objective contains coupled functions. Under the assumption that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz inequality, we prove that the sequence generated by the GADMM converges to a critical point of the augmented Lagrangian function when the penalty parameter in the augmented Lagrangian function is sufficiently large. Moreover, we also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.展开更多
This paper addresses a nonlinear partial differential control system arising in population dynamics.The system consist of three diffusion equations describing the evolutions of three biological species:prey,predator,a...This paper addresses a nonlinear partial differential control system arising in population dynamics.The system consist of three diffusion equations describing the evolutions of three biological species:prey,predator,and food for the prey or vegetation.The equation for the food density incorporates a hysteresis operator of generalized stop type accounting for underlying hysteresis effects occurring in the dynamical process.We study the problem of minimization of a given integral cost functional over solutions of the above system.The set-valued mapping defining the control constraint is state-dependent and its values are nonconvex as is the cost integrand as a function of the control variable.Some relaxationtype results for the minimization problem are obtained and the existence of a nearly optimal solution is established.展开更多
Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are present...Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.展开更多
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 r...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.展开更多
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 multiplie...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.展开更多
For solving minimization problems whose objective function is the sum of two functions without coupled variables and the constrained function is linear, the alternating direction method of multipliers （ADMM） has exh...For solving minimization problems whose objective function is the sum of two functions without coupled variables and the constrained function is linear, the alternating direction method of multipliers （ADMM） has exhibited its efficiency and its convergence is well understood. When either the involved number of separable functions is more than two, or there is a nonconvex function~ ADMM or its direct extended version may not converge. In this paper, we consider the multi-block sepa.rable optimization problems with linear constraints and absence of convexity of the involved component functions. Under the assumption that the associated function satisfies the Kurdyka- Lojasiewicz inequality, we prove that any cluster point of the iterative sequence generated by ADMM is a critical point, under the mild condition that the penalty parameter is sufficiently large. We also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.展开更多
LION(evoLedv sIng mOmeNumt)是Google公司通过启发式程序搜索的方式发现的优化器,是一种独特的基于学习的优化算法。LION算法通过在上步动量和本步梯度之间维持两个不同的插值,并有效结合了解耦的权重衰减技术,实现了超越传统符号梯度...LION(evoLedv sIng mOmeNumt)是Google公司通过启发式程序搜索的方式发现的优化器,是一种独特的基于学习的优化算法。LION算法通过在上步动量和本步梯度之间维持两个不同的插值,并有效结合了解耦的权重衰减技术,实现了超越传统符号梯度下降类算法的性能。LION算法在许多大规模深度学习问题中展现了较强的优势,得到了广泛的应用。然而,尽管已有工作已经证明了LION的收敛性,但尚未有研究给出一个全面的收敛速度分析。已有研究证明,LION能够解决一类特定的盒约束优化问题,本文着重证明了,在?1范数度量下,LION收敛到这类问题的Karush-Kuhn-Tucker(KKT)点的速度为(Q√dK^(-1/4)),其中d为问题维度,K为算法的迭代步数。更进一步,我们移除了约束条件,证明LION在一般无约束问题上以相同的速度收敛至目标函数的驻点。与已有研究工作相比,本文证明的收敛速度达到了关于问题维度d的最优依赖关系;关于迭代步数K,这一速度还达到了非凸优化问题中随机梯度类算法能实现的最优理论下界。此外,这一理论下界以梯度的?2范数度量,而LION所属的符号梯度下降类算法通常度量的是更大的?1范数。由于在不同的梯度范数度量下关于问题维度d得到的收敛速度结果会有所差异,为了验证本文证明的收敛速度关于维度d同样是最优的,我们在多种深度学习任务上设计了全面的实验,不仅证明了LION与同样匹配理论下界的随机梯度下降法相比具有更低的训练损失和更强的性能,而且还验证了LION算法在迭代过程中梯度的ℓ_(1)/ℓ_(2)范数比始终处于Q(√d)的量级,从而在经验上说明了本文证明的收敛速度同样匹配关于d的最优下界。展开更多
交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)求解两分块优化的研究已经逐渐完善,但对于非凸多分块优化的研究较少,提出了一种带松弛步长参数的对称邻近ADMM用于求解非凸一致性问题。在适当的假设条件下,证明了...交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)求解两分块优化的研究已经逐渐完善,但对于非凸多分块优化的研究较少,提出了一种带松弛步长参数的对称邻近ADMM用于求解非凸一致性问题。在适当的假设条件下,证明了算法的全局收敛性。其次,在效益函数满足Kurdyka-Lojasiewicz(KL)性质时,证明了算法的强收敛性。最后,数值实验验证了算法的有效性。展开更多
基金supported in part by the National Natural Science Foundation of China(62236002,62403004,62203001,62303009,62136008)the Open Project of Anhui Key Laboratory of Industrial Energy-Saving and Safety,Anhui University(KFKT202405)
文摘This paper addresses the distributed nonconvex optimization problem, where both the global cost function and local inequality constraint function are nonconvex. To tackle this issue, the p-power transformation and penalty function techniques are introduced to reframe the nonconvex optimization problem. This ensures that the Hessian matrix of the augmented Lagrangian function becomes local positive definite by choosing appropriate control parameters. A multi-timescale primal-dual method is then devised based on the Karush-Kuhn-Tucker(KKT) point of the reformulated nonconvex problem to attain convergence. The Lyapunov theory guarantees the model's stability in the presence of an undirected and connected communication network. Finally, two nonconvex optimization problems are presented to demonstrate the efficacy of the previously developed method.
基金supported by the Knut and Alice Wallenberg Foundationthe Swedish Foundation for Strategic Research+1 种基金the Swedish Research Councilthe National Natural Science Foundation of China(62133003,61991403,61991404,61991400)。
文摘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.
基金Projects(61173122,61262032) supported by the National Natural Science Foundation of ChinaProjects(11JJ3067,12JJ2038) supported by the Natural Science Foundation of Hunan Province,China
文摘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.
文摘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.
基金Project supported by the National Engineering Research Center of Rail Transportation Operation and Control System,Beijing Jiaotong University(Grant No.NERC2019K002)。
文摘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.
基金supported by the National Natural Science Foundation of China for Distinguished Young Scholars (60525303)the National Natural Science Foundation of China (60904048+2 种基金 60404022 60604012)the Natural Science Foundation of Hebei province (F2005000390)
文摘The margin maximization problem in digital subscriber line（DSL） systems is investigated.The particle swarm optimization（PSO） theory is applied to the nonconvex margin optimization problem with the target power and rate constraints.PSO is a new evolution algorithm based on the social behavior of swarms, which can solve discontinuous, nonconvex and nonlinear problems efficiently.The proposed algorithm can converge to the global optimal solution, and numerical example demonstrates that the proposed algorithm can guarantee the fast convergence within a few iterations.
文摘This paper considers the NP (Non-deterministic Polynomial)-hard problem of finding a minimum value of a quadratic program (QP), subject to m non-convex inhomogeneous quadratic constraints. One effective algorithm is proposed to get a feasible solution based on the optimal solution of its semidefinite programming (SDP) relaxation problem.
基金supported by the National Natural Science Foundation of China(Grant Nos.11671116,12071108 and 11701137)Natural Science Foundation of Hebei Province(Grant No.A2021202010)。
文摘We propose two nonmonotone retraction-based proximal gradient methods for solving a class of nonconvex nonsmooth optimization problems over the Stiefel manifold.The proposed methods are equipped with the descent direction obtained by a proximal mapping restricted in tangent space of the manifold and the BarzilaiBorwein stepsizes determined by two recent iteration points and the corresponding descent directions.By employing,respectively,the Grippo-Lampariello-Lucidi nonmonotone line search strategy and the Dai-Fletcher nonmonotone line search strategy,our proposed methods are proved to be globally convergent.Analysis on the iteration complexity for obtaining an?-stationary solution is provided.Numerical results on the sparse principle component analysis problems demonstrate the efficiency of our methods.
基金supported by the National Science Foundationof China(Nos.52305127 and 52475130)。
文摘Early fault detection for spiral bevel gears is crucial to ensure normal operation and prevent accidents.The harmonic components,excited by the time-varying mesh stiffness,always appear in measured vibration signal.How to extract the periodical impulses that indicate gear localized fault buried in the intensive noise and interfered by harmonics is a challenging task.In this paper,a novel Periodical Sparse-Assisted Decoupling(PSAD)method is proposed as an optimization problem to extract fault feature from noisy vibration signal.The PSAD method decouples the impulsive fault feature and harmonic components based on the sparse representation method.The sparsity within and across groups property and the periodicity of the fault feature are incorporated into the regularizer as the prior information.The nonconvex penalty is employed to highlight the sparsity of fault features.Meanwhile,the weight factor based on2norm of each group is constructed to strengthen the amplitude of fault feature.An iterative algorithm with Majorization-Minimization(MM)is derived to solve the optimization problem.Simulation study and experimental analysis confirm the performance of the proposed PSAD method in extracting and enhancing defect impulses from noisy signal.The suggested method surpasses other comparative methods in extracting and enhancing fault features.
基金supported by the National Key R&D Program of China under Grant No.2023YFA1011303the National Natural Science Foundation of China under Grant Nos.61806057 and 12301479+1 种基金the China Postdoctoral Science Foundation under Grant No.2018M632018the Natural Science Foundation of Liaoning Province under Grant No.2023-MS-126。
文摘The problem of nonconvex and nonsmooth optimization(NNO)has been extensively studied in the machine learning community,leading to the development of numerous fast and convergent numerical algorithms.Existing algorithms typically employ unified iteration schemes and require explicit solutions to subproblems for ensuring convergence.However,these inflexible iteration schemes overlook task-specific details and may encounter difficulties in providing explicit solutions to subproblems.In contrast,there is evidence suggesting that practical applications can benefit from approximately solving subproblems;however,many existing works fail to establish the theoretical validity of such approximations.In this paper,the authors propose a hybrid inexact proximal alternating method(hiPAM),which addresses a general NNO problem with coupled terms while overcoming all aforementioned challenges.The proposed hiPAM algorithm offers a flexible yet highly efficient approach by seamlessly integrating any efficient methods for approximate subproblem solving that cater to specificities.Additionally,the authors have devised a simple yet implementable stopping criterion that generates a Cauchy sequence and ultimately converges to a critical point of the original NNO problem.The proposed numerical experiments using both simulated and real data have demonstrated that hiPAM represents an exceedingly efficient and robust approach to NNO problems.
基金supported by the National Natural Science Foundation of China(No.12261008)the Guangxi Natural Science Foundation(Nos.2023GXNSFAA026158 and 2020GXNSFDA238017)+1 种基金the Xiangsihu Young Scholars Innovative Research Team of Guangxi Minzu University(No.2022GXUNXSHQN04)the Guangxi Scholarship Fund of Guangxi Education Department(GED).
文摘This work discusses a class of two-block nonconvex optimization problems with linear equality,inequality and box constraints.Based on the ideas of alternating direction method with multipliers(ADMM),sequential quadratic programming(SQP)and Armijo line search technique,we propose a novel monotone splitting SQP algorithm.First,the discussed problem is transformed into an optimization problem with only linear equality and box constraints by introduction of slack variables.Second,the idea of ADMM is used to decompose the traditional quadratic programming(QP)subproblem.In particular,the QP subproblem corresponding to the introduction of the slack variable is simple,and it has an explicit optimal solution without increasing the computational cost.Third,the search direction is generated by the optimal solutions of the subproblems,and the new iteration point is yielded by an Armijo line search with augmented Lagrange function.Fourth,the multiplier is updated by a novel approach that is different from the ADMM.Furthermore,the algorithm is extended to the associated optimization problem where the box constraints can be replaced by general nonempty closed convex sets.The global convergence of the two proposed algorithms is analyzed under weaker assumptions.Finally,some preliminary numerical experiments and applications in mid-to-large-scale economic dispatch problems for power systems are reported,and these show that the proposed algorithms are promising.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1157117811801455)the Fundamental Research Funds of China West Normal University(Grant No.17E084)
文摘In this paper, we consider the convergence of the generalized alternating direction method of multipliers（GADMM） for solving linearly constrained nonconvex minimization model whose objective contains coupled functions. Under the assumption that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz inequality, we prove that the sequence generated by the GADMM converges to a critical point of the augmented Lagrangian function when the penalty parameter in the augmented Lagrangian function is sufficiently large. Moreover, we also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.
基金supported by National Natural Science Foundation of China(12071165 and 62076104)Natural Science Foundation of Fujian Province(2020J01072)+2 种基金Program for Innovative Research Team in Science and Technology in Fujian Province University,Quanzhou High-Level Talents Support Plan(2017ZT012)Scientific Research Funds of Huaqiao University(605-50Y 19017,605-50Y14040)supported by Ministry of Science and Higher Education of Russian Federation(075-15-2020-787,large scientific project"Fundamentals,methods and technologies for digital monitoring and forecasting of the environmental situation on the Baikal natural territory")。
文摘This paper addresses a nonlinear partial differential control system arising in population dynamics.The system consist of three diffusion equations describing the evolutions of three biological species:prey,predator,and food for the prey or vegetation.The equation for the food density incorporates a hysteresis operator of generalized stop type accounting for underlying hysteresis effects occurring in the dynamical process.We study the problem of minimization of a given integral cost functional over solutions of the above system.The set-valued mapping defining the control constraint is state-dependent and its values are nonconvex as is the cost integrand as a function of the control variable.Some relaxationtype results for the minimization problem are obtained and the existence of a nearly optimal solution is established.
文摘Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.
基金National Natural Science Foundations of China(Nos.61362001,61365013,51165033)the Science and Technology Department of Jiangxi Province of China(Nos.20132BAB211030,20122BAB211015)+1 种基金the Jiangxi Advanced Projects for Postdoctoral Research Funds,China(o.2014KY02)the Innovation Special Fund Project of Nanchang University,China(o.cx2015136)
文摘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.
文摘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.
文摘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.
文摘LION(evoLedv sIng mOmeNumt)是Google公司通过启发式程序搜索的方式发现的优化器,是一种独特的基于学习的优化算法。LION算法通过在上步动量和本步梯度之间维持两个不同的插值,并有效结合了解耦的权重衰减技术,实现了超越传统符号梯度下降类算法的性能。LION算法在许多大规模深度学习问题中展现了较强的优势,得到了广泛的应用。然而,尽管已有工作已经证明了LION的收敛性,但尚未有研究给出一个全面的收敛速度分析。已有研究证明,LION能够解决一类特定的盒约束优化问题,本文着重证明了,在?1范数度量下,LION收敛到这类问题的Karush-Kuhn-Tucker(KKT)点的速度为(Q√dK^(-1/4)),其中d为问题维度,K为算法的迭代步数。更进一步,我们移除了约束条件,证明LION在一般无约束问题上以相同的速度收敛至目标函数的驻点。与已有研究工作相比,本文证明的收敛速度达到了关于问题维度d的最优依赖关系;关于迭代步数K,这一速度还达到了非凸优化问题中随机梯度类算法能实现的最优理论下界。此外,这一理论下界以梯度的?2范数度量,而LION所属的符号梯度下降类算法通常度量的是更大的?1范数。由于在不同的梯度范数度量下关于问题维度d得到的收敛速度结果会有所差异,为了验证本文证明的收敛速度关于维度d同样是最优的,我们在多种深度学习任务上设计了全面的实验,不仅证明了LION与同样匹配理论下界的随机梯度下降法相比具有更低的训练损失和更强的性能,而且还验证了LION算法在迭代过程中梯度的ℓ_(1)/ℓ_(2)范数比始终处于Q(√d)的量级,从而在经验上说明了本文证明的收敛速度同样匹配关于d的最优下界。
文摘交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)求解两分块优化的研究已经逐渐完善,但对于非凸多分块优化的研究较少,提出了一种带松弛步长参数的对称邻近ADMM用于求解非凸一致性问题。在适当的假设条件下,证明了算法的全局收敛性。其次,在效益函数满足Kurdyka-Lojasiewicz(KL)性质时,证明了算法的强收敛性。最后,数值实验验证了算法的有效性。
