凸规划的一种对偶内点算法

将带有不等式约束的凸规划问题转化为拉格朗日对偶问题,构造了一种求解凸规划的偶内点算法,证明了在不存在对偶差的情况下,当对偶变量序列收敛到对偶问题最优解时,原始变量序列收敛于原始问题的最优解。     

求解整数规划Surrogate对偶问题的一种算法

本文讨论整数线性规划的Ｓｕｒｒｏｇａｔｅ对偶问题，给出了求解Ｓｕｒｒｏｇａｔｅ对偶问 题的一种算法，论述了该算法具有的某些良好性质。计算结果说明：用该算法求解 Ｓｕｒｒｏｇａｔｅ对偶问题时，所解的背包问题的次数比较少，所存在的对偶间隙也较 小。     

多用户最优化的两种对偶方法

采用多用户问题的梯度近似分布式算法,对多用户最优化的原始对偶方法和正规化对偶方法进行了比较,集中于多用户凸最优化问题的概括,其中目标函数和约束函数不可分,而目标函数可通过非线性组约束,使用户决定耦合;在算法中,对原始对偶方法和正规化对偶方法可考虑不变步长,采用跨用户自然迭代计算,使每个用户能够只更新自身的决策变量．     

线性规划的无比值检验criss-CROSS算法

Zionts提出的求解线性规划问题的criss-cross算法实际是一阶段算法,不过与传统一阶段算法不同,它交替进行原始和对偶迭代,而产生的既可以是原始可行解,也可以是对偶可行解.为了提高计算效率,文章提出了一种采用无比值检验规则的新criss-crOss算法,基于新算法编制的一个稠密软件在对40个小问题进行的数值试验中,就迭代次数而言,以2.12的比率胜过了传统的两阶段算法.     

随机运输问题的对偶森林迭代算法

本算法从一个对偶森林向另一个对偶森林迭代。在非退化的情况下,每步迭代都使对 偶目标函数值严格增加,并在有限步内达到最优值,每步迭代最多只需解一个一维非线 性方程。在“宇宙６８０００”机上,对此算法进行了两个包括６００个以上变量的大型问题计 算,计算结果表明算法是可行有效的。     

求解LP问题的部分基变量算法

一般形式的线性规划问题在找不到基本可行解或对偶问题的基本可行解时,无法用传统的单纯形法或对偶单纯形法求解,即"两看一算"算法.为了解决这个问题,结合两种"两看一算"算法,提出了一种新的算法--部分基变量算法.该算法首先从部分基变量出发,由初等行变换将LP问题转化为准典式,然后由初等行变换找到全部可行基变量,最后用对偶单纯形法得到最优解.对算法的正确性和可行性进行了严格证明,提出算法的实现方式并举例进行了说明,对算法的特点进行了讨论.分析表明所提出的算法是实现线性规划问题求解的较为理想的算法.     

对经典Rosen算法的一点改进

用Rosen的投影梯度的方法求解凸约束优化问题中的对偶问题，在计算投影梯度的方向时，涉及到求关于原始变量的最小化问题的最优解，我们用并行算法计算出这一极小化问题的其近似解，证明近似解可以达到任何给定的精度，并说明当精度选取合适时，Rosen方法仍然是收敛的。     

求解约束最小二乘半正定规划问题的L-BFGS方法

对带等式和不等式约束的最小二乘半正定规划问题的求解进行了研究。在Slater约束规范条件下,对偶问题的最优解与原问题最优解相等。因此,考虑将最小二乘半正定规划问题转化为相应的对偶问题,通过求解对偶问题达到求解原问题的目的。针对最小二乘半正定规划问题的对偶问题,首先构造相应的二次模型,沿负梯度方向最小化该二次模型得到柯西点,在此基础上,利用积极约束技巧,划分积极约束集与非积极约束集,然后应用L-BFGS技巧对自由变量进行加速,从而求得对偶问题的最优解。最后,从理论上证明了算法的全局收敛性,并进行了初步的数值实验,将该算法与光滑化牛顿法作对比,结果表明该算法在计算时间上有一定的优势。     

一个改进的原始对偶内点方法

针对一般的光滑约束最优化问题, 提出一种原始对偶不可行内点算法, 该算法运用3个值函数使算法能收敛到局部极小点而非其他一阶最优性点, 并通过将等式约束的罚项和松弛变量的障碍项添加到目标函数中转化原问题. 计算结果证明了算法的可行性和有效性.     

变量有上界的线性规划的对偶单纯形方法

给出变量有上界的线性规划问题的对偶单纯形算法, 该算法包含了一般线性规划问题的对偶单纯形算法, 为解变量有上界的线性规划问题提供了又一种方法.     

基于一类非线性Lagrange函数的对偶问题

基于一类非线性Lagrange函数提出不等式约束优化问题的一类对偶问题,证明了在Jacobian惟一条件下,对偶问题的最优解处二阶充分性条件是成立的,因此对偶解处满足二阶增长条件.非线性Lagrange函数的鞍点存在是原始问题与对偶问题无对偶问隙的充分条件,给出了鞍点条件的等价条件,并且给出了用扰动函数来刻画的鞍点存在的一个充分条件.     

一阶双曲方程组自由边界问题的差分方法

本文用中心差分格式去解二个独立变量的一阶双曲方程组的自由边界問題,討論了这种方法的收斂性,並对气动力学的二个計算问題作了应用。     

线性规划内点算法的若干收敛性问题

对于线性规划问题 ｍｉｎ｛ｃтｘ｜Ａｘ≥ｂ，ｘ≥０｝，印度学者 и．Ｋａｒｍａｒｋａｒ于 １９８４年发明 了一种新的内点算法，它的时间复杂性为Ｏ（ｎ３．５Ｌ２），其中ｎ为问题的变量个数，Ｌ为输 入中的二进制位数。其后又出现了多种变形方案，如原始型和对偶型内点算法等等。本 文主要讨论它们的收敛性问题。关于Ｋａｒｍａｒｋａｒ算法，证明了当原始线性规划问题无有 限最优解时算法也可以收敛。关于原始型和对偶型内点算法，给出了它们的基本性质以 及若干收敛性结果。     

自由变量线性规划的对偶解法

针对自由变量的线性规划问题，提出不需增设人工变量，而直接采用单纯形法解其对偶规划，得原线性规划的解。此方法是对偶规划的一个应用，并且不会增加额外的计算量。     

状态空间法分析厚薄圆柱壳弯曲的多变量场

根据圆柱壳的控制方程及其混合变分原理 ,引入对偶变量即应力与位移作为状态变量 ,导出圆柱壳的状态方程 ,研究其解法。对于轴对称问题 ,应用分离变量法建立指数矩阵 ,将问题分解为两个一维问题。根据开莱 -哈密顿算法或直接展形法来计算指数矩阵 ,再根据应力与位移的边界条件 ,得到问题的定解方程 ,从而求得厚薄圆柱壳的两类场变量的统一解 ,即全部应力与位移量     

非定常问题的加权残数法

定常问题的加权残数法为人家熟知,用它解决固体力学中的静力问题的文章颇多。而用它解决结构动力问題的文章就比较少,多是用其它方法去解。近年来,秦荣教授提出了“结构动力问题的样条函数方法”,这是求解动力问题的很好的方法。目前要想把残数法应用到非定常问题,时间这个变量是一个障碍,本文就是想去掉时间这个变量,使得加权残数法全部应用过来。思路是对非定常问题的线性偏微分方程施以拉普拉斯变换,把非定     

求解变量有界的运输问题的新方法

提出了变量有界的运输问题的一种新解法:先将此类问题转化为变量有上界的产销平衡的运输问题,在求初始解时采用类似最小元素法确定基变量,若变量取值可能超过其上界约束,则用拆分销地并限制其销量的方法加以控制,优化调整时也采用拆分销地的方法,从而逐步将变量有上界的运输问题转化为一般运输问题求解.最后给出一个计算实例.     

用解加数法解运输问题的通用程序

物资的合理调拨问题是属于线性规划中的一种特殊类型——运输问题。这类问题运算复杂规模一般都是很大的。因此,在实际工作中,充分使用电子计算机是准确、迅速解决这类问题的好方法。解运输问题最常用的有位势法,单纯形法等。然而通过实际计算表明,采用在我国尚未使用的解加数法比位势法有更多的优点。它既能节省机器的内存贮量,又能大大缩短机器的运算时间。例如用DJS-8计算机计算m×n=19×419(m为发站,n为收站)的化肥运输合理方案时,用解加数法仅需机时为5分钟,而用位势法需机时约25分钟。虽然电子计算机的运算速度很快,但是在方法的选择和程序的编制中,如何达到既能节省机器的内存单元,又能提高机器的使用效率,仍然是一个很重要的问题。目前,在我国铁路运输工作中,已开始使用解加数法编制通用程序,计算物资的合理调拨方案,如计算铁矿石、化肥、汽油等的最优调拨方案,并取得较好的效果。本文将介绍用解加数法解运输问题的方法和程序的编制。     

凸二次规划的原-对偶内点算法数值实验初步

在线性规划原始对偶内点算法的基础上,进一步给出原始对偶内点算法在解凸二次规划问题中的应用, 并初步给出了该算法的数值例子, 作为对内点算法的一个重要补充.     

算术平均半亚式期权定价的快速算法

算术平均半亚式期权是一种推广的亚式期权,无解析定价公式.因此在实际中大多采用蒙特卡洛法等模拟算法进行定价,尽管定价精度较高,但定价的计算时间长.本文结合改进蒙特卡洛法和矩近似解析法,得到算术平均半亚式期权定价的近似半解析法,在确保精度的前提下,大幅减少计算时间.最后,本文利用对偶变量技术改进近似半解析法,进一步减少计算时间.