2
$\begingroup$

Let $S_n$ be the simplex in $n$-dimensions, i.e., the set $\{ (x_1, \ldots, x_n) ~|~ \sum_{i=1}^n x_i = 1, x_i \geq 0 \mbox{ for all } i \}$. I am interested in the optimization problem $$ {\rm max} \sum_{i=1}^n c_i x_i $$ subject to the two constraints $$ x \in S_{n}, ~~~~\sum_{i=1}^n d_i x_i = 0.$$

Does there exist a closed form expression for the optimal vector and for the optimal value?

Note that if all $d_i$ are zero then the optimal value is $\max_{i=1, \ldots, n} c_i$, achieved by taking $x_i=1$ corresponding to the largest $c_i$, and $x_i=0$ for other $i$. If the $d_i$ are all equal, then the set of feasible solutions is empty.

  • 0
    Did you mean to write $\sum_{i=1}^n x_i \leqslant 1$ in the definition of $S_n$, or did you mean to say $n-1$-dimensional simplex?2012-04-29

1 Answers 1

2

If there is an optimum, it must lie on one of the edges of the simplex, which are the line segments connecting two corners $e_i$ and $e_j$, i.e. $\lambda e_i+(1-\lambda)e_j$ with $\lambda\in[0,1]$. Substituting this into the constraint yields $d_i\lambda+d_j(1-\lambda)=0$, which has a solution in $[0,1]$ unless $d_i$ and $d_j$ are both non-zero and have the same sign. To avoid problems with division by zero, we can note that if $d_i=d_j$, then if $c_i=c_j$ the two variables $x_i$ and $x_j$ play the same role and we can eliminate one of them, and if, say, $c_i\gt c_j$, then we can eliminate $x_j$. Thus we can assume that $d_i\ne d_j$, and then $\lambda=d_j/(d_j-d_i)$, and the corresponding value of the objective function is $c_i\lambda+c_j(1-\lambda)=c_j+d_j(c_i-c_j)/(d_j-d_i)=(c_id_j-c_jd_i)/(d_j-d_i)$. Thus, after eliminating superfluous variables as described above, the maximal value is

$$\max_{d_id_j\le0}\frac{c_id_j-c_jd_i}{d_j-d_i}\;.$$

  • 0
    Thanks for the solution, which I"m reading and trying to understand. Could you provide some more justification for the claim that the optimum must lie on the edges of the simplex? Thank you!2012-04-30
  • 0
    @robinson: The constraint defines a hyperplane. If the hyperplane intersects the simplex, the intersection is a lower-dimensional simplex. The restriction of the linear objective function to that lower-dimensional simplex is still a linear function, and a linear function on a simplex takes its extreme values at the corners of the simplex. The corners of the lower-dimensonal simplex lie on the edges of the original simplex.2012-04-30