3
$\begingroup$

Let $p(x_{1},x_{2},\ldots,x_{n})=\sum_{i,j=1}^{n}{a_{ij}x_{i}x_{j}}$ be a homogenous multivariate polynomial of degree $2$.

I would like to know how many extrema $p$ has on the standard simplex in $\mathbb{R}^{n}$ (i.e. the set $\{(x_{1},x_{2},\ldots,x_{n}) | > \sum_{i=1}^{n}{x_{i}}=1\}$).

Are there standard ways to count or at least estimate the number of extrema?

Without the simplex constraint it's (almost but not quite) the same as asking how many zeros the gradient has but apparently the constraint further complicates things.

Or am I missing something altogether obvious?

P.S. Bezout's theorem comes to my mind but I can't quite make it apply to this case.

Improve this question
$\endgroup$
3
  • $\begingroup$ I think you mean sum instead of product in the definition of $p$. $\endgroup$
    – Neil Strickland
    Commented Mar 25, 2014 at 12:07
  • $\begingroup$ Here's a junk observation: If $A=0$, then every feasible vector $x$ is an extremum---so uncountably many ;-) More seriously, this suggests that in general you may not even be able to bound the number of extrema (unless you meant: how many different extreme values does $p$ have, as opposed to how many different vectors $x$ exist that lead to an extreme value...this should be clarified) $\endgroup$
    – Suvrit
    Commented Mar 25, 2014 at 13:45
  • $\begingroup$ @Suvrit Well, I am thinking of Motzkin-Straus-type problems as Dima Pasechnik has suggested below, where there are certainly a finite number of extrema - but fishing for a general theory... :) $\endgroup$
    – Felix Goldberg
    Commented Mar 25, 2014 at 14:11

1 Answer 1

Reset to default
2
$\begingroup$

This is a hard question, in view of Motzkin-Straus theorem (cf. e.g. 5.2.4 here), which in particular says that the local minima of $f(x):=x^\top (I+A) x$, where $A$ is the adjacency matrix of a graph $\Gamma$, on the standard simplex are in one to one correspondence with maximal independent sets of $\Gamma$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Basically, MS is why I'm asking... :) $\endgroup$
    – Felix Goldberg
    Commented Mar 25, 2014 at 10:34
  • $\begingroup$ The exact number is probably hard to find, but I am hoping that by using analytical tools it will be possible to provide at least some decent bounds. $\endgroup$
    – Felix Goldberg
    Commented Mar 25, 2014 at 10:40
  • $\begingroup$ you certainly can write down the Lagrange conditions and use algebraic geometry to write down some bounds, but they won't be very useful: they would typically count complex as well as real solutions, and I bet you won't beat known results on number of maximal independent sets in graphs this way. See arxiv.org/abs/1104.1243 $\endgroup$
    – Dima Pasechnik
    Commented Mar 25, 2014 at 10:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .