连续分片线性规划是一类应用广泛的重要规划，寻找连续分片线性规划的全局最优解是研究这类规划的重点和难点。该文研究的是一种对此类规划进行全局寻优的确定性启发式算法。由于此类规划问题可以转化为凸多面体上的凹优化问题进行求解，因此利用凹函数的上水平集的凸性，该文提出可以通过直接穿透目标函数上水平集在其等值面上进行搜索，以逃离当前局部最优解进行全局寻优。该方法中每次逃离的搜索方向都通过山形凹目标函数的顶点投影来确定，因此称为山顶投影穿山法。在数值实验中，将所提出的山顶投影穿山法与CPLEX以及绕山法进行了比较，结果表明该算法在计算速度与全局寻优能力上性能优越。
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.
[1] Fourer R. A simplex algorithm for piecewise-linear programming I:Derivation and proof[J]. Mathematical Programming, 1985, 33(2):204-233.[2] Fourer R. A simplex algorithm for piecewise-linear programming Ⅱ:Finiteness, feasibility and degeneracy[J]. Mathematical Programming, 1988, 41(1-3):281-315.[3] Fourer R. A simplex algorithm for piecewise-linear programming Ⅲ:Computational analysis and applications[J]. Mathematical Programming, 1992, 53(1-3):213-235.[4] Keha A B, De Farias J I R, Nemhauser G L. Abranch-and-cut algorithm without binary variables for nonconvex piecewise pinear optimization[J]. Operations Research, 2006, 54(5):847-858.[5] Vielma J P, Ahmed S, Nemhauser G. Mixed-integer models for nonseparable piecewise linear optimization:Unifying framework and extensions[J]. Operations Research, 2010, 58(2):303-315.[6] Xi X, Xu J, Mu X, et al. Continuous piecewise linear programming via concave optimization and genetic algorithm[C]//2012 IEEE 51st Annual Conference on Decision and Control (CDC). Maui, HI, USA:IEEE, 2012:2509-2514.[7] Huang X, Xu J, Mu X, et al. The hill detouring method for minimizing hinging hyperplanes functions[J]. Computers & Operations Research, 2012, 39(7):1763-1770.[8] Huang X, Xu J, Wang S. Exact penalty and optimality condition for nonseparable continuous piecewise linear programming[J]. Journal of Optimization Theory and Applications, 2012, 155(1):145-164.[9] Wang S, Sun X. Generalization of hinging hyperplanes[J]. Information Theory, IEEE Transactions on, 2005, 51(12):4425-4431.[10] Horst R, Tuy H. Global Optimization:Deterministic Approaches[M]. Berlin:Springer, 1996.[11] Dolan E D, More J J. Benchmarking optimization software with performance profiles[J]. Mathematical Programming, Series B, 2002, 91(2):201-213.
