运筹学学报

田英杰, 胥栋宽, 张春华

2018, 22(2): 1-17.

摘要 ( 9717 )

PDF (9313KB) ( 900 )

相关文章 | 多维度评价

多示例学习是一种特殊的机器学习问题，近年来得到了广泛的关注和研究，许多不同类型的多示例学习算法被提出，用以处理各个领域中的实际问题. 针对多示例学习的算法研究和应用进行了较为详细的综述, 介绍了多示例学习的各种背景假设, 从基于示例水平、包水平、嵌入空间三个方面对多示例学习的常见算法进行了描述, 并给出了多示例学习的算法拓展和若干领域的主要应用.

解一类结构变分不等式问题的非精确并行交替方向法

冯俊锴, 张海斌, 秦嫒, 张凯丽

2018, 22(2): 18-30. doi:10.15960/j.cnki.issn.1007-6093.2018.02.002

摘要 ( 1515 )

PDF (585KB) ( 228 )

相关文章 | 多维度评价

带线性约束的具有两分块结构的单调变分不等式问题, 出现在许多现代应用中, 如交通和经济问题等. 基于该问题良好的可分结构, 分裂型算法被广泛研究用于其求解. 提出新的带回代的非精确并行交替方向法解该类问题, 在每一步迭代中，首先以并行模式通过投影得到预测点, 然后对其校正得到下一步的迭代点. 在压缩型算法的理论框架下, 在适当条件下证明了所提算法的全局收敛性. 数值结果表明了算法的有效性. 此外, 该算法可推广到求解具有多分块结构的问题.

k-均值算法的初始化方法综述

徐大川, 许宜诚, 张冬梅

2018, 22(2): 31-40. doi:10.15960/j.cnki.issn.1007-6093.2018.02.003

摘要 ( 1223 )

PDF (583KB) ( 246 )

相关文章 | 多维度评价

k-均值问题自提出以来一直吸引组合优化和计算机科学领域的广泛关注, 是经典的NP-难问题之一. 给定N个d维实向量构成的观测集, 目标是把这N个观测点划分到k(\leq N)个集合中, 使得所有集合中的点到对应的聚类中心距离的平方和最小, 一个集合的聚类中心指的是该集合中所有观测点的均值. k-均值算法作为解决k-均值问题的启发式算法，在实际应用中因其出色的收敛速度而倍受欢迎. k-均值算法可描述为: 给定问题的初始化分组, 交替进行指派(将观测点分配到离其最近的均值点)和更新(计算新的聚类的均值点)直到收敛到某一解. 该算法通常被认为几乎是线性收敛的. 但缺点也很明显, 无法保证得到的是全局最优解, 并且算法结果好坏过于依赖初始解的选取. 于是学者们纷纷提出不同的初始化方法来提高k-均值算法的质量. 现筛选和罗列了关于选取初始解的k-均值算法的初始化方法供读者参考.

两个基于不同张量乘法的四阶张量分解

徐娇娇, 杨志霞

2018, 22(2): 41-54. doi:10.15960/j.cnki.issn.1007-6093.2018.02.004

摘要 ( 1158 )

PDF (651KB) ( 247 )

相关文章 | 多维度评价

提出了两个基于不同张量乘法的四阶张量分解. 首先, 在矩阵乘法的基础上, 定义第一种四阶张量乘法(F-乘), 基于F-乘提出了第一种四阶张量分解(F-TD). 其次, 基于三阶张量t-product给出了第二种四阶张量乘法(B-乘)和分解(FT-SVD). 同时, 利用两种分解方法, 分别给出两个张量逼近定理. 最后, 三个数值算例阐明提出的两种分解方法的准确性和可行性.

从支持向量机到非平行支持向量机

邵元海, 杨凯丽, 刘明增, 等

2018, 22(2): 55-65. doi:10.15960/j.cnki.issn.1007-6093.2018.02.005

摘要 ( 9516 )

PDF (1352KB) ( 577 )

相关文章 | 多维度评价

非平行支持向量机是支持向量机的延伸, 受到了广泛的关注. 非平行支持向量机构造允许非平行的支撑超平面, 可以描述不同类别之间的数据分布差异, 从而适用于更广泛的问题. 然而, 对非平行支持向量机模型与支持向量机模型之间的关系研究较少, 且尚未有等价于标准支持向量机模型的非平行支持向量机模型. 从支持向量机出发, 构造出新的非平行支持向量机模型, 该模型不仅可以退化为标准支持向量机, 保留了支持向量机的稀疏性和核函数可扩展性. 同时, 可以描述不同类别之间的数据分布差异, 适用于更广泛的非平行结构数据等. 最后, 通过实验初步验证了所提模型的有效性.

半监督距离度量学习内蕴加速投影梯度算法

仰迪, 白延琴, 李倩

2018, 22(2): 66-78. doi:10.15960/j.cnki.issn.1007-6093.2018.02.006

摘要 ( 1098 )

PDF (5001KB) ( 174 )

相关文章 | 多维度评价

考虑求解一类半监督距离度量学习问题. 由于样本集(数据库)的规模与复杂性的激增, 在考虑距离度量学习问题时, 必须考虑学习来的距离度量矩阵具有稀疏性的特点. 因此, 在现有的距离度量学习模型中, 增加了学习矩阵的稀疏约束. 为了便于模型求解, 稀疏约束应用了Frobenius 范数约束. 进一步, 通过罚函数方法将Frobenius范数约束罚到目标函数, 使得具有稀疏约束的模型转化成无约束优化问题. 为了求解问题, 提出了正定矩阵群上加速投影梯度算法, 克服了矩阵群上不能直接进行线性组合的困难, 并分析了算法的收敛性. 最后通过UCI数据库的分类问题的例子, 进行了数值实验, 数值实验的结果说明了学习矩阵的稀疏性以及加速投影梯度算法的有效性.

线性约束两分块非凸优化的ADMM-SQP算法

简金宝, 劳译娴, 晁绵涛, 马国栋

2018, 22(2): 79-92. doi:10.15960/j.cnki.issn.1007-6093.2018.02.007

摘要 ( 9812 )

PDF (647KB) ( 676 )

相关文章 | 多维度评价

基于乘子交替方向法(ADMM)和序列二次规划(SQP)方法思想, 致力于研究线性约束两分块非凸优化的新型高效算法. 首先, 以SQP思想为主线, 在其二次规划(QP)子问题的求解中引入ADMM思想, 将QP分解为两个相互独立的小规模QP求解. 其次, 借助增广拉格朗日函数和Armijo线搜索产生原始变量新迭代点. 最后, 以显式解析式更新对偶变量. 因此, 构建了一个新型ADMM-SQP算法. 在较弱条件下, 分析了算法通常意义下的全局收敛性, 并对算法进行了初步的数值试验.

设施选址博弈问题的无支付机制设计研究

程郁琨, 梅丽丽

2018, 22(2): 93-104. doi:10.15960/j.cnki.issn.1007-6093.2018.02.008

摘要 ( 1192 )

PDF (560KB) ( 246 )

相关文章 | 多维度评价

选址博弈是目前国际相关学术领域的重要前沿课题之一. 在选址博弈问题中, 存在n个相互影响的``理性"居民, 他们的住址等信息是其私有信息；设计者需要设计选址机制, 以居民汇报的住址信息为输入, 输出设施位置. 在进行机制设计的过程中, 如何在没有金钱的刺激下, 保证所有居民``说真话", 设计出防策略性无支付机制是其中的重要研究内容. 设施选址博弈问题的无支付机制设计是组合优化和理论计算机科学的交叉学科课题, 在管理科学、信息科学以及社会经济学等领域有着重要的应用, 具有重要的理论意义和实际的应用价值. 现根据不同设施类型及个数、不同个人偏好、不同度量空间以及不同社会总体目标等条件, 介绍各种类型的设施选址博弈模型, 罗列相关的研究成果, 并总结其中尚待解决的问题.

京津冀地区PM2.5污染特征的研究-----基于函数型数据分析的视角

梁银双, 刘黎明

2018, 22(2): 105-114. doi:10.15960/j.cnki.issn.1007-6093.2018.02.009

摘要 ( 9112 )

PDF (2246KB) ( 469 )

相关文章 | 多维度评价

近年来京津冀地区的雾霾重度污染事件频发, 引起国家和社会的普遍关注. 以京津冀地区68个监测站的数据为基础, 研究了京津冀地区PM2.5小时间隔的年度数据主要变异模式、时空变化类型等污染特征. 还研究了二氧化硫、氮氧化物年度累计排放量对PM2.5浓度变化的影响. 结果表明, 氮氧化物的排放对PM2.5浓度的贡献更显著, 削减氮氧化物等污染物的排放可有效降低PM2.5浓度, 改善空气质量. 采用函数型数据分析方法, 相对于传统的统计均值方法, 能够更有效的使用所采集到的不同的数据类型, 进行更细致的分析, 从而得到更可靠的结论.

基于时间序列分析的北京地区PM2.5浓度研究

李为东, 李莉, 徐岩

2018, 22(2): 115-126. doi:10.15960/j.cnki.issn.1007-6093.2018.02.010

摘要 ( 1215 )

PDF (4459KB) ( 263 )

相关文章 | 多维度评价

基于中国环境监测总站公布的实时空气质量监测数据, 利用时间序列模型对PM2.5指标的数据进行了平稳性、纯随机性检验, 同时进行了模型阶数、未知参数估计以及模型显著性检验与优化. 最终在此基础上建立了指标预测的数学模型, 并对未来三天的PM2.5浓度值进行预测. 进一步地, 基于向量自回归(VAR)模型, 对北京市万寿西宫站PM2.5数据进行相关性分析, 研究空气中污染物O_{2}、NO_{2}、CO、O_{3}、PM10与PM2.5的动态影响关系. 研究发现当天的PM2.5浓度会受到前几天PM2.5、PM10、O_{3}、SO_{2}等污染物浓度的影响, 其中PM10对PM2.5的影响最为明显且持续时间最长, O_{3}、SO_{2}对PM2.5浓度的影响在二、三期最为明显.

最小化三个凸函数之和的一个简单原始-对偶算法

王硕, 朱志斌, 张本鑫

2018, 22(2): 127-138. doi:10.15960/j.cnki.issn.1007-6093.2018.02.011

摘要 ( 1117 )

PDF (985KB) ( 257 )

相关文章 | 多维度评价

提出一个简单的原始-对偶算法求解三个凸函数之和的最小化问题, 其中目标函数包含有梯度李普希兹连续的光滑函数, 非光滑函数和含有复合算子的非光滑函数. 在新方法中, 对偶变量迭代使用预估-矫正的方案. 分析了算法的收敛性和收敛速率. 最后, 数值实验说明了算法的有效性.

带短期价格折扣和允许两次特殊补货的库存决策模型

成诚, 左传, 王宜举

2018, 22(2): 139-156. doi:10.15960/j.cnki.issn.1007-6093.2018.02.012

摘要 ( 899 )

PDF (2358KB) ( 193 )

相关文章 | 多维度评价

针对供应商提供短期价格折扣且允许零售商两次特殊补货的库存系统, 建立了以零售商库存效益最大化为目标的库存决策模型, 分析了模型的性质, 根据经济订单批量补货决策下补货时间点与折扣时段的关系, 确定了零售商在不同补货策略下的库存效益增值函数. 据此给出零售商相应的最优补货策略函数表达式, 提出了该模型的一个全局优化算法, 并通过数值算例验证了模型和算法的有效性与可行性.

当期目录