AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Objective Variation Simplex Algorithm for Continuous Piecewise Linear Programming

Yu Bai, Zhiming Xu, Xiangming Xi, Shuning Wang( )
Department of Automation, Tsinghua National Laboratory for Information Science and Technology (TNList), Tsinghua University, Beijing 100084, China.
Faculty of College of Science, Air Force Engineering University, Xi’an 710051
Department of Automation, Tsinghua University, Beijing 100084, China.
Show Author Information

Abstract

This paper works on a modified simplex algorithm for the local optimization of Continuous PieceWise Linear (CPWL) programming with generalization of hinging hyperplane objective and linear constraints. CPWL programming is popular since it can be equivalently transformed into difference of convex functions programming or concave optimization. Inspired by the concavity of the concave CPWL functions, we propose an Objective Variation Simplex Algorithm (OVSA), which is able to find a local optimum in a reasonable time. Computational results are presented for further insights into the performance of the OVSA compared with two other algorithms on random test problems.

Keywords

local optimizationcontinuous piecewise linear programmingmodified simplex algorithm

References

[1]
Dantzig G., Johnson S., White W., and Science M., A linear programming approach to the chemical equilibrium problem, General Information, vol. 5, pp. 38-43, 1958.
Crossref Google Scholar
[2]
Zionts S., Linear and Integer Programming. Prentice Hall, 1974.
[3]
Dantzig G. B., Linear Programming and Extensions. Princeton, NJ, USA: Princeton University Press, 1963.
Crossref
[4]
Charnes A. and Cooper W. W., Management models and applications of linear programming, General Information, vol. 4, pp. 38-91, 1957.
Crossref Google Scholar
[5]
Charnes A. and Lemke C. E., Minimization of non-linear separable convex functionals, Naval Research Logistics Quarterly, vol. 1, pp. 301-312, 1954.
Crossref Google Scholar
[6]
Dantzig G. B., Recent advances in linear programming, Management Science, vol. 2, pp. 131-144, 1956.
Crossref Google Scholar
[7]
Ho J. K., Relationships among linear formulations of separable convex piecewise linear programs, Mathematical Programming Study, vol. 24, pp. 126-140, 1985.
Crossref Google Scholar
[8]
Breiman L., Hinging hyperplanes for regression, classification and function approximation, IEEE Trans. Information Theory, vol. 39, pp. 999-1013, 1993.
Crossref Google Scholar
[9]
Beale E. M. L., Coen P. J., and Flowerdew A. D. J., Separable programming applied to an ore purchasing problem, Applied Statistics, vol. 14, nos. 2&3, pp. 89-101, 1965.
Crossref Google Scholar
[10]
Beale E. M. L., Numerical methods, in Nonlinear Programming, Abadie J., ed. Amsterdam, Holland: North-Holland, 1967, pp. 174-177.
[11]
Fourer R., A simplex algorithm for piecewise-linear programming I: Derivation and proof, Mathematical Programming, vol. 33, pp. 204-233, 1985.
Crossref Google Scholar
[12]
Fourer R., A simplex algorithm for piecewise-linear programming II: Finiteness, feasibility and degeneracy, Mathematical Programming, vol. 41, pp. 281-315, 1988.
Crossref Google Scholar
[13]
Fourer R., A simplex algorithm for piecewise-linear programming III: Computational analysis and applications, Mathematical Programming, vol. 53, pp. 213-335, 1992.
Crossref Google Scholar
[14]
Fourer R. and Marsten R., Solving piecewise-linear programs: Experiments with a simplex approach, ORSA Journal on Computing, no. 4, pp. 16-31, 1992.
Crossref Google Scholar
[15]
Güder F. and Nourie F. J., A dual simplex algorithm for piecewise-linear programming, Journal of the Operational Research Society, vol. 47, no. 4, pp. 583-590, 1996.
Crossref Google Scholar
[16]
Dantzig G., Johnson S., and White W., A linear programming approach to the chemical equilibrium problem, Management Science, vol. 5, no. 1, pp. 38-43, 1958.
Crossref Google Scholar
[17]
Huang X., Xu J., and Wang S., Operation optimization for centrifugal chiller plants using continuous piecewise linear programming, in 2010 IEEE International Conference on Systems Man and Cybernetics (SMC), 2010, pp. 1121-1126.
Crossref
[18]
Huang X., Xu J., and Wang S., Exact penalty and optimality condition for nonseparable continuous piecewise linear programming, Journal of Optimization Theory and Applications, vol. 155, pp. 145-164, 2012.
Crossref Google Scholar
[19]
Xi X., Xu J., Mu X., and Wang S., Continuous piecewise programming via concave optimization and genetic algorithm, in 2012 IEEE 51st Annual Conference on Decision and Control (CDC), 2012, pp. 2509-2514.
Crossref
[20]
Huang X., Xu J., Mu X., and Wang S., The hill detouring method for minimizing hinging hyperplanes functions, Computers Operations Research, vol. 39, pp. 1763-1770, 2012.
Crossref Google Scholar
[21]
Wang S. and Sun X., Generalization of hinging hyperplanes, IEEE Transactions on Information Theory, vol. 51, pp. 4425-4431, 2005.
Crossref Google Scholar
[22]
Guan M. G. and Zheng H. D., Linear Programming, (in Chinese). Ji’nan, China: Shandong Science &Technology Press, 1983.
[23]
Camm J. D., Raturi A. S., and Tsubakitani S., Cutting big M down to size, Interfaces, vol. 25, no. 5, pp. 61-66, 1990.
Crossref Google Scholar
[24]
Wolfe P., The composite simplex algorithm, SIAM Review, no. 1, pp. 42-54, 1965.
Crossref Google Scholar
[25]
Tao P. D., The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of Operations Research, vol. 133, nos. 1–4, pp. 23-46, 2005.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 22 Issue 1,
February 2017
Pages 73-82
DOI: 10.1109/TST.2017.7830897
Cite this article:
Bai Y, Xu Z, Xi X, et al. Objective Variation Simplex Algorithm for Continuous Piecewise Linear Programming. Tsinghua Science and Technology, 2017, 22(1): 73-82. https://doi.org/10.1109/TST.2017.7830897

573

Views

19

Downloads

1

Crossref

N/A

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 11 January 2016
Accepted: 18 March 2016
Published: 26 January 2017
© The author(s) 2017
Return