-
作者：Mai, Ngoc Hoang Anh; Lasserre, Jean-Bernard; Magron, Victor
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：In a first contribution, we revisit two certificates of positivity on (possibly non-compact) basic semialgebraic sets due to Putinar and Vasilescu (C R Acad Sci Ser I Math 328(6):495-499, 1999). We use Jacobi's technique from (Math Z 237(2):259-273, 2001) to provide an alternative proof with an effective degree bound on the sums of squares weights in such certificates. As a consequence, it allows one to define a hierarchy of semidefinite relaxations for a general polynomial optimization proble...
-
作者：Barak, Boaz; Moitra, Ankur
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：In the noisy tensor completion problem we observe m entries (whose location is chosen uniformly at random) from an unknown n(1) x n(2) x n(3) tensor T. We assume that T is entry-wise close to being rank r. Our goal is to fill in its missing entries using as few observations as possible. Let n = max(n(1), n(2), n(3)). We show that if m greater than or similar to n(3/2)r then there is a polynomial time algorithm based on the sixth level of the sum-of-squares hierarchy for completing it. Our esti...
-
作者：Naderi, Mohammad Javad; Buchanan, Austin; Walteros, Jose L.
作者单位：Oklahoma State University System; Oklahoma State University - Stillwater; State University of New York (SUNY) System; University at Buffalo, SUNY
摘要：The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) for the clique problem that have more desirable worst-case properties, especially for sparse graphs. The smallest MIP that we pro...
-
作者：Kiraly, Csaba; Mihalyko, Andras
作者单位：Eotvos Lorand University; HUN-REN
摘要：For two integers k > 0 and l, a graph G = (V, E) is called (k, l)-tight if vertical bar E vertical bar = k vertical bar V vertical bar-l and i(G)(X) <= k vertical bar X vertical bar-l for each X subset of V for which i(G)(X) >= 1, where i(G)(X) denotes the number of induced edges by X. G is called (k, l)-redundant if G - e has a spanning (k, l)-tight subgraph for all e is an element of E. We consider the following augmentation problem. Given a graph G = (V, E) that has a (k, l)-tight spanning ...
-
作者：Kocyigit, Cagil; Rujeerapaiboon, Napat; Kuhn, Daniel
作者单位：University of Luxembourg; National University of Singapore; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer, only knowing that the buyer's values for the goods range over a rectangular uncertainty set. We interpret this pricing problem as a zero-sum game between the seller, who chooses a selling mechanism, and a fictitious adversary or 'nature', who chooses the buyer's values from within the uncertainty set. Using duality techniques rooted in robust optimizati...
-
作者：Ahmed, Shabbir; Cabral, Filipe Goulart; Paulo da Costa, Bernardo Freitas
作者单位：University System of Georgia; Georgia Institute of Technology; Universidade Federal do Rio de Janeiro
摘要：We propose a new algorithm for solving multistage stochastic mixed integer linear programming (MILP) problems with complete continuous recourse. In a similar way to cutting plane methods, we construct nonlinear Lipschitz cuts to build lower approximations for the non-convex cost-to-go functions. An example of such a class of cuts are those derived using Augmented Lagrangian Duality for MILPs. The family of Lipschitz cuts we use is MILP representable, so that the introduction of these cuts does...
-
作者：Zhang, Shixuan; Sun, Xu Andy
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT)
摘要：In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with non-Lipschitzian value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based o...
-
作者：Banholzer, Dirk; Fliege, Jorg; Werner, Ralf
作者单位：University of Southampton; University of Augsburg
摘要：We study the rates at which optimal estimators in the sample average approximation approach converge to their deterministic counterparts in the almost sure sense and in mean. To be able to quantify these rates, we consider the law of the iterated logarithm in a Banach space setting and first establish under relatively mild assumptions almost sure convergence rates for the approximating objective functions, which can then be transferred to the estimators for optimal values and solutions of the ...
-
作者：Fujishige, Satoru; Tardella, Fabio
作者单位：Kyoto University; University of Florence
摘要：We focus on a new class of integrally convex functions which we call discrete 2-convex functions. Discrete 2-convexity generalizes known classes of integrally convex functions such as the well-established M-/M-(sic)-convex and L-/L-(sic)-convex functions by Murota et al., the recently investigated globally/locally discrete midpoint convex functions by Moriguchi, Murota, Tamura, and Tardella, the directed discrete midpoint convex functions by Tamura and Tsurumi, and BS*- convex and UJ-convex fu...
-
作者：Barmann, Andreas; Schneider, Oskar
作者单位：University of Erlangen Nuremberg; Fraunhofer Gesellschaft
摘要：In the present work, we consider Zuckerberg's method for geometric convex-hull proofs introduced in Zuckerberg (Oper Res Lett 44(5):625-629, 2016). It has only been scarcely adopted in the literature so far, despite the great flexibility in designing algorithmic proofs for the completeness of polyhedral descriptions that it offers. We suspect that this is partly due to the rather heavy algebraic framework its original statement entails. This is why we present a much more lightweight and access...
