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

项目名称： 全局分片线性优化方法与应用

项目编号： No.61473165

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 王书宁

作者单位： 清华大学

项目金额： 83万元

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

中文关键词： 全局优化；分片线性模型；凹优化；绕山法；分片线性罚函数

英文摘要： 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.

英文关键词： global optimization;piecewise linear model;concave optimization;hill detouring method;piecewise linear penalty