连续分片线性规划问题的山顶投影穿山法

发布时间：2018-04-27 21:39

本文选题：全局优化 + 分片线性　；参考：《清华大学学报(自然科学版)》2017年12期

【摘要】：连续分片线性规划是一类应用广泛的重要规划,寻找连续分片线性规划的全局最优解是研究这类规划的重点和难点。该文研究的是一种对此类规划进行全局寻优的确定性启发式算法。由于此类规划问题可以转化为凸多面体上的凹优化问题进行求解,因此利用凹函数的上水平集的凸性,该文提出可以通过直接穿透目标函数上水平集在其等值面上进行搜索,以逃离当前局部最优解进行全局寻优。该方法中每次逃离的搜索方向都通过山形凹目标函数的顶点投影来确定,因此称为山顶投影穿山法。在数值实验中,将所提出的山顶投影穿山法与CPLEX以及绕山法进行了比较,结果表明该算法在计算速度与全局寻优能力上性能优越。
[Abstract]:Continuous piecewise linear programming (CPLP) is a kind of important programming which is widely used. Finding the global optimal solution of continuous piecewise linear programming (CPLP) is the focus and difficulty of this kind of programming. In this paper, a deterministic heuristic algorithm for global optimization of this kind of programming is studied. Because this kind of programming problem can be transformed into concave optimization problem on convex polyhedron, by using the convexity of the upper level set of concave function, this paper proposes that the level set can be searched on its isosurface by penetrating directly on the level set of objective function. In order to escape from the current local optimal solution for global optimization. In this method, the searching direction of each escape is determined by the projection of the vertex of the mountain concave objective function, so it is called the mountain top projection through the mountain. In the numerical experiments, the proposed mountain projection method is compared with the CPLEX method and the surrounding mountain method. The results show that the proposed algorithm is superior in computing speed and global optimization ability.
【作者单位】：清华大学自动化系信息科学与技术国家实验室;空军工程大学理学院;
【基金】：国家自然科学基金资助项目(61473165,61134012) 国家“九七三”重点基础研究项目(2012CB720505)
【分类号】：O221

【相似文献】