1

Almost all the semidefinite programming paper I found has a linear objective function, which is $\mbox{tr}(CX)$. Why?

For example, in this paper and Wikipedia, the objective function is always $\mbox{tr}(CX)$, where $C$ is a known matrix. The goal is to minimize $\mbox{tr}(CX)$, such that $X\succeq0$ and satisfy some linear constraints. I wonder what is the difficulty to generalize the objective function $\mbox{tr}(CX)$ to general cases, e.g. convex functions? Such as strictly convex smooth objective function $\ell(X)=\mbox{tr}(CXX)$, where $C\succ0$? Or $\ell(X)=\mbox{tr}(CXX) -\sum_{i=1}^{n}\log(X_{ii})$?

Tan
  • 621
  • 1
    That is just how it is defined. However, all (single) objective optimisation problems can be expressed as a constrained problem with a linear objective. – copper.hat Nov 09 '21 at 22:02
  • I am confused why it has to be defined this way. Can you please elaborate more on "all (single) objective optimisation problems can be expressed as a constrained problem with a linear objective"? For example, if we would like to minimize negative log likelihood of gaussian with precision matrix as parameter, I am not sure how it would be expressed as a linear objective functioin. – Tan Nov 09 '21 at 22:04
  • 1
    $\min { f(x) | x \in D } $ is equivalent to $\min { t | f(x) \le t, x \in D}$. It is not saying much really. – copper.hat Nov 09 '21 at 22:07
  • Thanks, but I don't think it answers the question. – Tan Nov 09 '21 at 22:16
  • 1
    All linear functions on real symmetric matrices can be expressed as a trace. Is that what you are asking? – copper.hat Nov 09 '21 at 22:20
  • No, sorry for not being clear. It looks people only use $\mbox{tr}(CX)$ as objective in SPD. Why not objective function $l(X) = \mbox{tr}(CXX^T)$, or $l(X) = \mbox{tr}(CXX^T) - \sum_{i=1}^{n}\log(X_{ii})$, or other strictly convex function? Here let's say $C\succ0$. – Tan Nov 09 '21 at 22:24
  • It is a good question, I suppose it is partly answered by the fact I mentioned above (the equivalent problem) and partly that it is not fashionable. I have found that it is often better to solve the original problem rather that the reformulated one, but often requires more analysis. – copper.hat Nov 09 '21 at 22:33
  • Basically what @copper.hat said: if you allowed arbitrary objectives, the problem would be as complex as general convex programming – Bananach Nov 10 '21 at 08:24

0 Answers0