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
    @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