大规模非光滑有界约束问题的优化方法研究

There exist a wide range of applications in engineering, finance and the optimal control etc. for nonsmooth box constrained optimization problems, which is one of the difficult problems to be solved. With the development of social economy, the large-scale nonsmooth box constrained problems become more and more difficult for them to be solved. The difficulty and the time spent are unpredictable for solving these problems when the dimension increases. It is a very meaningful work to find some effective methods for those problems. And it will enrich the theory of the nonsmooth box constrained optimization.. The purpose of this work is listed as follows: (1) The conjugate gradient methods using projected technology for large-scale nonsmooth box constrained optimization problems are studied and some good convergences are obtained; (2) More efficient algorithms are designed by combining with the conjugate gradient methods and active-set methods and using recognition technology; (3) For numerical experiment, nonsmooth box constrained optimization problems with large-scale dimension (strive to reach 50,000 variables) are successfully solved by Matlab and Fortran software.

非光滑有界约束优化在工程、金融和最优控制等不同领域都有广泛的应用背景，是难求解的问题之一。随着社会经济的发展，大规模非光滑有界约束问题越来越多，可求解的难度也越来越大。因为随着问题维数的增加，求解的难度和所花费的时间是难以预料的。所以寻找求解大规模非光滑有界约束问题的方法是一项很有意义的研究工作，同时也将丰富非光滑有界约束问题求解方面的理论体系。. 鉴于此，本项目重点研究：第一、研究求解大规模非光滑有界约束问题的共轭梯度算法，同时将其与投影技术结合，获得理想的收敛性；第二、将共轭梯度方法与积极集法相结合，利用识别技术，设计出效率更高的算法；第三、数值结果方面，利用Matlab和Fortran语言来编译算法程序，成功求解更高维数(争取达到50,000个变量)的非光滑有界约束问题。

非光滑优化问题具有广泛的应用背景，本项目主要针对非光滑问题、光滑优化问题、非线性方程组问题等进行较为深入的研究工作，设计求解优化问题的有效算法，分析其理论性质，并通过问题进行验证算法的有效性。. 具体研究内容和结果如下：设计了求解非光滑问题的有效集拟牛顿共轭梯度算法，利用了识别技术，证明了算法的全局收敛性；充分利用有限记忆拟牛顿方法存储量小的优点，结合子空间技术，应用于盒子约束的非光滑问题，获得了算法的全局收敛性，验证了11000维的大规模问题；关于无约束的非光滑问题，定义了三项共轭梯度公式，结合MY正则化技术，证明了算法具有充分下降性、信頼域特征和全局收敛性，成功求解了规模为10万维的问题；定义了一个修正WWP线搜索技术，证明了PRP共轭梯度算法和BFGS拟牛顿方法在此技术下对非凸函数的全局收敛性，同时进行了数值实验，证实了新技术的有效性；结合投影技术，定义了理想迭代点和不理想迭代点的分离抛物曲面，设计了投影PRP共轭梯度算法和投影BFGS算法，建立了算法的全局收敛性；充分利用加速技术和回溯线搜索技术，设计了一个三项共轭梯度算法，成功应用于非线性方程组问题，获得了算法的全局收敛性，验证了10万维的非线性方程组问题，同时也能用于图像恢复问题；发现了一个修正线搜索技术，证明了该技术下BFGS方法和Broyden族方法的全局收敛性，验证了工程问题的有效性。. 重要结果：利用投影技术，设计了投影PRP方法和BFGS方法，获得了全局收敛性，部分解决了近50年的无约束优化的两个公开问题。. 关键数据：能成功求解有界约束11000维的非光滑问题，之前求解的最大规模是1000维，我们提升了11倍。. 科学意义：利用投影技术设计算法，解决了近半个世纪的公开问题，开辟了一条设计优化算法的新途径；通过修正线搜索技术克服一些不理想的下降量，同样能获得较为理想的数值算法，并用于一些公开问题。