连续分片线性规划问题的山顶投影穿山法
Hill tunneling method via peak subpoints for continuous piecewise linear programming

连续分片线性规划是一类应用广泛的重要规划，寻找连续分片线性规划的全局最优解是研究这类规划的重点和难点。该文研究的是一种对此类规划进行全局寻优的确定性启发式算法。由于此类规划问题可以转化为凸多面体上的凹优化问题进行求解，因此利用凹函数的上水平集的凸性，该文提出可以通过直接穿透目标函数上水平集在其等值面上进行搜索，以逃离当前局部最优解进行全局寻优。该方法中每次逃离的搜索方向都通过山形凹目标函数的顶点投影来确定，因此称为山顶投影穿山法。在数值实验中，将所提出的山顶投影穿山法与CPLEX以及绕山法进行了比较，结果表明该算法在计算速度与全局寻优能力上性能优越。
Abstract：Continuous piecewise linear (CPWL) optimization is a widely used mathematical programming method, and searching for the globally optimal solution is the research emphasis. This paper presents a heuristic algorithm with determinacy for the global optimization of CPWL programming, which is referred to as the hill tunneling via peak subpoint (HTPS) algorithm. A CPWL programming problem can be transformed into an equivalent concave optimization problem over a polyhedron; thus, the current algorithm makes use of the concavity of the super-level sets of concave piecewise linear functions to escape a local optimum to search on the other side of its contour surface by cutting across the super-level set. Each searching path for the hill tunneling is established using the peak subpoint of the "hill" shaped concave objective function. Numerical tests show that this algorithm is more efficient and has better global search capability than CPLEX or the hill detouring (HD) method, which shows its superior performance.