A global optimization algorithm for linear fractional and bilinear programs.

*(English)*Zbl 0835.90074Summary: A deterministic method is proposed for the global optimization of mathematical programs that involve the sum of linear fractional and/or bilinear terms. Linear and nonlinear convex estimator functions are developed for the linear fractional and bilinear terms. Conditions under which these functions are nonredundant are established. It is shown that additional estimators can be obtained through projections of the feasible region that can also be incorporated in a convex nonlinear underestimator problem for predicting lower bounds for the global optimum. The proposed algorithm consists of a spatial branch-and-bound search for which several branching rules are discussed. Illustrative examples and computational results are presented to demonstrate the efficiency of the proposed algorithm.

##### Keywords:

bilinear programming; convex underestimators; global optimization; linear fractional and bilinear terms; spatial branch-and-bound
PDF
BibTeX
Cite

\textit{I. Quesada} and \textit{I. E. Grossmann}, J. Glob. Optim. 6, No. 1, 39--76 (1995; Zbl 0835.90074)

Full Text:
DOI

##### References:

[1] | Al-Khayyal, F.A. (1992), Generalized bilinear programming: Part I. Models, applications and linear programming relaxation,European Journal of Operational Research 60, 306-314. · Zbl 0784.90051 |

[2] | Al-Khayyal, F.A. and Falk, J.E. (1983), Jointly constrained biconvex programming,Mathematics of Operations Research 8, 273-286. · Zbl 0521.90087 |

[3] | Bazaraa, M.S. and Shetty, C.M. (1979),Nonlinear Programming Theory and Algorithms, John Wiley & Sons, New York. · Zbl 0476.90035 |

[4] | Charnes, A. and Cooper, W.W. (1962), Programming with linear fractional functionals,Naval Research Logistics Quarterly 9, 181-186. · Zbl 0127.36901 |

[5] | Dinkelbach, W. (1967), On nonlinear fractional programming,Management Science 13, 492-498. · Zbl 0152.18402 |

[6] | Falk, J.E. and Palocsay, S.W. (1992), Optimizing the sum of linear fractional functions,Recent Advances in Global Optimization, in Floudas, C.A and Pardalos, P.M. (eds.), 221-258. |

[7] | Floudas, C.A. and Pardalos, P.M. (1990),A Collection of Test Problems for Constrained Global Optimization Algorithms, G. Goss and J. Hartmanis (eds.), Springer Velag. · Zbl 0718.90054 |

[8] | Floudas, C.A. and Visweswaran, V. (1990), A global optimization algorithm (GOP) for certain classes of nonconvex NLPs-I Theory,Computers Chem. Engng. 14, 1397-1417. |

[9] | Grossmann, I.E. (1990), Mixed-Integer Non-Linear Programming Techniques for the Synthesis of Engineering System,Res. Eng. Des. 1, 205-228. |

[10] | Horst, R. (1990), Deterministic methods in constrained global optimization: Some recent advances and fields of application,Naval Research Logistics 37, 433-471. · Zbl 0709.90093 |

[11] | Horst, R. and Tuy, T. (1990),Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin, New York. · Zbl 0704.90057 |

[12] | Konno, H., Yajima, Y. and Matsui, T. (1991), Parametric Simplex Algorithms for Solving a Special Class of Nonconvex Minimization Problems.Journal of Global Optimization 1, 65-81. · Zbl 0746.90056 |

[13] | Lasdon, L.S., Waren, A.D., Sarkar, S., and Palacios, F. (1979), Solving the Pooling Problem Using Generalized Reduced Gradient and Successive Linear Programming Algorithms,SIGMAP Bull 77, 9-15. |

[14] | Liebman, J., Lasdon, L., Schrage, L., and Waren, A. (1986),Modelling and Optimization with GINO, The Scientific Press, Palo Alto, CA. |

[15] | Lo, C. and Papalambros, P.Y. (1990), A Deterministic Global Design Optimization Method for Nonconvex Generalized Polynomial Problems,Advances in Design Automation, New York. |

[16] | McCormick, G.P. (1976), Computability of Global Solutions to Factorable Nonconvex Programs: Part I ? Convex Underestimating Problems,Mathematical Programming,10, 146-175. · Zbl 0349.90100 |

[17] | Papalambros, P. and Wilde, D.L. (1988),Principles of Optimal Design: Modelling and Computation, Cambridge University Press, Cambridge. · Zbl 0654.90047 |

[18] | Quesada, I. and Grossmann, I.E. (1993), Global optimization algorithm for heat exchanger netwoks.Ind. Eng. Chem. Res.,32. 487-499. |

[19] | Quesada, I. and Grossmann, I.E. (1995), Global optimization of process networks with multicomponent flows. To appear inComputers and Chem. Eng. · Zbl 0835.90074 |

[20] | Reklaitis, G.V. and Ravindran, A. (1983),Engineering Optimization: Methods and Applications. Wiley, New York. |

[21] | Sahinidis, N.V. and Grossmann, I.E. (1991), Convergence Properties of Generalized Benders Decomposition.Computers and Chem. Eng. 15, 481-491. |

[22] | Schoen, F. (1991), Stochastic Techniques for Global Optimization: A Survey of Recent Advances.Journal of Global Optimization 1, 207-228 · Zbl 0752.90071 |

[23] | Sherali, H.D. and Alameddine, A. (1992), A new reformulation-linearization technique for bilinear programming problems,Journal of Global Optimization 2, 379-410. · Zbl 0791.90056 |

[24] | Swaney, R.E. (1993), Global solution of algebraic nonlinear programs. Paper MC36.3 presented at TIMS/ORSA meeting, Phoenix, AZ. |

[25] | Visweswaran, V. and Floudas, C. A. (1990), A global optimization algorithm (GOP) for certain classes of nonconvex NLPs-II Application of theory and test problems,Computers Chem. Engng. 14, 1419. |

[26] | Visweswaran, V. and Floudas, C.A. (1991), Global optimization of problems with polynomial functions in one variable.Recent Advances in Global Optimization, in Floudas, C.A and Pardalos, P.M. (eds.), 165-199. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.