兰州大学机构库 >数学与统计学院
求解无约束优化问题和非线性方程组的几种有效算法
Alternative TitleSeveral effective algorithms for solving unconstrained optimization problems and nonlinear equations
李群
Subtype博士
Thesis Advisor郑兵
2021-05-22
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name理学博士
Degree Discipline计算数学
Keyword无约束优化 Unconstrained optimization 非线性方程组 Nonlinear equations 信赖域方法 Trust region method 自适应三次正则化方法 Adaptive cubic regularization method Barzila-Borwein梯度法 Barzilai-Borwein gradient method 修正的Levenberg-Marquardt 方法 Modifed Levenberg-Marquardt method 无导数投影算法 Derivative-free projection algorithm 局部误差界条件 Local error bound conditions 全局收敛性 Global convergence
Abstract

      无约束优化问题在国防建设、工程设计、交通运输、工农业生产、金融贸易等众多领域有着广泛应用. 随着社会经济和信息技术的快速发展, 使得该问题的变量维数急剧增加及结构复杂性增强, 从而有效的求解大规模无约束优化问题显得尤为重要. 同时, 无约束优化问题与非线性方程组问题有着密切的联系, 许多无约束优化问题最后都归结为非线性方程组问题的求解. 此外, 实际工程中的许多问题, 如非线性互补问题、非线性电路问题、力学问题、经济平衡问题等, 也可转化为非线性方程组的求解. 因此, 研究非线性方程组的数值解法具有重要的意义. 本文针对大规模无约束优化问题, 提出了非单调信赖域方法和自适应三次正则化方法; 针对非线性方程组问题, 提出了修正的自适应Levenberg-Marquardt (LM) 方法和无导数投影算法. 具体的研究内容及结果如下:
       首先, 提出了具有Barzilai-Borwein (BB) 参数的简单模型信赖域算法求解无约束优化问题. 在该方法中, 我们给出一个新的信赖域比率, 并在拒绝试步方向上进行线搜索来避免重新求解信赖域子问题. 此方法可看作是谱梯度算法的一种推广. 在适当的条件下, 我们分析了算法的收敛性. 数值实验表明了该算法的有效性和优越性.
      其次, 结合非单调线搜索技巧和修正的自适应三次正则化方法, 提出了求解大规模无约束优化问题的非单调自适应三次正则化方法. 同时, 基于带有正则化参数的截断方程, 提出一个新的自适应BB类参数, 并将其嵌入我们所提的算法中. 另外, 我们分析了该算法的收敛性. 数值实验表明我们的方法有较好的数值性能.  

       再次, 提出了修正的自适应多步LM算法求解非线性方程组问题. 在该方法中我们引入了一个新的LM参数, 并在近似LM步采用线搜索获取加速步长. 在一般的假设条件下, 证明了所提算法的收敛性. 若局部误差界条件成立, 该算法是超线性收敛的. 数值实验表明, 此方法的数值性能要优于一些存在的LM算法. 进一步, 将该方法应用于求解具有一般系数张量的多重线性系统, 数值结果表明了我们方法的可行性和有效性.

       此外, 提出了求解大规模非线性单调方程组问题的两种无导数投影算法, 该方法的搜索方向满足充分下降条件并独立于任何线搜索. 所提的算法可看作是 Bojari 和Eslahchi 提出的求解无约束优化问题的共轭梯度方法和超平面投影技巧相结合的扩展. 此类方法具有低存储且不需要求导数的优点, 因此非常适用于求解大规模非线性单调
方程组. 在适当的假设条件下, 我们证明了所提方法的全局收敛性和Q-线性收敛速度. 数值实验结果表明, 与已有的一些投影算法相比, 我们的方法在迭代次数、运行时间及函数调用次数方面都具有显著的优势.
       最后, 在Dai-Liao 共轭梯度算法的基础上, 提出了求解凸约束的非线性单调方程组的Dai-Liao 型无导数投影算法. 在适当的条件下, 建立了此算法的全局收敛性. 进一步, 将该算法成功地应用于压缩感知中的l1正则化问题.

 

Other Abstract

Unconstrained optimization problems have wide applications in many felds, such as national defense construction, engineering design, transportation, industrial and agricultural production, fnancial and trade. With the rapid development of the social economy and information technology, he dimension of variables of the problems has increased dramatically and the structural complexities have enhanced. Then, it is articularly important to design efective algorithms for solving large-scale unconstrained optimization problems. Meanwhile, unconstrained optimization problems are closely related to nonlinear equations. Many unconstrained optimization problems are fnally reduced to solving nonlinear equations. Moreover, a lot of problems in actual engineering can also be transformed into solving nonlinear equations, such as onlinear
complementarity problems, nonlinear circuit problems,  echanical problems, economic balance problems, etc. Therefore, it is of great signifcance to research the numerical solution of nonlinear equations. In this paper, for large-scale unconstrained optimization problems, we propose the non-monotone trust region method and the non-monotone adaptive cubic regularization method. Considering nonlinear equations, the modifed adaptive Levenberg-Marquardt (LM) method and the derivative-free projection algorithms are proposed. The specifc contents and results are as follows:

 Firstly, we propose a non-monotone trust-region algorithm based on simple model with Barzilai-Borwein (BB) parameter to solve unconstrained optimization problems. In this method, we introduce a new trust-region ratio and perform the line search in the direction of the rejected trial step to avoid resolving the trust-region subproblem. Our method can be regarded as a generalization of the spectral gradient algorithm. Also, the convergence of our algorithm is analyzed. Numerical experiments illustrate the efciency and efectiveness of our proposed method.

Secondly, combined with the modifed adaptive cubic regularization method and non-monotone line search technique, we propose a non-monotone adaptive cubic regularization method for solving large-scale unconstrained optimization problems. Meanwhile, based on the modifed secant equation with the regularization parameter, we propose a new adaptive BB-like parameter and embed it into our proposed algorithm. In addition, we prove the convergence of the proposed algorithm. Numerical experiments show that our method has the better numerical performance.

Thirdly, we propose the modifed adaptive multi-step LM algorithm to solve nonlinear equations. We introduce a new LM parameter in this method and employ a line search for the approximate LM steps to the step length. Under some appropriate conditions, we prove the convergence of the proposed algorithm. If the local error bound condition
holds, the superlinear convergence rate of the algorithm is given. Numerical experiments show the superiority of the proposed method in comparison with other existing LM methods. Moreover, this method is applied to solve multilinear systems with general coefcient tensors. Numerical results illustrate the feasibility and efciency of our method.

Fourthly, we propose two derivative-free algorithms for solving large-scale nonlinear monotone equations, in which the search directions are sufciently descent and independent of the line search. The methods are the extensions of the conjugate gradient methods proposed by Bojari and
Eslahchi combined with the hyperplane projection technique. Our approaches are low storage memory and derivative-free, which make them suitable for large-scale nonlinear monotone equations. Under proper assumptions, we prove the global convergence property and the Q-linear convergence rate of the proposed methods. Finally, numerical experiments show that the proposed methods outperform some existing ones
in terms of the number of iterations, the number of function evaluations, and CPU time.

Finally, based on the Dai-Liao conjugate gradient method, we propose the Dai-Liao type derivative-free projection algorithm for solving large-scale nonlinear monotone equations with convex constraints. Under proper assumptions, we establish the global convergence property of our approach. Furthermore, we successfully apply the proposed method
to solve the l1-regularization problem in compressive sensing.






 

Subject Area数值代数与优化
MOST Discipline Catalogue理学 - 数学 - 计算数学
URL查看原文
Language中文
Other Code262010_120170903950
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/532859
Collection数学与统计学院
Affiliation
兰州大学数学与统计学院
Recommended Citation
GB/T 7714
李群. 求解无约束优化问题和非线性方程组的几种有效算法[D]. 兰州. 兰州大学,2021.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[李群]'s Articles
Baidu academic
Similar articles in Baidu academic
[李群]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[李群]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.