Abstract
This paper addresses the problem of minimizing an arbitrary finite sum of products of two convex functions over a convex set. Nonconvex problems in this form constitute a class of generalized convex multiplicative problems. Convex analysis results allow to reformulate the problem as an indefinite quadratic problem with infinitely many linear constraints. Special properties of the quadratic problem combined with an adequate outer approximation procedure for handling its semi-infinite constrained set enable an efficient constraint enumeration global optimization algorithm for generalized convex multiplicative programs. Computational experiences illustrate the proposed approach.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Benson H.P.: An outcome space branch and bound-outer approximation algorithm for convex multiplicative programming. J. Glob. Optim. 15, 315–342 (1999)
Benson H.P.: Global optimization of nonlinear sums of ratios. J. Math. Anal. Appl. 263, 301–315 (2001)
Benson H.P.: A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem. Eur. J. Oper. Res. 182, 597–611 (2007)
Benson H.P.: Global maximization of a generalized concave multiplicative function. J. Optim. Theory Appl. 137, 105–120 (2008)
Bertsekas D.P.: Nonlinear Programming. 2nd edn. Athena Scientific, Belmont (1995)
Falk J.E., Palocsay S.W.: Optimizing the sum of linear fractional functions. In: Floudas, C., Pardalos, M. (eds) Recent Advances in Global Optimization, pp. 221–258. Princeton University Press, Princeton (1992)
Falk J.E., Palocsay S.W.: Image space analysis of generalized fractional programs. J. Glob. Optim. 4, 63–88 (1994)
Floudas C.A., Visweswaran V.: Quadratic optimization. In: Horst, R., Pardalos, P.M. (eds) Handbook of Global Optimization, pp. 217–269. Kluwer, Netherlands (1991)
Hager W.W., Pardalos P.M., Roussos I.M., Sahinoglou H.D.: Active constraints, indefinite quadratic test problems, and complexity. J. Optim. Theory Appl. 68, 499–511 (1991)
Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Netherlands (1995)
Jaumard B., Meyer C., Tuy H.: Generalized convex multiplicative programming via quasiconcave minimization. J. Glob. Optim. 10, 229–256 (1997)
Katoh N., Ibaraki T.: A parametric characterization and an ε-approximation scheme for the minimization of a quasiconcave program. Discrete Appl. Math. 17, 39–66 (1987)
Konno H., Kuno T.: Generalized linear multiplicative and fractional programming. Ann. Oper. Res. 25, 147–161 (1990)
Konno H., Kuno T.: Multiplicative programming problems. In: Horst, R., Pardalos, P.M. (eds) Handbook of Global Optimization, pp. 369–405. Kluwer, Netherlands (1995)
Konno H., Yajima Y., Matsui T.: Parametric simplex algorithms for solving a special class of nonconvex minimization problems. J. Glob. Optim. 1, 65–81 (1991)
Konno H., Kuno T., Yajima Y.: Global minimization of a generalized convex multiplicative function. J. Glob. Optim. 4, 47–62 (1994)
Konno H., Yamashita H.: Minimizing sums and products of linear fractional functions over a polytope. Nav. Res. Logist. 46, 583–596 (1999)
Kuno T., Yajima Y., Konno H.: An outer approximation method for minimizing the product of several convex functions on a convex set. J. Glob. Optim. 3, 325–335 (1993)
Lasdon L.S.: Optimization Theory for Large Systems. MacMillan Publishing Co., New York (1970)
MATLAB, User’s Guide, The MathWorks Inc., http://www.mathworks.com/
Oliveira R.M., Ferreira P.A.V.: A convex analysis approach for convex multiplicative programming. J. Glob. Optim. 41, 579–592 (2008)
Pardalos P.M.: Global optimization algorithms for linearly constrained indefinite quadratic programming problems. Comput. Math. Appl. 21, 87–97 (1991)
Quesada I., Grossmann I.E.: Global optimization algorithm for heat exchanger networks. Ind. Eng. Chem. Res. 32, 487–499 (1993)
Royden H.L.: Real Analysis. Macmillan Publishing Co., New York (1988)
Ryoo H.S., Sahinidis N.V.: Analysis of bounds for multilinear functions. J. Glob. Optim. 19, 403–424 (2001)
Ryoo H.S., Sahinidis N.V.: Global optimization of multiplicative problems. J. Glob. Optim. 26, 387–418 (2003)
Schaible S.: Fractional programming. In: Horst, R., Pardalos, P.M. (eds) Handbook of Global Optimization, pp. 495–608. Kluwer, Netherlands (1995)
Tuy H.: Convex Analysis and Global Optimization. Kluwer, Dordrecht (1998)
Yu P.-L.: Multiple-Criteria Decision Making. Plenum Press, New York (1985)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Oliveira, R.M., Ferreira, P.A.V. An outcome space approach for generalized convex multiplicative programs. J Glob Optim 47, 107–118 (2010). https://doi.org/10.1007/s10898-009-9460-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-009-9460-9