Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$.

(Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. $\mid\mathcal{S}\mid$ denotes the cardinality of set $\mathcal{S}$.)

Consider the following problem \begin{align} \max_{\substack{\mathcal{S}\subset\{1,\dots,L\}\\ \mathbf{x}\in\mathcal{J}}}\,\mid\mathcal{S}\mid \\ x_i\,\leq\, -1,~i\in\mathcal{S } \end{align} Is there a way to rewrite this problem in terms of variables rather than the cardinality? For instance, one way I am familiar is \begin{align} \max_{\substack{v_1,\dots,v_L\\\mathbf{x}\in\mathcal{J} }}&\sum_{i=1}^{L}v_i\\ &v_i(x_i+1)\leq 0,i\in\{1,\dots,L\}\\ &v_i\in\{0,1\},\,\forall i \end{align} Actually I am trying to derive the the dual of this problem. Any suggestion in that regard would be really helpful.


First of all, one can shift the set $\mathcal{J}$ so that the condition $x_i \leq 1$ can be replaced by $x_i \geq 0$.

Let $M_i$ be the maximal absolute value of $x_i$ in $\mathcal{J}$, then we can introduce binary variables $v_i$ and write the problem as:

$\max \sum_{i\in S} v_i$

$M(v_i - 1) \leq x_i$ $\forall i \in S$.

The LP-relaxation of this description is probably poor because of the large constant $M_i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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