Given a connected graph G = (V,E) with a nonnegative cost on each edge in E, a nonnegative prize at each vertex in V, and a target set V'⊆ V, the Prize Collecting Steiner Tree (PCST) problem is to find a tree T in G interconnecting all vertices of V' such that the total cost on edges in T minus the total prize at vertices in T is minimized. The PCST problem appears frequently in practice of operations research. While the problem is NP-hard in general, it is polynomial-time solvable when graphs G are restricted to series-parallel graphs. In this paper, we study the PCST problem with interval costs and prizes, where edge e could be included in T by paying cost xe ∈ [ce-, ce+] while taking risk (ce+ -xe)/(ce+ -ce-) of malfunction at e, and vertex v could be asked for giving a prize yv ∈ [pv-, pv+] for its inclusion in T while taking risk (yv - pv-)/(pv+ - pv-) of refusal by v. We establish two risk models for the PCST problem with interval data. Under given budget upper bound on constructing tree T, one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T. We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality. Our study shows that the risk models proposed have advantages over the existing robust optimization model, which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.
In this paper, we give a variational characterization for the growth rate of a multitype population modelled by a multitype Galton-Watson branching process. In particular, the so-called retrospective process plays an important role in the description of the equilibrium state used in the variational characterization. We define the retrospective process associated with a multitype Galton-Watson branching process and identify it with the mutation process describing the type evolution along typical lineages of the multitype Galton-Watson branching process.
In this paper, we propose a bias-corrected empirical likelihood (BCEL) ratio to construct a goodness-of-fit test for generalized linear mixed models. BCEL test maintains the advantage of empirical likelihood that is self scale invariant and then does not involve estimating limiting variance of the test statistic to avoid deteri- orating power of test. Furthermore, the bias correction makes the limit to be a process in which every variable is standard chi-squared. This simple structure of the process enables us to construct a Monte Carlo test procedure to approximate the null distribution. Thus, it overcomes a problem we encounter when classical empirical likelihood test is used, as it is asymptotically a functional of Gaussian process plus a normal shift function. The complicated covariance function makes it difficult to employ any approximation for the null distribution. The test is omnibus and power study shows that the test can detect local alternatives approaching the null at parametric rate. Simulations are carried out for illustration and for a comparison with existing method.
Multilevel (hierarchical) modeling is a generalization of linear and generalized linear modeling in which regression coefficients are modeled through a model, whose parameters are also estimated from data. Multilevel model fails to fit well typically by the use of the EM algorithm once one of level error variance (like Cauchy distribution) tends to infinity. This paper proposes a composite multilevel to combine the nested structure of multilevel data and the robustness of the composite quantile regression, which greatly improves the efficiency and precision of the estimation. The new approach, which is based on the Gauss-Seidel iteration and takes a full advantage of the composite quantile regression and multilevel models, still works well when the error variance tends to infinity. We show that even the error distribution is normal, the MSE of the estimation of composite multilevel quantile regression models nearly equals to mean regression. When the error distribution is not normal, our method still enjoys great advantages in terms of estimation efficiency.
In this paper, the infinite Prandtl number limit of Rayleigh-Bénard convection is studied. For well prepared initial data, the convergence of solutions in L∞(0, t;H2(G)) is rigorously justified by analysis of asymptotic expansions.
Nagurney (1999) used variational inequalities to study economic equilibrium and financial networks and applied the modified projection method to solve the problem. In this paper, we formulate the problem as a nonlinear complementarity problem. The complementarity model is just the KKT condition for the model of Nagurney (1999). It is a simpler model than that of Nagurney (1999). We also establish sufficient conditions for existence and uniqueness of the equilibrium pattern, which are weaker than those in Nagurney (1999). Finally, we apply a smoothing Newton-type algorithm to solve the problem and report some numerical results.
Rarefaction wave solutions for a one-dimensional model system associated with non-Newtonian compressible fluid are investigated in terms of asymptotic stability. The rarefaction wave solution is proved to be asymptotically stable, provided the initial disturbance is suitably small. The proof is given by the elemental L2 energy method.
The Landweber scheme is a method for algebraic image reconstructions. The convergence behavior of the Landweber scheme is of both theoretical and practical importance. Using the diagonalization of matrix, we derive a neat iterative representation formula for the Landweber schemes and consequently establish the convergence conditions of Landweber iteration. This work refines our previous convergence results on the Landweber scheme.
In this paper, we propose a class of varying coefficient seemingly unrelated regression models, in which the errors are correlated across the equations. By applying the series approximation and taking the contemporaneous correlations into account, we propose an efficient generalized least squares series estimation for the unknown coefficient functions. The consistency and asymptotic normality of the resulting estimators are established. In comparison with the ordinary least squares ones, the proposed estimators are more efficient with smaller asymptotical variances. Some simulation studies and a real application are presented to demonstrate the finite sample performance of the proposed methods. In addition, based on a B-spline approximation, we deduce the asymptotic bias and variance of the proposed estimators.
This paper is devoted to study the Crouzeix-Raviart (C-R) type nonconforming linear triangular finite element method (FEM) for the nonstationary Navier-Stokes equations on anisotropic meshes. By introducing auxiliary finite element spaces, the error estimates for the velocity in the L2-norm and energy norm, as well as for the pressure in the L2-norm are derived.
This article proposes a method for fitting models subject to a convex and log-convex constraint on the probability vector of a product multinomial (binomial) distribution. We present an iterative algorithm for finding the restricted maximum likelihood estimates (MLEs) of the probability vector and show that the algorithm converges to the true solution. Some examples are discussed to illustrate the method.
In this paper, we consider the following quasilinear differential equation (øp(u'))' + λf(t, u) = 0 subject to one of the two boundary conditions: u(0) = u'(1) = 0, u'(0) = u(1) = 0. After transforming them into a problem of symmetrical solutions, the existence of three solutions of the problem is obtained by using a recent critical point theorem of Recceri. An example is given to demonstrate our main result.
In this paper, we analyze the Bregman iterative model using the G-norm. Firstly, we show the convergence of the iterative model. Secondly, using the source condition and the symmetric Bregman distance, we consider the error estimations between the iterates and the exact image both in the case of clean and noisy data. The results show that the Bregman iterative model using the G-norm has the similar good properties as the Bregman iterative model using the L2-norm.
This paper is concerned with the Cauchy problems of one-dimensional compressible Navier-Stokes equations with density-dependent viscosity coefficients. By assuming ρ0 ∈ L1(R), we will prove the existence of weak solutions to the Cauchy problems for θ > 0. This will improve results in Jiu and Xin's paper (Kinet. Relat. Models, 1(2): 313-330 (2008)) in which θ > 1/2 is required. In addition, We will study the large time asymptotic behavior of such weak solutions.
This paper deals with a discrete-time batch arrival retrial queue with the server subject to starting failures. Different from standard batch arrival retrial queues with starting failures, we assume that each customer after service either immediately returns to the orbit for another service with probability or leaves the system forever with probability 1 -θ (0 ≤θ < 1). On the other hand, if the server is started unsuccessfully by a customer (external or repeated), the server is sent to repair immediately and the customer either joins the orbit with probability q or leaves the system forever with probability 1 - q (0 ≤ q < 1). Firstly, we introduce an embedded Markov chain and obtain the necessary and sufficient condition for ergodicity of this embedded Markov chain. Secondly, we derive the steady-state joint distribution of the server state and the number of customers in the system/orbit at arbitrary time. We also derive a stochastic decomposition law. In the special case of individual arrivals, we develop recursive formulae for calculating the steady-state distribution of the orbit size. Besides, we investigate the relation between our discrete-time system and its continuous counterpart. Finally, some numerical examples show the influence of the parameters on the mean orbit size.
One of the main goals of machine learning is to study the generalization performance of learning algorithms. The previous main results describing the generalization ability of learning algorithms are usually based on independent and identically distributed (i.i.d.) samples. However, independence is a very restrictive concept for both theory and real-world applications. In this paper we go far beyond this classical framework by establishing the bounds on the rate of relative uniform convergence for the Empirical Risk Minimization (ERM) algorithm with uniformly ergodic Markov chain samples. We not only obtain generalization bounds of ERM algorithm, but also show that the ERM algorithm with uniformly ergodic Markov chain samples is consistent. The established theory underlies application of ERM type of learning algorithms.
This paper discuss the cusp bifurcation of codimension 2 (i.e. Bogdanov-Takens bifurcation) in a Leslie-Gower predator-prey model with prey harvesting, which was not revealed by Zhu and Lan [Phase portraits, Hopf bifurcation and limit cycles of Leslie-Gower predator-prey systems with harvesting rates, Discrete and Continuous Dynamical Systems Series B. 14(1) (2010), 289-306]. It is shown that there are different parameter values for which the model has a limit cycle or a homoclinic loop.
In this paper we mainly study the difference between the weak solutions generated by a wave front tracking algorithm to isentropic and non-isentropic isothermal Euler system of steady supersonic flow. Under the hypothesis that the initial data are of sufficiently small total variation, we prove that the difference between solutions to isentropic and non-isentropic isothermal Euler system of steady supersonic flow can be bounded by the cube of the total variation of the initial perturbation.
This paper is concerned with the existence and stability of steady states for a prey-predator system with cross diffusion of quasilinear fractional type. We obtain a sufficient condition for the existence of positive steady state solutions by applying bifurcation theory and a detailed priori estimate. In virtue of the principle of exchange of stability, we prove the stability of local bifurcating solutions near the bifurcation point.