We consider some problems of inference from censored discrete-time Markov chains. The censoring mechanism is general enough to be useful in applications and maintains the conditional multinomial sampling model for suc...
详细信息
We consider some problems of inference from censored discrete-time Markov chains. The censoring mechanism is general enough to be useful in applications and maintains the conditional multinomial sampling model for successive transitions. Procedures are given for nonparametric estimation of transition probabilities and tests of the intrinsic-time and time-homogeneity hypotheses. These procedures apply to multiwave panel data when continuous-time Markov chains are only periodically monitored. To illustrate this we build on a result of Singer and Cohen (1979) by showing that a nonhomogeneous Markov chain without an intrinsic-time is a reasonable model for transition data from a WHO malaria survey.
Semi-infinite linear programs often arise as the limit of a sequence of approximating linear programs. Hence, studying the behavior of extensions of linear programming algorithms to semi-infinite problems can yield va...
详细信息
Semi-infinite linear programs often arise as the limit of a sequence of approximating linear programs. Hence, studying the behavior of extensions of linear programming algorithms to semi-infinite problems can yield valuable insight into the behavior of the underlying linear programming algorithm when the number of constraints or the number of variables is very large. In this paper, we study the behavior of the affine-scaling algorithm on a particular semi-infinite linear programming problem. We show that the continuous trajectories converge to the optimal solution but that, for any strictly positive step, there are starting points for which the discrete algorithm converges to nonoptimal boundary points.
Tsuchiya and Muramatsu recently proved that the affine-scaling algorithm for linear programming generates convergent sequences of primal and dual variables whose limits are optimal for the corresponding primal and dua...
详细信息
Tsuchiya and Muramatsu recently proved that the affine-scaling algorithm for linear programming generates convergent sequences of primal and dual variables whose limits are optimal for the corresponding primal and dual problems as long as the step size is no more than two-thirds of the distance to the nearest face of the polytope. An important feature of this result is that it does not require any nondegeneracy assumptions. In this paper we show that Tsuchiya and Muramatsu's result is sharp by providing a simple linear programming problem for which the sequence of dual variables fails to converge for every step size greater than two-thirds.
Version 5.1 of MINOS was used to analyze a set of linear programming test problems, which were run with different sets of options for scaling and partial pricing to illustrate the effects of these options on the perfo...
详细信息
Version 5.1 of MINOS was used to analyze a set of linear programming test problems, which were run with different sets of options for scaling and partial pricing to illustrate the effects of these options on the performance of the simplex method. Testing was performed on a DEC VAXstation II with 13 megabytes of main memory. The solution time was measured by timing the MINOS subroutine M5SOLV. The results demonstrate that the different options can significantly improve or degrade the performance of the simplex method. Scaling and partial pricing can improve the performance of the simplex method in most cases. However, options must be carefully chosen - a difficult task - in order not to degrade the performance of the simplex method.
A new method for obtaining an initial feasible interior-point solution to a linear program is presented. This method avoids the use of a "big-M", and is shown to work well on a standard set of test problems....
详细信息
A new method for obtaining an initial feasible interior-point solution to a linear program is presented. This method avoids the use of a "big-M", and is shown to work well on a standard set of test problems. Conditions are developed for obtaining a near-optimal solution that is feasible for an associated problem, and details of the computational testing are presented. Other issues related to obtaining and maintaining accurate feasible solutions to linear programs with an interior-point method are discussed. These issues are important to consider when solving problems that have no primal or dual interior-point feasible solutions.
作者：
STEELE, JMPrinceton University
Program in Statistics and Operations Research School of Engineering and Applied Science Princeton NJ 08544 USA
A bound is given for the cost of the spanning tree produced by the sequential minimal insertion procedure as applied to n points in the unit d -cube. The technique developed is reasonably general and can be applied to...
详细信息
A bound is given for the cost of the spanning tree produced by the sequential minimal insertion procedure as applied to n points in the unit d -cube. The technique developed is reasonably general and can be applied to several other problems of computational geometry, including the nearest neighbour heuristic for the traveling salesman problem. Attention is also given to bounding the sum of the powers of the edge lengths of sequentially constructed trees and paths. Examples illustrate that the bounds obtained are of best possible order as a function of the number of points.
We consider a system of interacting diffusive particles with finite range random interaction. The variables can be interpreted as charges at sites indexed by a periodic multidimensional lattice. The equilibrium states...
We consider a system of interacting diffusive particles with finite range random interaction. The variables can be interpreted as charges at sites indexed by a periodic multidimensional lattice. The equilibrium states of the system are canonical Gibbs measures with finite range random interaction. Under the diffusive scaling of lattice spacing and time, we derive a deterministic nonlinear diffusion equation for the time evolution of the macroscopic charge density. This limit is almost sure with respect to the random environment.
This note sharpens and generalizes an inequality of Platzman and Bartholdi on the ratio of the cost of the path provided by the spacefilling heuristic to the cost of the optimal path through n points in R d .
This note sharpens and generalizes an inequality of Platzman and Bartholdi on the ratio of the cost of the path provided by the spacefilling heuristic to the cost of the optimal path through n points in R d .
The problem of estimating the transition probabilities for the Markov chain associated to a Markov renewal process is considered. The estimators are to be based on censored observations of the Markov renewal process. ...
详细信息
The problem of estimating the transition probabilities for the Markov chain associated to a Markov renewal process is considered. The estimators are to be based on censored observations of the Markov renewal process. For a class of Markov renewal processes whose transition distributions factor, nonparametric estimators are defined. They are shown to be consistent and to converge weakly go Gaussian random variables. The result builds upon those in Gill (1980) for nonparametric estimation in this setting.
We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is {Mathematical expression} instead ...
详细信息
暂无评论