Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Sasha Apr 29 '12 at 19:11
    
Thanks, fixed now. –  robinson Apr 29 '12 at 19:15
add comment

1 Answer 1

up vote 2 down vote accepted

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}\;.$$

share|improve this answer
    
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! –  robinson Apr 30 '12 at 20:45
    
@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. –  joriki Apr 30 '12 at 23:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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