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 $p\in \left[0,1\right]$ and take $a_1,a_2,\ldots,a_n\in \mathbb{R}^{+}$. What is the maximum number of solutions that the system of (nonlinear) equations $$x_1^p +x_2^p +\cdots+x_n^p = 1\\ x_1^{1-p}\left(a_1-x_1\right)=x_2^{1-p}\left(a_2-x_2\right)=\cdots =x_n^{1-p}\left(a_n-x_n\right),$$ can have in $\left[0,a_1\right]\times \left[0,a_2\right]\times \cdots \times \left[0,a_n\right]$? Can we solve this system of equations in polynomial time?

I know that there are results in Algebraic Geometry that can give upper bounds on the number of solutions, at least for rational values of $p$, but they are for a generic system of polynomial equations; for the specific equations above those bounds seem to be very loose.

EDIT:

  • There is actually another condition that I forgot: for any $1\leq i,j\leq n$, if $a_i>a_j$ the solution must satisfy $x_i>x_j$. In other words, the $x_i$'s and $a_i$'s should have the same order.
  • I derived these equations while trying to solve a non-convex optimization problem.
  • Based on some numerical experiments, my conjecture is that the are no more than 3 solutions.
share|improve this question
1  
This type of equation, with real exponents and positive variables is called a posynomial in the real algebraic geometry literature. There are bounds for such systems, depending on the number of terms. Also, questions about computational time of root finding can be very delicate depending on how you represent the real numbers in the input and output. –  Dustin Cartwright Sep 19 '12 at 3:48
    
@Dustin Cartwright: Thanks for the information. Since posynomials don't have negative coefficients I may have to reorganize the terms so that they become true posynomials. In any case, are there specific techniques that can be applied to the particular equations I have? It would be great to show that the number of solutions is $O(1)$, but as long as it's not exponential in $n$ it should be fine. Regarding the computation time, I'm assuming a finite precision computer so any (approximate) solution within the precision of the machine is acceptable. –  S.B. Sep 20 '12 at 1:09
    
My mistake: I had remembered posynomial as allowing real exponents but no restrictions on the coefficients, which is what you're asking about. Regardless of the name, there are bounds for this type of equation, for example here: link. This still gives an exponential bound, but maybe you could do better after rearranging the equation. –  Dustin Cartwright Sep 20 '12 at 12:11

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.