Linear constraint expressing the sum of the $k$ largest elements

689 Views Asked by At

I have an optimization problem: \begin{align*} \quad \max\limits_{x\in\mathbb{R}^n}& f(x)\\ \text{subject to} \quad & 0\leq x_i \leq 1 &\forall i\in\{1, \dots, n\}\\ & x\in D \end{align*} where $D$ is the set of all vectors $x\in [0,1]^n$ such that the sum of the largest $k$ components of $x$ is less than or equal to $m$, where $1 \leq k \leq n$ and $m \geq 0$ are fixed numbers.

My question is: Can I translate the constraint $x\in D$ into a set of linear constraints for this optimization problem? Furthermore, can the set of resulting linear constraints be polynomial in $n$?

I looked at Minimize the sum of $r$-largest entries with constraints and How to optimize objective function that contains the “k-largest” operator? , but I don't know if I can translate the constraint $x\in D$ into a set of linear constraints on its own (i.e. without translating it into an optimization problem of its own), which is what I would want because I already have an objective function $f(x)$ that I want to optimize.

1

There are 1 best solutions below

3
On

Let binary decision variable $y_i$ indicate whether $x_i$ is among the largest $k$. Let continuous decision variable $z_i\in[0,1]$ represent the product $x_i y_i$. Let $w$ represent the $k$th largest value of $x_i$. The constraints are: \begin{align} \sum_i y_i &= k \\ \sum_i z_i &\le m \\ z_i &\le y_i &&\text{for all $i$} \\ -(1-y_i) \le z_i - x_i &\le 0 &&\text{for all $i$} \\ x - w &\le y_i &&\text{for all $i$} \\ w - x &\le 1-y_i &&\text{for all $i$} \end{align}