Simplicial branch-and-reduce algorithm for convex programs with a multiplicative constraint (Q987514): Difference between revisions

The focus of the article is on solving the global optimization problem \(\min \{ f_0(x): \Pi_{i=1}^p f_i(x) \leq 1, x\in X \}\), where \(X \subset R^n\) is a compact convex set, \(p \geq 2\), \(f_i: R^n \to R\), \(i=0, 1, \dots, p\), are convex functions, and \(f_i\), \(i=1, \dots, p\), are positive valued on \(X\). The author presents a branch-and-reduce algorithm for finding a global optimal solution. To globally solve this problem, the algorithm instead globally solves an equivalent master problem. At any stage of the algorithm, a disconnected set consisting of a union of simplices is constructed. This set is guaranteed to contain a portion of the boundary of the feasible region of the master problem where a global optimal solution lies. The algorithm uses a new branch-and-reduce scheme to iteratively reduce the sizes of these sets until a global optimal solution is found. Several potential computational advantages of the algorithm are explained, and a numerical example is solved.