大规模非线性约束优化问题的滤子方法及其应用

Many applications give rise to unconstrained optimization problems with thousands or millions of variables and are of higher importance in recent years. Different from small and moderate progblems, problems of this size can be solved efficiently only if the storage and computational costs of the optimization algorithm can be kept at a tolerable level. .Firstly, the project will utilize the filter idea and develop inexact algorithms and limited memory methods, expecting to reduce the CPU time and the amount of memory. .Secondly, the project will extend the generalized pattern search method with filter idea and line search technique for solving noninear constrained optimization. The new algorithm does not compute or approximate any derivatives, penalty constants, or Lagrange multipliers which lead to the new results of theory in smooth (nonsmooth) optimization. .Thirdly, by using non-monotone technique in the filter method, the study of the project will establish a proposed algorithm which can overcome the Maratos effect without using second order correction step and conduct detailed analysis. .Finally, the project will apply the above results to the numerical computation of large scale variational inequality and complementarity. .The work of the project agrees with the area of research and development,and is of great theoretic and practical importance.

大规模优化问题的数值计算作为最优化的研究方向之一已成为国内外研究的热点。与中小规模的问题不同，只有当CPU计算时间和内存使用量控制在合理范围内时，这类问题才能被有效解决。本项目使用目前受到国际高度重视的滤子方法，发展不精确算法与有限内存法，研究大规模非线性约束优化问题的数值计算，期望有效降低CPU计算时间、内存使用量；推广广义模式搜索方法的理论，并结合滤子思想与线搜索技术，解决非线性约束优化问题，避免计算或近似任何的导数，也无需计算任何惩罚因子或拉格朗日乘子信息，期待在光滑（非光滑）的非线性约束优化领域有新的理论结果；在滤子方法中使用非单调技术，在不使用二阶校正步的条件下，试图克服Maratos效应和函数形状狭窄的情况，分析产生作用的机理；将研究成果应用于大规模变分不等式和互补问题的数值实现。本项目的工作契合该领域的研究思路与发展方向，具有理论与实践意义。

近年来，滤子方法得到了国内外学者的高度重视和广泛研究。但是，大规模非线性约束优化问题的滤子方法还没有得到针对性、系统性的研究。随着最优化的应用越来越广，对于这类问题的数值算法的研究是一个迫在眉睫的课题，具有极高的理论价值和广阔的应用前景。.本项目使用目前受到国际高度重视的滤子方法，发展不精确算法与有限内存法，研究大规模非线性约束优化问题的数值计算，期望有效降低CPU计算时间、内存使用量；将研究成果应用于大规模变分不等式和互补问题的数值实现。.项目研究的重要结果：.1.发展了渐弱滤子思想，提出了渐弱滤子线搜索算法解非线性等式约束优化问题。渐弱滤子的封套随着步长趋于零而变得越来越薄，使得新算法比以往的滤子方法更容易接受试探点，对大规模问题的数值计算比较有利。.2.提出了不精确的投影Hessian算法，该算法借助数值代数中的迭代算法计算两个线性方程组的不精确解，从而得到搜索方向，有效地降低了计算量，对大规模优化问题能明显降低CPU的计算时间。.3.在渐弱滤子思想的基础上加以改进，并与一种修改的子问题相结合，提出了渐弱滤子线搜索算法解非线性不等式约束优化问题。证明了当搜索步长充分小时，试探点能被滤子接受，从而避免算法进入可行性恢复阶段，解决了滤子方法的不足之处。进一步，我们将渐弱滤子思想推广到信赖域算法，得到了同样的结论。.4.非线性等式与不等式系统是应用数学、最优化理论、变分不等式、均衡问题等领域的核心问题。作为滤子方法的一个应用，采用滤子思想来研究此类问题的数值计算，得到了较好的效果。.本项目的成果契合该领域的研究思路与发展方向，在石油勘探、航空航天、数据挖掘等领域具有广阔的应用前景。