Branchandreduce algorithm for convex programs with additional multiplicative constraints
This article presents a branchandreduce algorithm for globally solving for the first time a convex minimization problem (P) with p[greaterorequal, slanted]1 additional multiplicative constraints. In each of these p additional constraints, the product of two convex functions is constrained to be less than or equal to a positive number. The algorithm works by globally solving a 2pdimensional master problem (MP) equivalent to problem (P). During a typical stage k of the algorithm, a point is found that minimizes the objective function of problem (MP) over a nonconvex set Fk that contains the portion of the boundary of the feasible region of the problem where a global optimal solution lies. If this point is feasible in problem (MP), the algorithm terminates. Otherwise, the algorithm continues by branching and creating a new, reduced nonconvex set Fk+1 that is a strict subset of Fk. To implement the algorithm, all that is required is the ability to solve standard convex programming problems and to implement simple algebraic steps. Convergence properties of the algorithm are given, and results of some computational experiments are reported.
Year of publication: 
2009


Authors:  Benson, Harold P. ; Sun, Erjiang 
Published in: 
European Journal of Operational Research.  Elsevier, ISSN 03772217.  Vol. 199.2009, 1, p. 18

Publisher: 
Elsevier 
Keywords:  Global optimization Multiplicative programming Product of convex functions Branchandreduce 
Saved in favorites
Similar items by person

Benson, Harold P., (2002)

Branchandreduce algorithm for convex programs with additional multiplicative constraints
Benson, Harold P., (2009)

Benson, Harold P., (2002)
 More ...