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. 



A difficult combinatorial optimization problem
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$. 


