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]

Liran Rotem. Banach limit in convexity and geometric means for convex bodies. Electronic Research Announcements, 2016, 23: 41-51. doi: 10.3934/era.2016.23.005

[2]

Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767

[3]

Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357

[4]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349

[5]

Sophie Guillaume. Evolution equations governed by the subdifferential of a convex composite function in finite dimensional spaces. Discrete & Continuous Dynamical Systems - A, 1996, 2 (1) : 23-52. doi: 10.3934/dcds.1996.2.23

[6]

Murat Adivar, Shu-Cherng Fang. Convex optimization on mixed domains. Journal of Industrial & Management Optimization, 2012, 8 (1) : 189-227. doi: 10.3934/jimo.2012.8.189

[7]

Nelly Point, Silvano Erlicher. Convex analysis and thermodynamics. Kinetic & Related Models, 2013, 6 (4) : 945-954. doi: 10.3934/krm.2013.6.945

[8]

Roland Hildebrand. Barriers on projective convex sets. Conference Publications, 2011, 2011 (Special) : 672-683. doi: 10.3934/proc.2011.2011.672

[9]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[10]

Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064

[11]

Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851

[12]

Silvia Faggian. Boundary control problems with convex cost and dynamic programming in infinite dimension part II: Existence for HJB. Discrete & Continuous Dynamical Systems - A, 2005, 12 (2) : 323-346. doi: 10.3934/dcds.2005.12.323

[13]

Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052

[14]

Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305

[15]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078

[16]

Mickaël Crampon. Entropies of strictly convex projective manifolds. Journal of Modern Dynamics, 2009, 3 (4) : 511-547. doi: 10.3934/jmd.2009.3.511

[17]

Małgorzata Wyrwas, Dorota Mozyrska, Ewa Girejko. Subdifferentials of convex functions on time scales. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 671-691. doi: 10.3934/dcds.2011.29.671

[18]

Lorenzo Brasco, Eleonora Cinti. On fractional Hardy inequalities in convex sets. Discrete & Continuous Dynamical Systems - A, 2018, 38 (8) : 4019-4040. doi: 10.3934/dcds.2018175

[19]

Gang Li, Lipu Zhang, Zhe Liu. The stable duality of DC programs for composite convex functions. Journal of Industrial & Management Optimization, 2017, 13 (1) : 63-79. doi: 10.3934/jimo.2016004

[20]

Frank Natterer. Photo-acoustic inversion in convex domains. Inverse Problems & Imaging, 2012, 6 (2) : 315-320. doi: 10.3934/ipi.2012.6.315

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]