1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$$

Check this counts, please. Probably, you will need to use the Newton's Method to solve It. In addition, check this related question

Multivariate Quadratic Regression

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Min Wu Oct 7 '19 at 20:15
  • $\begingroup$ 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. $\endgroup$ – Alexandre Frias Oct 7 '19 at 22:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Min Wu Oct 8 '19 at 5:26
  • $\begingroup$ You can use Newton's Method. For algebric approach, I think that you need to learn grobner basis. I prefer numerical methods. $\endgroup$ – Alexandre Frias Oct 8 '19 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.