Cardinality Minimization, Constraints, and Regularization: A Survey

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

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

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

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

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

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

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

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

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

A Sequential Algorithm for Solving Nonlinear Optimization Problems with Chance Constraints

An algorithm is presented for solving nonlinear optimization problems with chance constraints, i.e., those in which a constraint involving an uncertain parameter must be satisfied with at least a minimum probability. In particular, the algorithm is designed to solve cardinality-constrained nonlinear optimization problems that arise in sample average approximations of chance-constrained problems, as well as … Read more