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

Question

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 1

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 2

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.

Answer 3

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