cardinality constraints

Inexact Penalty Decomposition Methods for Optimization Problems with Geometric Constraints

  • Christian Kanzow
  • Matteo Lapucci
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , , ,

    This paper provides a theoretical and numerical investigation of a penalty decomposition scheme for the solution of optimization problems with geometric constraints. In particular, we consider some  situations where parts of the constraints are nonconvex and complicated, like cardinality constraints, disjunctive programs, or matrix problems involving rank constraints. By a variable duplication and  decomposition strategy, … Read more

    Cardinality Minimization, Constraints, and Regularization: A Survey

  • Daniel Bienstock
  • Andrea Lodi
  • Andreas M. Tillmann
  • Alexandra Schwartz
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization Tags , , , , , , ,

    We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and … Read more

    Multilinear Sets with Two Monomials and Cardinality Constraints

  • Rui Chen
  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , ,

    Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization … Read more

    Price Optimization with Practical Constraints

  • Lanshan Han
  • Hsin-Chan Huang
  • Alvin Lim
  • Xiaojie Wang
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Yield Management Tags , , , , ,

    In this paper, we study a retailer price optimization problem which includes the practical constraints: maximum number of price changes and minimum amount of price change (if a change is recommended). We provide a closed-form formula for the Euclidean projection onto the feasible set defined by these two constraints, based on which a simple gradient … Read more

    Marketing Mix Optimization with Practical Constraints

  • Hsin-Chan Huang
  • Alvin Lim
  • Jiefeng Xu
    • Categories (Mixed) Integer Nonlinear Programming, Marketing, Second-Order Cone Programming Tags , , , , , ,

    In this paper, we address a variant of the marketing mix optimization (MMO) problem which is commonly encountered in many industries, e.g., retail and consumer packaged goods (CPG) industries. This problem requires the spend for each marketing activity, if adjusted, be changed by a non-negligible degree (minimum change) and also the total number of activities … Read more

    Local search and swapping strategies.Challenging the greedy maximization of a polymatroid subject to a cardinality constraint

  • Mirco Soffritti
    • Categories Approximation Algorithms, Combinatorial Optimization, Meta Heuristics Tags , , , , , ,

    This paper studies the maximization of a polymatroid subject to a cardinality constraint. In particular, we consider the problem of improving the value of the greedy set by swapping one of its members with an element that does not belong to it. To achieve this goal, we first define a (set-based) post-greedy measure of curvature … Read more

    An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems

  • Carina Moreira Costa
  • Dennis Kreber
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Statistics Tags , , , ,

    Cardinality-constrained optimization problems are notoriously hard to solve both in theory and practice. However, as famous examples such as the sparse portfolio optimization and best subset selection problems show, this class is extremely important in real-world applications. In this paper, we apply a penalty alternating direction method to these problems. The key idea is to … Read more

    Feature selection in SVM via polyhedral k-norm

  • Manlio Gaudioso
  • Enrico Gorgone
  • Jean-Baptiste Hiriart-Urruty
    • Categories Data-Mining, Global Optimization Tags , , , ,

    We treat the Feature Selection problem in the Support Vector Machine (SVM) framework by adopting an optimization model based on use of the $\ell_0$ pseudo–norm. The objective is to control the number of non-zero components of normal vector to the separating hyperplane, while maintaining satisfactory classification accuracy. In our model the polyhedral norm $\|.\|_{[k]}$, intermediate … Read more

    A Novel Approach for Solving Convex Problems with Cardinality Constraints

  • Goran Banjac
  • Paul J. Goulart
    • Categories Approximation Algorithms Tags , , , ,

    In this paper we consider the problem of minimizing a convex differentiable function subject to sparsity constraints. Such constraints are non-convex and the resulting optimization problem is known to be hard to solve. We propose a novel generalization of this problem and demonstrate that it is equivalent to the original sparsity-constrained problem if a certain … Read more

    On the Structure of Linear Programs with Overlapping Cardinality Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid … Read more