×

A global optimization approach for solving the convex multiplicative programming problem. (English) Zbl 0752.90056

Summary: We consider a convex multiplicative programming problem of the form \(\min\{f_ 1(x)\cdot f_ 2(x): x\in X\}\), where \(X\) is a compact convex subset of \(\mathbb{R}^ n\) and \(f_ 1\), \(f_ 2\) are convex functions which have nonnegative values over \(X\). Using two additional variables we transform this problem into a problem with a special structure in which the objective function depends only on two of the \((n+2)\) variables. Following a decomposition concept in global optimization we then reduce this problem to a master problem of minimizing a quasi-concave function over a convex set in \(\mathbb{R}^ 2_ +\). This master problem can be solved by an outer approximation method which requires performing a sequence of simplex tableau pivoting operations. The proposed algorithm terminates when the function \(f_ i\), \((i=1,2)\) are affine-linear and \(X\) is a polytope and it is convergent for the general convex case.

MSC:

90C25 Convex programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Aneja Y. P., Aggarwal V. and Nair K. (1984), On a Class of Quadratic Programming, European Journal of Oper. Res. 18, 62-70. · Zbl 0599.90094
[2] Bector C. R. and Dahl M. (1974), Simplex Type Finite Iteration Technique and Reality for a Special Type of Pseudo-Concave Quadratic Functions, Cahiers du Centre d’Etudes de Recherche Operationnelle 16, 207-222. · Zbl 0297.90064
[3] Gabasov, R. and Kirillova, F. M. (1980), Linear Programming Methods, Part 3 (Special Problems), Minsk (in Russian). · Zbl 0484.90067
[4] Hoffman K. L. (1981), A Method for Globally Minimizing Concave Functions over Convex Sets, Mathematical Programming 20, 22-32. · Zbl 0441.90096
[5] Horst R. and Thoai N. V. (1989), Modification, Implementation and Comparison of Three Algorithms for Globally Solving Linearly Constrained Concave Minimization Problems, Computing 42, 271-289. · Zbl 0675.65063
[6] Horst, R. and Tuy, H. (1990), Global Optimization: Deterministic Approaches, Springer-Verlag. · Zbl 0704.90057
[7] Horst R., Thoai N. V. and Tuy H. (1987), Outer Approximation by Polyhedral Convex Sets, Oper. Res. Spektrum 9, 153-159. · Zbl 0642.90094
[8] Horst R., Thoai N. V., and Tuy H. (1989), On an Outer Approximation Concept in Global Optimization, Optimization 20, 255-264. · Zbl 0675.90077
[9] Horst R., Thoai N. V., and de Vries J. (1988), On Finding New Vertices and Redundant Constraints in Cutting Plane Algorithms for Global Optimization, Oper. Res. Letters 7, 85-90. · Zbl 0644.90085
[10] Konno, H. and Kuno, T. (1989), Linear Multiplicative Programming, IHSS 89-13, Institute of Human and Social Sciences, Tokyo Institute of Technology.
[11] Kuno, T. and Konno, H. (1990), A Parametric Successive Underestimation Method for Convex Multiplicative Programming Problems, IHSS 90-19, Institute of Human and Social Sciences, Tokyo Institute of Technology. · Zbl 0752.90057
[12] Pardalos, P. M. (1988), Polynomial Time Algorithms for Some Classes of Constrained Nonconvex Quadratic Problems, Preprint, Computer Science Department, The Pennsylvania State University.
[13] Rockafellar R. T. (1970), Convex Analysis, Princeton University Press, Princeton, N.J. · Zbl 0193.18401
[14] Schaible S. (1976), Minimization of Ratios, J. Optimization Theory Appl. 19, 347-352. · Zbl 0308.90041
[15] Swarup K. (1966), Programming with Indefinite Quadratic Function with Linear Constraints, Cahiers de Centre d’Etudes de Recherche Operationnelle 8, 133-136. · Zbl 0141.17505
[16] Tuy H. (1985), Concave Minimization under Linear Constraints with Special Structure, Optimization 16, 335-352. · Zbl 0584.90080
[17] Tuy H. (1990), The Complementary Convex Structure in Global Optimization, Preprint, Institute of Mathematics, Hanoi. · Zbl 0734.90085
[18] Tuy H. and Tam B. T. (1990), An Efficient Solution Method for Rank Two Quasiconcave Minimization Problems, Preprint, Institute of Mathematics, Hanoi. · Zbl 0817.90079
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.