Global optimization in reduced space-猫眼课题宝

缩小空间的全局优化

DOI：

发表时间：

2014

期刊：

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

A. Wechsung

优化是任何工程的关键活动纪律。尤其是全球优化方法解决非概念问题，通常在化学中出现工程和确定性算法，例如分支机构为确定的解决方案提供最佳证书。不幸的是，这些算法的最差案例运行时间是问题维度的指数。这导致了缩小空间问题公式的数量算法分支的变量减少或仅减少实际的自由度可见算法，将变量分为独立和依赖的。这种方法引入了新的挑战：麦考密克放松，很容易应用设置，可能是非平滑的，很可能是不受约束，导致集群问题和信息约束中包含的不容易被利用。在这个论文报道了理论和方法的几个进步。首先，提供了群集问题的新分析重申二阶收敛边界的重要性方法。集群问题是指A 最低附近的大量箱子由分支结合算法。特别是表明更紧密的放松会导致大幅减少访问的盒子数量。接下来，一种约束传播技术为了间隔，将扩展到麦考密克放松。这个反向 McCormick更新在约束和改善因变量的放松，可以使用要么加强可行集合的放松，要么使用广义的麦考密克放松，构建缩小空间放松目标功能。第三，二阶参数零的收敛间隔边界方法提出了方程式的非线性系统。这对向广义提供二阶收敛间隔信息麦考密克放松，例如，在反向传播方案中。第四，基于麦考密克放松的理论扩大了到一类不连续的函数。进一步表明分支和结合算法仍然具有收敛性特性。

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.

Global optimization in reduced space

缩小空间的全局优化

文献摘要

被引文献

相似文献