约束优化问题的无导数信赖域算法及其应用研究

This project is a hot subject of the optimization–derivative-free optimization theory, algorithm and its application. However, there are numerous optimization problems in science and engineering where derivatives are unavailable. This subject has a powerful theoretical and practical significance. This project focuses on designing some new derivative-free trust-region algorithms for constrained optimization and studying their applications in practice. First, by using interpolation technology and compressed sensing theory, we construct some new reliable random models with good properties, design the sparse derivative-free trust-region algorithms based on the new modes, and obtain higher computational efficiency, the proposed algorithms strive to solve large scale derivative-free optimization. Second, this project explores the connection between the reliability of the model and the poised sample set, design new self-correcting geometry processes based on the wedge trust region method, and improve the calculation steps. Finally, we deal with the separable optimization problems where derivatives are unavailable, explore their structures and study the characteristics of the model. Combing the classical alternating direction methods, we extend the derivative-free trust-region algorithms to solve such problems, analyze the convergence of the algorithm and the computational complexity. The results in this project will supplement the theories the domain of derivative-free optimization, meanwihle, provide the field of image processing, communication engineering and traffic assignment with new theoretical tools and methods.

本项目是优化领域的热点课题—无导数优化理论、算法及其应用。由于科学工程中大量优化问题的导数不可求或者难以求出，这个课题是很有理论和实际意义的。项目旨在研究约束优化问题的无导数信赖域算法及其在实际中的应用。首先利用插值技术和压缩传感理论，研究建立可靠的随机模型并使其具有良好的性质，在此基础上构造稀疏无导数信赖域算法，并从数值上加以验证，力求提高无导数算法的可解规模；其次，探讨无导数信赖域算法中模型的可靠性与样本集的均衡性之间的关系，基于楔形信赖域方法，设计新的自校正几何步，以避免冗长的计算步骤；最后，在可分离优化问题具有无导数优化特性的前提下，探讨问题的自身结构及模型特征，结合经典的交替方向法，提出求解此类问题的无导数信赖域算法，分析算法的收敛性和计算复杂度。本项目的研究既能丰富和发展无导数优化理论，又能为图像处理、通信工程、交通规划等领域提供新的理论工具和方法。

目前，对无导数算法的研究还比较少。这一缺陷限制了无导数优化的应用范围。为此，项目主持人及其研究生以及多年的合作者在无导数优化算法及应用方面进行了深入的研究。具体包括：.1）我们在求解变分不等式的投影算法中提出了新的搜索方向函数，新算法每步产生的迭代点到最优解的距离严格单调下降，并且当算法产生的迭代点收敛到最优解时，搜索方向函数不收敛到零。在Ｆ单调且连续的假设条件下证明了算法的全局收敛性。数值实验表明了算法的有效性。.2）针对界约束优化问题，首次构造了一个单参数填充函数并证明了其填充性质。以目标函数值和填充函数值构成的数对作为滤子中的元素，将滤子与构造的新的单参数填充函数结合，形成单参数滤子填充函数算法。初始点在整个闭箱内随机产生。.3）对一类无约束随机优化问题的算法进行了研究，提出了一种随机信赖域方法，并证明了该算法在求解具有随机目标的无约束极小化问题时是收敛的。基于信赖域算法框架结合随机 BFGS 方法，可以有效解决目标函数是病态的凸随机优化问题和非凸随机优化问题。数值结果表明，相对于经典的随机算法，该算法能更高效地求解算例中几类典型的大规模随机问题。.4）针对导数不可用且函数值具有噪声的随机优化问题，给出了一种基于随机信赖域框架的无导数算法，该算法利用压缩传感中的理论以大概率构造了目标函数的具有稀疏 Hessian 矩阵的完全二次模型，并结合信赖域算法进行了问题的求解。最后在一定的假设下，我们证明了该算法以接近 1 的概率收敛到二阶驻点。.5）提出了一种内点信赖域算法来解决可分离的约束优化问题，特别该算法可用于解决可分离结构的非凸优化问题。我们借助对数障碍问题的拉格朗日函数给出了松弛变量的具体表达式，进而得到了带有障碍和调比参数的原始对偶非线性系统此系统的解即为原问题的KKT点。 我们对算法进行了收敛性分析, 并做了数值模拟试验。