how can I linearize a constraint of the form $\sum (\min(x(i),y(i)))$ for a linear optimisation problem?

Question

I have an linear optimization problem, and I'd like to impose a constraint of the following form:

$∑_{i=0}^N \min⁡(x_i,y_i)≥C$ where $x_i,y_i$ are rational numbers greater or equal to 0. How can I linearize it ?

Edit

Optimization objective :

$ \max \text{PortfolioSpread}(x_1,x_2,\dots,x_N) = (∑_{i=0}^Nx_is_i)/\text{budget}$

s.t.

1. $∑_{i=0}^N x_i = \text{budget}$ (+ other constraints)
2. $∑_{i=0}^N \min⁡(x_i,y_i)≥C$

where decision variables $x_i$ represent market values, $y_i$ represent current holdings expressed in market values while $C$ is the constraint value.

I've used lpsolve to run this optimization exercise without the second constraint, and now I'd like to add the second constraint as well.

Answer 1

min is a concave function. Therefore the left-hand side of the constraint is concave as is, making the constraint convex as is. Therefore it can be linearized without use of binary or integer variables.

Specifically, for each $i$, declare a new continuous optimization (decision) variable $z_i$ (it might be the case that you wish to declare $z$ as a vector consisting of all the $Z_i$). Replace the constraint with $∑_{i=0}^N z_i≥C$ and add the constraints $z_i \le x_i, z_i \le y_i$

It might appear these constraints enforce $z_i \le \text{min}(x_i,y_i)$ rather than $z_i = \text{min}(x_i,y_i)$. But the optimization will drive this to $z_i = \text{min}(x_i,y_i)$ at the optimum, because the optimizer will want to make the constraint as weak as the formulation allows, to give it the most optimization capability.

Many (linear) optimization solvers and optimization modeling languages allow use of min, and will handle this reformulation automatically (under the hood).

I am adding CVX (under MATLAB) code showing how to do this in that tool

cvx_begin
variables x(N+1) z(N+1)
% omitting code except for constraint of interest
z <= x
z <= y
sum(z) >= C
cvx_end

However, this can be done even more simply in CVX, using its ability to allow convex use of min (similarly in CVXR and CVXPY).

cvx_begin
variable x(N+1)
% omitting code except for constraint of interest
sum(min(x,y,[],2)) >= C % x and y are column vectors, and min is taken across each row
cvx_end