非光滑约束优化束方法和梯度取样法研究

Nonsmooth optimization is an important branch of optimization studies. It not only has important theoretical value, but also is widely used in practical problems, such as optimal control, engineering design and image processing, etc. This project studies the bundle methods and gradient sampling (GS) methods for solving nonsmooth constrained optimization. The research contents and innovation are: (1) to propose new bundle methods for solving nonsmooth constrained optimization based on upper-lower polyhedral approximation model, DC piecewise affine model, quadratic approximation model and bundle modification strategy, etc; (2) to design strongly sub-feasible GS method, interior point GS method, trust region GS method and filter GS method for nonsmooth constrained optimization, and to improve the proposed methods by the use of nonderivative technique, gradient approximation technique and adaptive technique, in order to reduce the computational cost and accelerate the rate of convergence; (3) to present a new class of nonsmooth method: GS-bundle method by incorporating GS idea into bundle methods; (4) aiming at the special structure of minimax problems, to propose new bundle methods and GS methods for solving constrained minimax problems by combining the incremental technique, nonderivative technique, aggregation technique and polyhedral approximation technique, etc; (5) to analyze and prove the convergence of the algorithms, and set up a large number of numerical experiments to verify the effectiveness of the proposed algorithms.

非光滑优化是最优化研究的重要分支，不仅有重要的理论意义，而且广泛应用于最优控制、工程设计和图像处理等实际领域。本项目研究求解非光滑约束优化的束方法和梯度取样（GS）法。研究内容与创新主要有：（1）基于"上-下"多面体近似模型、DC分片仿射模型、二次逼近模型及bundle修正策略等，提出求解非光滑约束优化的新型束方法；（2）构建非光滑约束优化的强次可行GS方法、内点型GS方法、信赖域型GS方法和filter型GS方法，并利用无导数技术、梯度近似技术和自适应技术等，对提出方法进一步改进，旨在减少计算量、加快收敛速度；（3）探索将GS思想融入到束方法中，提出一类新型非光滑方法：GS-束方法；（4）针对minimax问题的特殊结构，结合增量型技术、无导数技术、聚集技术和多面体近似技术等，提出约束minimax问题的束方法和GS方法；（5）分析论证算法的收敛性，并进行大量数值试验，验证算法的有效性。

非光滑优化是最优化研究的重要分支，广泛应用于最优控制、图像处理、数据挖掘和机器学习等实际领域。本项目研究求解非光滑优化的新型高效数值方法，研究成果主要有：1）提出了求解非光滑优化问题的若干新型束方法，包括强次可行束方法、交替线性化束方法、拟牛顿加速束方法、带bundle修正策略的可行点束方法、部分割平面模型束方法等。2）分别针对非光滑不等式约束minimax优化问题、凸集约束minimax优化问题和线性约束minimax优化问题，构建了可行增量束方法、邻近-投影部分束方法、基于部分割平面模型的束方法。3）从理论上分析论证了算法的全局收敛性和局部快速收敛性，为算法的实际应用提供了理论保障。4）对提出的大部分算法均进行了大量的计算机数值模拟试验，结果表明算法是稳定有效的，且制作成了计算机软件包，可供实际应用。将外逼近优化方法应用于求解电力系统优化中的机组组合问题，获得了优良的数值结果。. 这些新方法的提出，不仅在理论上完善和提升了现有方法，而且在数值上显著减少了计算量和计算时间。