A unified approach to nonconvex programming problems using branch-and-bound algorithms

我们主要研究了三类非凸优化问题，每一类问题在现实社会系统中都有丰富的应用：(1)在几乎所有优化问题中，目标函数和约束函数都可以写成两个凸函数的差。利用这一性质，可以将该问题转化为带有附加反向凸约束的凸最小化问题。针对这类非凸优化问题，提出了三种分支定界算法。我们证明了如果逆凸约束函数是可分离的，每个算法在有限迭代中产生一个全局最优解。比率和问题是一个最小化凸集上的线性比率和的问题，并且已知是难以处理的。我们设计了一种计算光学值的严格下界的廉价程序。我们将其融入到分支定界算法中，并成功地以比现有算法更快的速度解决了问题。(3)许多化工过程设计问题可以表述为优化问题，但高度非凸问题，如混合整数非线性规划问题。为了解决这类问题，我们提出了一种混合的品牌绑定算法和改进的通用弯曲器分解方法。然后，我们证明了该算法确实收敛于一些典型化工过程设计问题的全局最优解。每一种算法都是基于分支定界的思想。为了有效地执行边界运算，我们还研究了一种求解松弛问题的内点算法。

We made a study mainly on three classes of nonconvex optimization problems, each of which is abundant in applications to real-world social systems :(1) In almost every optimization problem, both objective and constraint functions can be written as the difference of two convex functions. Using this property, the problem can be trans-formed into a convex minimization problem with an additional reverse convex constraint. We proposed three branch-and-bound algorithms for solving this kind of nonconvex optimization problems. We showed that each algorithm generates a globally optimal solution in finite iterations if the reverse convex constraint function is separable.(2) The sum-of-ratios problem is a problem, of minimizing a sum of linear rations over a convex set, and is known to be intractable. We devised an inexpensive procedure for computing a tignt lower bound on the optical value. We incorporated it into a branch-and-bound algorithm and succeeded in solving the problem much faster than the existing algorithms.(3) Many of chemical process design problems can be formulated as optimization problems but highly nonconvex ones, say mixed-integer nonlinear programming problems. To solve this kind of problems, we proposed a hybrid algorithm of brand-and-bound and revised general benders decomposition methods. We then proved that the algorithm certainly converges to globally optimal solutions for some typical chemical process design problems.Each of the proposed algorithms is based on the idea of branch and bound. To execute the bounding operations efficiently, we also studied an interior-point algorithm for solving relaxed problems.