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

点击翻译按钮获取中文摘要

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.