How to solve this linear program with an exponential number of constraints?

Question

Consider the following convex program:

\begin{align*} \min g(x) && \text{such that} \\ f_i(x) &\geq b_1 && \text{ for } i \in 1,\ldots,n; \\ f_i(x)+f_j(x) &\geq b_1+b_2 && \text{ for } i,j \in 1,\ldots,n; \\ f_i(x)+f_j(x)+f_k(x) &\geq b_1+b_2+b_3 && \text{ for } i,j,k \in 1,\ldots,n; \\ \cdots \\ f_1(x)+\cdots+f_n(x) &\geq b_1+\cdots +b_n \end{align*}

That is: every function $f_i$ is at least $b_1$; every pair of functions sum up to at least $b_1+b_2$; every three functions sum up to at least $b_1+b_2+b_3$; etc. The $b_i$ are constants: $0<b_1<\cdots <b_n$.

The problem is that the number of constraints is exponential in $n$. Is there a way to attain the same outcome with a convex program of size polynomial in $n$?

Answer 1

For each $k\in\{1,\dots,n\}$, you want the sum of the $k$ smallest $f_i(x)$ to be at least $\sum_{j=1}^k b_j$. Equivalently, you want the sum of the $n-k$ largest $f_i(x)$ to be at most $\sum_{i=1}^n f_i(x) - \sum_{j=1}^k b_j$.

Introduce variable $y_k$ to represent the $(n-k)$th largest $f_i(x)$ and nonnegative variable $z_{ik}$ to represent $\max(f_i(x)-y_k,0)$. Now impose $n+n^2$ constraints \begin{align} (n-k)y_k + \sum_{i=1}^n z_{ik} &\le \sum_{i=1}^n f_i(x) - \sum_{j=1}^k b_j &&\text{for all $k$} \\ z_{ik} &\ge f_i(x) - y_k &&\text{for all $i$ and $k$} \end{align}

---

Alternatively, a slightly more direct approach is to introduce variable $y_k$ to represent the $k$th smallest $f_i(x)$ and nonnegative variable $z_{ik}$ to represent $\max(y_k-f_i(x),0)$. Now impose $n+n^2$ constraints \begin{align} k y_k - \sum_{i=1}^n z_{ik} &\ge \sum_{j=1}^k b_j &&\text{for all $k$} \\ z_{ik} &\ge y_k - f_i(x) &&\text{for all $i$ and $k$} \end{align}