Abstract
This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Konno, H., Kuno, T., Yajima, Y.: Global minimization of a generalized convex multiplicative function. J. Glob. Optim. 4, 47–62 (1994)
Cambini, R., Sodini, C.: Decomposition methods for solving nonconvex quadratic programs via branch and bound. J. Glob. Optim. 33, 313–336 (2006)
Tuy, H.: Convex Analysis and Global Optimization. Kluwer Academic, Dordrecht (1998)
Pardalos, P.M., Rosen, J.B.: Constrained Global Optimization: Algorithms and Applications. Springer, Berlin (1987)
Floudas, C.A., Visweswaran, V.: Quadratic optimization. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, pp. 217–269. Kluwer Academic, Dordrecht (1995)
Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic, Dordrecht (1995)
Watanabe, H.: IC layout generation and compaction using mathematical programming. Ph.D. Thesis, University of Rochester (1984)
Konno, H., Yajima, Y.: Solving rank two bilinear programs by parametric simplex algorithms. Institute of Human and Social Sciences Working Paper IHSS 90–17, Tokyo Institute of Technology (1990)
Konno, H., Thach, P.T., Tuy, H.: Optimization on Low Rank Nonconvex Structures. Kluwer Academic, Dordrecht (1997)
Mangasarian, O.L.: Equilibrium points of bimatrix games. SIAM J. 12, 778–780 (1964)
Freize, A.M.: A bilinear programming formulation of the 3-dimensional assignment problem. Math. Program. 7, 376–379 (1979)
Falk, J.E.: A linear max-min problem. Math. Program. 5, 169–188 (1973)
Raghavachari, M.: On connections between zero-one integer programming and concave programming under linear constraints. Oper. Res. 17, 680–684 (1969)
Nemhauser, G.L., Wolsey, L.A.: Combinatorial Optimization. Wiley, New York (1998)
Avriel, M., Diewart, W.E., Schaible, S., Zang, I.: Generalized Concavity. Plenum, New York (1988)
Benson, H.P.: Global maximization of a generalized concave multiplicative function. Warrington College of Business Administration Working Paper, University of Florida (2007)
Horst, R., Tuy, H.: Global Optimization—Deterministic Approaches. Springer, Berlin (1993)
Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8, 273–286 (1983)
Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming—Theory and Algorithms. Wiley, New York (1993)
Benson, H.P.: Deterministic algorithms for constrained concave minimization: a unified critical survey. Nav. Res. Logist. 43, 765–795 (1996)
LINDO SYSTEMS: Optimization modeling with LINGO. LINDO Systems, Chicago (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Benson, H.P. Global Maximization of a Generalized Concave Multiplicative Function. J Optim Theory Appl 137, 105–120 (2008). https://doi.org/10.1007/s10957-007-9323-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-007-9323-9