Journal Home > Volume 22 , Issue 1

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.


menu
Abstract
Full text
Outline
About this article

Objective Variation Simplex Algorithm for Continuous Piecewise Linear Programming

Show Author's information Yu BaiZhiming XuXiangming XiShuning 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.

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: continuous piecewise linear programming, local optimization, modified simplex algorithm

References(25)

[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.
[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.
DOI
[4]
Charnes A. and Cooper W. W., Management models and applications of linear programming, General Information, vol. 4, pp. 38-91, 1957.
[5]
Charnes A. and Lemke C. E., Minimization of non-linear separable convex functionals, Naval Research Logistics Quarterly, vol. 1, pp. 301-312, 1954.
[6]
Dantzig G. B., Recent advances in linear programming, Management Science, vol. 2, pp. 131-144, 1956.
[7]
Ho J. K., Relationships among linear formulations of separable convex piecewise linear programs, Mathematical Programming Study, vol. 24, pp. 126-140, 1985.
[8]
Breiman L., Hinging hyperplanes for regression, classification and function approximation, IEEE Trans. Information Theory, vol. 39, pp. 999-1013, 1993.
[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.
[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.
[12]
Fourer R., A simplex algorithm for piecewise-linear programming II: Finiteness, feasibility and degeneracy, Mathematical Programming, vol. 41, pp. 281-315, 1988.
[13]
Fourer R., A simplex algorithm for piecewise-linear programming III: Computational analysis and applications, Mathematical Programming, vol. 53, pp. 213-335, 1992.
[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.
[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.
[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.
[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.
DOI
[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.
[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.
DOI
[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.
[21]
Wang S. and Sun X., Generalization of hinging hyperplanes, IEEE Transactions on Information Theory, vol. 51, pp. 4425-4431, 2005.
[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.
[24]
Wolfe P., The composite simplex algorithm, SIAM Review, no. 1, pp. 42-54, 1965.
[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.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 11 January 2016
Accepted: 18 March 2016
Published: 26 January 2017
Issue date: February 2017

Copyright

© The author(s) 2017

Acknowledgements

This project wss jointly supported by the National Natural Science Foundation of China (Nos. 61473165 and 61134012) and the National Key Basic Research and Development (973) Program of China (No. 2012CB720505).

Rights and permissions

Return