Interior hybrid proximal extragradient methods for the linear monotone complementarity problem

We present new infeasible path-following methods for linear monotone complementarity problems based on Auslender, Teboulle and Ben-Tiba’s log-quadratic barrier functions. The central paths associated with these barriers are always well defined and, for those problems which have a solution, convergent to a pair of complementary solutions. Starting points in these paths are easy to compute. The theoretical iteration-complexity of these new path-following methods is derived and improved by a strategy which uses relaxed hybrid proximal-extragradient steps to control the quadratic term. Encouraging preliminary numerical experiments are presented.     

A simple but NP-hard problem of mixed-discrete programming and its solution by approximate algorithms

A NP-hard problem (P) of mixed-discrete linear programming is considered which consists in the minimization of a linear objective function subject to a special non-connected subset of an unbounded polymatroid. For this problem we describe three polynomial approximate algorithms including a greedy algorithm and a fully polynomial approximation scheme solving a special subproblem of (P).     

Clustering Multivariate Longitudinal Observations: The Contaminated Gaussian Hidden Markov Model

The Gaussian hidden Markov model (HMM) is widely considered for the analysis of heterogenous continuous multivariate longitudinal data. To robustify this approach with respect to possible elliptical heavy-tailed departures from normality, due to the presence of outliers, spurious points, or noise (collectively referred to as bad points herein), the contaminated Gaussian HMM is here introduced. The contaminated Gaussian distribution represents an elliptical generalization of the Gaussian distribution and allows for automatic detection of bad points in the same natural way as observations are typically assigned to the latent states in the HMM context. Once the model is fitted, each observation has a posterior probability of belonging to a particular state and, inside each state, of being a bad point or not. In addition to the parameters of the classical Gaussian HMM, for each state we have two more parameters, both with a specific and useful interpretation: one controls the proportion of bad points and one specifies their degree of atypicality. A sufficient condition for the identifiability of the model is given, an expectation-conditional maximization algorithm is outlined for parameter estimation and various operational issues are discussed. Using a large-scale simulation study, but also an illustrative artificial dataset, we demonstrate the effectiveness of the proposed model in comparison with HMMs of different elliptical distributions, and we also evaluate the performance of some well-known information criteria in selecting the true number of latent states. The model is finally used to fit data on criminal activities in Italian provinces. Supplementary materials for this article are available online     

����EM�㷨��II�ͻ��ɾʧ���ݵIJ�������

??In this paper, we estimate parameters of gamma life distribution and normal life distribution by EM algorithm based on Type-II hybrid censored data. The covariance matrices are derived as well. Some numerical examples are also presented for illustration.     

Some notes on split Newton iterative algorithm

In this study, a parameterized split Newton method is derived by using the accelerating technique. Convergence and error estimates of the method are obtained. In practical application, the proposed method can give a better result in view of computational CPU time. Numerical examples on several partial differential equations are shown to illustrate our findings. Copyright © 2015 John Wiley & Sons, Ltd.     

Discovery Through Gossip

We study randomized gossip‐based processes in dynamic networks that are motivated by information discovery in large‐scale distributed networks such as peer‐to‐peer and social networks. A well‐studied problem in peer‐to‐peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self‐stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network — new edges are added to the network — and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip‐based discovery processes. In the push discovery or triangulation process, each node repeatedly chooses two random neighbors and connects them (i.e., “pushes” their mutual information to each other). In the pull discovery process or the two‐hop walk, each node repeatedly requests or “pulls” a random contact from a random neighbor and connects itself to this two‐hop neighbor. Both processes are lightweight in the sense that the amortized work done per node is constant per round, local, and naturally robust due to the inherent randomized nature of gossip. Our main result is an almost‐tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n‐node graph both processes take rounds to connect every node to all other nodes with high probability, whereas is a lower bound. We also study the two‐hop walk in directed graphs, and show that it takes time with high probability, and that the worst‐case bound is tight for arbitrary directed graphs, whereas Ω(n²) is a lower bound for strongly connected directed graphs. A key technical challenge that we overcome in our work is the analysis of a randomized process that itself results in a constantly changing network leading to complicated dependencies in every round. We discuss implications of our results and their analysis to discovery problems in P2P networks as well as to evolution in social networks. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 565–587, 2016     

Optimal replacement and allocation of multi‐state elements in k‐within‐m‐from‐r/n sliding window systems

This paper proposes a new model that generalizes the linear sliding window system to the case of multiple failures. The considered k ‐within‐ m ‐from‐ r / n sliding window system consists of n linearly ordered multi‐state elements and fails if at least k groups out of m consecutive groups of r consecutive multi‐state elements have cumulative performance lower than the demand W . A reliability evaluation algorithm is suggested for the proposed system. In order to increase the system availability, maintenance actions can be performed, and the elements can be optimally allocated. A joint element allocation and maintenance optimization model is formulated with the objective of minimizing the total maintenance cost subjected to the pre‐specified system availability requirement. Basic procedures of genetic algorithms are adapted to solve the optimization problem. Numerical experiments are presented to illustrate the applications. Copyright © 2015 John Wiley & Sons, Ltd.     

广义半无限规划问题的一种可行方向算法

基于Zoutendijk可行方向算法,本文提出了一种求解广义半无限规划问题的可行方向算法,在保证算法收敛的情况下,此算法比以往的算法在假设条件的要求上有着一定的优势,且数值试验表明此法是可行的.     

Nonlinear function approximation: Computing smooth solutions with an adaptive greedy algorithm

In contrast to linear schemes, nonlinear approximation techniques allow for dimension independent rates of convergence. Unfortunately, typical algorithms (such as, e.g., backpropagation) are not only computationally demanding, but also unstable in the presence of data noise. While we can show stability for a weak relaxed greedy algorithm, the resulting method has the drawback that it requires in practise unavailable smoothness information about the data.In this work we propose an adaptive greedy algorithm which does not need this information but rather recovers it iteratively from the available data. We show that the generated approximations are always at least as smooth as the original function and that the algorithm also remains stable, when it is applied to noisy data. Finally, the applicability of this algorithm is demonstrated by numerical experiments.