-
作者：Rothvoss, Thomas
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We prove that there are 0/1 polytopes P subset of R-n that do not admit a compact LP formulation. More precisely we show that for every n there is a set X subset of {0, 1}(n) such that conv(X) must have extension complexity at least 2(n/2.(1-o(1))). In otherwords, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. Conditioning on NP not subset of P-/poly, our ...
-
作者：Stockbridge, Rebecca; Bayraksan, Guzin
作者单位：University of Arizona; University of Arizona
摘要：Monte Carlo sampling-based estimators of optimality gaps for stochastic programs are known to be biased. When bias is a prominent factor, estimates of optimality gaps tend to be large on average even for high-quality solutions. This diminishes our ability to recognize high-quality solutions. In this paper, we present a method for reducing the bias of the optimality gap estimators for two-stage stochastic linear programs with recourse via a probability metrics approach, motivated by stability r...
-
作者：Wen, Zaiwen; Yin, Wotao
作者单位：Shanghai Jiao Tong University; Shanghai Jiao Tong University; Rice University
摘要：Minimization with orthogonality constraints (e.g., X-inverted perpendicular X = I) and/or spherical constraints (e. g., parallel to x parallel to(2) = 1) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with these diff...
-
作者：Ioffe, Alexander D.
作者单位：Technion Israel Institute of Technology
摘要：The paper studies regularity properties of set-valued mappings between metric spaces. In the context of metric regularity, nonlinear models correspond to nonlinear dependencies of estimates of error bounds in terms of residuals. Among the questions addressed in the paper are equivalence of the corresponding concepts of openness and pseudo-Holder behavior, general and local regularity criteria with special emphasis on regularity of order , for local settings, and variational methods to extimate...
-
作者：Houska, Boris; Diehl, Moritz
作者单位：KU Leuven
摘要：In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min-max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curv...
-
作者：Geihe, Benedict; Lenz, Martin; Rumpf, Martin; Schultz, Ruediger
作者单位：University of Bonn; University of Duisburg Essen
摘要：Shape optimization of the fine scale geometry of elastic objects is investigated under stochastic loading. Thus, the object geometry is described via parametrized geometric details placed on a regular lattice. Here, in a two dimensional set up we focus on ellipsoidal holes as the fine scale geometric details described by the semiaxes and their orientation. Optimization of a deterministic cost functional as well as stochastic loading with risk neutral and risk averse stochastic cost functionals...
-
作者：Aussel, D.; Eberhard, A.
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Perpignan Via Domitia; Royal Melbourne Institute of Technology (RMIT)
摘要：The concept of maximal quasimonotonicity of set-valued map is introduced and studied. Regularity properties of this class of operators is investigated, in particular the ccvc property, an adaptation to the quasimonotone case of the classical notion of cusco map. In an Asplund space, we provide sufficient conditions for a ccvc quasimonotone operator to be single-directional on a -dense subset.
-
作者：Li, Guoyin
作者单位：University of New South Wales Sydney
摘要：In this paper, by examining the recession properties of convex polynomials, we provide a necessary and sufficient condition for a piecewise convex polynomial to have a Holder-type global error bound with an explicit Holder exponent. Our result extends the corresponding results of Li (SIAM J Control Optim 33(5):1510-1529, 1995) from piecewise convex quadratic functions to piecewise convex polynomials.
-
作者：Dontchev, A. L.; Rockafellar, R. T.
作者单位：University of Washington; University of Washington Seattle
摘要：For solving the generalized equation , where is a smooth function and is a set-valued mapping acting between Banach spaces, we study the inexact Newton method described by (f(x(k)) + Df(x(k))(x(k+1) - x(k)) + F(x(k+1) )) boolean AND R-k(x(k), x(k+1) ) not equal empty set, where is the derivative of and the sequence of mappings represents the inexactness. We show how regularity properties of the mappings and are able to guarantee that every sequence generated by the method is convergent either ...
-
作者：Hemmecke, Raymond; Onn, Shmuel; Romanchuk, Lyubov
作者单位：Technical University of Munich; Technion Israel Institute of Technology
摘要：n-Fold integer programming is a fundamental problem with a variety of natural applications in operations research and statistics. Moreover, it is universal and provides a new, variable-dimension, parametrization of all of integer programming. The fastest algorithm for n-fold integer programming predating the present article runs in time with L the binary length of the numerical part of the input and g(A) the so-called Graver complexity of the bimatrix A defining the system. In this article we ...
