权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

使用分支定界算法解决非凸规划问题的统一方法

基本信息

批准号：
13680505
负责人：
KUNO Takahito
金额：
$ 2.24万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680505/
关键词：
Global optimization nonconvex program branch-and-bound method mathematical programming algorithm

项目摘要

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.

本文主要研究了三类非凸优化问题，它们在现实社会系统中有着丰富的应用：（1）在几乎所有的优化问题中，目标函数和约束函数都可以表示为两个凸函数的差。利用这一性质，问题可以转化为一个凸极小化问题与一个额外的反凸约束。我们提出了三个分支定界算法来解决这类非凸优化问题。我们表明，每个算法生成一个全局最优解在有限的迭代，如果反向凸约束函数是可分离的。(2)比率和问题是一个在凸集上最小化线性比率和的问题，并且已知是难以处理的。我们设计了一个廉价的程序来计算光学值的一个严格的下限。我们将其纳入一个分支定界算法，并成功地解决了这个问题比现有的算法快得多。(3)许多化工过程设计问题都可以转化为优化问题，但都是高度非凸的问题，如混合整数非线性规划问题。针对这类问题，提出了一种结合品牌定界法和修正的广义Benders分解法的混合算法。对一些典型的化工过程设计问题，证明了算法的全局最优性，所提出的算法都是基于分支定界的思想。为了有效地执行定界操作，我们还研究了一种求解松弛问题的邻域点算法。