April  2012, 8(2): 429-455. doi: 10.3934/jimo.2012.8.429

An efficient convexification method for solving generalized geometric problems

1. 

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

Received  September 2010 Revised  November 2011 Published  April 2012

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.
Citation: Hao-Chun Lu. An efficient convexification method for solving generalized geometric problems. Journal of Industrial & Management Optimization, 2012, 8 (2) : 429-455. doi: 10.3934/jimo.2012.8.429
References:
[1]

M. Avriel and A. C. Williams, Complementary geometric programming,, SIAM Journal on Applied Mathematics, 19 (1970), 125.  doi: 10.1137/0119011.  Google Scholar

[2]

D. A. Babayev, Piece-wise linear approximation of functions of two variables,, Journal of Heuristics, 2 (1997), 313.  doi: 10.1007/BF00132502.  Google Scholar

[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.   Google Scholar

[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.  doi: 10.1016/S0098-1354(02)00129-1.  Google Scholar

[5]

G. E. Blau and D. J. Wilde, Generalized polynomial programming,, The Canadian Journal of Chemical Engineering, 47 (1969), 317.  doi: 10.1002/cjce.5450470401.  Google Scholar

[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.  doi: 10.1287/opre.1050.0254.  Google Scholar

[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.  doi: 10.1007/s10479-004-5035-9.  Google Scholar

[8]

M. Chiang, "Geometric Programming for Communication Systems,", Now Publishers, (2005).   Google Scholar

[9]

R. J. Duffin, Linearizing geometric programming,, SIAM Review, 12 (1970), 211.  doi: 10.1137/1012043.  Google Scholar

[10]

R. J. Duffin and E. L. Peterson, Duality theory for geometric programming,, SIAM Journal on Applied Mathematics, 14 (1966), 1307.  doi: 10.1137/0114105.  Google Scholar

[11]

R. J. Duffin and E. L. Peterson, Geometric programming with signomials,, Journal of Optimization Theory and Applications, 11 (1973), 3.  doi: 10.1007/BF00934288.  Google Scholar

[12]

J. G. Ecker, Geometric programming: Methods, computation and application,, SIAM Review, 22 (1980), 338.  doi: 10.1137/1022058.  Google Scholar

[13]

C. A. Floudas, "Nonlinear and Mixed-Integer Optimization-Fundamentals and Applications,", Oxford University Press, (1995).   Google Scholar

[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, (1999), 85.   Google Scholar

[15]

C. A. Floudas, "Deterministic Global Optimization: Theory, Methods and Application,", Kluwer Academic Publishers, (2000), 257.   Google Scholar

[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.  doi: 10.1021/i260039a026.  Google Scholar

[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.  doi: 10.1057/jors.1973.45.  Google Scholar

[18]

, LINGO, Release 12, Lindo System Inc., Chicago,, 2010. Available from: \url{http://www.lindo.com/}., (2010).   Google Scholar

[19]

H.-L. Li and J.-F. Tsai, Treating free variables in generalized geometric global optimization programs,, Journal of Global Optimization, 33 (2005), 1.  doi: 10.1007/s10898-005-2098-3.  Google Scholar

[20]

H.-L. Li and H.-C. Lu, Global optimization for generalized geometric programs with mixed free-sign variables,, Operations Research, 57 (2009), 701.  doi: 10.1287/opre.1080.0586.  Google Scholar

[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.  doi: 10.1287/ijoc.1080.0294.  Google Scholar

[22]

P. O. Lindberg, "Power Convex Functions: Generalized Concavity in Optimization and Economics,", Academic Publishers, (1981), 153.   Google Scholar

[23]

M. Padberg, Approximating separable nonlinear functions via mixed zero-one programs,, Operations Research Letters, 27 (2000), 1.  doi: 10.1016/S0167-6377(00)00028-6.  Google Scholar

[24]

A. Paoluzzi, "Geometric Programming for Computer Aided Design,", John Wiley & Sons, (2003).  doi: 10.1002/0470013885.  Google Scholar

[25]

P. M. Pardalos and E. Romeijn, Global optimization: Software, test problem, and applications,, in, ().   Google Scholar

[26]

L. D. Pascual and A. Ben-Israel, Constrained maximization of posynomials by geometric programming,, Journal of Optimization Theorem and Application, 5 (1970), 73.  doi: 10.1007/BF00928296.  Google Scholar

[27]

U. Passy, Generalized weighted mean programming,, SIAM Journal on Applied Mathematics, 20 (1971), 763.  doi: 10.1137/0120075.  Google Scholar

[28]

U. Passy and D. J. Wilde, Generalized polynomial optimizations,, SIAM Journal on Applied Mathematics, 15 (1967), 1344.  doi: 10.1137/0115117.  Google Scholar

[29]

I. Quesada and I. Grossmann, Global optimization algorithm for heat exchanger networks,, Industrial and Engineering Chemical Research, 32 (1993), 487.  doi: 10.1021/ie00015a012.  Google Scholar

[30]

C. D. Maranas and C. A. Floudas, Global optimization in generalized geometric programming,, Computer and Chemical Engineering, 21 (1997), 351.  doi: 10.1016/S0098-1354(96)00282-7.  Google Scholar

[31]

R. Pörn, K. M. Björk and T. Westerlund, Global solution of optimization problems with signomial parts,, Discrete Optimization, 5 (2008), 108.  doi: 10.1016/j.disopt.2007.11.005.  Google Scholar

[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.  doi: 10.1016/0098-1354(92)85004-R.  Google Scholar

[33]

E. Sandgren, Nonlinear integer and discrete programming in mechanical design optimization,, Journal of Mechanical Design, 112 (1990), 223.  doi: 10.1115/1.2912596.  Google Scholar

show all references

References:
[1]

M. Avriel and A. C. Williams, Complementary geometric programming,, SIAM Journal on Applied Mathematics, 19 (1970), 125.  doi: 10.1137/0119011.  Google Scholar

[2]

D. A. Babayev, Piece-wise linear approximation of functions of two variables,, Journal of Heuristics, 2 (1997), 313.  doi: 10.1007/BF00132502.  Google Scholar

[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.   Google Scholar

[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.  doi: 10.1016/S0098-1354(02)00129-1.  Google Scholar

[5]

G. E. Blau and D. J. Wilde, Generalized polynomial programming,, The Canadian Journal of Chemical Engineering, 47 (1969), 317.  doi: 10.1002/cjce.5450470401.  Google Scholar

[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.  doi: 10.1287/opre.1050.0254.  Google Scholar

[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.  doi: 10.1007/s10479-004-5035-9.  Google Scholar

[8]

M. Chiang, "Geometric Programming for Communication Systems,", Now Publishers, (2005).   Google Scholar

[9]

R. J. Duffin, Linearizing geometric programming,, SIAM Review, 12 (1970), 211.  doi: 10.1137/1012043.  Google Scholar

[10]

R. J. Duffin and E. L. Peterson, Duality theory for geometric programming,, SIAM Journal on Applied Mathematics, 14 (1966), 1307.  doi: 10.1137/0114105.  Google Scholar

[11]

R. J. Duffin and E. L. Peterson, Geometric programming with signomials,, Journal of Optimization Theory and Applications, 11 (1973), 3.  doi: 10.1007/BF00934288.  Google Scholar

[12]

J. G. Ecker, Geometric programming: Methods, computation and application,, SIAM Review, 22 (1980), 338.  doi: 10.1137/1022058.  Google Scholar

[13]

C. A. Floudas, "Nonlinear and Mixed-Integer Optimization-Fundamentals and Applications,", Oxford University Press, (1995).   Google Scholar

[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, (1999), 85.   Google Scholar

[15]

C. A. Floudas, "Deterministic Global Optimization: Theory, Methods and Application,", Kluwer Academic Publishers, (2000), 257.   Google Scholar

[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.  doi: 10.1021/i260039a026.  Google Scholar

[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.  doi: 10.1057/jors.1973.45.  Google Scholar

[18]

, LINGO, Release 12, Lindo System Inc., Chicago,, 2010. Available from: \url{http://www.lindo.com/}., (2010).   Google Scholar

[19]

H.-L. Li and J.-F. Tsai, Treating free variables in generalized geometric global optimization programs,, Journal of Global Optimization, 33 (2005), 1.  doi: 10.1007/s10898-005-2098-3.  Google Scholar

[20]

H.-L. Li and H.-C. Lu, Global optimization for generalized geometric programs with mixed free-sign variables,, Operations Research, 57 (2009), 701.  doi: 10.1287/opre.1080.0586.  Google Scholar

[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.  doi: 10.1287/ijoc.1080.0294.  Google Scholar

[22]

P. O. Lindberg, "Power Convex Functions: Generalized Concavity in Optimization and Economics,", Academic Publishers, (1981), 153.   Google Scholar

[23]

M. Padberg, Approximating separable nonlinear functions via mixed zero-one programs,, Operations Research Letters, 27 (2000), 1.  doi: 10.1016/S0167-6377(00)00028-6.  Google Scholar

[24]

A. Paoluzzi, "Geometric Programming for Computer Aided Design,", John Wiley & Sons, (2003).  doi: 10.1002/0470013885.  Google Scholar

[25]

P. M. Pardalos and E. Romeijn, Global optimization: Software, test problem, and applications,, in, ().   Google Scholar

[26]

L. D. Pascual and A. Ben-Israel, Constrained maximization of posynomials by geometric programming,, Journal of Optimization Theorem and Application, 5 (1970), 73.  doi: 10.1007/BF00928296.  Google Scholar

[27]

U. Passy, Generalized weighted mean programming,, SIAM Journal on Applied Mathematics, 20 (1971), 763.  doi: 10.1137/0120075.  Google Scholar

[28]

U. Passy and D. J. Wilde, Generalized polynomial optimizations,, SIAM Journal on Applied Mathematics, 15 (1967), 1344.  doi: 10.1137/0115117.  Google Scholar

[29]

I. Quesada and I. Grossmann, Global optimization algorithm for heat exchanger networks,, Industrial and Engineering Chemical Research, 32 (1993), 487.  doi: 10.1021/ie00015a012.  Google Scholar

[30]

C. D. Maranas and C. A. Floudas, Global optimization in generalized geometric programming,, Computer and Chemical Engineering, 21 (1997), 351.  doi: 10.1016/S0098-1354(96)00282-7.  Google Scholar

[31]

R. Pörn, K. M. Björk and T. Westerlund, Global solution of optimization problems with signomial parts,, Discrete Optimization, 5 (2008), 108.  doi: 10.1016/j.disopt.2007.11.005.  Google Scholar

[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.  doi: 10.1016/0098-1354(92)85004-R.  Google Scholar

[33]

E. Sandgren, Nonlinear integer and discrete programming in mechanical design optimization,, Journal of Mechanical Design, 112 (1990), 223.  doi: 10.1115/1.2912596.  Google Scholar

[1]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067

[2]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[3]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151

[4]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709

[5]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[6]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[7]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018

[8]

Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1

[9]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907

[10]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[11]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379

[12]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[13]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045

[14]

Ravi Anand, Dibyendu Roy, Santanu Sarkar. Some results on lightweight stream ciphers Fountain v1 & Lizard. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020128

[15]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617

[16]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (69)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]