3
$\begingroup$

I have an optimization problem where I am trying to minimize $$x^ \top A^{-1} x + Tr(A)$$ with respect to A, on the set of symmetric positive definite matrices.

I can see the problem is convex (the first term is jointly convex in $x$ and $A$, the second one is linear) and that $Tr(A)$ acts as a regularizer to prevent the solution from being "$+ \infty * Id$", but otherwise I am stuck: I do not know how to apply Fermat's rule to the first term. I thought about diagonalizing $A$, but since this diagonalization depends on $A$ I also get stuck. Any ideas?

$\endgroup$
  • $\begingroup$ 1) We agree that $x$ is fixed. Can it be assumed with norm = 1 ? 2) Could you give the context in which this question arose ? It can help to think to special methods... $\endgroup$ – Jean Marie May 9 '17 at 15:26
2
$\begingroup$

$\newcommand{\inne}[1]{\langle #1 \rangle}$ Assume $x$ is fixed and of unit $l^2$ norm. For any symmetric positive definite $A$ with associated orthonormal eigenvectors $\{v_j\}_{j=1}^N$ we have that $A=\sum_{j=1}^N \lambda_j v_jv_j^T$ and $A^{-1} = \sum_{j=1}^N \frac{v_jv_j^T}{\lambda_j }$. , then, using the wonderful properties of orthonormal bases, the term we are trying to minimize is $$x^T A^{-1} x + Tr(A)= \sum_{j=1}^N \frac{|\inne{x,v_j}|^2}{\lambda_j}+\sum_{j+1}^N\lambda_j$$ where $\sum_{j=1}^{N} |\inne{x, v_j}|^2=||x||^2=1$ and $\lambda_j>0$ for $1\leq j\leq N$. Computing the gradient with respect to the $\lambda_j$'s and setting the gradient equal to zero yields the $N$ equations: $$ 1-\frac{|\inne{x,v_j}|^2}{\lambda_j^2}=0 \mbox{ for } 1\leq j\leq N~\iff~ \lambda_j = |\inne{x,v_j}|$$ where we have to take the positive solution given the positivity of the $\lambda$'s. Thus the minimization problem can be recast as $$\mbox{minimize } 2\sum_{j=1}^N |\inne{x,v_j}|\mbox{ given } \sum_{j=1}^N |\inne{x,v_j}|^2=1,$$ which is clearly solved by any $A$ with $v_k=x$ for some $1\leq k\leq N$ as $$1=\sum_{j=1}^N |\inne{x,v_j}|^2\leq \sum_{j=1}^N |\inne{x,v_j}| \Rightarrow \inne{x,v_j}=\begin{cases} 1 & j=k \\ 0 & o.w.\end{cases}$$ yielding a minimum value of $2$.

$\newcommand{eps}{\varepsilon}$ However, this is not possible as $A$ would not be invertible. So the system can't achieve an actual minimum value, however, we can make the solution arbitrarily close to $2$, using exactly what you're trying to prevent with the regularization. Given $\varepsilon>0$, let $v_0=x$ and let $\{v_j\}_{j=2}^N$ be any orthonormal basis for the orthogonal complement of the span of $x$ and define $A$ as above with $\lambda_1=1$ and $\lambda_j=\frac{\varepsilon}{N-1}$ then we have $$\sum_{j=1}^N \frac{|\inne{x,v_j}|^2}{\lambda_j}+\sum_{j+1}^N\lambda_j = 1+\sum_{j=2}^N \frac{0(n-1)}{\varepsilon} +1+\varepsilon=2+\epsilon.$$

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