首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
本文给出了求解一类约束优化问题的一个Newton分裂算法,并证明了算法的局部平方收敛性,该算法与已有算法相比,具有计算量小的特点,因而特别适合于求解大规模问题,为进一步降低算法的计算复杂性,我们结合Broyden算法,给出了两类Broyden类分裂算法。  相似文献   

2.
FMT问题的两种三Ⅰ算法及其还原性   总被引:30,自引:8,他引:22  
进一步研究FMT问题,得到该问题的三Ⅰ算法的一般计算公式,提出该问题的一种新算法三Ⅰ^*算法,给出新算法的一般计算公式,讨论两种算法的还原性问题,明确两种还原性的含义,证明FMT问题的三Ⅰ算法是W-还原的,而三Ⅰ^*算法是Z-还原的。  相似文献   

3.
汤丹 《运筹学学报》2011,15(4):124-128
本文是对非线性规划问题提出的一种算法,该算法把模拟退火算法应用到CRS算法中,根据模拟退火算法每一次迭代都体现集中和扩散两个策略的平衡的特点,使CRS算法更能够搜索到全局最优解,而不会陷入局部最优解。最后把提出的算法应用到两个典型的函数优化问题中,结果表明,算法是可行的、有效的  相似文献   

4.
何吉欢 《应用数学和力学》2002,23(12):1255-1260
详细讨论了大约在公元前二世纪广泛流行的一种中国算法,这种算法在西方被称作为双假设法。强调指出双假设法是中国算法的一种译版。首次给出了中国算法与牛顿迭代算法之间的联系,如果引入了导数的概念,中国算法可以非常方便地转化为牛顿迭代算法,提出了一种改进的中国算法,并给出中国算法在非线性振动方程中的应用。  相似文献   

5.
一个修正的PVT算法   总被引:2,自引:0,他引:2  
对Fkshima(1998)所提出的PVT算法给出一种修正算法,称为修正PVT算法,这一修正算法对PVT原算法中的并行步中的停止准则和同步步骤作了修正。修正PVT算法的停止条件对PVT原算法的停止条件弱,因此更适用于并行计算,并且计算时间比PVT原算法少。  相似文献   

6.
变分不等式的几类求解方法   总被引:5,自引:1,他引:4  
本文转为系统地分析和概述了变分不等式问题中几类占有重要地位的求解方法,包括方法产生的背景,主要结果及应用等,这几类算法分别为连续算法,(拟)牛顿型算法,一般迭代模型,投影算法,投影收缩算法等。  相似文献   

7.
两台机器超载实时系统的On-line算法   总被引:1,自引:0,他引:1  
对超载实时系统的On—line算法中的SR算法作了修改,提出了NSR算法,并证明NSR算法的竞争比至少为2/5,因而它比SR算法更为优异.  相似文献   

8.
掌握算法和算法思想是信息时代对学生提出的一项新要求,算法进入中学数学课程也是世界课程改革的一大潮流.我国高中数学新课程就顺应了这种趋势,第一次把算法引入高中数学课程.新课标中提出:“学生要通过对具体问题过程与步骤的分析,体会算法思想,了解算法的含义.”在教学说明意见部分提出,要将算法思想渗透到高中课程的其他相关内容.从广义上讲,每一个问题(特别是数学问题)的解决都对应着一个算法,研究问题的方法就是研究算法.而算法思想,应该包括两个层面:  相似文献   

9.
模拟退火算法的改进及其应用   总被引:3,自引:0,他引:3  
王强 《应用数学》1993,6(4):392-397
模拟退火算法是随机优化近似算法。本文首先介绍其物理背景和一般形式,然后通过对算法增加记忆和返回两个功能以及在算法之后链接一个局部搜索过程,改善了算法性能,接着将改进算法应用于解旅游商问题,最后对该算法作简要的性能评论。  相似文献   

10.
本提出了一类教育最优投资模型的快速瓶颈消除算法,给出了算法的思想和具体迭代过程,对算法的最优性进行了证明。最后通过实例给出了算法直观的表上作业法。该算法迭代次数非常少,是一种实用的好算法。  相似文献   

11.
The several published methods for mapping a dual solution estimate to a primal solution estimate in posynomial geometric programming provide no criteria for deciding how much deviation from primal feasibility, or discrepancy between the primal and dual objective function values, should be permitted before the primal solution estimate is accepted by the designer. This paper presents a new and simple dual-to-primal conversion method that uses the cost coefficients to provide a sound economic criterion for determining when to accept a primal solution estimate. The primal solution estimate generated is the exact solution to a modified primal obtained from the given primal by modifying the cost coefficients, with the exponent matrix left unchanged. The method is shown to have desirable properties when coupled with a convergent dual algorithm.  相似文献   

12.
Many theoretical and algorithmic results in semidefinite programming are based on the assumption that Slater's constraint qualification is satisfied for the primal and the associated dual problem. We consider semidefinite problems with zero duality gap for which Slater's condition fails for at least one of the primal and dual problem. We propose a numerically reasonable way of dealing with such semidefinite programs. The new method is based on a standard search direction with damped Newton steps towards primal and dual feasibility.  相似文献   

13.
PRIMAL PERTURBATION SIMPLEX ALGORITHMS FOR LINEAR PROGRAMMING   总被引:2,自引:0,他引:2  
1. IntroductionExtensive research in linear programming, such as [1,2,9,10,if, 12,13,14,19], hasbeen to improve pivot rules to reduce the number of iterations required. Relatively lesseffort was made on perturbing problem data with pivot rules unaltered (for instance, theself--dual parametric method [7] and perturbation--based methods [3,5]). And, becauseof the papametrization, the latter do not proceed as simply as the conventional simplexalgorithm itself.Recently, Pan [17] proposes new pert…  相似文献   

14.
线性规划的对偶基线算法   总被引:6,自引:0,他引:6  
In this paper,we studied the dual form of the basic line algorthm for linear programs.It can be easily implemented in tableau that similar to the primal/dual simplex method.Different from primal simplex method or dual simplex method,the dual basic line algorithm can keep primal feasibility and dual feasibility at the same time in a tableau,which makes it more efficient than the former ones.Principles and convergence of dual basic line algorthm were discussed.Some examplex and computational experience were given to illustrate the efficiency of our method.  相似文献   

15.
Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242.  相似文献   

16.
Many branch and bound procedures for integer programming employ linear programming to obtain bound information. Nodes in the tree structure are defined by explicitly changing bounds on certain variables and/or adding one or more constraints to the parent LP; thus, primal feasibility is destroyed. The design and analysis of the resulting tree structure requires that basis information be stored for each node and that feasibility restoring pivots be used to obtain the node bound. In turn, this may require the introduction of artificial variables and/or dual simplex pivots.This paper describes a simple procedure for branch and bound that does not destroy primal feasibility. Moreover, the information required to be stored to define the node problems is minimal.  相似文献   

17.
A duality theory for algebraic linear (integer) programming (ALP) is developed which is of the same importance for linear (integer) programming with linear algebraic objectives as linear programming duality is for classical LP. In particular, optimality criteria for primal, primal-dual, and dual methods are given which generalize feasibility and complementarity criteria of classical LP. Strong duality results are given for special combinatorial problems. Further, the validity and finiteness of a primal simplex method based on a feasibility criterion are proved in the case of nondiscrete variables. In this case a strong duality result is shown.  相似文献   

18.
In this paper, we design a new variable target value procedure, the trust region target value (TRTV) method, for optimizing nondifferentiable Lagrangian dual formulations of large-scale, ill-conditioned linear programming problems. Such problems typically arise in the context of Lagrangian relaxation approaches and branch-and-bound/cut algorithms for solving linear mixed-integer programs. Subgradient optimization strategies are well-suited for this purpose and are popularly used, particularly in Lagrangian relaxation contexts, because of their simplicity in computation and mild memory requirements. However, they lack robustness and can often stall while yet remote from optimality. With this motivation, we design our proposed TRTV method to retain simplicity in computations, be theoretically convergent, as well as yield an effective and robust performance in practice. Furthermore, we augment this approach with dual refinement and primal recovery procedures based on outer-linearization and trust region strategies to further improve the accuracy of the resulting solutions and to derive primal solutions as well. Our computational study reveals a highly competitive performance of the proposed TRTV algorithm among several implemented nondifferentiable optimization procedures. Moreover, the dual refinement and primal recovery procedures help further reduce the optimality gap and promote attaining a relatively greater degree of primal feasibility as compared with several alternative ergodic primal recovery schemes. Also, the proposed method displays significantly lesser computational requirement than that of a commercial linear programming solver CPLEX.This research has been supported by the National Science Foundation under Grant Number DMI-0094462.  相似文献   

19.
In this paper, we generalize the concept of sensitivity analysis in fuzzy number linear programming (FLNP) problems by applying fuzzy simplex algorithms and using the general linear ranking functions on fuzzy numbers. The purpose of sensitivity analysis is to determine changes in the optimal solution of FNLP problem resulting from changes in the data. If the change affects the optimality of the basis, we perform primal pivots to achieve optimality by use of the fuzzy primal simplex method. Whenever the change destroys the feasibility of the optimal basis, we perform dual pivots to achieve feasibility by use of the fuzzy dual simplex method.  相似文献   

20.
Curet曾提出了一种有趣的原始一对偶技术,在优化对偶问题的同时单调减少原始不可行约束的数量,当原始可行性产生时也就产生了原问题的最优解.然而该算法需要一个初始对偶可行解来启动,目标行的选择也是灵活、不确定的.根据Curet的原始一对偶算法原理,提出了两种目标行选择准则,并通过数值试验进行比较和选择.对不存在初始对偶可行解的情形,通过适当改变目标函数的系数来构造一个对偶可行解,以求得一个原始可行解,再应用原始单纯形算法求得原问题的最优解.数值试验对这种算法的计算性能进行验证,通过与经典两阶段单纯形算法比较,结果表明,提出的算法在大部分问题上具有更高的计算效率.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号