Hill tunneling method via peak subpoints for continuous piecewise linear programming
XU Zhiming1,2, LIU Kuangyu1, BAI Yu1, WANG Shuning1
1. National Laboratory for Information Science and Technology, Department of Automation, Tsinghua University, Beijing 100084, China;
2. Science College, Air Force Engineering University, Xi'an 710051, China
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.
续志明, 刘匡宇, 白宇, 王书宁. 连续分片线性规划问题的山顶投影穿山法[J]. 清华大学学报（自然科学版）, 2017, 57(12): 1265-1271.
XU Zhiming, LIU Kuangyu, BAI Yu, WANG Shuning. Hill tunneling method via peak subpoints for continuous piecewise linear programming. Journal of Tsinghua University(Science and Technology), 2017, 57(12): 1265-1271.
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.
2017, Vol. 57 
