Global optimization in reduced space

[摘要] Optimization is a key activity in any engineering discipline. Global optimization methods, in particular, strive to solve nonconvex problems, which often arise in chemical engineering, and deterministic algorithms such as branch-and-bound provide a certificate of optimality for the identified solution. Unfortunately, the worst-case runtime of these algorithms is exponential in the problem dimension. This leads to the notion of reduced-space problem formulations where either the number of variables that the algorithm branches on is reduced or only the actual degrees of freedom are visible to the optimization algorithms, following a partition of the variables into independent and dependent ones. This approach introduces new challenges though: McCormick relaxations, which are very easily applied in this setting, can be nonsmooth, the minima are very likely to be unconstrained causing the cluster problem and the information contained in the constraints is not as readily exploited. In this thesis, several advances to both theory and methods are reported. First, a new analysis of the cluster problem is provided reaffirming the importance of second-order convergent bounding methods. The cluster problem refers to the phenomenon whereby a large number of boxes in the vicinity of a minimum are visited by branch-and-bound algorithms. In particular, it is shown that tighter relaxations can lead to a significant reduction in the number of boxes visited. Next, a constraint propagation technique for intervals is extended to McCormick relaxations. This reverse McCormick update utilizes information in the constraints and improves relaxations of the dependent variables, which can be used to either strengthen the relaxations of the feasible set or, using generalized McCormick relaxations, to construct reduced-space relaxations of the objective function. Third, a second-order convergent interval bounding method for the zeros of parametric nonlinear systems of equations is presented. This is useful to provide second-order convergent interval information to generalized McCormick relaxations, e.g., in the reverse propagation scheme. Fourth, the theory underpinning McCormick relaxations is extended to a class of discontinuous functions. It is further shown that branch-and-bound algorithms still possess their convergence properties.

[发布机构] Massachusetts Institute of Technology