Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Is there any reason to believe that there are exact (by which I assume you mean "rational") answers? –  Igor Rivin May 14 '12 at 15:37
1  
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. –  Boris Bukh May 14 '12 at 15:39
    
@Igor: no, the answer may not be rational (see page 10 of the linked paper). @Boris: thanks! –  Emil May 14 '12 at 16:06
add comment

3 Answers 3

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.

share|improve this answer
    
Nice! But maybe there is an inefficient programmbale way... –  Felix Goldberg May 14 '12 at 16:01
    
Good point. However, I'm not really interested in the complexity of this problem. –  Emil May 14 '12 at 16:07
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
Thanks for the link! It looks like they are interested in numerical solutions though. –  Emil May 14 '12 at 16:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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