An Incremental Algorithm for the Maximum Flow Problem

An incremental algorithm may yield an enormous computational time saving to solve a network flow problem. It updates the solution to an instance of a problem for a unit change in the input. In this paper we have proposed an efficient incremental implementation of maximum flow problem after inserting an edge in the network G. The algorithm has the time complexity of O((n)² m), where n is the number of affected vertices and m is the number of edges in the network. We have also discussed the incremental algorithm for deletion of an edge in the network G.     

一类带约束min-max-min问题的区间算法

构造了求解一类带不等式约束的min-max-min问题的区间算法,其中目标函数和约束函数都是一阶连续可微函数,证明了方法的收敛性,给出了数值算例.该方法可以同时求出问题的最优值和全部全局最优解,是有效和可靠的.     

用于非光滑优化的信赖域算法的一个实施方案

本给出了处理无约束非光滑优化的信赖域算法的一个实施方案。数值实验表明：这种方案是切实可行和可靠的。     

带概率判断和模糊区间判断的一种排序算法

对于 AHP中一类判断为模糊、不确定性问题 ,用随机变量和模糊区间描述其判断 ,采用 0 .1～ 0 .9标度 ,建立模糊互补判断矩阵 ,利用数学变换得到模糊一致性判断矩阵 ,给出排序向量算法及公式 ,便于实际应用     

An Interval Analysis Approach to the EM Algorithm

Abstract

The EM algorithm is widely used in incomplete-data problems (and some complete-data problems) for parameter estimation. One limitation of the EM algorithm is that, upon termination, it is not always near a global optimum. As reported by Wu (1982), when several stationary points exist, convergence to a particular stationary point depends on the choice of starting point. Furthermore, convergence to a saddle point or local minimum is also possible. In the EM algorithm, although the log-likelihood is unknown, an interval containing the gradient of the EM q function can be computed at individual points using interval analysis methods. By using interval analysis to enclose the gradient of the EM q function (and, consequently, the log-likelihood), an algorithm is developed that is able to locate all stationary points of the log-likelihood within any designated region of the parameter space. The algorithm is applied to several examples. In one example involving the t distribution, the algorithm successfully locates (all) seven stationary points of the log-likelihood.     

An Efficient Implementation of the EMICM Algorithm for the Interval Censored NPMLE

The EMICM algorithm is an established method for computing the interval-censored NPMLE, a generalization of the Kaplan Meier curves for interval censored data. The novel contribution in this work is an efficient implementation, allowing each iteration to be computed in linear time. Using simulated data, it is shown that this new implementation is significantly faster than alternative EMICM implementations or other competing algorithms, allowing for analyses of datasets orders of magnitude larger than previously available.     

需求区间型运输问题的求解算法

为了便于建立与需求区间型运输问题有关的决策支持系统，本给出了一个求解需求区间型运输问题的数值算法，证明了算法的理论依据，并举例说明算法的应用，该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法有较高的计算效率。     

一类求解非线性等式和不等式约束优化问题的区间算法

在Moore二分法的基础上,通过构造的区间列L中标志矢量R的分量取值来删除部分不满足约束条件的区域,将非线性约束优化问题转化为初始域子域上的无约束优化问题,该算法可利用极大熵方法求解多目标优化问题,理论分析和数值结果均表明,这种算法是稳定且可靠的.     

An Adaptive Version for the Metropolis Adjusted Langevin Algorithm with a Truncated Drift

This paper extends some adaptive schemes that have been developed for the Random Walk Metropolis algorithm to more general versions of the Metropolis-Hastings (MH) algorithm, particularly to the Metropolis Adjusted Langevin algorithm of Roberts and Tweedie (1996). Our simulations show that the adaptation drastically improves the performance of such MH algorithms. We study the convergence of the algorithm. Our proves are based on a new approach to the analysis of stochastic approximation algorithms based on mixingales theory.      

The Incremental Gauss-Newton Algorithm with Adaptive Stepsize Rule

In this paper, we consider the Extended Kalman Filter (EKF) for solving nonlinear least squares problems. EKF is an incremental iterative method based on Gauss-Newton method that has nice convergence properties. Although EKF has the global convergence property under some conditions, the convergence rate is only sublinear under the same conditions. One of the reasons why EKF shows slow convergence is the lack of explicit stepsize. In the paper, we propose a stepsize rule for EKF and establish global convergence of the algorithm under the boundedness of the generated sequence and appropriate assumptions on the objective function. A notable feature of the stepsize rule is that the stepsize is kept greater than or equal to 1 at each iteration, and increases at a linear rate of k under an additional condition. Therefore, we can expect that the proposed method converges faster than the original EKF. We report some numerical results, which demonstrate that the proposed method is promising.     

求多变量非光滑函数所有总体极小点的区间算法

本文通过区间分析和目标函数的特殊导数,建立寻求X^0属于R^n上一类非光滑函数所有总体极小点的区间算法。理论分析和数值结果均表明本文算法是可靠和有效的。     

一类min-max-min问题的区间算法

讨论了一类由一阶连续可微函数构成的无约束min-max-min问题．通过构造目标函数的区间扩张、无解区域删除原则，建立了求解min-max-min问题的区间算法，证明了算法的收敛性，给出了数值算例．理论证明和数值结果表明方法是可靠和有效的．     

一类线性规划问题的区间调节熵算法

本文将熵函数的思想和区间分析相结合,构造了一类线性规划问题的区间调节熵算法,讨论了调节熵函数的区间扩张及其收敛阶,以及相关的区域删除检验原则,证明了算法的收敛性,给出了数值算例.理论与数值结果表明该方法是可靠和有效的.     

The Distance Education Debate: An Australian View

This essay tells the story of one person's transformation from ineffective to effective teacher. While ostensibly a narrative of personal revelation and growth, the author reveals that re-envisioning who he is as a teacher required critical reflection on the social forces that shape people. He shows the link between his early discomforts and failures in the classroom and the basic messages about education and self-worth conveyed in the community that raised him. And he introduces us to remarkable students who taught him the real-world and classroom implications of abstractions like race and class. These experiences culminated in better teaching but, more importantly, in the recognition that we cannot know and reach our students unless we are willing to interrogate and transform the lens—the social self—that we bring to the classroom.     

A Feasibility Result for the Block Interval Gaussian Algorithm

A new class of block interval matrices is given for which the block interval Gaussian algorithm is feasible.     

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.     

一类非光滑总体极值的区间算法

本文利用区间分析知识 ,构造了一类 n维非光滑函数总体极值的区间算法 ,理论分析和实例计算均表明本文算法安全可靠 ;能求出全部总体极小点 ;收敛速度也比以前方法[1] 明显加快     

ICTM: An Interval Tessellation-Based Model for Reliable Topographic Segmentation

This work introduces a tessellation-based model for the declivity analysis of geographic regions. The analysis of the relief declivity, which is embedded in the rules of the model, categorizes each tessellation cell, with respect to the whole considered region, according to the (positive, negative, null) sign of the declivity of the cell. Such information is represented in the states assumed by the cells of the model. The overall configuration of such cells allows the division of the region into subregions of cells belonging to a same category, that is, presenting the same declivity sign. In order to control the errors coming from the discretization of the region into tessellation cells, or resulting from numerical computations, interval techniques are used. The implementation of the model is naturally parallel since the analysis is performed on the basis of local rules. An immediate application is in geophysics, where an adequate subdivision of geographic areas into segments presenting similar topographic characteristics is often convenient.     

Interval Algorithm for a Kind of Nonsmooth Global Optimization

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｆｏｌｌｏｗｉｎｇｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｉｓｃｏｎｓｉｄｅｒｅｄ：ｇｌｏｂａｌｍｉｎｉｍｉｚｅｆ（ｘ）,ｆ：Ｘ０Ｒｎ→Ｒ,（１）ｗｈｅｒｅＸ０ｉｓａｎｙｃｌｏｓｅｄｄｏｍａｉｎ,ｆｉｓａｃｏｎｔｉｎｕｏｕｓａｎｄｐｉｅｃｅｗｉｓｅｓｍｏｏｔｈｆｕｎｃｔｉｏｎｏｖｅｒＸ０,ａｎｄｉｔｓｒｉｇｈｔａｎｄｌｅｆｔｄｅｒｉｖａｔｉｖｅｅｘｉｓｔａｔｎｏｎ－ｄｉｆｆｉｅｒｅｎｔｉａｂｌｅｐｏｉｎｔ,ｆｉｓｃａｌｌｅｄｑｕａｓｉ－ｓｍｏｏｔ…     

A New Version of the Price's Algorithm for Global Optimization

We present an algorithm for finding a global minimum of a multimodal,multivariate function whose evaluation is very expensive, affected by noise andwhose derivatives are not available. The proposed algorithm is a new version ofthe well known Price's algorithm and its distinguishing feature is that ittries to employ as much as possible the information about the objectivefunction obtained at previous iterates. The algorithm has been tested on alarge set of standard test problems and it has shown a satisfactorycomputational behaviour. The proposed algorithm has been used to solveefficiently some difficult optimization problems deriving from the study ofeclipsing binary star light curves.