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

Nguyen Van Thoai

J. Glob. Optim. 1, No. 4, 341-357 (1991).

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

Keywords:

convex multiplicative programming; decomposition; global optimization; outer approximation

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