1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Is there any reason to believe that there are exact (by which I assume you mean "rational") answers? $\endgroup$
    – Igor Rivin
    May 14, 2012 at 15:37
  • 1
    $\begingroup$ I asked a similar question at mathoverflow.net/questions/1493/… The short answer is that the problem is computationally hard. Small instances can be solved by general decision algorithms for the theory of real closed fields, but anything realistic is currently impractical. $\endgroup$
    – Boris Bukh
    May 14, 2012 at 15:39
  • $\begingroup$ @Igor: no, the answer may not be rational (see page 10 of the linked paper). @Boris: thanks! $\endgroup$
    – Emil
    May 14, 2012 at 16:06

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Nice! But maybe there is an inefficient programmbale way... $\endgroup$ May 14, 2012 at 16:01
  • $\begingroup$ Good point. However, I'm not really interested in the complexity of this problem. $\endgroup$
    – Emil
    May 14, 2012 at 16:07
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the link! It looks like they are interested in numerical solutions though. $\endgroup$
    – Emil
    May 14, 2012 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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