-
作者：Kiraly, Csaba; Szigeti, Zoltan; Tanigawa, Shin-ichi
作者单位：Eotvos Lorand University; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); University of Tokyo
摘要：Edmonds' arborescence packing theorem characterizes directed graphs that have arc-disjoint spanning arborescences in terms of connectivity. Later he also observed a characterization in terms of matroid intersection. Since these fundamental results, intensive research has been done for understanding and extending these results. In this paper we shall extend the second characterization to the setting of reachability-based packing of arborescences. The reachability-based packing problem was intro...
-
作者：Mehlitz, Patrick
作者单位：Brandenburg University of Technology Cottbus
摘要：In optimal control, switching structures demanding at most one control to be active at any time instance appear frequently. Discretizing such problems, a so-called mathematical program with switching constraints is obtained. Although these problems are related to other types of disjunctive programs like optimization problems with complementarity or vanishing constraints, their inherent structure makes a separate consideration necessary. Since standard constraint qualifications are likely to fa...
-
作者：Hosseini, Reshad; Sra, Suvrit
作者单位：University of Tehran; Institute for Research in Fundamental Sciences IPM; Massachusetts Institute of Technology (MIT)
摘要：We consider maximum likelihood estimation for Gaussian Mixture Models (Gmm s). This task is almost invariably solved (in theory and practice) via the Expectation Maximization (EM) algorithm. EM owes its success to various factors, of which is its ability to fulfill positive definiteness constraints in closed form is of key importance. We propose an alternative to EM grounded in the Riemannian geometry of positive definite matrices, using which we cast Gmm parameter estimation as a Riemannian o...
-
作者：Philpott, A. B.; Wahid, F.; Bonnans, J. F.
作者单位：University of Auckland; Inria
摘要：Mixed integer dynamic approximation scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description ofMIDAS, and prove its almost-sure convergence to a 2T e-optimal policy for problems with T stages when the Bellman functions are known to be monotonic, and the sampling...
-
作者：Permenter, Frank; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies certain invariance conditions, restricting to its range yields an equivalent primal-dual pair over a lower-dimensional symmetric cone-namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices. We present a simple algorithm for minimizing the rank of this projection and hence the dimension of this subalgebra. We also s...
-
作者：Burer, Samuel; Ye, Yinyu
作者单位：University of Iowa; Stanford University
摘要：We study a class of quadratically constrained quadratic programs (QCQPs), called diagonal QCQPs, which contain no off-diagonal terms x j xk for j = k, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature and can be checked in polynomial time. We then extend our analysis from diagonal QCQPs to general QCQPs, i.e., ones with no particular structure...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Moran R, Diego A.
作者单位：International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez
摘要：Given P. Rn, a mixed-integer set PI = P n (Zt x Rn-t), and a k-tuple of ndimensional integral vectors (p1,..., pk) where the last n - t entries of each vector is zero, we consider the relaxation of PI obtained by taking the convex hull of points x in P for which pT 1 x,..., pT k x are integral. We then define the k-dimensional lattice closure of PI to be the intersection of all such relaxations obtained from k-tuples of n-dimensional vectors. When P is a rational polyhedron, we show that given...
