基于改进的粒子群算法求解0/1背包问题

本文尝试把粒子群优化算法应用于0/1背包问题中,对算法模型进行适当的修改,并采用以目标函数加约束惩罚函数作为适应度函数的方法,仿真实验表明:粒子群算法在求解背包问题上结果良好。     

低秩半定最小二乘问题

讨论低秩半定最小二乘问题(lrSDLS)的启发式方法,并利用l0范数的光滑近似函数将(lrSDLS)中的非光滑非凸秩函数进行光滑化处理,并对其线性化,进而转化为光滑凸优化问题,为使用光滑优化方法近似求解(lrSDLS)提供了一个新的途径.     

可分离的二次背包问题的一种直接算法

二次背包问题是一个NP hard问题.给出一般的可分离二次背包问题的一种快速求解的直接算法,分析可分离连续二次背包问题的结构特性,并研究此问题最优解与拉格朗日系数λ的关系.在此基础上,提出通过调节λ来找到可分离二次背包问题的局部最优解的算法,此算法的计算复杂度为O(n).     

广义二次矩阵线性组合的秩与零度

利用广义二次矩阵与幂等矩阵的关系及幂等矩阵线性组合的秩及零度的不变性, 证明了广义二次矩阵某些线性组合的秩及零度与其线性组合系数的选择是无关的, 从而概括并推广了数量幂等矩阵、 数量对合矩阵、 二次矩阵线性组合的秩及零度的一些相关结果.     

二次矩阵广义Jordan积秩的不变性

通过给出二次矩阵与二次多项式的互为确定关系,利用矩阵变换得到了二次矩阵广义Jordan积秩的不变性及一种新的与二次矩阵相关的秩等式,所得结果概括并推广了关于(数量)幂等矩阵、(数量)对合矩阵等秩等式的相关结果.     

亏秩线性最小二乘问题的AOR迭代法的半收敛性

本文研究了找不相容线性方程组Ax=b的极小范数最小二乘解x=A^＋b的AOR迭代法．利用广义逆矩阵的知识，我们给出了AOR法的迭代阵Br，ω半收敛的充分必要条件，并且给出了文[8]与[9]中几个主要定理的较简单的证明．     

一类二次半定规划问题及其内点算法

讨论一类二次半定规划对偶性理论及与半定最小二乘问题的联系,并在对偶理论基础上讨论该规划的原始对偶内点算法,同时给出了基于NT方向的唯一性证明.     

广义二次矩阵和与积线性组合的秩与零度

应用广义二次矩阵与幂等矩阵互为确定的关系, 证明了在某种条件下广义二次矩阵和与积的线性组合的秩与其组合系数选择无关.     

多维O-1背包问题的混合遗传算法

将贪婪法和遗传算法相结合，设计了一种价值密度，提出了一种求解多维0-1背包问题的混合遗传算法。经实例证明，该方法能较好地解决多维0-1背包问题并较简单遗传算法有较好的改善。     

背包问题的微粒群算法

针对典型的背包问题,给出一种基于微粒群算法的求解方法。经过数值实验测试和验证,微粒群算法有较好的性能。     

0-1多项式背包问题的一种精确算法

提出了0-1多项式背包问题的一种新的精确算法. 该算法是一个基于拉格朗日松弛和对偶搜索的分枝定界方法. 用外逼近法求拉格朗日对偶问题得到上界,其中拉格朗日松弛问题通过转化为一个网络最大流问题来求解. 为了提高算法的效率,利用两种启发式方法求初始可行解,并用填充和交换的方法改进后得到初始下界; 并且在分枝定界前, 利用所得到的拉格朗日界, 先固定最优解中某些变量的值. 数值结果表明该算法是有效的.     

基于模拟退火算法(SAA)求解列车控制问题

提出了一种解水平轨道的列车节能控制问题的算法 ,该算法考虑了无限制速度和有限制速度两种情形 ,并基于模拟退火算法、动态罚函数法。     

二次半定规划的原始对偶预估校正内点算法

将半定规划(Semidefinite Programming,SDP)的内点算法推广到二次半定规划(QuadraticSemidefinite Programming,QSDP),重点讨论了AHO搜索方向的产生方法.首先利用Wolfe对偶理论推导得到了求解二次半定规划的非线性方程组,利用牛顿法求解该方程组,得到了求解QSDP的内点算法的AHO搜索方向,证明了该搜索方向的存在唯一性,最后给出了求解二次半定规划的预估校正内点算法的具体步骤,并对基于不同搜索方向的内点算法进行了数值实验,结果表明基于NT方向的内点算法最为稳健.     

求解低秩密度矩阵约束最小二乘问题的优函数罚方法

本文应用优函数罚方法求解具有低秩密度矩阵约束的最小二乘问题. 首先用凸差方法处理非凸的低秩约束,并结合罚方法和优函数方法将原问题转化为一系列具有密度矩阵约束的凸优化问题,然后给出求解该优化问题的优函数罚方法,并对该方法进行收敛性分析. 之后,运用半光滑牛顿增广拉格朗日算法求解优函数罚方法的子问题. 最后,合成数据集和真实数据集上的数值结果表明了优函数罚方法有效地求解了具有低秩密度矩阵约束的最小二乘问题.     

一类非线性半定规划问题的连续线性化方法

给出一类非线性半定规划问题的一种连续线性化方法.该方法能用于求解较大规模的优化问题,因为它处理的是比较简单的子问题.该算法利用l1精确罚函数和信赖域型的全局优化方法,每步迭代需要解的子问题可以重新表述成一个可用已有的半定规划软件有效解决的半定规划问题.     

Min-Max-Min问题的区间极大熵算法

讨论了目标函数和约束函数都是一阶连续可微的离散Min-Max-Min问题.利用罚函数法和极大熵函数思想将问题转化为无约束可微优化问题,构造了极大熵函数的区间扩张并证明了它的收敛性,给出了无解区域删除原则,建立了区间极大熵算法,理论证明和实例计算表明算法是可靠和有效的.     

一类非线性半定规划问题改进的序列线性化算法

针对一类非线性半定规划问题,提出一个改进的序列线性化算法．该方法能用于求解较大规模的优化问题,因为它处理的是比较简单的子问题．该算法利用l1-精确罚函数和信赖域型的全局优化方法,每步迭代需要解的子问题是一个二次半定规划问题,它可以用已有的半定规划软件有效的解决．在某些假定条件下,证明了算法是全局收敛的．     

求解0-1背包问题的混合遗传算法

对于0-1背包问题设计一种价值密度,并在此基础上提出求解0-1背包问题的混合遗传算法.经大量数值实验比较该方法与传统方法及简单遗传算法,结果表明算法能有效求解0-1背包问题.     

单调半定互补问题的非单调Derivative-free算法(英文)

基于正规间隙函数,讨论了一类单调半定互补问题的非单调Derivative-free算法,并在与单调算法相同的条件下建立了其全局收敛性.     

背包问题的分布估计算法

背包问题经常应用在资源约束条件下的资源分配中,并在组合数学、计算机科学、复杂性理论和密码学中也有应用。给出了常见的几种背包问题,将分布估计算法应用于背包问题。分布估计算法提供了一个新的进化模式,它从有前途的候选解建立概率模型来引导搜索过程。分析个体种群数量、选择比例对算法的影响。仿真结果表明:分布估计算法求解背包问题是可靠有效的;此方法具有较好的可扩展性,修改此算法可解决其他背包问题。