Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1 - MathOverflow

Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1

2012-05-14T15:31:09Z

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,

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$.

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$.

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.

The motivation is I would like to be able to compute 3-graph Lagrangians (see e.g. this paper) of arbitrary 3-graphs. (A 3-graph is a 3-uniform hypergraph.)

I would appreciate any pointers in the right direction...

Edit: I am only interested in obtaining exact answers. I know how to solve these problems numerically.

Answer by Gjergji Zaimi for Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1

2012-05-14T15:49:07Z

There can be no efficient 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 independence number of the graph. Computing $\alpha$ is known to be NP-hard.

Answer by Felix Goldberg for Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1

2012-05-14T15:59:28Z

Googling a bit, I found this paper:

http://www.sciencedirect.com/science/article/pii/S037704270000385X

Penalized maximum-likelihood estimation, the Baum–Welch algorithm, diagonal balancing of symmetric matrices and applications to training acoustic data

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 might be the kind of thing you're looking for.

HTH...

Answer by Federico Poloni for Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1

2012-05-15T11:21:08Z

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.

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 weighted AM-GM).

For the second, use one of Maclaurin's inequalities 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$.

This kind of tricks can work in simple cases, or where there is much symmetry in the variables (check Muirhead's inequality for instance for another highly-symmetric case); if this is not your case you may be out of luck though.