共查询到20条相似文献,搜索用时 125 毫秒
1.
基于非线性规划和割平面方法,给出了凸半无限规划问题的一个分析中央割平面算法(ACCPM).该算法不需要在每一次迭代时计算所有的约束数值,而只需要求解一个中央割平面,从而使得问题的求解规模变小,这种算法对于求解可行域结构比较复杂的半无限规划非常有效,最后给出算法的收敛性证明. 相似文献
2.
3.
本文给出了求解一类凸二次规划问题的新算法.这种算法既保留了传统算法的优点,又避免了其它算法中出现的添加人工变量过多、循环等问题.算例表明,这种算法是简便而有效的. 相似文献
4.
本文提出了一种求解某类等式约束二次规划问题的一个共轭方向迭代法,并给出了算法的有限终止性证明.同时我们把此算法推广到不等式约束二次规划问题中,从而得到了一种求解不等式约束二次规划问题的算法. 相似文献
5.
6.
7.
以下层问题的K-T最优性条件代替下层问题,将线性二层规划转化为相应的单层规划问题,通过分析单层规划可行解集合的结构特征,设计了一种求解线性二层规划全局最优解的割平面算法.数值结果表明所设计的割平面算法是可行、有效的. 相似文献
8.
标准的二次优化问题是NP-hard问题,把该问题转化为半不定的线性规划问题,且提出了一个线性规划的割平面算法来求解这个半不定的线性规划问题,并给出了该算法的收敛性证明. 相似文献
9.
郭飞 《应用数学与计算数学学报》1997,11(1):19-26
Wilson,Han和Powell提出的序列二次规划方法(简称SQP方法)是求解非线性规划问题的一个著名方法,这种方法每次迭代的搜索方向是通过求解一个二次规划子问题得到的,本文受[1]启发,得到二次规划子问题的一个近似解,进而给出了一类求解线性约束非线性规划问题的可行方向法,在约束集合满足正则性的条件下,证明了该算法对五种常用线性搜索方法具有全局收敛性。 相似文献
10.
一种内点法解二次规划 总被引:2,自引:0,他引:2
二次规划(QP)为NP完全问题,本文研究了一种简单形式的二次规划。 一种基于依赖域子问题和内点法的算法被给出,其全局收敛被给出,特殊情况下,具有局部二次收敛。 相似文献
11.
This paper presents an improved lower bound and an approximation algorithm based on spectral decomposition for the binary
constrained quadratic programming problem. To decompose spectrally the quadratic matrix in the objective function, we construct
a low rank problem that provides a lower bound. Then an approximation algorithm for the binary quadratic programming problem
together with a worst case performance analysis for the algorithm is provided. 相似文献
12.
Zdeněk Dostál 《Journal of Computational and Applied Mathematics》2009,231(2):577-591
By combining FETI algorithms of dual-primal type with recent results for bound constrained quadratic programming problems, we develop an optimal algorithm for the numerical solution of coercive variational inequalities. The model problem is discretized using non-penetration conditions of mortar type across the potential contact interface, and a FETI-DP algorithm is formulated. The resulting quadratic programming problem with bound constraints is solved by a scalable algorithm with a known rate of convergence given in terms of the spectral condition number of the quadratic problem. Numerical experiments for non-matching meshes across the contact interface confirm the theoretical scalability of the algorithm. 相似文献
13.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献
14.
15.
A two level global optimization algorithm for multidimensional scaling (MDS) with city-block metric is proposed. The piecewise quadratic structure of the objective function is employed. At the upper level a combinatorial global optimization problem is solved by means of branch and bound method, where an objective function is defined as the minimum of a quadratic programming problem. The later is solved at the lower level by a standard quadratic programming algorithm. The proposed algorithm has been applied for auxiliary and practical problems whose global optimization counterpart was of dimensionality up to 24. 相似文献
16.
Solving large scale Max Cut problems via tabu search 总被引:1,自引:0,他引:1
Gary A. Kochenberger Jin-Kao Hao Zhipeng Lü Haibo Wang Fred Glover 《Journal of Heuristics》2013,19(4):565-571
In recent years many algorithms have been proposed in the literature for solving the Max-Cut problem. In this paper we report on the application of a new Tabu Search algorithm to large scale Max-cut test problems. Our method provides best known solutions for many well-known test problems of size up to 10,000 variables, although it is designed for the general unconstrained quadratic binary program (UBQP), and is not specialized in any way for the Max-Cut problem. 相似文献
17.
18.
Hong-Xuan Huang Panos M. Pardalos Oleg A. Prokopyev 《Computational Optimization and Applications》2006,33(2-3):187-208
In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations
we describe four different kinds of strategies for estimating lower bounds of the objective function, which can be integrated
into a branch and bound algorithm for solving the quadratic binary programming problem. We also give a theoretical explanation
for forcing rules used to branch the variables efficiently, and explore several properties related to obtained subproblems.
From the viewpoint of the number of subproblems solved, new strategies for estimating lower bounds are better than those used
before. A variant of a depth-first branch and bound algorithm is described and its numerical performance is presented. 相似文献
19.
The uncapacitated plant location problem under uncertainty is formulated in a mean-variance framework with prices in various markets correlated via their response to a common random factor. This formulation results in a mixed-integer quadratic programming problem. However, for a given integer solution, the resulting quadratic programming problem is amenable to a very simple solution procedure. The simplicity of this algorithm means that reasonably large problems should be solvable using existing branch-and-bound techniques. 相似文献
20.
一种新的可分凸二次规划的不可行内点算法 总被引:3,自引:0,他引:3
本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) . 相似文献