Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

WA05

by common constraint qualifications for zero duality gap imply the existence of singular dual solutions that are difficult to find and interpret. We call this the Slater conundrum. We provide sufficient conditions that guarantee that there exists an optimal dual solution that is not singular. 2 - Linear Programming with Fourier Transform Constraints Elahesadat Naghib, Princeton University, Princeton, NJ, United States, Robert J. Vanderbei We exploit the special structure of Fourier Transforms that appear in certain linear optimizations to efficiently approximate their optimal solution. In many important instances of this family of problems such as upper-bounds on Sphere Packing, and Turan’s extremal problem, computational results can shed light and provide intuition about the form of solutions in these problems. Especially for higher geometrical dimensions that the computational efforts suffer from curse of dimensionality, and a theoretical understanding is very much lacking. 3 - Bounding Infinite Dimensional LPs by Finite Dimensional LPs via Poisson Summation Jacob Carruth, PhD, University of Texas at Austin, Austin, TX, United States Optimization problems in which both a function and its Fourier transform are pointwise constrained by inequalities are common in applied and pure math problems. We demonstrate a technique which, if the problem has the right structure, allows one to bound the value of this infinite dimensional problem by the value of a finite dimensional linear programming problem. We’ll discuss applications of this technique to sphere packings and to the Beurling-Selberg box minorant problem. Perturbation Analysis of Conic Optimization Sponsored: Optimization/Linear and Conic Optimization Sponsored Session Chair: Ali Mohammad Nezhad, Lehigh University, Bethlehem, PA, 18015, United States 1 - Parametric Analysis of Linear Conic Optimization Ali Mohammad Nezhad, Lehigh University, Bethlehem, PA, 18015, United States, Tamas Terlaky We consider the parametric and stability analysis of a linear conic optimization problem when the objective function is perturbed along a fixed direction. We study the continuity of the optimal set mapping and present the behavior of the so called optimal partition with respect to the perturbation of the objective vector. We estimate the length of a nonlinearity interval, where the dimension of the minimal faces containing the primal and dual optimal sets stays constant. 2 - Condition Numbers for Convex Functions with Polytope Domains David Gutman, Carnegie Mellon University, Pittsburgh, PA, United States, Javier Pena We propose a condition number of a smooth convex function relative to a reference polytope. This relative condition number is defined as the ratio of a relative smooth constant to a relative strong convexity constant of the function, where both constants are relative to the reference polytope. The relative condition number extends the main properties of the traditional condition number. In particular, we show that the condition number of a quadratic convex function relative to a polytope is precisely the square of the diameter-to-facial- distance ratio of a scaled polytope for a canonical scaling induced by the function. Furthermore, we illustrate how the relative condition number of a function bounds the linear rate of convergence of first-order methods for minimization of the function over the polytope. In the final part of the talk, we will discuss possible extensions of the condition numbers to non-polytope domains. 3 - On the Structure of the Inverse-feasible Region of a Linear Program Onur Tavaslioglu, Research Assistant, University of Pittsburgh, 708 William Pitt Union, Pittsburgh, PA, 15260, United States, Taewoo Lee, Silviya Valeva, Andrew J. Schaefer Given a set of feasible solution X to a linear program, we study the set of objectives that make X optimal, known as the inverse-feasible region. We show the relationship between the dimension of a face of a polyhedron and the dimension of the corresponding inverse-feasible region, which leads to necessary and sufficient conditions of the extreme, boundary, and inner points of a linear program. We also characterize the set of objectives that render a given solution uniquely optimal. n WA05 North Bldg 122B

n WA03 North Bldg 121C Stochastic and Robust Optimization Sponsored: Optimization/Optimization under Uncertainty Sponsored Session Chair: Ruiwei Jiang, University of Michigan, Ann Arbor, MI, 48109, United States 1 - Data-driven Chance Constrained Programs over Wasserstein Balls Zhi Chen, Imperial College Business School, London, United Kingdom, Daniel Kuhn, Wolfram Wiesemann We provide an exact deterministic reformulation for data-driven chance constrained programs over Wasserstein balls. For individual chance constraints as well as joint chance constraints with right-hand side uncertainty, our reformulation amounts to a mixed-integer conic program. In the special case of a Wasserstein ball with the 1-norm or the infinity norm, the chance constrained program can be reformulated as a mixed-integer linear program. Using our reformulation, we show that two popular approximation schemes based on the conditional-value-at-risk and the Bonferroni inequality can perform conservatively in practice and that these two schemes are generally incomparable with each other. 2 - Exploiting Partial Correlations in Distributionally Robust Optimization Karthyek Murthy, Singapore University of Technology and Design, Singapore, Karthik Natarajan, Divya Padmanabhan We aim to identify partial covariance structures that allow polynomial-time solvable tight reformulations for evaluating the worst-case expected value of mixed integer linear programs whose objective coefficients are uncertain. Assuming only the knowledge of the mean and covariance entries restricted to block-diagonal patterns, we develop a reduced SDP formulation whose complexity is characterized by a suitable projection of the convex hull of {(1,x)’(1,x): x \in X}, where X is the feasible region. These projected constraints lend to efficient characterizations for appointment scheduling problem, PERT networks, and linear assignment problems that are polynomial-time solvable. 3 - The Discrete Moment Problem with Nonconvex Shape Constraints Christopher Ryan, University of Chicago, 5807 S. Woodlawn Ave, Chicago, IL, 60637, United States, Xi Chen, Simai He, Bo Jiang, Teng Zhang The discrete moment problem finds a worst-case discrete distribution that satisfies a given set of moments. We study the problem with additional “shape constraints that guarantee the worst case distribution is either log-concave or has an increasing failure rate. We characterize the structure of optimal extreme point distributions by developing new results in reverse convex optimization. We are able to show that an optimal extreme point solution to a moment problem with m moments and log-concave shape constraints is piecewise geometric with at most m pieces. This structure allows us to design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. 4 - Distributionally Robust Combinatorial Optimization Ruiwei Jiang, University of Michigan, 1205 Beal Ave., Ann Arbor, MI, 48109, United States, Shabbir Ahmed, Mohit Singh We study distributionally robust analogs of combinatorial optimization problem with uncertain objective coefficients. We provide equivalent deterministic reformulations of such problems under several types of ambiguity sets, and discuss corresponding solution approaches. n WA04 North Bldg 122A Joint Session OPT/Practice Curated: Infinite Dimensional LP with Applications to Sphere Packing Sponsored: Optimization/Integer and Discrete Optimization Sponsored Session Chair: Elahesadat Naghib, Princeton University, Princeton, NJ, United States 1 - The Slater Conundrum: Duality and Pricing in Infinite-dimensional Optimization Christopher Ryan, University of Chicago, 5807 S. Woodlawn Ave, Chicago, IL, 60637, United States, Kipp Martin, Matthew Stern In finite dimensions, a dual solution is a vector of “dual prices that index the primal constraints and have a natural economic interpretation. In infinite dimensions, this structure may fail to hold for a broad class of problems with constraint vector spaces that are Riesz spaces that are s-order complete or satisfy the projection property. In these spaces, the existence of interior points required

411