5
$\begingroup$

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$?

$\endgroup$
3
  • 1
    $\begingroup$ You could try and add the constraints on the fly if they are violated. $\endgroup$
    – Kuifje
    Sep 7, 2022 at 13:57
  • $\begingroup$ @Kuifje this is a general heuristic for solving programs with many constraints. But in the worst case it might still be exponential. I am looking for a way to convert this specific program into a program of polynomial size. $\endgroup$ Sep 7, 2022 at 13:58
  • 3
    $\begingroup$ True in the worst case you might end up with an exponential number of constraints. But note that it is not a heuristic as optimality is guaranteed if you do add all the necessary cuts dynamically. $\endgroup$
    – Kuifje
    Sep 7, 2022 at 14:30

1 Answer 1

8
$\begingroup$

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}

$\endgroup$
1
  • $\begingroup$ This is ingenious. Thanks! $\endgroup$ Sep 8, 2022 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.