求解非减上模集函数最小值问题的近似算法及其性能保证

上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.     

求解多维约束下下模函数最大值的改进贪婪算法

提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.     

基于二次多项式的积极集光滑化max函数及其在无约束minimax问题中的应用

本文基于分段二次多项式方程,构造了一种积极集策略的光滑化max函数.通过给出与光滑化max函数相关的分量函数指标集的直接计算方法,将分段二次多项式方程转化为一般二次多项式方程.利用二次多项式方程根的性质,给出了该光滑化max函数的稳定计算策略,证明了其具有一阶光滑性,其梯度函数具有局部Lipschitz连续性和强半光滑性.该光滑化max函数仅与函数值较大的分量函数相关,适用于含分量函数较多且复杂的max函数的问题.为了验证其效率,本文基于该函数构造了一种解含多个复杂分量函数的无约束minimax问题的光滑化算法,数值实验表明了该光滑化max函数的可行性及有效性.     

自反Banach空间中锥线性优化问题初始——对偶目标函数水平集的几何性质

讨论自反Banach空间中的原——对偶锥线性优化问题的目标函数水平集的几何性质．在自反Banach空间中,证明了原目标函数水平集的最大模与对偶目标函数水平集的最大内切球半径几乎是成反比例的．     

解含多个复杂分量函数无约束minimax问题的积极集光滑化算法

本文利用分段三次多项式方程构造了一种积极集策略的二次连续可微的光滑化max函数,给出积极集及稳定的光滑化max函数的计算方法.基于该光滑化max函数,结合Armijo线搜索,负梯度和牛顿方向及光滑化参数的更新策略,给出一种解含多个复杂分量函数无约束minimax问题的积极集光滑化算法.初步的数值实验表明了该算法的有效性.     

求解界约束优化问题的有效集算法综述

主要介绍了求解界约束优化问题的有效集方法,包括投影共轭梯度法和有效集识别函数法,讨论了各自的优点和不足.最后,指出了有效集法的研究趋势及应用前景.     

直觉(λ,η)-函数粗集

利用函数S-粗集,提出直觉(λ,η)-函数粗集,给出它的数学结构和特性,又探讨直觉(λ,η)-函数粗集与函数S-粗集的关系。从解决实际问题的角度来说,直觉(λ,η)-函数粗集是函数粗集的一般形式,函数S-粗集是直觉(λ,η)-函数粗集的特例。直觉(λ,η)-函数粗集是粗集研究的一个新方向。     

带次模惩罚的仓库—零售商网络设计问题的近似算法

本文研究了一个带次模惩罚的仓库—零售商网络设计问题.在该类问题中,允许以支付惩罚费用为代价,拒绝给部分零售商供货,并且我们假设问题的惩罚费用函数是一个不减的非负次模函数.对于此问题,我们给出一个近似比为3的原始对偶算法.     

基于扩散函数的内集-外集模型

内集-外集模型用于计算小样本事件的可能性-概率分布(PPD),以表达概率估计的模糊性。基于分配函数的内集-外集模型存在三点不足:①论域步长的选取随意性太大;②PPD值在0.5到1之间无值;③信息过于集中,PPD值在很多区间值为0。本文从解决此三问题入手,对传统模型进行了改进。首先讨论了论域步长选取的合理性问题;其次引入扩散函数替换分配函数,同时解决了问题②和③;最后,仿真实验的结果显示,改进模型的估计比传统模型的估计更接近于真实分布。     

集值映射的Epi-导数及其应用

在本文里，集值映射的Epi-导数被引入，它可以认作是实值Lipschitz函数的Clarke-广义方向导数的推广，同时它的一些性质也被研究．进一步地，利用这个Epi-导数集值映射的次微分被定义并研究它的性质．作为其应用，我们给出了集值优化问题的一些(必要或充分)最优性条件．