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

我们主要研究了三类在现实社会系统中有着广泛应用的非凸优化问题：(1)在几乎所有的优化问题中，目标函数和约束函数都可以表示为两个凸函数的差。利用这一性质，可以将问题转化为一个带有附加反凸约束的凸极小化问题。针对这类非凸优化问题，我们提出了三种分枝定界算法。我们证明了如果反凸约束函数是可分的，则每个算法在有限次迭代中都会产生一个全局最优解。(2)比率和问题是一个极小化凸集上的线性配给和的问题，并且众所周知是难以解决的。我们设计了一个廉价的程序来计算光学值的下限。我们将其融入到分支定界算法中，并成功地解决了比现有算法快得多的问题。(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.