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

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.

MSC:

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