convexification

On the convexification of constrained quadratic optimization problems with indicator variables

  • Andrés Gómez
  • Simge Küçükyavuz
  • Linchuan Wei
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , , ,

    Motivated by modern regression applications, in this paper, we study the convexification of quadratic optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear objective, indicator variables, and combinatorial constraints. We prove that for a separable quadratic … Read more

    Outlier detection in time series via mixed-integer conic quadratic optimization

  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , , , ,

    We consider the problem of estimating the true values of a Wiener process given noisy observations corrupted by outliers. The problem considered is closely related to the Trimmed Least Squares estimation problem, a robust estimation procedure well-studied from a statistical standpoint but poorly understood from an optimization perspective. In this paper we show how to … Read more

    Quantifying Double McCormick

  • Jon Lee
  • Emily Speakman
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , , , ,

    When using the standard McCormick inequalities twice to convexify trilinear monomials, as is often the practice in modeling and software, there is a choice of which variables to group first. For the important case in which the domain is a nonnegative box, we calculate the volume of the resulting relaxation, as a function of the … Read more

    Relaxations and discretizations for the pooling problem

  • Shabbir Ahmed
  • Myun-Seok Cheon
  • Santanu S. Dey
  • Akshay Gupte
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment, and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives unifying arguments and new insights on prevalent techniques. We also present new ideas for computing … Read more

    Lagrangian-Conic Relaxations, Part I: A Unified Framework and Its Applications to Quadratic Optimization Problems

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In Part I of a series of study on Lagrangian-conic relaxations, we introduce a unified framework for conic and Lagrangian-conic relaxations of quadratic optimization problems (QOPs) and polynomial optimization problems (POPs). The framework is constructed with a linear conic optimization problem (COP) in a finite dimensional vector space endowed with an inner product, where the … Read more

    Inclusion Certificates and Simultaneous Convexification of Functions

  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization Theory Tags , , ,

    We define the inclusion certificate as a measure that expresses each point in the domain of a collection of functions as a convex combination of other points in the domain. Using inclusion certificates, we extend the convex extensions theory to enable simultaneous convexification of functions. We discuss conditions under which the domain of the functions … Read more