# Minimization of the squared difference of a generalized quadratic form and a given number

For $$i,j\in [n]$$, let $$\alpha_{ij}\in\mathbb{R}$$ be given. Consider the function $$F:\mathbb{R}^d\times\cdots\times\mathbb{R}^d\to\mathbb{R}$$ defined by $$F(x_1,\cdots,x_n) = \sum_{i = 1}^n\sum_{j = 1}^n \alpha_{ij}(x_i,x_j)$$ where $$(x_i,x_j)$$ denotes the standard inner product of $$x_i$$ and $$x_j$$ in $$\mathbb{R}^d$$. I call this kind of function a generalized quadratic form since, if $$d = 1$$, the function is exactly a quadratic form. In fact, letting $$A = [\alpha_{ij}]_{n\times n}$$ and $$S = (A+A^T)/2$$, $$F(x_1,\cdots,x_n)$$ may be written compactly as $$F(x_1, \cdots, x_n) = \text{tr}(XSX^T)$$, where $$X$$ is the $$d\times n$$ matrix formed by putting $$x_1,\cdots,x_n$$ as its columns. My question is: given a fixed number, say $$\alpha\in\mathbb{R}$$, how do I solve $$\min_{x_1,\cdots,x_n\in\mathbb{R}^d} (F(x_1,\cdots,x_n)-\alpha)^2$$ and how do I find $$x_1,\cdots,x_n$$ that achieve the minimum? For my purpose, we may assume $$S$$ constructed above is positive semi-definite but I am also curious about the general situation. I am wondering whether this problem can be solved by playing with eigenvalues and eigenvectors of $$S$$. Any useful comments or direction to literature/topics would be appreciated.

Note that $$F'_{x_j}=2\sum_{i=1}^{n}a_{ij}x_i$$. In general, $$F'=tr(2XS)$$. You can use this derivates to find the extreme points of $$(F-\alpha)^2$$. You need to solve
$$2(-\alpha+\sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij}x_i x_j)(2\sum_{i=1}^{n}a_{ij}x_i)=0\quad\forall j \in 1...n$$
• Thanks for the answer. I did try to compute the gradient and set it to zero. It seems that setting $2\sum_{i = 1}^n a_{ij}x_i=0, j = 1, ..., n$ would give me a system of linear equations. But what if I set the first part to zero? How do I solve it? – Min Wu Oct 7 '19 at 20:15
• you need to find the solutions of $$\nabla (F(x_1, ..., x_n)-\alpha)^2 = 0$$ then I suppose there are many other solutions. You need to solve $$2(-\alpha+\sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij}x_i x_j)(2\sum_{i=1}^{n}a_{ij}x_i)=0\quad\forall j \in 1...n$$ rather than $$2\sum_{i = 1}^n a_{ij}x_i=0, j = 1, ..., n$$. Try to solve by parts $$2(-\alpha+\sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij}x_i x_j) =0 \quad\forall j \in 1...n$$ or $$(2\sum_{i=1}^{n}a_{ij}x_i)=0\quad\forall j \in 1...n$$. Probably, you need to use numerical methods. – Alexandre Frias Oct 7 '19 at 22:26
• Thanks for the response. I think there is no changing $j$ for $2(-\alpha+\sum_{i = 1}^n\sum_{j = 1}^n a_{ij}x_ix_j) = 0$ since $j$ is already in the summation. Also, this equation is a degree 2 polynomial equation. It feels like a codimension 1 algebraic variety and I am not sure how numerics could solve it. I do notice the active field of "polynomial system solving". Maybe I will find some notes and figure something out. Thanks anyway. – Min Wu Oct 8 '19 at 5:26