An efficient convexification method for solving generalized geometric problems

Hao-Chun Lu

doi:10.3934/jimo.2012.8.429

Article Contents

2012, Volume 8, Issue 2: 429-455. Doi: 10.3934/jimo.2012.8.429

This issue Previous Article Calculus rules of generalized $\epsilon-$subdifferential for vector valued mappings and applications Next Article A new heuristic algorithm for laser antimissile strategy optimization

An efficient convexification method for solving generalized geometric problems

Hao-Chun Lu^1,

1.
Department of Information Management, Fu Jen Catholic University, No.510, Zhongzheng Rd., Xinzhuang Dist., New Taipei City 24205

Received: August 31, 2010

Revised: October 31, 2011

Published: March 2012

Abstract Related Papers Cited by

Abstract

Convexification transformation is vital for solving Generalized Geometric Problems (GGP) in global optimization. Björk et al. [3] posited that transforming non-convex signomial terms in a GGP into 1-convex functions is currently the most efficient convexification technique. However, to the best of our knowledge, an efficient convexification method based on the concept of 1-convex functions has not been proposed. To address this research gap, we present a Beta method to maximally improve the efficiency of convexification based on the concept of 1-convex functions, and thereby enhance the accuracy of linearization without increasing the number of break points and binary variables in the piecewise linear function. The Beta method yields an excellent solution quality and computational efficiency. We compare its performance, with that of three existing approaches using four numerical examples. The computational results demonstrate that, in terms of solution quality and computation time, the proposed method outperforms the compared approaches.

Keywords:

Mathematics Subject Classification: Primary: 90C26, 90C30; Secondary: 49K10, 90C47.

Citation:

Related Papers

Cited by

References

[1]	M. Avriel and A. C. Williams, Complementary geometric programming, SIAM Journal on Applied Mathematics, 19 (1970), 125-141.doi: 10.1137/0119011.
[2]	D. A. Babayev, Piece-wise linear approximation of functions of two variables, Journal of Heuristics, 2 (1997), 313-320.doi: 10.1007/BF00132502.
[3]	K. M. Björk, P. O. Lindberg and T. Westerlund, Some convexifications in global optimization of problems containing signomial terms, Computers and Chemical Engineering, 27 (2003), 669-679.
[4]	K. M. Björk and T. Westerlund, Global optimization of heat exchanger network synthesis problems with and without the isothermal mixing assumption, Computers and Chemical Engineering, 26 (2002), 1581-1593.doi: 10.1016/S0098-1354(02)00129-1.
[5]	G. E. Blau and D. J. Wilde, Generalized polynomial programming, The Canadian Journal of Chemical Engineering, 47 (1969), 317-326.doi: 10.1002/cjce.5450470401.
[6]	S. P. Boyd, S.-J. Kim, D. D. Patil and M. A. Horowitz, Digital circuit optimization via geometric programming, Operations Research, 53 (2005), 899-932.doi: 10.1287/opre.1050.0254.
[7]	H. Cheng, S. C. Fang and J. E. Lavery, A geometric programming framework for univariate cubic L1 smoothing splines, Annals of Operations Research, 133 (2005), 229-248.doi: 10.1007/s10479-004-5035-9.
[8]	M. Chiang, "Geometric Programming for Communication Systems," Now Publishers, Inc., Boston, 2005.
[9]	R. J. Duffin, Linearizing geometric programming, SIAM Review, 12 (1970), 211-227.doi: 10.1137/1012043.
[10]	R. J. Duffin and E. L. Peterson, Duality theory for geometric programming, SIAM Journal on Applied Mathematics, 14 (1966), 1307-1349.doi: 10.1137/0114105.
[11]	R. J. Duffin and E. L. Peterson, Geometric programming with signomials, Journal of Optimization Theory and Applications, 11 (1973), 3-35.doi: 10.1007/BF00934288.
[12]	J. G. Ecker, Geometric programming: Methods, computation and application, SIAM Review, 22 (1980), 338-362.doi: 10.1137/1022058.
[13]	C. A. Floudas, "Nonlinear and Mixed-Integer Optimization-Fundamentals and Applications," Oxford University Press, Chapter 7, 1995.
[14]	C. A. Floudas, P. M. Pardalos, C. S. Adjiman, W. R. Esposito, Z. H. Gumus, S. T. Harding, J. L. Klepeis, C. A. Meyer and C. A. Schweiger, "Handbook of Test Problems in Local and Global Optimization," Academic Publishers, Boston, (1999), 85-105.
[15]	C. A. Floudas, "Deterministic Global Optimization: Theory, Methods and Application," Kluwer Academic Publishers, Boston, (2000), 257-306.
[16]	L. J. Hellinckx and M. J. Rijckaert, Minimization of capital investment for batch processes, Industrial & Engineering Chemistry Process Design and Development, 10 (1971), 422-423.doi: 10.1021/i260039a026.
[17]	A. Kochenberger, R. E. D. Woolsey and B. A. McCarl, On the solution of geometric programs via separable programming, Operations Research, 24 (1973), 285-294.doi: 10.1057/jors.1973.45.
[18]	LINGO, Release 12, Lindo System Inc., Chicago,, 2010. Available from: \url{http://www.lindo.com/}., (2010).
[19]	H.-L. Li and J.-F. Tsai, Treating free variables in generalized geometric global optimization programs, Journal of Global Optimization, 33 (2005), 1-13.doi: 10.1007/s10898-005-2098-3.
[20]	H.-L. Li and H.-C. Lu, Global optimization for generalized geometric programs with mixed free-sign variables, Operations Research, 57 (2009), 701-713.doi: 10.1287/opre.1080.0586.
[21]	H.-L. Li, H.-C. Lu, C.-H. Huang and N.-Z. Hu, A superior representation method for piecewise linear functions, INFORMS Journal on Computing, 21 (2009), 314-321.doi: 10.1287/ijoc.1080.0294.
[22]	P. O. Lindberg, "Power Convex Functions: Generalized Concavity in Optimization and Economics," Academic Publishers, Boston, (1981), 153-168.
[23]	M. Padberg, Approximating separable nonlinear functions via mixed zero-one programs, Operations Research Letters, 27 (2000), 1-5.doi: 10.1016/S0167-6377(00)00028-6.
[24]	A. Paoluzzi, "Geometric Programming for Computer Aided Design," John Wiley & Sons, Inc., Hoboken, 2003.doi: 10.1002/0470013885.
[25]	P. M. Pardalos and E. Romeijn, Global optimization: Software, test problem, and applications, in "Handbook of Global Optimization," Vol. 2, Chapter 15,
[26]	L. D. Pascual and A. Ben-Israel, Constrained maximization of posynomials by geometric programming, Journal of Optimization Theorem and Application, 5 (1970), 73-80.doi: 10.1007/BF00928296.
[27]	U. Passy, Generalized weighted mean programming, SIAM Journal on Applied Mathematics, 20 (1971), 763-778.doi: 10.1137/0120075.
[28]	U. Passy and D. J. Wilde, Generalized polynomial optimizations, SIAM Journal on Applied Mathematics, 15 (1967), 1344-1356.doi: 10.1137/0115117.
[29]	I. Quesada and I. Grossmann, Global optimization algorithm for heat exchanger networks, Industrial and Engineering Chemical Research, 32 (1993), 487-499.doi: 10.1021/ie00015a012.
[30]	C. D. Maranas and C. A. Floudas, Global optimization in generalized geometric programming, Computer and Chemical Engineering, 21 (1997), 351-370.doi: 10.1016/S0098-1354(96)00282-7.
[31]	R. Pörn, K. M. Björk and T. Westerlund, Global solution of optimization problems with signomial parts, Discrete Optimization, 5 (2008), 108-120.doi: 10.1016/j.disopt.2007.11.005.
[32]	H. E. Salomone and O. A. Iribarren, Posynomial modeling of batch plants: A procedure to include process decision variables, Computer and Chemical Engineering, 16 (1992), 173-184.doi: 10.1016/0098-1354(92)85004-R.
[33]	E. Sandgren, Nonlinear integer and discrete programming in mechanical design optimization, Journal of Mechanical Design, 112 (1990), 223-229.doi: 10.1115/1.2912596.