0

Let $u(x):R\rightarrow{}R$ a real function. And a vector of integer numbres $\mathbf x =(x_1,x_2,...x_n)$ with $x_1\geq{}x_2\geq{}...\geq{}x_i\geq{}0\geq x_{i+1}\geq...\geq{}x_n.$

Let $S=\left\{{\mathbf y_1, \mathbf y_2, ..., \mathbf y_t}\right\}$ the set of partitions of vector $\mathbf x$.

Define $v(\mathbf x)=\displaystyle\sum_{i=1}^n{u(x_i)}.$

I want to find $\mathbf y_i \in S$ that maximizes $v(\mathbf y_i)$ for all $\mathbf y_i \in S$.

Quema
  • 49
  • Something looks wrong with your sign constraints. What does $x_i \ge 0 \ge x_n$ mean when you haven't specified a fixed $i$? – RobPratt Dec 10 '19 at 22:39
  • Take for example $\mathbf (10,8,-3,-5)$ in this case $i=2$. In this case, since $n=4,$ then $S$ has 15 vectors. I do not know how to write the constraint of a vector as an element of $S$. – Quema Dec 11 '19 at 12:09
  • What does $u$ look like? – RobPratt Dec 11 '19 at 21:18
  • $u$ is concave in the positive domain and convex in the negative domain, with $u(0)=0$ and $-u(-x)\geq u(x)$ for $x>0$ – Quema Dec 11 '19 at 21:21
  • Do you have a specific $u$ of this form in mind? – RobPratt Dec 11 '19 at 21:29
  • I think you have overloaded $v$, which is defined to take a vector as input but is then evaluated at a partition. Maybe a small numerical example would help clarify the question. – RobPratt Dec 12 '19 at 02:47
  • Let $\mathbf x=(5,3,-3)$ and $v(x)=x^{0.5}$ for $x \geq 0$ and $-2(-x)^{0.5}$ if $x<0$. I am interested in finding the optimal vector for the following partition $\mathbf y_1=(5+3,0,-3), \mathbf y_2=(5-3,3,0), \mathbf y_3=(5,0,3-3), \mathbf y_4=(5,3,-3)$ It is immediate to notice that vector $\mathbf y_2$ maximizes $v$. – Quema Dec 12 '19 at 18:22
  • A correction: $u(x)=x^{0.5}$ for $x>0$, $u(x)=-2(-x^{0.5})$ for $x<0$ – Quema Dec 12 '19 at 18:30

1 Answers1

0

You can solve this problem as a set partitioning problem. For each nonempty subset $S \subseteq \{1,\dots,n\}$, let binary decision variable $z_S$ indicate whether $S$ appears in the partition. The reward for subset $S$ is $r(S) = u(\sum_{i\in S} x_i)$. The problem is to maximize the total reward $\sum_S r(S) z_S$ subject to: \begin{align} \sum_{S:\ i \in S} z_S &= 1 &&\text{for all $i\in\{1,\dots,n\}$}\\ z_S &\in \{0,1\} &&\text{for all $S \subseteq \{1,\dots,n\}$} \end{align}

RobPratt
  • 45,619