User - MathOverflow

Restriction of a linear functional equation to surface of a sphere

2011-02-07T01:38:07Z

Let $f_i : R \rightarrow R$ and $g_j: R \rightarrow R$ be unknown functions, for $i = 1, \cdots, N$ and $j = 1, \cdots, K$. Let $A$ be a $K \times N$ matrix whose columns are unit-length vectors ${\mathbf{a}}_i$. Consider the functional equation $\displaystyle\sum_i f_i ({\mathbf{a}}_i^\top {\mathbf{x}} ) = \displaystyle\sum_j g_j(x_j)$, where ${\mathbf{x}} = [x_1, \cdots, x_K]^\top$.

For some $r > 0$, when the domain of ${\mathbf{x}}$ contains the set $B$, where $B = ( \mathbf{x} : |x_i| < r, i = 1, \cdots, K )$, it is known that when ${\mathbf{a}}_i$ are linearly independent, with at least two non-zero components in each ${\mathbf{a}}_i$, then the functions $f_i$ and $g_j$ must all be quadratic polynomials. This is proved in, for example, this paper: http://www.jstor.org/stable/25049527 .

My question is: are similar results known for functional equations of the above type when the ${\mathbf{x}}$ are restricted to be on the unit sphere, that is, $||{\mathbf{x}}|| = 1$?

Non-negative quadratic maximization

2010-12-09T22:22:54Z

For a given symmetric, positive semidefinite, $n \times n$ matrix $A$, we want to solve the problem $$\max_{||x|| = 1, \;\;x >= 0} x^T A x.$$ Here, $x >= 0$ indicates that $x$ must be component-wise non-negative. Without the $x >= 0$ constraint, the solution $x$ must be the eigenvector corresponding to the largest eigenvalue (from Ky Fan). Is there a well-known solution for the case when $x >= 0$?

If not, are there any good relaxations (or randomized algorithms) to find $x$? For instance, are there any approximation bounds on how far from the optimum is the "largest eigenvector" of $A$?

Comment by

2011-02-09T02:07:38Z

Hi Michael, thanks for your input. The condition in the linked paper actually mentions that each a_i must have at least two non-zero components. I have added that to the question now. But in general, please feel free to assume any reasonable conditions that produce "non-trivial" conditions on f and g.

Comment by

2010-12-10T04:13:03Z

Thanks, Noah. This is indeed a QCQP, with one quadratic constraint. If we just had one (non-convex) quadratic objective, with a (non-convex) quadratic constraint, it is a special QCQP with nice duality properties (for example, S-procedure in control theory, or Appendix B of Boyd and Vandenberghe book). So, I wonder if there are any such special properties when we have a concave objective, with more than one (but quite simple) convex constraints (that is, $||x|| \leq 1$ and $x \geq 0$.

Comment by

2010-12-10T04:07:02Z

That's not correct, note that we want to maximize the objective, not minimize.