Hill tunneling method via peak subpoints for continuous piecewise linear programming

doi:10.16511/j.cnki.qhdxxb.2017.25.059

Download: PDF(1807 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords global optimization piecewise linear concave minimization cutting plane method hill tunneling

ZTFLH:

O221

Issue Date: 15 December 2017

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	XU Zhiming
	LIU Kuangyu
	BAI Yu
	WANG Shuning

Cite this article:

XU Zhiming,LIU Kuangyu,BAI Yu, et al. Hill tunneling method via peak subpoints for continuous piecewise linear programming[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(12): 1265-1271.

URL:

http://jst.tsinghuajournals.com/EN/10.16511/j.cnki.qhdxxb.2017.25.059 OR http://jst.tsinghuajournals.com/EN/Y2017/V57/I12/1265

[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. url: http://dx.doi.org/ters
[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.