Nonconvex long-short constraints - 7 ways to count

A question on the forum today asked how one can constrain a solution to ensure a certain percentage of a vector to have a particular sign. This could for instance be of relevance in a portfolio allocation problem where we have constraints on the ratio of long (positive) and short (negative) positions.

There are many natural ways to write this in MATLAB, but to include it in YALMIP code, it has to be based on operators which are supported by YALMIP. Let’s look at some alternatives.

Let us assume we have a vector \(x\) of length \(n\) and we want at least half of the elements to be non-negative. To have a problem to work with, we will minimize the distance to a vector \(y\).

n = 20;
x = sdpvar(n,1);
y = randn(n,1);
Objective = (x-y)'*(x-y);

To begin with, one has to understand that the constraint is nonconvex (it is a combinatorial constraint), and the end result in YALMIP will be a mixed-integer representation of the constraint, more precisely a big-M representation.

A manual big-M model

For the experienced user, a manual big-M model is obvious. Define a binary vector \(d\), where \(d_i = 1\) indicates that \(x_i\) is non-negative, and the model is straightforward. For future reference, we introduce a global bound on \(x\) as it will be required later when YALMIP has to derive a big-M constant.

d = binvar(n,1)
M = 1;
Model = [x >= -(1-d)*M, sum(d) >= 0.5*n, -1 <= x <= 1];
optimize(Model,Objective)

Using implications

What we have implemented above is essentially an implication between the binary vector d and x. This can more conveniently be written using implies.

d = binvar(n,1)
Model = [implies(d,x>=0), sum(d) >= 0.5*n,  -1 <= x <= 1];
optimize(Model,Objective)

Going beyond these two models is never adviced, as it only complicates matters. However, let’s see if we can come up with other models just for fun.

sort

The operator sort is overloaded, and our constraint can be states as the last \(n/2\) elements of the sorted version of \(x\) should be non-negative. This will lead to a much worse integer model so never ever use the sort operator unless you really have to

sorted = sort(x);
Model = [sorted(n/2:end) >= 0,  -1 <= x <= 1];
optimize(Model,Objective)

median

An alternative to the sort operator, but effectively the same thing both mathematically and by implementation in YALMIP, is to say that the median is non-negative

Model = [median(x) >= 0,  -1 <= x <= 1];
optimize(Model,Objective)

sign

Yet another poor way to express our constraint is that the sum of the signs of the vector should be non-negative.

Model = [sum(sign(x)) >= 0,  -1 <= x <= 1];
optimize(Model,Objective)

nnz

Another approach is to work with cardinality and the nnz applied to constraints.

Model = [nnz(x >= 0) >= n/2,  -1 <= x <= 1];
optimize(Model,Objective)