An Asynchronous Distributed Expectation Maximization Algorithm for Massive Data: The DEM Algorithm

The family of expectation--maximization (EM) algorithms provides a general approach to fitting flexible models for large and complex data. The expectation (E) step of EM-type algorithms is time-consuming in massive data applications because it requires multiple passes through the full data. We address this problem by proposing an asynchronous and distributed generalization of the EM called the distributed EM (DEM). Using DEM, existing EM-type algorithms are easily extended to massive data settings by exploiting the divide-and-conquer technique and widely available computing power, such as grid computing. The DEM algorithm reserves two groups of computing processes called workers and managers for performing the E step and the maximization step (M step), respectively. The samples are randomly partitioned into a large number of disjoint subsets and are stored on the worker processes. The E step of DEM algorithm is performed in parallel on all the workers, and every worker communicates its results to the managers at the end of local E step. The managers perform the M step after they have received results from a γ-fraction of the workers, where γ is a fixed constant in (0, 1]. The sequence of parameter estimates generated by the DEM algorithm retains the attractive properties of EM: convergence of the sequence of parameter estimates to a local mode and linear global rate of convergence. Across diverse simulations focused on linear mixed-effects models, the DEM algorithm is significantly faster than competing EM-type algorithms while having a similar accuracy. The DEM algorithm maintains its superior empirical performance on a movie ratings database consisting of 10 million ratings. Supplementary material for this article is available online.     

Factorizations of tropical and sign polynomials

In this text, we study factorizations of polynomials over the tropical hyperfield and the sign hyperfield, which we call tropical polynomials and sign polynomials, respectively. We classify all irreducible polynomials in either case. We show that tropical polynomials factor uniquely into irreducible factors, but that unique factorization fails for sign polynomials. We describe division algorithms for tropical and sign polynomials by linear terms that correspond to roots of the polynomials.     

艾拉姆咖分布参数变点的Bayes估计

研究了艾拉姆咖分布变点估计的非迭代抽样算法(IBF)和MCMC算法.在贝叶斯框架下,选取无信息先验分布,得到关于变点位置的后验分布和各参数的满条件分布,并且详细介绍了IBF算法和MCMC方法的实施步骤.最后进行随机模拟试验,结果表明两种算法都能够有效的估计变点位置,并且IBF算法的计算速度优于MCMC方法.     

线性权互补问题的新全牛顿步可行内点算法

基于一个连续可微函数,通过等价变换中心路径,给出求解线性权互补问题的一个新全牛顿步可行内点算法.该算法每步迭代只需求解一个线性方程组,且不需要进行线搜索.通过适当选取参数,分析了迭代点的严格可行性,并证明算法具有线性优化最好的多项式时间迭代复杂度.数值结果验证了算法的有效性.     

基于贝叶斯多元有序probit模型的休闲渔业游客满意度研究

游客满意度是休闲渔业景区制定管理决策的重要参考信息。通过探究游览过程中游客对各单一维度的满意程度与旅游总满意度之间的关系,管理者可以从中准确了解游客偏好、消费行为以及获取旅游产品设计等重要信息。据此,本文采取实地调研,获取11家全国休闲渔业示范基地1510份游客满意度信息,使用马尔科夫链蒙特卡洛法(Markov Chain Monte Carlo, MCMC),估算贝叶斯多元有序probit模型,并利用模型后验结果衡量休闲渔业游客7种分满意度对总体满意度的贡献。研究结果表明:渔憩体验满意度、景区环境满意度以及旅游餐饮满意度是对总体满意度影响程度最大的三种分满意度,所占比例分别为43.58%、24.67%、10.62%。     

考虑翻箱的场桥调度和提箱集卡数量的集成优化

在集装箱码头的进口箱堆场中,码头预约机制、待提箱的实时位置和场桥作业调度方案是制约堆场作业效率和堵塞情况的关键。为缓解进口箱堆场的拥塞情况并提高作业效率,在固定的预约时段内,考虑实时压箱量最少的翻箱规则,兼顾场桥间不可跨越和保持安全间距等现实约束,以场桥最长完工时间最小为目标,构建数学优化模型,设计了嵌入修复算子的改进遗传算法用于求解;通过算例实验验证了算法的有效性和方案的优越性,可为堆场实际作业提供决策参考。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$（t,t+\Delta（t）]$内到达工件的信息,这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长,其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in（0,1）$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

考虑破产控制的多期模糊资产-负债组合优化模型

在实际的投资决策过程中,一些投资者需要同时管理资产和负债,因此本文研究考虑破产控制和偿债行为的资产-负债管理问题。假设风险资产的收益率和负债的增长率为模糊数,用资产-负债组合的可能性期望和下半绝对偏差度量其收益和风险,以最大化最终期望净财富和最小化最终累积风险为目标,建立了允许限制性卖空的多期模糊资产-负债组合优化模型。然后,设计了一个基于粒子群算法和模拟退火算法的混合智能算法对模型进行求解。最后,通过实例分析说明了所设计算法与传统粒子群算法相比具有更好的优化性能和稳定性。本文所提出策略可以为需要同时管理资产和负债的投资者提供决策支持。