User - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T20:11:21Z http://mathoverflow.net/feeds/user/11443 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54589/restriction-of-a-linear-functional-equation-to-surface-of-a-sphere Restriction of a linear functional equation to surface of a sphere unknown (yahoo) 2011-02-07T01:38:07Z 2011-09-21T14:22:11Z <p>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$. </p> <p>For some $r > 0$, when the domain of ${\mathbf{x}}$ contains the set $B$, where $B = ( \mathbf{x} : |x_i| &lt; 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: <a href="http://www.jstor.org/stable/25049527" rel="nofollow">http://www.jstor.org/stable/25049527</a> .</p> <p>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$?</p> http://mathoverflow.net/questions/48843/non-negative-quadratic-maximization Non-negative quadratic maximization unknown (yahoo) 2010-12-09T22:22:54Z 2010-12-13T19:16:50Z <p>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$? </p> <p>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$?</p> http://mathoverflow.net/questions/54589/restriction-of-a-linear-functional-equation-to-surface-of-a-sphere/54814#54814 Comment by 2011-02-09T02:07:38Z 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 &quot;non-trivial&quot; conditions on f and g. http://mathoverflow.net/questions/48843/non-negative-quadratic-maximization/48847#48847 Comment by 2010-12-10T04:13:03Z 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$. http://mathoverflow.net/questions/48843/non-negative-quadratic-maximization/48846#48846 Comment by 2010-12-10T04:07:02Z 2010-12-10T04:07:02Z That's not correct, note that we want to maximize the objective, not minimize.