We present a Hermitian and skew-Herrnitian splitting （HSS） iteration method for solving large sparse continuous Sylvester equations with non-Hermitian and positive definite/semi- definite matrices. The unconditional...We present a Hermitian and skew-Herrnitian splitting （HSS） iteration method for solving large sparse continuous Sylvester equations with non-Hermitian and positive definite/semi- definite matrices. The unconditional convergence of the HSS iteration method is proved and an upper bound on the convergence rate is derived. Moreover, to reduce the computing cost, we establish an inexact variant of the HSS iteration method and analyze its convergence property in detail. Numerical results show that the HSS iteration method and its inexact variant are efficient and robust solvers for this class of continuous Sylvester equations.展开更多
Inexact Newton methods are constructed by combining Newton＇s method with another iterative method that is used to solve the Newton equations inexactly. In this paper, we establish two semilocal convergence theorems f...Inexact Newton methods are constructed by combining Newton＇s method with another iterative method that is used to solve the Newton equations inexactly. In this paper, we establish two semilocal convergence theorems for the inexact Newton methods. When these two theorems are specified to Newton＇s method, we obtain a different Newton-Kantorovich theorem about Newton＇s method. When the iterative method for solving the Newton equations is specified to be the splitting method, we get two estimates about the iteration steps for the special inexact Newton methods.展开更多
In this paper, the non-quasi-Newton＇s family with inexact line search applied to unconstrained optimization problems is studied. A new update formula for non-quasi-Newton＇s family is proposed. It is proved that the ...In this paper, the non-quasi-Newton＇s family with inexact line search applied to unconstrained optimization problems is studied. A new update formula for non-quasi-Newton＇s family is proposed. It is proved that the constituted algorithm with either Wolfe-type or Armijotype line search converges globally and Q-superlinearly if the function to be minimized has Lipschitz continuous gradient.展开更多
To solve nonlinear complementarity problems （NCP）, at each iteration, the classical proximal point algorithm solves a well-conditioned sub-NCP while the Logarithmic-Quadratic Proximal （LQP） method solves a system ...To solve nonlinear complementarity problems （NCP）, at each iteration, the classical proximal point algorithm solves a well-conditioned sub-NCP while the Logarithmic-Quadratic Proximal （LQP） method solves a system of nonlinear equations （LQP system）. This paper presents a practical LQP method-based prediction-correction method for NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed restriction, and the new iterate （the corrector） is computed directly by an explicit formula derived from the original LQP method. The implementations are very easy to be carried out. Global convergence of the method is proved under the same mild assumptions as the original LQP method. Finally, numerical results for traffic equilibrium problems are provided to verify that the method is effective for some practical problems.展开更多
The modified Hermitian and skew-Hermitian splitting （MHSS） iteration method and preconditioned MHSS （PMHSS） iteration method were introduced respectively. In the paper, on the basis of the MHSS iteration method, w...The modified Hermitian and skew-Hermitian splitting （MHSS） iteration method and preconditioned MHSS （PMHSS） iteration method were introduced respectively. In the paper, on the basis of the MHSS iteration method, we present a PMHSS iteration method for solving large sparse continuous Sylvester equations with non-Hermitian and complex symmetric positive definite/semi-definite matrices. Under suitable conditions, we prove the convergence of the PMHSS iteration method and discuss the spectral properties of the preconditioned matrix. Moreover, to reduce the computing cost, we establish an inexact variant of the PMHSS iteration method and analyze its convergence property in detail. Numerical results show that the PMHSS iteration method and its inexact variant are efficient and robust solvers for this class of continuous Sylvester equations.展开更多
Numerical treatment of engineering application problems often eventually results in a solution of systems of linear or nonlinear equations.The solution process using digital computational devices usually takes tremend...Numerical treatment of engineering application problems often eventually results in a solution of systems of linear or nonlinear equations.The solution process using digital computational devices usually takes tremendous time due to the extremely large size encountered in most real-world engineering applications.So,practical solvers for systems of linear and nonlinear equations based on multi graphic process units（GPUs）are proposed in order to accelerate the solving process.In the linear and nonlinear solvers,the preconditioned bi-conjugate gradient stable（PBi-CGstab）method and the Inexact Newton method are used to achieve the fast and stable convergence behavior.Multi-GPUs are utilized to obtain more data storage that large size problems need.展开更多
We first propose a new class of smoothing functions for the non- linear complementarity function which contains the well-known Chen-Harker- Kanzow-Smale smoothing function and Huang-Han-Chen smoothing function as spec...We first propose a new class of smoothing functions for the non- linear complementarity function which contains the well-known Chen-Harker- Kanzow-Smale smoothing function and Huang-Han-Chen smoothing function as special cases, and then present a smoothing inexact Newton algorithm for the P0 nonlinear complementarity problem. The global convergence and local superlinear convergence are established. Preliminary numerical results indicate the feasibility and efficiency of the algorithm.展开更多
The proximal-based decomposition method was originally proposed by Chen and Teboulle （Math. Programming, 1994, 64：81-101 for solving corrvex minimization problems. This paper extends it to solving monotone variation...The proximal-based decomposition method was originally proposed by Chen and Teboulle （Math. Programming, 1994, 64：81-101 for solving corrvex minimization problems. This paper extends it to solving monotone variational inequalities associated with separable structures with the improvements that the restrictive assumptions on the involved parameters are much relaxed, and thus makes it practical to solve the subproblems easily. Without additional assumptions, global convergence of the new method is proved under the same mild assumptions on the problem＇s data as the original method.展开更多
We propose an inexact affine scaling Levenberg-Marquardt method for solving bound-constrained semismooth equations under the local error bound assumption which is much weaker than the standard nonsingularity condition...We propose an inexact affine scaling Levenberg-Marquardt method for solving bound-constrained semismooth equations under the local error bound assumption which is much weaker than the standard nonsingularity condition. The affine scaling Levenberg-Marquardt equation is based on a minimization of the squared Euclidean norm of linearized model adding a quadratic affine scaling matrix to find a solution which belongs to the bounded constraints on variable. The global convergence and the superlinear convergence rate are proved.Numerical results show that the new algorithm is efficient.展开更多
The proximal alternating linearized minimization(PALM)method suits well for solving blockstructured optimization problems,which are ubiquitous in real applications.In the cases where subproblems do not have closed-for...The proximal alternating linearized minimization(PALM)method suits well for solving blockstructured optimization problems,which are ubiquitous in real applications.In the cases where subproblems do not have closed-form solutions,e.g.,due to complex constraints,infeasible subsolvers are indispensable,giving rise to an infeasible inexact PALM(PALM-I).Numerous efforts have been devoted to analyzing the feasible PALM,while little attention has been paid to the PALM-I.The usage of the PALM-I thus lacks a theoretical guarantee.The essential difficulty of analysis consists in the objective value nonmonotonicity induced by the infeasibility.We study in the present work the convergence properties of the PALM-I.In particular,we construct a surrogate sequence to surmount the nonmonotonicity issue and devise an implementable inexact criterion.Based upon these,we manage to establish the stationarity of any accumulation point,and moreover,show the iterate convergence and the asymptotic convergence rates under the assumption of the Lojasiewicz property.The prominent advantages of the PALM-I on CPU time are illustrated via numerical experiments on problems arising from quantum physics and 3-dimensional anisotropic frictional contact.展开更多
Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact cus...Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint.We design two types of inexact error criteria for the subproblems.The first one is absolutely summable error criterion,under which both subproblems can be solved inexactly.When one of the two subproblems is easily solved,we propose another novel error criterion which is easier to implement,namely relative error criterion.The relative error criterion only involves one parameter,which is more implementable.We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms.The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.展开更多
In this paper, a unified matrix recovery model was proposed for diverse corrupted matrices. Resulting from the separable structure of the proposed model, the convex optimization problem can be solved efficiently by ad...In this paper, a unified matrix recovery model was proposed for diverse corrupted matrices. Resulting from the separable structure of the proposed model, the convex optimization problem can be solved efficiently by adopting an inexact augmented Lagrange multiplier (IALM) method. Additionally, a random projection accelerated technique (IALM+RP) was adopted to improve the success rate. From the preliminary numerical comparisons, it was indicated that for the standard robust principal component analysis (PCA) problem, IALM+RP was at least two to six times faster than IALM with an insignificant reduction in accuracy; and for the outlier pursuit (OP) problem, IALM+RP was at least 6.9 times faster, even up to 8.3 times faster when the size of matrix was 2 000×2 000.展开更多
In this paper,we consider the problem of computing the smallest enclosing ball(SEB)of a set of m balls in Rn,where the product mn is large.We first approximate the non-differentiable SEB problem by its log-exponentia...In this paper,we consider the problem of computing the smallest enclosing ball(SEB)of a set of m balls in Rn,where the product mn is large.We first approximate the non-differentiable SEB problem by its log-exponential aggregation function and then propose a computationally efficient inexact Newton-CG algorithm for the smoothing approximation problem by exploiting its special(approximate)sparsity structure.The key difference between the proposed inexact Newton-CG algorithm and the classical Newton-CG algorithm is that the gradient and the Hessian-vector product are inexactly computed in the proposed algorithm,which makes it capable of solving the large-scale SEB problem.We give an adaptive criterion of inexactly computing the gradient/Hessian and establish global convergence of the proposed algorithm.We illustrate the efficiency of the proposed algorithm by using the classical Newton-CG algorithm as well as the algorithm from Zhou et al.(Comput Optim Appl 30:147–160,2005)as benchmarks.展开更多
A trust-region algorithm is presented for a nonlinear optimization problem of equality-constraints. The characterization of the algorithm is using inexact gradient information. Global convergence results are demonstra...A trust-region algorithm is presented for a nonlinear optimization problem of equality-constraints. The characterization of the algorithm is using inexact gradient information. Global convergence results are demonstrated where the gradient values are obeyed a simple relative error condition.展开更多
To improve the accuracy of runoff forecasting,an uncertain multiple linear regression(UMLR) model is presented in this study. The proposed model avoids the transfer of random error generated in the independent variabl...To improve the accuracy of runoff forecasting,an uncertain multiple linear regression(UMLR) model is presented in this study. The proposed model avoids the transfer of random error generated in the independent variable to the dependent variable, as this affects prediction accuracy. On this basis, an inexact two-stage stochastic programming(ITSP) model is used for crop planting structure optimization(CPSO) with the inputs that are interval flow values under different probabilities obtained from the UMLR model. The developed system, in which the UMLR model for runoff forecasting and the ITSP model for crop planting structure optimization are integrated, is applied to a real case study. The aim of the developed system is to optimize crops planting area with limited available water resources base on the downstream runoff forecasting in order to obtain the maximum system benefit in the future. The solution obtained can demonstrate the feasibility and suitability of the developed system, and help decision makers to identify reasonable crop planting structure under multiple uncertainties.展开更多
In this paper, a S-CR method with inexact solvers on the subdomains is presented, and then its convergence property is proved under very general conditions. This result is important because it guarantees the effective...In this paper, a S-CR method with inexact solvers on the subdomains is presented, and then its convergence property is proved under very general conditions. This result is important because it guarantees the effectiveness of the Schwarz alternating method when executed on message-passing distributed memory multiprocessor system.展开更多
We propose an inexact Newton method with a filter line search algorithm for nonconvex equality constrained optimization. Inexact Newton＇s methods are needed for large-scale applications which the iteration matrix can...We propose an inexact Newton method with a filter line search algorithm for nonconvex equality constrained optimization. Inexact Newton＇s methods are needed for large-scale applications which the iteration matrix cannot be explicitly formed or factored. We incorporate inexact Newton strategies in filter line search, yielding algorithm that can ensure global convergence. An analysis of the global behavior of the algorithm and numerical results on a collection of test problems are presented.展开更多
文摘We present a Hermitian and skew-Herrnitian splitting （HSS） iteration method for solving large sparse continuous Sylvester equations with non-Hermitian and positive definite/semi- definite matrices. The unconditional convergence of the HSS iteration method is proved and an upper bound on the convergence rate is derived. Moreover, to reduce the computing cost, we establish an inexact variant of the HSS iteration method and analyze its convergence property in detail. Numerical results show that the HSS iteration method and its inexact variant are efficient and robust solvers for this class of continuous Sylvester equations.
基金Supported by State Key Laboratory of Scientific/Engineering Computing,Chinese Academy of Sciencesthe National Natural Science Foundation of China (10571059,10571060).
文摘Inexact Newton methods are constructed by combining Newton＇s method with another iterative method that is used to solve the Newton equations inexactly. In this paper, we establish two semilocal convergence theorems for the inexact Newton methods. When these two theorems are specified to Newton＇s method, we obtain a different Newton-Kantorovich theorem about Newton＇s method. When the iterative method for solving the Newton equations is specified to be the splitting method, we get two estimates about the iteration steps for the special inexact Newton methods.
文摘In this paper, the non-quasi-Newton＇s family with inexact line search applied to unconstrained optimization problems is studied. A new update formula for non-quasi-Newton＇s family is proposed. It is proved that the constituted algorithm with either Wolfe-type or Armijotype line search converges globally and Q-superlinearly if the function to be minimized has Lipschitz continuous gradient.
文摘To solve nonlinear complementarity problems （NCP）, at each iteration, the classical proximal point algorithm solves a well-conditioned sub-NCP while the Logarithmic-Quadratic Proximal （LQP） method solves a system of nonlinear equations （LQP system）. This paper presents a practical LQP method-based prediction-correction method for NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed restriction, and the new iterate （the corrector） is computed directly by an explicit formula derived from the original LQP method. The implementations are very easy to be carried out. Global convergence of the method is proved under the same mild assumptions as the original LQP method. Finally, numerical results for traffic equilibrium problems are provided to verify that the method is effective for some practical problems.
文摘The modified Hermitian and skew-Hermitian splitting （MHSS） iteration method and preconditioned MHSS （PMHSS） iteration method were introduced respectively. In the paper, on the basis of the MHSS iteration method, we present a PMHSS iteration method for solving large sparse continuous Sylvester equations with non-Hermitian and complex symmetric positive definite/semi-definite matrices. Under suitable conditions, we prove the convergence of the PMHSS iteration method and discuss the spectral properties of the preconditioned matrix. Moreover, to reduce the computing cost, we establish an inexact variant of the PMHSS iteration method and analyze its convergence property in detail. Numerical results show that the PMHSS iteration method and its inexact variant are efficient and robust solvers for this class of continuous Sylvester equations.
文摘Numerical treatment of engineering application problems often eventually results in a solution of systems of linear or nonlinear equations.The solution process using digital computational devices usually takes tremendous time due to the extremely large size encountered in most real-world engineering applications.So,practical solvers for systems of linear and nonlinear equations based on multi graphic process units（GPUs）are proposed in order to accelerate the solving process.In the linear and nonlinear solvers,the preconditioned bi-conjugate gradient stable（PBi-CGstab）method and the Inexact Newton method are used to achieve the fast and stable convergence behavior.Multi-GPUs are utilized to obtain more data storage that large size problems need.
文摘We first propose a new class of smoothing functions for the non- linear complementarity function which contains the well-known Chen-Harker- Kanzow-Smale smoothing function and Huang-Han-Chen smoothing function as special cases, and then present a smoothing inexact Newton algorithm for the P0 nonlinear complementarity problem. The global convergence and local superlinear convergence are established. Preliminary numerical results indicate the feasibility and efficiency of the algorithm.
基金the National Natural Science Foundation of China(No.70671024)the Na-tional High-Tech Research and Development Program of China(863 Program)(No.2006AA11Z209)
文摘The proximal-based decomposition method was originally proposed by Chen and Teboulle （Math. Programming, 1994, 64：81-101 for solving corrvex minimization problems. This paper extends it to solving monotone variational inequalities associated with separable structures with the improvements that the restrictive assumptions on the involved parameters are much relaxed, and thus makes it practical to solve the subproblems easily. Without additional assumptions, global convergence of the new method is proved under the same mild assumptions on the problem＇s data as the original method.
基金Supported by National Natural Science Foundation of China(No.11571074)Scientific Research Fund of Hunan Provincial Education Department(No.18A351,17C0393)Natural Science Foundation of Hunan Province(No.2019JJ50105)
文摘We propose an inexact affine scaling Levenberg-Marquardt method for solving bound-constrained semismooth equations under the local error bound assumption which is much weaker than the standard nonsingularity condition. The affine scaling Levenberg-Marquardt equation is based on a minimization of the squared Euclidean norm of linearized model adding a quadratic affine scaling matrix to find a solution which belongs to the bounded constraints on variable. The global convergence and the superlinear convergence rate are proved.Numerical results show that the new algorithm is efficient.
基金supported by National Natural Science Foundation of China(Grant Nos.12125108,11971466,11991021,11991020,12021001 and 12288201)Key Research Program of Frontier Sciences,Chinese Academy of Sciences(Grant No.ZDBS-LY-7022)CAS(the Chinese Academy of Sciences)AMSS(Academy of Mathematics and Systems Science)-PolyU(The Hong Kong Polytechnic University)Joint Laboratory of Applied Mathematics.
文摘The proximal alternating linearized minimization(PALM)method suits well for solving blockstructured optimization problems,which are ubiquitous in real applications.In the cases where subproblems do not have closed-form solutions,e.g.,due to complex constraints,infeasible subsolvers are indispensable,giving rise to an infeasible inexact PALM(PALM-I).Numerous efforts have been devoted to analyzing the feasible PALM,while little attention has been paid to the PALM-I.The usage of the PALM-I thus lacks a theoretical guarantee.The essential difficulty of analysis consists in the objective value nonmonotonicity induced by the infeasibility.We study in the present work the convergence properties of the PALM-I.In particular,we construct a surrogate sequence to surmount the nonmonotonicity issue and devise an implementable inexact criterion.Based upon these,we manage to establish the stationarity of any accumulation point,and moreover,show the iterate convergence and the asymptotic convergence rates under the assumption of the Lojasiewicz property.The prominent advantages of the PALM-I on CPU time are illustrated via numerical experiments on problems arising from quantum physics and 3-dimensional anisotropic frictional contact.
基金the National Natural Science Foundation of China(Nos.11971238 and 11871279)。
文摘Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint.We design two types of inexact error criteria for the subproblems.The first one is absolutely summable error criterion,under which both subproblems can be solved inexactly.When one of the two subproblems is easily solved,we propose another novel error criterion which is easier to implement,namely relative error criterion.The relative error criterion only involves one parameter,which is more implementable.We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms.The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.
基金Supported by National Natural Science Foundation of China (No.51275348)College Students Innovation and Entrepreneurship Training Program of Tianjin University (No.201210056339)
文摘In this paper, a unified matrix recovery model was proposed for diverse corrupted matrices. Resulting from the separable structure of the proposed model, the convex optimization problem can be solved efficiently by adopting an inexact augmented Lagrange multiplier (IALM) method. Additionally, a random projection accelerated technique (IALM+RP) was adopted to improve the success rate. From the preliminary numerical comparisons, it was indicated that for the standard robust principal component analysis (PCA) problem, IALM+RP was at least two to six times faster than IALM with an insignificant reduction in accuracy; and for the outlier pursuit (OP) problem, IALM+RP was at least 6.9 times faster, even up to 8.3 times faster when the size of matrix was 2 000×2 000.
基金the National Natural Science Foundation of China(Nos.11331012 and 11301516).
文摘In this paper,we consider the problem of computing the smallest enclosing ball(SEB)of a set of m balls in Rn,where the product mn is large.We first approximate the non-differentiable SEB problem by its log-exponential aggregation function and then propose a computationally efficient inexact Newton-CG algorithm for the smoothing approximation problem by exploiting its special(approximate)sparsity structure.The key difference between the proposed inexact Newton-CG algorithm and the classical Newton-CG algorithm is that the gradient and the Hessian-vector product are inexactly computed in the proposed algorithm,which makes it capable of solving the large-scale SEB problem.We give an adaptive criterion of inexactly computing the gradient/Hessian and establish global convergence of the proposed algorithm.We illustrate the efficiency of the proposed algorithm by using the classical Newton-CG algorithm as well as the algorithm from Zhou et al.(Comput Optim Appl 30:147–160,2005)as benchmarks.
文摘A trust-region algorithm is presented for a nonlinear optimization problem of equality-constraints. The characterization of the algorithm is using inexact gradient information. Global convergence results are demonstrated where the gradient values are obeyed a simple relative error condition.
基金supported by the National Key Research and Development Plan of China (2016YFC0400207)the National Natural Science Foundation of China (51439006)the National High Technology Research and Development Program of China (2013AA102904)
文摘To improve the accuracy of runoff forecasting,an uncertain multiple linear regression(UMLR) model is presented in this study. The proposed model avoids the transfer of random error generated in the independent variable to the dependent variable, as this affects prediction accuracy. On this basis, an inexact two-stage stochastic programming(ITSP) model is used for crop planting structure optimization(CPSO) with the inputs that are interval flow values under different probabilities obtained from the UMLR model. The developed system, in which the UMLR model for runoff forecasting and the ITSP model for crop planting structure optimization are integrated, is applied to a real case study. The aim of the developed system is to optimize crops planting area with limited available water resources base on the downstream runoff forecasting in order to obtain the maximum system benefit in the future. The solution obtained can demonstrate the feasibility and suitability of the developed system, and help decision makers to identify reasonable crop planting structure under multiple uncertainties.
文摘In this paper, a S-CR method with inexact solvers on the subdomains is presented, and then its convergence property is proved under very general conditions. This result is important because it guarantees the effectiveness of the Schwarz alternating method when executed on message-passing distributed memory multiprocessor system.
基金Supported in part by the National Natural Science Foundation of China under Grant No.11371253Natural Science Foundation of Hunan Province under Grant No.2016JJ2038the project of Scientific Research Fund of Hunan Provincial Education Department under Grant No.14B044
文摘We propose an inexact Newton method with a filter line search algorithm for nonconvex equality constrained optimization. Inexact Newton＇s methods are needed for large-scale applications which the iteration matrix cannot be explicitly formed or factored. We incorporate inexact Newton strategies in filter line search, yielding algorithm that can ensure global convergence. An analysis of the global behavior of the algorithm and numerical results on a collection of test problems are presented.
