Quadratic optimization

Supermodularity, Curvature, and Convex Relaxations in a Class of Quadratic Binary Optimization Problems

  • Bismark Singh
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization Tags , , ,

    We study the combinatorial structure of a quadratic set function $F(S)$ arising from a class of binary optimization models within the family of undesirable facility location problems. Despite strong empirical evidence of nested optimal solutions in previously studied real-world instances, we show that $F(S)$ is, in general, neither submodular nor supermodular. To quantify deviation from … Read more

    Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Semi-definite Programming Tags , , , ,

    The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a … Read more

    A Parametric Approach for Solving Convex Quadratic Optimization with Indicators Over Trees

  • Aaresh Bhathena
  • Salar Fattahi
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Quadratic Programming Tags , , , , ,

    This paper investigates convex quadratic optimization problems involving $n$ indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix $Q$ defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this … Read more

    Polyhedral Analysis of Quadratic Optimization Problems with Stieltjes Matrices and Indicators

  • Peijing Liu
  • Alper Atamturk
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising … Read more

    Quadratic Optimization Through the Lens of Adjustable Robust Optimization

  • Abbas Khademi
  • Ahmadreza Marandi
    • Categories Quadratic Programming, Robust Optimization Tags , , , , ,

    Quadratic optimization (QO) has been studied extensively in the literature due to its applicability in many practical problems. While practical, it is known that QO problems are generally NP-hard. So, researchers developed many approximation methods to find good solutions. In this paper, we analyze QO problems using robust optimization techniques. To this end, we first … Read more

    Explicit convex hull description of bivariate quadratic sets with indicator variables

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Integer Programming Tags , , , , ,

    We consider the nonconvex set \(S_n = \{(x,X,z): X = x x^T, \; x (1-z) =0,\; x \geq 0,\; z \in \{0,1\}^n\}\), which is closely related to the feasible region of several difficult nonconvex optimization problems such as the best subset selection and constrained portfolio optimization. Utilizing ideas from convex analysis and disjunctive programming, we … Read more

    On the convex hull of convex quadratic optimization problems with indicators

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

    We consider the convex quadratic optimization problem with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of a single positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of … Read more

    A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators

  • Peijing Liu
  • Salar Fattahi
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , , , , ,

    In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This … Read more