Supermodularity and valid inequalities for quadratic optimization with indicators

• URL: http://arxiv.org/abs/2012.14633v1
• Date: Tue, 29 Dec 2020 07:03:09 GMT
• Title: Supermodularity and valid inequalities for quadratic optimization with indicators
• Authors: Alper Atamturk and Andres Gomez
• Abstract summary: We show that the underlying set function for the rank-one quadratic can be minimized in linear time. Explicit forms of the convexhull are given, both in the original space variables and in an extended formulation via conic quadratic-representable inequalities. Experiments indicate that the lifted supermodular inequalities in conic quadratic form are quite effective in reducing the integrality gap for quadratic optimization with indicators.
• Score: 3.8073142980733
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in general, difficult, the specific set function for the rank-one quadratic can be minimized in linear time. We show that the convex hull of the epigraph of the quadratic can be obtaining from inequalities for the underlying supermodular set function by lifting them into nonlinear inequalities in the original space of variables. Explicit forms of the convex-hull description are given, both in the original space of variables and in an extended formulation via conic quadratic-representable inequalities, along with a polynomial separation algorithm. Computational experiments indicate that the lifted supermodular inequalities in conic quadratic form are quite effective in reducing the integrality gap for quadratic optimization with indicators.

Related papers

• Structured model selection via $\ell_1-\ell_2$ optimization [1.933681537640272]
  We develop a learning approach for identifying structured dynamical systems. We show that if the set of candidate functions forms a bounded system, the recovery is stable and is bounded.
  arXiv  Detail & Related papers  (2023-05-27T12:51:26Z)
• Constrained Optimization of Rank-One Functions with Indicator Variables [0.0]
  optimization problems involving a rank-one convex function over constraints modeling restrictions on the support of the decision variables emerge in various machine learning applications. We propose a constructive approach that exploits a hidden conic structure induced by perspective functions. This enables us to systematically give perspective formulations for the convex hull descriptions of sets with nonlinear separable or non-separable objective functions, sign constraints on continuous variables, and constraints on indicator variables.
  arXiv  Detail & Related papers  (2023-03-31T15:51:56Z)
• Multiple Convex Objects Image Segmentation via Proximal Alternating Direction Method of Multipliers [2.294014185517203]
  The convex shape prior turns out to be a simple quadratic inequality constraint on the binary indicator function associated with each object. An image segmentation model incorporating convex shape prior into a probability-based method is proposed. Numerical experiments on natural and medical images demonstrate that the proposed method is superior to some existing methods.
  arXiv  Detail & Related papers  (2022-03-22T00:05:19Z)
• On the convex hull of convex quadratic optimization problems with indicators [2.867517731896504]
  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 and linear constraints. The new theory presented here paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.
  arXiv  Detail & Related papers  (2022-01-02T18:04:52Z)
• Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection [136.4014229319618]
  We study the role of the representation of state-action value functions in regret minimization in finite-horizon Markov Decision Processes (MDPs) with linear structure. We first derive a necessary condition on the representation, called universally spanning optimal features (UNISOFT), to achieve constant regret in any MDP with linear reward function.
  arXiv  Detail & Related papers  (2021-10-27T22:07:08Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Principal Component Hierarchy for Sparse Quadratic Programs [27.812191030127618]
  We propose a novel approximation hierarchy for cardinality-constrained, convex quadratic programs. We show that the proposed methods are competitive with the existing screening methods in the current sparse regression.
  arXiv  Detail & Related papers  (2021-05-25T15:45:16Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  We propose a new formulation for the bundle adjustment problem which relies on nullspace marginalization of landmark variables by QR decomposition. Our approach, which we call square root bundle adjustment, is algebraically equivalent to the commonly used Schur complement trick. We show in real-world experiments with the BAL datasets that even in single precision the proposed solver achieves on average equally accurate solutions.
  arXiv  Detail & Related papers  (2021-03-02T16:26:20Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Non-parametric Models for Non-negative Functions [48.7576911714538]
  We provide the first model for non-negative functions from the same good linear models. We prove that it admits a representer theorem and provide an efficient dual formulation for convex problems.
  arXiv  Detail & Related papers  (2020-07-08T07:17:28Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.