共查询到18条相似文献,搜索用时 78 毫秒
1.
本文提出了一种求解带二次约束和线性约束的二次规划的分支定界算法.在算法中,我们运用Lipschitz条件来确定目标函数和约束函数的在每个n矩形上的上下界,对于n矩形的分割,我们采用选择n矩形最长边的二分法,同时我们采用了一些矩形删除技术,在不大幅增加计算量的前提下,起到了加速算法收敛的效果.从理论上我们证明了算法的收敛性,同时数值实验表明该算法是有效的. 相似文献
2.
3.
4.
5.
给出了粒子群算法中惯性权值和学习因子的一种简单改进,并将其应用到非凸二次规划的求解中,通过数值试验与现有的求解非凸二次规划问题的分支定界法进行了比较,得到了较好的结果. 相似文献
6.
解带有二次约束二次规划的一个整体优化方法 总被引:1,自引:0,他引:1
在本文中,我们提出了一种解带有二次约束二次规划问题(QP)的新算法,这种方法是基于单纯形分枝定界技术,其中包括极小极大问题和线性规划问题作为子问题,利用拉格朗日松弛和投影次梯度方法来确定问题(QP)最优值的下界,在问题(QP)的可行域是n维的条件下,如果这个算法有限步后终止,得到的点必是问题(QP)的整体最优解;否则,该算法产生的点的序列{v^k}的每一个聚点也必是问题(QP)的整体最优解。 相似文献
7.
8.
9.
针对一类非负整数二次规划问题,提出了一个新的分枝定界缩减方法.在这个方法里,使用了一个新的超矩形二分技术和一个新的线性规划松弛定下界技术,同时为了提高逼近程度和加快收敛速度,使用了超矩形缩减策略.数值结果表明所提出的算法是可行的和有效的. 相似文献
10.
本文给出确定线性约束0-1二次规划问题最优值下界的方法,该方法结合McBride和Yormark的思想和总体优化中定下界的方法,证明了所定的界较McBride和Yormark的要好.求解线性约束0-1二次规划问题的分支定界算法可以利用本文的定界技术. 相似文献
11.
Decomposition Methods for Solving Nonconvex Quadratic Programs via Branch and Bound* 总被引:1,自引:0,他引:1
The aim of this paper is to suggest branch and bound schemes, based on a relaxation of the objective function, to solve nonconvex
quadratic programs over a compact polyhedral feasible region. The various schemes are based on different d.c. decomposition
methods applied to the quadratic objective function. To improve the tightness of the relaxations, we also suggest solving
the relaxed problems with an algorithm based on the so called “optimal level solutions” parametrical approach.
*This paper has been partially supported by M.I.U.R. and C.N.R. 相似文献
12.
Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem 总被引:1,自引:0,他引:1
In this paper, we consider problem (P) of minimizing a quadratic function q(x)=x
t
Qx+c
t
x of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this,
we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x
i
2=x
i, we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable
vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first
one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P) is solved.
We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our two solution methods
to several other exact solution methods. Furthermore, we report computational results for the max-cut problem. 相似文献
13.
A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems 总被引:6,自引:0,他引:6
This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems. 相似文献
14.
不等式约束二次规划的一新算法 总被引:3,自引:0,他引:3
文献[1]提出了一般等式约束非线性规划问题一种求解途径.文献[2]应用这一途径给出了等式约束二次规划问题的一种算法,本文在文献[1]和[2]的基础上对不等式约束二次规划问题提出了一种新算法. 相似文献
15.
16.
一种内点法解二次规划 总被引:2,自引:0,他引:2
二次规划(QP)为NP完全问题,本文研究了一种简单形式的二次规划。 一种基于依赖域子问题和内点法的算法被给出,其全局收敛被给出,特殊情况下,具有局部二次收敛。 相似文献
17.
Zi-Luan Wei 《计算数学(英文版)》2002,20(6):643-652
A regular splitting and potential reduction method is presented for solving a quadratic programming problem with box constraints (QPB) in this paper. A general algorithm is designed to solve the QPB problem and generate a sequence of iterative points. We show that the number of iterations to generate an e-minimum solution or an e-KKT solution by the algorithm is bounded by O( nlog(1 )), and the total running time is bounded by O(n2(n logn log1/ε)(n/εlog1/ε logn)) arithmetic operations. 相似文献
18.
1IntroductionWeconsiderastrictlyconvex(i.e.,positivedefinite)quadraticprogrammingproblemsubjecttoboxconstraints:t-iereA=[aij]isannxnsymmetricpositivedefinitematrix,andb,canddaren-vectors.Letg(x)bethegradient,Ax b,off(x)atx.Withoutlossofgeneralityweassumebothcianddiarefinitenumbers,ci相似文献