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$
1
  • $\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, 2017 at 15:26

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .