1
$\begingroup$

I'm faced with this squared quadratic form: $$ f(\mathbf{x}) = (a - \mathbf{x}^{T}\mathbf{Ax})^{2} $$ where $a$ is a scalar, $\mathbf{x}$ is a $d$-dimensional vector, and $\mathbf{A}$ is a $d\times d$ symmetric positive definite matrix. The minimization of this function with regard to the vector $\mathbf{x}$ requires solving this unusual matrix-vector equation $$ \arg\min_{\mathbf{x}\in \mathbb{R}^{d}} f(\mathbf{x}) = \left\{\mathbf{x}\in \mathbb{R}^{d}:\mathbf{Ax}(a-\mathbf{x}^{T}\mathbf{Ax}) = 0\right\} $$

Does this minimization problem have an analytical solution? Or should I resort to some kind of numerical optimization algorithm? It would be best to find the closed-form expression, hopefully, if there is one.

$\endgroup$
3
$\begingroup$

Use the Spectral Theorem to write $A=PDP^T$ where $D$ is diagonal and $P$ is orthogonal. Notice that $D$ has strictly positive diagonal elements because $A$ is positive definite.

A guaranteed minimum occurs if

$$a=x^TPDP^Tx$$

Write $y=P^Tx$ and this becomes $a=y^TDy$. If the diagonal elements of $D$ are $\lambda_i$ for $i=1,\dots,d$ and $y=(y_1,\dots,y_d)$ then this is equivalent to

$$a=\sum_{i=1}^d\lambda_i y_i^2 \tag{$*$}$$

When $a<0$, we see there can be no solution. When $a=0$, $y=0$ is the only solution. For both these cases, the best we can do is $y=x=0$.
When $a>0$, we see there are plenty of solutions -- an ellipsoid of solutions!


In other words, when $a>0$, what you can do is:

$\quad(1)$: Calculate the eigenvalues $\lambda_i$ of $A$.

$\quad(2)$: Calculate an orthonormal basis of eigenvectors for A, thus obtaining $P$.

$\quad(3)$: Choose some $y$ that solves $(*)$.

$\quad(4)$: Set $x=Py$ $($ remember that $P$ is orthogonal$)$.

$\endgroup$
1
$\begingroup$

It seems you're making this way too difficult. If $a>0$, you choose $\mathbf x$ so that $\mathbf x^\top A\mathbf x = a$ and you make $f(\mathbf x)=0$. If $a\le 0$, you get the minimum when $\mathbf x = \mathbf 0$. Your calculus equation is solved by taking either $a=\mathbf x^\top A\mathbf x$ (my first case) or $\mathbf x=\mathbf 0$ (my second case) since $A$ is nonsingular.

$\endgroup$

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.