In this paper,we provide some gentle introductions to the recent advance in augmented Lagrangian methods for solving large-scale convex matrix optimization problems(cMOP).Specifically,we reviewed two types of sufficie...In this paper,we provide some gentle introductions to the recent advance in augmented Lagrangian methods for solving large-scale convex matrix optimization problems(cMOP).Specifically,we reviewed two types of sufficient conditions for ensuring the quadratic growth conditions of a class of constrained convex matrix optimization problems regularized by nonsmooth spectral functions.Under a mild quadratic growth condition on the dual of cMOP,we further discussed the R-superlinear convergence of the Karush-Kuhn-Tucker(KKT)residuals of the sequence generated by the augmented Lagrangian methods(ALM)for solving convex matrix optimization problems.Implementation details of the ALM for solving core convex matrix optimization problems are also provided.展开更多
Tensor robust principal component analysis（TRPCA） problem aims to separate a low-rank tensor and a sparse tensor from their sum. This problem has recently attracted considerable research attention due to its wide ra...Tensor robust principal component analysis（TRPCA） problem aims to separate a low-rank tensor and a sparse tensor from their sum. This problem has recently attracted considerable research attention due to its wide range of potential applications in computer vision and pattern recognition. In this paper, we propose a new model to deal with the TRPCA problem by an alternation minimization algorithm along with two adaptive rankadjusting strategies. For the underlying low-rank tensor, we simultaneously perform low-rank matrix factorizations to its all-mode matricizations; while for the underlying sparse tensor,a soft-threshold shrinkage scheme is applied. Our method can be used to deal with the separation between either an exact or an approximate low-rank tensor and a sparse one. We established the subsequence convergence of our algorithm in the sense that any limit point of the iterates satisfies the KKT conditions. When the iteration stops, the output will be modified by applying a high-order SVD approach to achieve an exactly low-rank final result as the accurate rank has been calculated. The numerical experiments demonstrate that our method could achieve better results than the compared methods.展开更多
This paper formulates a two-dimensional strip packing problem as a non- linear programming （NLP） problem and establishes the first-order optimality conditions for the NLP problem. A numerical algorithm for solving t...This paper formulates a two-dimensional strip packing problem as a non- linear programming （NLP） problem and establishes the first-order optimality conditions for the NLP problem. A numerical algorithm for solving this NLP problem is given to find exact solutions to strip-packing problems involving up to 10 items. Approximate solutions can be found for big-sized problems by decomposing the set of items into small-sized blocks of which each block adopts the proposed numerical algorithm. Numerical results show that the approximate solutions to big-sized problems obtained by this method are superior to those by NFDH, FFDH and BFDH approaches.展开更多
In this paper,we analyze the convergence properties of a stochastic augmented Lagrangian method for solving stochastic convex programming problems with inequality constraints.Approximation models for stochastic convex...In this paper,we analyze the convergence properties of a stochastic augmented Lagrangian method for solving stochastic convex programming problems with inequality constraints.Approximation models for stochastic convex programming problems are constructed from stochastic observations of real objective and constraint functions.Based on relations between solutions of the primal problem and solutions of the dual problem,it is proved that the convergence of the algorithm from the perspective of the dual problem.Without assumptions on how these random models are generated,when estimates are merely sufficiently accurate to the real objective and constraint functions with high enough,but fixed,probability,the method converges globally to the optimal solution almost surely.In addition,sufficiently accurate random models are given under different noise assumptions.We also report numerical results that show the good performance of the algorithm for different convex programming problems with several random models.展开更多
The augmented Lagrangian function and the corresponding augmented Lagrangian method are constructed for solving a class of minimax optimization problems with equality constraints.We prove that,under the linear indepen...The augmented Lagrangian function and the corresponding augmented Lagrangian method are constructed for solving a class of minimax optimization problems with equality constraints.We prove that,under the linear independence constraint qualification and the second-order sufficiency optimality condition for the lower level problem and the second-order sufficiency optimality condition for the minimax problem,for a given multiplier vectorμ,the rate of convergence of the augmented Lagrangian method is linear with respect to||μu-μ^(*)||and the ratio constant is proportional to 1/c when the ratio|μ-μ^(*)||/c is small enough,where c is the penalty parameter that exceeds a threshold c_(*)>O andμ^(*)is the multiplier corresponding to a local minimizer.Moreover,we prove that the sequence of multiplier vectors generated by the augmented Lagrangian method has at least Q-linear convergence if the sequence of penalty parameters(ck)is bounded and the convergence rate is superlinear if(ck)is increasing to infinity.Finally,we use a direct way to establish the rate of convergence of the augmented Lagrangian method for the minimax problem with a quadratic objective function and linear equality constraints.展开更多
In this work,we propose a second-order model for image denoising by employing a novel potential function recently developed in Zhu(J Sci Comput 88:46,2021)for the design of a regularization term.Due to this new second...In this work,we propose a second-order model for image denoising by employing a novel potential function recently developed in Zhu(J Sci Comput 88:46,2021)for the design of a regularization term.Due to this new second-order derivative based regularizer,the model is able to alleviate the staircase effect and preserve image contrast.The augmented Lagrangian method(ALM)is utilized to minimize the associated functional and convergence analysis is established for the proposed algorithm.Numerical experiments are presented to demonstrate the features of the proposed model.展开更多
This paper is concerned with a novel deep learning method for variational problems with essential boundary conditions.To this end,wefirst reformulate the original problem into a minimax problem corresponding to a feas...This paper is concerned with a novel deep learning method for variational problems with essential boundary conditions.To this end,wefirst reformulate the original problem into a minimax problem corresponding to a feasible augmented La-grangian,which can be solved by the augmented Lagrangian method in an infinite dimensional setting.Based on this,by expressing the primal and dual variables with two individual deep neural network functions,we present an augmented Lagrangian deep learning method for which the parameters are trained by the stochastic optimiza-tion method together with a projection technique.Compared to the traditional penalty method,the new method admits two main advantages:i)the choice of the penalty parameter isflexible and robust,and ii)the numerical solution is more accurate in the same magnitude of computational cost.As typical applications,we apply the new ap-proach to solve elliptic problems and(nonlinear)eigenvalue problems with essential boundary conditions,and numerical experiments are presented to show the effective-ness of the new method.展开更多
.In this paper,an augmented Lagrangian Uzawa iterative method is developed and analyzed for solving a class of double saddle-point systems with semidefinite(2,2)block.Convergence of the iterativemethod is proved under....In this paper,an augmented Lagrangian Uzawa iterative method is developed and analyzed for solving a class of double saddle-point systems with semidefinite(2,2)block.Convergence of the iterativemethod is proved under the assumption that the double saddle-point problem exists a unique solution.An application of the iterative method to the double saddle-point systems arising from the distributed Lagrange multiplier/fictitious domain(DLM/FD)finite element method for solving elliptic interface problems is also presented,in which the existence and uniqueness of the double saddle-point system is guaranteed by the analysis of the DLM/FD finite element method.Numerical experiments are conducted to validate the theoretical results and to study the performance of the proposed iterative method.展开更多
It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality.Recently,we have proposed a unified algorithmic framework which can guide ...It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality.Recently,we have proposed a unified algorithmic framework which can guide us to construct the solution methods for solving these monotone variational inequalities.In this work,we revisit two full Jacobian decomposition of the augmented Lagrangian methods for separable convex programming which we have studied a few years ago.In particular,exploiting this framework,we are able to give a very clear and elementary proof of the convergence of these solution methods.展开更多
In this paper,operator splitting scheme for dynamic reservoir characterization by binary level set method is employed.For this problem,the absolute permeability of the two-phase porous medium flow can be simulated by ...In this paper,operator splitting scheme for dynamic reservoir characterization by binary level set method is employed.For this problem,the absolute permeability of the two-phase porous medium flow can be simulated by the constrained augmented Lagrangian optimization method with well data and seismic time-lapse data.By transforming the constrained optimization problem in an unconstrained one,the saddle point problem can be solved by Uzawas algorithms with operator splitting scheme,which is based on the essence of binary level set method.Both the simple and complicated numerical examples demonstrate that the given algorithms are stable and efficient and the absolute permeability can be satisfactorily recovered.展开更多
In this paper,we propose using the tailored finite point method(TFPM)to solve the resulting parabolic or elliptic equations when minimizing the Huber regularization based image super-resolution model using the augment...In this paper,we propose using the tailored finite point method(TFPM)to solve the resulting parabolic or elliptic equations when minimizing the Huber regularization based image super-resolution model using the augmented Lagrangian method(ALM).The Hu-ber regularization based image super-resolution model can ameliorate the staircase for restored images.TFPM employs the method of weighted residuals with collocation tech-nique,which helps get more accurate approximate solutions to the equations and reserve more details in restored images.We compare the new schemes with the Marquina-Osher model,the image super-resolution convolutional neural network(SRCNN)and the classical interpolation methods:bilinear interpolation,nearest-neighbor interpolation and bicubic interpolation.Numerical experiments are presented to demonstrate that with the new schemes the quality of the super-resolution images has been improved.Besides these,the existence of the minimizer of the Huber regularization based image super-resolution model and the convergence of the proposed algorithm are also established in this paper.展开更多
Orthogonal nonnegative matrix factorization(ONMF)is widely used in blind image separation problem,document classification,and human face recognition.The model of ONMF can be efficiently solved by the alternating direc...Orthogonal nonnegative matrix factorization(ONMF)is widely used in blind image separation problem,document classification,and human face recognition.The model of ONMF can be efficiently solved by the alternating direction method of multipliers and hierarchical alternating least squares method.When the given matrix is huge,the cost of computation and communication is too high.Therefore,ONMF becomes challenging in the large-scale setting.The random projection is an efficient method of dimensionality reduction.In this paper,we apply the random projection to ONMF and propose two randomized algorithms.Numerical experiments show that our proposed algorithms perform well on both simulated and real data.展开更多
In this paper,we accomplish the unified convergence analysis of a second-order method of multipliers(i.e.,a second-order augmented Lagrangian method)for solving the conventional nonlinear conic optimization problems.S...In this paper,we accomplish the unified convergence analysis of a second-order method of multipliers(i.e.,a second-order augmented Lagrangian method)for solving the conventional nonlinear conic optimization problems.Specifically,the algorithm that we investigate incorporates a specially designed nonsmooth(generalized)Newton step to furnish a second-order update rule for the multipliers.We first show in a unified fashion that under a few abstract assumptions,the proposed method is locally convergent and possesses a(nonasymptotic)superlinear convergence rate,even though the penalty parameter is fixed and/or the strict complementarity fails.Subsequently,we demonstrate that for the three typical scenarios,i.e.,the classic nonlinear programming,the nonlinear second-order cone programming and the nonlinear semidefinite programming,these abstract assumptions are nothing but exactly the implications of the iconic sufficient conditions that are assumed for establishing the Q-linear convergence rates of the method of multipliers without assuming the strict complementarity.展开更多
基金Chao Ding’s research was supported by the National Natural Science Foundation of China(Nos.11671387,11531014,and 11688101)Beijing Natural Science Foundation(No.Z190002)+6 种基金Xu-Dong Li’s research was supported by the National Key R&D Program of China(No.2020YFA0711900)the National Natural Science Foundation of China(No.11901107)the Young Elite Scientists Sponsorship Program by CAST(No.2019QNRC001)the Shanghai Sailing Program(No.19YF1402600)the Science and Technology Commission of Shanghai Municipality Project(No.19511120700)Xin-Yuan Zhao’s research was supported by the National Natural Science Foundation of China(No.11871002)the General Program of Science and Technology of Beijing Municipal Education Commission(No.KM201810005004).
文摘In this paper,we provide some gentle introductions to the recent advance in augmented Lagrangian methods for solving large-scale convex matrix optimization problems(cMOP).Specifically,we reviewed two types of sufficient conditions for ensuring the quadratic growth conditions of a class of constrained convex matrix optimization problems regularized by nonsmooth spectral functions.Under a mild quadratic growth condition on the dual of cMOP,we further discussed the R-superlinear convergence of the Karush-Kuhn-Tucker(KKT)residuals of the sequence generated by the augmented Lagrangian methods(ALM)for solving convex matrix optimization problems.Implementation details of the ALM for solving core convex matrix optimization problems are also provided.
基金Supported by the National Natural Science Foundation of China(Grant Nos.6157209961320106008+2 种基金91230103)National Science and Technology Major Project(Grant Nos.2013ZX040050212014ZX04001011)
文摘Tensor robust principal component analysis（TRPCA） problem aims to separate a low-rank tensor and a sparse tensor from their sum. This problem has recently attracted considerable research attention due to its wide range of potential applications in computer vision and pattern recognition. In this paper, we propose a new model to deal with the TRPCA problem by an alternation minimization algorithm along with two adaptive rankadjusting strategies. For the underlying low-rank tensor, we simultaneously perform low-rank matrix factorizations to its all-mode matricizations; while for the underlying sparse tensor,a soft-threshold shrinkage scheme is applied. Our method can be used to deal with the separation between either an exact or an approximate low-rank tensor and a sparse one. We established the subsequence convergence of our algorithm in the sense that any limit point of the iterates satisfies the KKT conditions. When the iteration stops, the output will be modified by applying a high-order SVD approach to achieve an exactly low-rank final result as the accurate rank has been calculated. The numerical experiments demonstrate that our method could achieve better results than the compared methods.
基金State Foundstion of Ph.D Units of China(2003-05)under Grant 20020141013the NNSF(10471015)of Liaoning Province,China.
文摘This paper formulates a two-dimensional strip packing problem as a non- linear programming （NLP） problem and establishes the first-order optimality conditions for the NLP problem. A numerical algorithm for solving this NLP problem is given to find exact solutions to strip-packing problems involving up to 10 items. Approximate solutions can be found for big-sized problems by decomposing the set of items into small-sized blocks of which each block adopts the proposed numerical algorithm. Numerical results show that the approximate solutions to big-sized problems obtained by this method are superior to those by NFDH, FFDH and BFDH approaches.
基金supported by the National Key R&D Program of China(Project No.2022YFA1004000)by the Natural Science Foundation of China(Project No.12371298).
文摘In this paper,we analyze the convergence properties of a stochastic augmented Lagrangian method for solving stochastic convex programming problems with inequality constraints.Approximation models for stochastic convex programming problems are constructed from stochastic observations of real objective and constraint functions.Based on relations between solutions of the primal problem and solutions of the dual problem,it is proved that the convergence of the algorithm from the perspective of the dual problem.Without assumptions on how these random models are generated,when estimates are merely sufficiently accurate to the real objective and constraint functions with high enough,but fixed,probability,the method converges globally to the optimal solution almost surely.In addition,sufficiently accurate random models are given under different noise assumptions.We also report numerical results that show the good performance of the algorithm for different convex programming problems with several random models.
基金the National Natural Science Foundation of China(Nos.11991020,11631013,11971372,11991021,11971089 and 11731013)the Strategic Priority Research Program of Chinese Academy of Sciences(No.XDA27000000)Dalian High-Level Talent Innovation Project(No.2020RD09)。
文摘The augmented Lagrangian function and the corresponding augmented Lagrangian method are constructed for solving a class of minimax optimization problems with equality constraints.We prove that,under the linear independence constraint qualification and the second-order sufficiency optimality condition for the lower level problem and the second-order sufficiency optimality condition for the minimax problem,for a given multiplier vectorμ,the rate of convergence of the augmented Lagrangian method is linear with respect to||μu-μ^(*)||and the ratio constant is proportional to 1/c when the ratio|μ-μ^(*)||/c is small enough,where c is the penalty parameter that exceeds a threshold c_(*)>O andμ^(*)is the multiplier corresponding to a local minimizer.Moreover,we prove that the sequence of multiplier vectors generated by the augmented Lagrangian method has at least Q-linear convergence if the sequence of penalty parameters(ck)is bounded and the convergence rate is superlinear if(ck)is increasing to infinity.Finally,we use a direct way to establish the rate of convergence of the augmented Lagrangian method for the minimax problem with a quadratic objective function and linear equality constraints.
文摘In this work,we propose a second-order model for image denoising by employing a novel potential function recently developed in Zhu(J Sci Comput 88:46,2021)for the design of a regularization term.Due to this new second-order derivative based regularizer,the model is able to alleviate the staircase effect and preserve image contrast.The augmented Lagrangian method(ALM)is utilized to minimize the associated functional and convergence analysis is established for the proposed algorithm.Numerical experiments are presented to demonstrate the features of the proposed model.
基金supported by the National Key Research and Development Project(Grant No.2020YFA0709800)NSFC(Grant No.12071289)+4 种基金Shanghai Municipal Science and Technology Major Project(2021SHZDZX0102)supported by the National Key R&D Program of China(2020YFA0712000)NSFC(under grant numbers 11822111,11688101)the science challenge project(No.TZ2018001)youth innovation promotion association(CAS).
文摘This paper is concerned with a novel deep learning method for variational problems with essential boundary conditions.To this end,wefirst reformulate the original problem into a minimax problem corresponding to a feasible augmented La-grangian,which can be solved by the augmented Lagrangian method in an infinite dimensional setting.Based on this,by expressing the primal and dual variables with two individual deep neural network functions,we present an augmented Lagrangian deep learning method for which the parameters are trained by the stochastic optimiza-tion method together with a projection technique.Compared to the traditional penalty method,the new method admits two main advantages:i)the choice of the penalty parameter isflexible and robust,and ii)the numerical solution is more accurate in the same magnitude of computational cost.As typical applications,we apply the new ap-proach to solve elliptic problems and(nonlinear)eigenvalue problems with essential boundary conditions,and numerical experiments are presented to show the effective-ness of the new method.
基金supported by the 10 plus 10 project of Tongji University(No.4260141304/004/010).
文摘.In this paper,an augmented Lagrangian Uzawa iterative method is developed and analyzed for solving a class of double saddle-point systems with semidefinite(2,2)block.Convergence of the iterativemethod is proved under the assumption that the double saddle-point problem exists a unique solution.An application of the iterative method to the double saddle-point systems arising from the distributed Lagrange multiplier/fictitious domain(DLM/FD)finite element method for solving elliptic interface problems is also presented,in which the existence and uniqueness of the double saddle-point system is guaranteed by the analysis of the DLM/FD finite element method.Numerical experiments are conducted to validate the theoretical results and to study the performance of the proposed iterative method.
基金The author was supported by the NSFC Grant No.11871029.
文摘It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality.Recently,we have proposed a unified algorithmic framework which can guide us to construct the solution methods for solving these monotone variational inequalities.In this work,we revisit two full Jacobian decomposition of the augmented Lagrangian methods for separable convex programming which we have studied a few years ago.In particular,exploiting this framework,we are able to give a very clear and elementary proof of the convergence of these solution methods.
基金The author thanks to his supervisor Prof.Lin Qun(Institute of Computational Mathematics,Chinese Academy of Sciences),Prof.Tai Xuecheng,Prof.S.I.Aanonsen(CIPR,University of Bergen)for useful suggestions.This work is also supported by China NSFC(NO.11101084)and NSFC(NO.11101081).
文摘In this paper,operator splitting scheme for dynamic reservoir characterization by binary level set method is employed.For this problem,the absolute permeability of the two-phase porous medium flow can be simulated by the constrained augmented Lagrangian optimization method with well data and seismic time-lapse data.By transforming the constrained optimization problem in an unconstrained one,the saddle point problem can be solved by Uzawas algorithms with operator splitting scheme,which is based on the essence of binary level set method.Both the simple and complicated numerical examples demonstrate that the given algorithms are stable and efficient and the absolute permeability can be satisfactorily recovered.
基金partially supported by the NSFC Project Nos.12001529,12025104,11871298,81930119.
文摘In this paper,we propose using the tailored finite point method(TFPM)to solve the resulting parabolic or elliptic equations when minimizing the Huber regularization based image super-resolution model using the augmented Lagrangian method(ALM).The Hu-ber regularization based image super-resolution model can ameliorate the staircase for restored images.TFPM employs the method of weighted residuals with collocation tech-nique,which helps get more accurate approximate solutions to the equations and reserve more details in restored images.We compare the new schemes with the Marquina-Osher model,the image super-resolution convolutional neural network(SRCNN)and the classical interpolation methods:bilinear interpolation,nearest-neighbor interpolation and bicubic interpolation.Numerical experiments are presented to demonstrate that with the new schemes the quality of the super-resolution images has been improved.Besides these,the existence of the minimizer of the Huber regularization based image super-resolution model and the convergence of the proposed algorithm are also established in this paper.
基金the National Natural Science Foundation of China(No.11901359)Shandong Provincial Natural Science Foundation(No.ZR2019QA017)。
文摘Orthogonal nonnegative matrix factorization(ONMF)is widely used in blind image separation problem,document classification,and human face recognition.The model of ONMF can be efficiently solved by the alternating direction method of multipliers and hierarchical alternating least squares method.When the given matrix is huge,the cost of computation and communication is too high.Therefore,ONMF becomes challenging in the large-scale setting.The random projection is an efficient method of dimensionality reduction.In this paper,we apply the random projection to ONMF and propose two randomized algorithms.Numerical experiments show that our proposed algorithms perform well on both simulated and real data.
基金supported by National Natural Science Foundation of China (Grant No. 11801158)the Hunan Provincial Natural Science Foundation of China (Grant No. 2019JJ50040)+2 种基金the Fundamental Research Funds for the Central Universities in Chinasupported by National Natural Science Foundation of China (Grant No. 11871002)the General Program of Science and Technology of Beijing Municipal Education Commission (Grant No. KM201810005004)
文摘In this paper,we accomplish the unified convergence analysis of a second-order method of multipliers(i.e.,a second-order augmented Lagrangian method)for solving the conventional nonlinear conic optimization problems.Specifically,the algorithm that we investigate incorporates a specially designed nonsmooth(generalized)Newton step to furnish a second-order update rule for the multipliers.We first show in a unified fashion that under a few abstract assumptions,the proposed method is locally convergent and possesses a(nonasymptotic)superlinear convergence rate,even though the penalty parameter is fixed and/or the strict complementarity fails.Subsequently,we demonstrate that for the three typical scenarios,i.e.,the classic nonlinear programming,the nonlinear second-order cone programming and the nonlinear semidefinite programming,these abstract assumptions are nothing but exactly the implications of the iconic sufficient conditions that are assumed for establishing the Q-linear convergence rates of the method of multipliers without assuming the strict complementarity.
