0

I am trying to check if the dual expression of slide 13 of http://ee364a.stanford.edu/lectures/duality.pdf

$- \lambda^TAP^{-1}A^T\lambda - b^T\lambda$

is either convex or concave but am having a hard time. Computing the hessian gives me $-AP^{-1}A^T$ but I am not sure if that is positive or negative semi definite.

I have been looking through these slides on convex sets and convex functions but i still dont know http://ee364a.stanford.edu/lectures/functions.pdf

http://ee364a.stanford.edu/lectures/sets.pdf

Someone please help

enter image description here

Kong
  • 884
  • Your question is unclear. First, matrices like P are not convex or concave, so "its inverse is also definite and thus convex" isn't sensible. It's also unclear which of the expressions in your question is the one that you want to know is convex or concave? – Brian Borchers Apr 05 '18 at 14:13
  • @BrianBorchers okay so I am completely wrong then. I am trying to see if the dual problem is either concave or convex. I have edited my post. – Kong Apr 05 '18 at 14:15

1 Answers1

1

The matrix $P$ has positive eigenvalues $\lambda_i$. The eigenvalues of $P^{-1}$ are $1/\lambda_i$ and therefore $P^{-1}$ is positive definite. Writing $P^{-1} = UU^T$ for some matrix $U$, you get for any $x \in R^n$: $$x^T AP^{-1}A^T x = x^T AUU^TA^T x = (U^TA^T x)^T(U^TA^T x) \geq 0$$ Therefore, $AP^{-1}A^T$ is positive semidefinite. This means that the optimization problem is concave. Another way to show that the objective is concave, is by noticing that it is the infimum of functions that are linear in $\lambda$.

LinAlg
  • 19,822