共查询到20条相似文献,搜索用时 15 毫秒
1.
This paper presents an efficient branch and bound algorithm for globally solving sum of geometric fractional functions under geometric constraints, which arise in various practical problems. By using an equivalent transformation and a new linear relaxation technique, a linear relaxation programming problem of the equivalent problem is obtained. The proposed algorithm is convergent to the global optimal solution by means of the subsequent solutions of a series of linear programming problems. Numerical results are reported to show the feasibility of our algorithm. 相似文献
2.
In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial
fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic
difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear
underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently,
the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively
refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the
primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed
algorithm is feasible and can successfully be used to solve the present problem (P). 相似文献
3.
对广义几何规划问题(GGP)提出了一个确定型全局优化算法,这类优化问题能广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中,使用指数变换及对目标函数和约束函数的线性下界估计,建立了GGP的松弛线性规划(RLP),通过对RLP可行域的细分以及一系列RLP的求解过程,从理论上证明了算法能收敛到GGP的全局最优解,对一个化学工程设计问题应用本文算法,数值实验表明本文方法是可行的。 相似文献
4.
5.
In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum. 相似文献
6.
为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的. 相似文献
7.
本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的. 相似文献
8.
对许多工程设计中常用的广义几何规划问题(GGP)提出一种确定性全局优化算法,该算法利用目标和约束函数的线性下界估计,建立GGP的松弛线性规划(RLP),从而将原来非凸问题(GGP)的求解过程转化为求解一系列线性规划问题(RLP).通过可行域的连续细分以及一系列线性规划的解,提出的分枝定界算法收敛到GGP的全局最优解,且数值例子表明了算法的可行性. 相似文献
9.
提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的. 相似文献
10.
Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented. 相似文献
11.
本文提出了一个求不定二次规划问题全局最优解的新算法.首先,给出了三种计算下界的方法:线性逼近法、凸松弛法和拉格朗日松弛法;并且证明了拉格朗日对偶界与通过凸松弛得到的下界是相等的;然后建立了基于拉格朗日对偶界和矩形两分法的分枝定界算法,并给出了初步的数值试验结果. 相似文献
12.
This paper is concerned with the development of an algorithm to solve continuous polynomial programming problems for which the objective function and the constraints are specified polynomials. A linear programming relaxation is derived for the problem based on a Reformulation Linearization Technique (RLT), which generates nonlinear (polynomial) implied constraints to be included in the original problem, and subsequently linearizes the resulting problem by defining new variables, one for each distinct polynomial term. This construct is then used to obtain lower bounds in the context of a proposed branch and bound scheme, which is proven to converge to a global optimal solution. A numerical example is presented to illustrate the proposed algorithm. 相似文献
13.
14.
Hongwei Jiao Sanyang Liu Yongqiang Chen 《Journal of Applied Mathematics and Computing》2012,40(1-2):551-568
This article present a branch and bound algorithm for globally solving generalized linear multiplicative programming problems with coefficients. The main computation involve solving a sequence of linear relaxation programming problems, and the algorithm economizes the required computations by conducting the branch and bound search in R p , rather than in R n , where p is the number of rank and n is the dimension of decision variables. The proposed algorithm will be convergent to the global optimal solution by means of the subsequent solutions of the series of linear relaxation programming problems. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm. 相似文献
15.
本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小. 相似文献
16.
针对一类多乘积规划问题(MP),给出一个加速算法.首先导出一个与(MP)等价的逆凸问题(RCP),然后构造问题(RCP)的线性松弛化问题.算法的主要特点是提出了两个加速技巧,这些技巧可以用于改善算法的收敛速度.数值算例表明算法是可行的. 相似文献
17.
18.
In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm
uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each
node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step
is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear
programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower
bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP
techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing
algorithms for these types of problems. 相似文献
19.
20.
《Optimization》2012,61(5):627-641
We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem. 相似文献