全局分片线性优化方法与应用

This project mainly studies the global search methods for piecewise linear optimization problems. It can be viewed as an extension and further developments of PI's previous studies. The key idea of this project lies in two aspects. First, using the fact that there exists exact penalty for piecewise linear optimization models and techniques for equivalent transformation of piecewise linear functions, we will transform the general piecewise linear optimization problem into that of minimizing a concave piecewise linear function on a convex polyhedron. Second, using the property that the contour surfaces of a concave piecewise linear function is the facets of a convex polyhedron, we can escape from local minima trap by searching other feasible solution on the contour surfaces. In short, we will carry out research in three related directions: the equivalent transformation techniques for piecewise linear functions, the search algorithms on the contour surfaces of local minima, and the fusion of other global optimization algorithms. Besides, we will apply the methods obtained to some related problems appeared in signal processing and statistical learning fields.

本项目主要研究分片线性优化模型的全局求解方法。该项研究是申请人课题组前期相关工作的深入和发展。指导本项研究的基本思想有两点：第一，利用分片线性优化模型存在精确罚函数的性质以及对分片线性函数进行等价转换的技术，把一般性的分片线性优化模型转换为凸多面体上的凹分片线性函数的极小化问题；第二，利用凹分片线性函数的等值面是凸多面体边界的性质，采用在局部最优解的等值面上搜索其他可行解的策略逃离局部陷阱。为此将在分片线性函数的等价转换技术、凹目标函数等值面搜索方法以及和其它全局优化方法有效融合等三个方面开展研究工作。此外，项目还将针对信号处理和统计学习领域有关问题展开应用研究。

本项目主要针对凹分片线性优化问题，探讨基于先离开（可行域）再进入（可行域）的局部陷阱逃离策略及其相应的全局优化方法。所取得的主要成果是，提出了能够快速逃离当前局部最优解的单纯型穿山法和山顶投影穿山法，这些方法相对本项研究拟重点改进的求解相同问题的绕山法具有显著的改善效果。项目还以实践中经常遇到的若干问题，如压缩感知领域的稀疏信号恢复问题、采用斜坡损失分片线性函数解决样本集包含极端野值点的支持向量机模型的训练问题、采用S型价值函数的投资组合优化问题、分片线性黑箱模型的辨识问题、凹分片线性目标函数的最小费用流问题以及航空信息物理融合系统的无人机智能编队飞行控制和机群协同探测问题为具体对象，研究了所提出的分片线性优化方法的应用效果，验证了它们在解决这些问题中的有效性。