Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T08:04:06Z http://mathoverflow.net/feeds/question/96909 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96909/finding-maximum-value-of-degree-3-homogeneous-polynomials-when-variables-sum-to-1 Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1 Emil 2012-05-14T15:31:09Z 2012-05-15T11:21:08Z <p>I would like to be able to find maximum values of degree-3 homogeneous polynomials, when the variables are non-negative real numbers that sum to 1. For example,</p> <p>For example, the maximum value of $xy^2$ subject to $x+y=1$, $x\ge0$, $y\ge0$, occurs when $x=1/3$ and $y=2/3$.</p> <p>And the maximum value of $xyz + xyw + xzw$ subject to $x+y+z+w=1$, $x,y,z,w\ge0$, occurs when $x=1/3$ and $y=z=w=2/9$.</p> <p>I have found that I can do many cases by hand (using Lagrange multipliers), but I would like to be able to do this computationally.</p> <p>The motivation is I would like to be able to compute 3-graph Lagrangians (see e.g. <a href="http://arxiv.org/abs/1110.4287" rel="nofollow">this paper</a>) of arbitrary 3-graphs. (A 3-graph is a 3-uniform hypergraph.)</p> <p>I would appreciate any pointers in the right direction...</p> <p><strong>Edit:</strong> I am only interested in obtaining exact answers. I know how to solve these problems numerically.</p> http://mathoverflow.net/questions/96909/finding-maximum-value-of-degree-3-homogeneous-polynomials-when-variables-sum-to-1/96913#96913 Answer by Gjergji Zaimi for Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1 Gjergji Zaimi 2012-05-14T15:49:07Z 2012-05-14T15:49:07Z <p>There can be no <em>efficient</em> way to compute such optimal values. Already for degree two this is NP-hard. Let $A$ be the adjacency matrix of a graph. The optimization problem $\min_{\Delta} x^T(I+A)x$ over the standard simplex $\sum x_i=1$ is equal to $1/\alpha$, where $\alpha$ is the <a href="http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29" rel="nofollow">independence number</a> of the graph. Computing $\alpha$ is known to be NP-hard.</p> http://mathoverflow.net/questions/96909/finding-maximum-value-of-degree-3-homogeneous-polynomials-when-variables-sum-to-1/96916#96916 Answer by Felix Goldberg for Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1 Felix Goldberg 2012-05-14T15:59:28Z 2012-05-14T15:59:28Z <p>Googling a bit, I found this paper:</p> <p><a href="http://www.sciencedirect.com/science/article/pii/S037704270000385X" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S037704270000385X</a></p> <p><em>Penalized maximum-likelihood estimation, the Baum–Welch algorithm, diagonal balancing of symmetric matrices and applications to training acoustic data</em></p> <p>It seems to tangentially discuss your problem on p.3 (1.3-1.4). The thrust of this paper is to compare the numerical Baum–Welch algorithm to something called the "degree raising algorithm" which <em>might</em> be the kind of thing you're looking for.</p> <p>HTH...</p> http://mathoverflow.net/questions/96909/finding-maximum-value-of-degree-3-homogeneous-polynomials-when-variables-sum-to-1/96989#96989 Answer by Federico Poloni for Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1 Federico Poloni 2012-05-15T11:21:08Z 2012-05-15T11:21:08Z <p>I do not know how far these methods can go, but in both your examples the maximum can be computed easily and without calculus using some algebraic inequality techniques, the kind of "standard tricks" that is taught to contestants in high-school math Olympiads.</p> <p>For the first inequality, AM-GM suffices: $$xy^2 = 4 (x \cdot y/2 \cdot y/2) \leq 4 \left(\frac{x+y/2+y/2}{3}\right)^3 = \frac{4}{27} (x+y)^3$$ (look also for <a href="http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means" rel="nofollow">weighted AM-GM</a>).</p> <p>For the second, use one of <a href="http://en.wikipedia.org/wiki/Maclaurin%2527s_inequality" rel="nofollow">Maclaurin's inequalities</a> in three variables to get $$(yz+yw+zw) \leq \frac{1}{3}\left(y+z+w\right)^2,$$ and then the inequality can be reduced to the previous one by setting $Y=y+z+w$.</p> <p>This kind of tricks can work in simple cases, or where there is much symmetry in the variables (check <a href="http://en.wikipedia.org/wiki/Muirhead_inequality" rel="nofollow">Muirhead's inequality</a> for instance for another highly-symmetric case); if this is not your case you may be out of luck though.</p>