Browsing by Author "Xie, W."

Now showing 1 - 3 of 3
  • Thumbnail Image
    Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design
    Singh, Manoj; Xie, W. (2018-02-26)
    Experimental design is a classical problem in statistics and has also found new applications in machine learning. In the experimental design problem, the aim is to estimate an unknown vector x in m-dimensions from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameter x. Given a set S of chosen experiments, the most likelihood estimate x' can be obtained by a least squares computation. One of the robust measures of error estimation is the D-optimality criterion which aims to minimize the generalized variance of the estimator. This corresponds to minimizing the volume of the standard confidence ellipsoid for the estimation error x-x'. The problem gives rise to two natural variants depending on whether repetitions are allowed or not. The latter variant, while being more general, has also found applications in the geographical location of sensors. In this work, we first show that a 1/e-approximation for the D-optimal design problem with and without repetitions giving us the first constant factor approximation for the problem. We also consider the case when the number of experiments chosen is much larger than the dimension of the measurements and provide an asymptotically optimal approximation algorithm.
  • Thumbnail Image
    On Distributionally Robust Chance Constrained Program with Wasserstein Distance
    Xie, W. (2018-06-21)
    This paper studies a distributionally robust chance constrained program (DRCCP) with Wasserstein ambiguity set, where the uncertain constraints should satisfy with a probability at least a given threshold for all the probability distributions of the uncertain parameters within a chosen Wasserstein distance from an empirical distribution. In this work, we investigate equivalent reformulations and approximations of such problems. We first show that a DRCCP can be reformulated as a conditional-value-at-risk constrained optimization problem, and thus admits tight inner and outer approximations. When the metric space of uncertain parameters is a normed vector space, we show that a DRCCP of bounded feasible region is mixed integer representable by introducing big-M coefficients and additional binary variables. For a DRCCP with pure binary decision variables, by exploring submodular structure, we show that it admits a big-M free formulation and can be solved by branch and cut algorithm. This result can be generalized to mixed integer DRCCPs. Finally, we present a numerical study to illustrate effectiveness of the proposed methods.
  • Thumbnail Image
    Optimal layout of transshipment facility locations on an infinite homogeneous plane
    Xie, W.; Ouyang, Y. (Pergamon-Elsevier, 2015-05-01)