5
$\begingroup$

$x^5y + y^5z + z^5x$

Let $x$, $y$, and $z$ be non-negative reals such that $x+y+z=1$

The maximum value of the above expression can be represented as $a^b/c^d$, where a and c are not perfect powers, and $a, b, c, d$ are positive integers. Find the value of $a+b+c+d$.

I want to know how to solve such questions. What are useful methods? What should I learn about to solve these "maximum and minimum values"?

Note: I'm a self-learner. What happened is that I saw this question on a site and many other such questions about "maximum and minimum values". My main point is to know what should I learn about to solve it (Resources would be helpful).

$\endgroup$
  • 1
    $\begingroup$ Learn lots of inequality theorems! Rearrangement inequality, AM-GM, Cauchy-Schwarz, Jensen's, etc. All of these are on Wikipedia and they help you solve lots of problems like these! $\endgroup$ – Ant Nov 22 '16 at 12:45
  • $\begingroup$ Also, look for symmetry; lots of problems like these have solutions that are very symmetric (e.g., I haven't worked through this problem yet, but I would bet that the solution is $x=y=z=\frac{1}{3}$. $\endgroup$ – Ant Nov 22 '16 at 12:48
  • $\begingroup$ @JohnChessant Honestly, I felt the same about (the 1/3 solution), but so far I can't prove it. I can't even be sure of that solution. Also, thanks for pointing out these theorems. $\endgroup$ – Ahmed Amir Nov 22 '16 at 12:51
  • 1
    $\begingroup$ Lagrange multipliers can sort this out, if you know calculus. tutorial.math.lamar.edu/Classes/CalcIII/… $\endgroup$ – Kaynex Nov 22 '16 at 13:25
1
$\begingroup$

I don't know if the following answer is the better one, but it shows that $x = y = z = 1/3$ is not the optimal solution.

Let $f(x,y,z) = x^5y +y^5z+z^5x$ be the objective function. The problem is equivalent to minimize the Lagrangian function

$$ L = -f(x,y,z) -\mu_1x-\mu_2y- \mu_3z + \lambda(x+y+z-1),$$ where $\mu_1, \mu_2, \mu_3$ and $\lambda$ are Lagrangian multipliers. The stationary points satisfy the polynomial system

$$ \lambda = \mu_1 + 5x^4y +z^5$$ $$ \lambda = \mu_2 + 5y^4z +x^5 $$ $$ \lambda = \mu_3 + 5z^4x + y^5 $$ $$ x + y + z =1$$ $$ \mu_1x = 0 $$ $$ \mu_2y = 0 $$ $$ \mu_3z = 0 .$$ $$ \mu_1 \geq 0,\mu_2 \geq 0,\mu_3 \geq 0$$

Now, we evaluate all possible cases for the multipliers $\mu_1, \mu_2$, and $\mu_3.$

Case (1): $\mu_1, \mu_2$, and $\mu_3$ are positives

In that case the system has no solution (the last three equations lead to $x=y=z=0$, not satisfying the equality constraint).

Case (2): at most a multiplier is zero

There is no solution such as all multipliers are nonnegative. Indeed, assuming $\mu_1 = 0$, we have $(x,y,z) = (1,0,0) \implies \lambda =0.$ Hence, $\mu_2 = -1$. Similarly, $\mu_2 = 0 \implies \mu_3 = -1$ or $\mu_3 = 0 \implies \mu_1 = -1$.

Case (3): at most two multipliers are zero

The set of solutions are $$(x,y,z) = \{(5/6,1/6,0),(1/6,0, 5/6),(0,5/6,1/6)\},$$

for $\lambda \approx 0.4019$ in all solutions, and

$$(\mu_1,\mu_2,\mu_3) = \{(0,0, 0.4017),(0,0.4017, 0),(0.4017,0,0)\}.$$ The objective is $f(x,y,z) \approx 0.067.$

Case (4): all multipliers are zero

In this case, we need to solve the following system

$$ 5x^4y + z^5 = 5y^4z + x^5$$ $$ 5z^4x +y^5 = 5y^4z + x^5 $$ $$x +y +z =1, $$ which it seems to be not so simple. An idea is to compute a Grobner basis in order to simplify the system to tackle univariate polynomials. See the basis computed with WolframAlpha here.

Nevertheless,I've computed the solutions of the system with the command solve of Matlab. It gives a total of $25$ solutions, but only four ones are real and nonnegative. The solutions given by the solver are

$$(x,y,z) = \{(1/3,1/3,1/3), (0.3631,0.5426,0.0943), (0.5426,0.0943, 0.3631), (0.0943, 0.3631, 0.5426)\}.$$

For the first solution, the objective is $f(x,y,z) \approx 0.0041$. The other three solutions give the value $f(x,y,z) \approx 0.0079$.

Thus, the optimal solution lies in the case (3).

$\endgroup$
  • $\begingroup$ I don't know about "Lagrange multiplier" which requires a backgorund about calculus (It's my problem. I will study about these theorems), so I'm not fully understanding the solution, but I can see the main idea. Thanks for your answer! $\endgroup$ – Ahmed Amir Nov 22 '16 at 17:26
  • $\begingroup$ @AhmedAmir, To learn about, I suggest you the Stephen Boyd and Liven Vandenberghe's book Convex Optimization, chapter 5. $\endgroup$ – Alex Silva Nov 22 '16 at 22:20
  • $\begingroup$ According to Amazon, it's a really good book. amazon.com/Convex-Optimization-Stephen-Boyd/dp/0521833787 I read the introduction and I'm interested in studying the entire book. However, the author suggested to have a solid understanding in advanced calculus and advanced linear algebra. I'm working on this at the time. Thanks for the great suggestion! $\endgroup$ – Ahmed Amir Nov 23 '16 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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