共查询到20条相似文献,搜索用时 125 毫秒
1.
本文提出一类基于DC分解的非凸二次规划问题SDP松弛方法,并通过求解一个二阶锥问题得到原问题的近似最优解.我们首先对非凸二次目标函数进行DC分解,然后利用线性下逼近得到一个凸二次松弛问题,而最优的DC分解可通过求解一个SDP问题得到.数值试验表明,基于DC分解的SDP近似解平均优于经典SDP松弛和随机化方法产生的近似解。 相似文献
2.
3.
4.
本文提出了一个求不定二次规划问题全局最优解的新算法.首先,给出了三种计算下界的方法:线性逼近法、凸松弛法和拉格朗日松弛法;并且证明了拉格朗日对偶界与通过凸松弛得到的下界是相等的;然后建立了基于拉格朗日对偶界和矩形两分法的分枝定界算法,并给出了初步的数值试验结果. 相似文献
5.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献
6.
根据广义乘子法的思想,将具有等式约束和非负约束的凸二次规划问题转化只有非负约束的简单凸二次规划,通过简单凸二次规划来得到解等式约束一非负约束的凸二次规划新算法,新算法不用求逆矩阵,这样可充分保持矩阵的稀疏性,用来解大规模稀疏问题,数值结果表明:在微机486/33上就能解较大规模的凸二次规划。 相似文献
7.
金照林 《数学的实践与认识》2023,(4):43-51
提出使用凸松弛的方法求解二层规划问题,通过对一般带有二次约束的二次规划问题的半定规划松弛的探讨,研究了使用半定规划(SDP)松弛结合传统的分枝定界法求解带有凸二次下层问题的二层二次规划问题,相比常用的线性松弛方法,半定规划松弛方法可快速缩小分枝节点的上下界间隙,从而比以往的分枝定界法能够更快地获得问题的全局最优解. 相似文献
8.
本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解. 相似文献
9.
为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的. 相似文献
10.
正定二次规划的一个对偶算法 总被引:1,自引:1,他引:0
给出了一个正定二次规划的对偶算法.算法把原问题分解为一系列子问题,在保持原问题的Wolfe对偶可行的前提下,通过迭代计算,由这一系列子问题的最优解向原问题的最优解逼近.同时给出了算法的有限收敛性. 相似文献
11.
12.
13.
Yinyu Ye 《Journal of Global Optimization》1999,15(1):1-17
We consider the problem of approximating the global maximum of a quadratic program (QP) subject to convex non-homogeneous quadratic constraints. We prove an approximation quality bound that is related to a condition number of the convex feasible set; and it is the currently best for approximating certain problems, such as quadratic optimization over the assignment polytope, according to the best of our knowledge. 相似文献
14.
15.
Jörgen Boo 《Journal d'Analyse Mathématique》1998,76(1):45-65
We say that a setA ⊂ ℂ
n
is quadratically convex if its complement is a union of quadratic hypersurfaces. Some geometric properties of quadratically
convex sets are investigated; in particular, they are related to lineally convex sets in a space of higher dimension. We say
thatA is strongly quadratically convex if a certain generalization of the Fantappiè transform is surjective, which in effect means
that we have a representation for any function holomorphic onA as a superposition of reciprocals of quadratic expressions. The main theorem in this paper gives a sufficient condition for
a compact set to be strongly quadratically convex. Using integral representation formulas for holomorphic functions, an explicit
inversion formula for the transform is obtained. 相似文献
16.
The quadratic X-splines, Which are an analogy of cubic X-splinesintroduced recently by Clenshaw & Negus (1978)and generalizedby Behforooz, Papamichael & Worsey (1980), are defined andtheir order of convergence, smoothness and complexity of constructionare examined. 相似文献
17.
S. Vajda 《The Journal of the Operational Research Society》1965,16(2):256-257
18.
Recently Dolezal and Tewarson [2], and Papamichael and Soares [3] have considered the cubic spline-on-spline for the purpose of the approximating the derivatives y(2),y(3), and y(4). In this paper their ideas have been extended and the quadratic spline-on-spline has been established for the same purpose. This technique yields better results than the traditional process using a single quadratic spline. 相似文献
19.
20.
Hans-Joachim Baues 《Transactions of the American Mathematical Society》1999,351(2):429-475
We describe axioms for a `quadratic homology theory' which generalize the classical axioms of homology. As examples we consider quadratic homology theories induced by 2-excisive homotopy functors in the sense of Goodwillie and the homology of a space with coefficients in a square group which generalizes the homology of a space with coefficients in an abelian group.