convex relaxation

Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations

  • Dimitris Bertsimas
  • Caio de Próspero Iglesias
  • Nicholas A. G. Johnson
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , , ,

    We study Sparse Multiple Kernel Learning (SMKL), which is the problem of selecting a sparse convex combination of prespecified kernels for support vector binary classification. Unlike prevailing \(\ell_1\)‐regularized approaches that approximate a sparsifying penalty, we formulate the problem by imposing an explicit cardinality constraint on the kernel weights and add an \(\ell_2\) penalty for robustness. … Read more

    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

    Strong Formulations and Algorithms for Regularized A-Optimal Design

  • Yongchun Li
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , , ,

    We study the Regularized A-Optimal Design (RAOD) problem, which selects a subset of \(k\) experiments to minimize the inverse of the Fisher information matrix, regularized with a scaled identity matrix. RAOD has broad applications in Bayesian experimental design, sensor placement, and cold-start recommendation. We prove its NP-hardness via a reduction from the independent set problem. … Read more

    Compressed Sensing: A Discrete Optimization Approach

  • Dimitris Bertsimas
  • Nicholas A. G. Johnson
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming, Statistics Tags , , , ,

    We study the Compressed Sensing (CS) problem, which is the problem of finding the most sparse vector that satisfies a set of linear measurements up to some numerical tolerance. CS is a central problem in Statistics, Operations Research and Machine Learning which arises in applications such as signal processing, data compression, image reconstruction, and multi-label … Read more

    Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Nicholas A. G. Johnson
    • Categories Applications - OR and Management Sciences, Data-Mining, Statistics Tags , , , ,

    We study the Sparse Plus Low-Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, … Read more

    Efficient Joint Object Matching via Linear Programming

  • Antonio De Rosa
  • Aida Khajavirad
    • Categories Cutting Plane Approaches, Integer Programming, Linear Programming Tags , , , ,

    Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear … Read more

    On Piecewise Linear Approximations of Bilinear Terms: Structural Comparison of Univariate and Bivariate Mixed-Integer Programming Formulations

  • Lukas Hager
  • Robert Burlacu
  • Andreas Bärmann
  • Thomas Kleinert
    • Categories (Mixed) Integer Linear Programming, Global Optimization Theory, Quadratic Programming Tags , , , ,

    Bilinear terms naturally appear in many optimization problems. Their inherent nonconvexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of … Read more

    An Alternative Perspective on Copositive and Convex Relaxations of Nonconvex Quadratic Programs

  • E. Alper Yildirim
    • Categories Convex Optimization, Global Optimization Tags , , ,

    We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family … Read more

    A Polynomial-time Algorithm with Tight Error Bounds for Single-period Unit Commitment Problem

  • S.C. Fang
  • Ruotian Gao
  • Wenxun Xing
  • Cheng Lu
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Scheduling Tags , , , ,

    This paper proposes a Lagrangian dual based polynomial-time approximation algorithm for solving the single-period unit commitment problem, which can be formulated as a mixed integer quadratic programming problem and proven to be NP-hard. Tight theoretical bounds for the absolute errors and relative errors of the approximate solutions generated by the proposed algorithm are provided. Computational … Read more

    Dual-density-based reweighted $\ell_{1}hBcalgorithms for a class of $\ell_{0}hBcminimization problems

  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted $\ell_{1}$-algorithms for a class of $\ell_{0}$-minimization models which can be used to model a wide range of practical problems. This class of … Read more