1
$\begingroup$

Let G be a graph with vertices $1,2,...,n$ and $F(x)=\displaystyle{\sum_{ij\in\rm{E(G)}}x_ix_j}$.

Let S be the subset of $\mathbb{R}^n$ given by $x_i\ge 0$, $\sum x_i=1$. We're interested in $\displaystyle{\max_{x\in S}}$ $F(x)$.

Why is any local maximum of F in the interior of S also a global maximum?


I was reading this paper, http://math.ca/cjm/v17/cjm1965v17.0533-0540.pdf. In the middle of the third page, there is a remark saying:

Any local maximum of F in the interior of S is also a global maximum.

I don't see why this is true. Is this obvious? Or well-known?

$\endgroup$

2 Answers 2

5
$\begingroup$

It's because the Hessian quadratic form of $F$ restricted to the orthogonal complement of the vector of all ones is exactly the Laplacian of the graph $G$ (a good basis for the orthogonal complement is the set of vectors having $1$ in the first coordinates, and $-1$ in the $i>1$-st coordinate). The Laplacian matrix is positive semi-definite.

$\endgroup$
1
$\begingroup$

Does the problem actually depend at all on the graph theoretic context, or are we just asking about the sum of any subset of products of coordinate pairs? And is there any way for a quadratic function on a connected open linear manifold to have more than one isolated local extremum?

$\endgroup$
1
  • $\begingroup$ @Alan Cooper: you don't have to mention graphs, but the graph theoretic connections make it easier to think about the question. As for local maxima, your point is well taken, though strictly speaking the OP did not say "isolated", which is somewhat relevant. $\endgroup$
    – Igor Rivin
    Mar 29, 2011 at 13:54

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.