Convex Programming Methods for Global Optimization

We investigate some approaches to solving nonconvex global optimization problems by convex nonlinear programming methods. We assume that the problem becomes convex when selected variables are fixed. The selected variables must be discrete, or else discretized if they are continuous. We provide a survey of disjunctive programming with convex relaxations, logic-based outer approximation, and logic-based Ben- ders decomposition. We then introduce a branch-and-bound method with convex quasi-relaxations (BBCQ) that can be effective when the discrete variables take a large number of real values. The BBCQ method gener- alizes work of Bollapragada, Ghattas and Hooker on structural design problems. It applies when the constraint functions are concave in the discrete variables and have a weak homogeneity property in the contin- uous variables. We address global optimization problems that become convex when selected variables are fixed. If these variables are discrete, the constraints can be refor- mulated as logical disjunctions of convex constraints. If some of the selected variables are not discrete, we discretize them in order to obtain an approximate global solution. The motivation for this approach is to take advantage of highly developed nonlinear programming methods for convex problems, as well as branch-and- bound methods for discrete problems. A branch-and-bound method chooses the appropriate disjunct in each constraint. Nonlinear programming is applied to the convex subproblem that results when the disjuncts are chosen. We present four variations of this general approach. Two of them are most practical when the discrete variables do not take a large number of possible val- ues: (a) disjunctive programming with convex relaxations, and (b) logic-based outer approximation. The disjunctive programming model can also be solved as a mixed integer/nonlinear programming (MINLP) problem. When there are a large number of discrete values, as when some discrete variables represent discretized continuous variables, one can turn to methods that do not require explicit representation of the disjunctions: (c) logic-based Benders decomposi- tion, and (d) branch and bound with convex quasi-relaxations (BBCQ). The