An outcome space branch and bound-outer approximation algorithm for convex multiplicative programming. (English) Zbl 0997.90078

Benson, Harold P.

J. Glob. Optim. 15, No. 4, 315-342 (1999).

The article under review is a valuable contribution to both theory and, in particular, numerical analysis of so-called convex multiplicative programming. By definition, in this field of nonlinear minimization the objective function is a finite product of convex functions over some compact convex set \(D\). Such a problem \((P_D)\) arises in economic analysis, portfolio and multi-objective optimization, and in VLSI design.
In order to solve this NP-hard problem with computational savings, the author bases his development of an approximate algorithm on an equivalent quasiconcave minimization problem, called outcome space problem \((P_Y)\).
Assuming \(D\) finitely convex and differentiably defined, the algorithm firstly implies outer approximation of the nonempty, compact outcome space \(Y\) by decreasing polytopes, found by a nonlinear convex program, resolution of a system of linear (in)equalities, and a “cut off” from one iteration to the other. Herewith, the algorithm works “economized”. Secondly, we find branching and, thirdly, bounding techniques from linear programming, prepared by suitable notions and notations.
The author presents an (upon termination) finite convergence theorem to an \(\varepsilon\)-optimal solution, and gives detailed computational issues. Finally, this carefully written investigation in global optimization becomes applied to a numerical example.

Reviewer: Gerhard-Wilhelm Weber (Darmstadt)

MSC:

90C30	Nonlinear programming
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C26	Nonconvex programming, global optimization
65K05	Numerical mathematical programming methods

Keywords:

branch and bound algorithm; convex multiplicative programming; quasiconcave minimization; outcome space problem