Is this function of Semi-definite matrices, convex?

Question

Is the following function is convex. Consider the following function

$$ f(X)=\langle X,D\rangle-c \cdot \sqrt{\langle X,E\rangle}$$ where $X,D,E$ are all semi-definite matrices. Is this function convex?

score 3 · Answer 1 · answered Mar 07 '15 at 23:40

3

The function $X \mapsto \langle X,D \rangle$ is linear, hence convex. Same for $X \mapsto \langle X,E \rangle$.

The function $t \mapsto -c \sqrt{t}$ is convex for $t \ge 0$, hence $f$ is convex.

answered Mar 07 '15 at 23:40

copper.hat

172,524

thank you. Could you tell anything about it's minimum? – user85361 Mar 08 '15 at 06:39
Nothing leaps out at me... – copper.hat Mar 08 '15 at 06:50

score 1 · Accepted Answer · edited Apr 13 '17 at 12:19

1

You asked @copper.hat above about the minimum. Without the semidefinite constraint, the function is likely unbounded below except for certain combinations of $D$ and $E$ (e.g, $D=\alpha E$ for some $\alpha>0$; see my answer to your other question).

With the semidefinite constraint, it is unlikely there is an analytic solution. You'll need a semidefinite programming framework to determine the constrained minimum. If you use my CVX framework, for instance, this is your model:

n = size(D,1);
cvx_begin
    variable X(n,n) semidefinite
    minimize( trace(X'*D)-c*sqrt(trace(X'*E)) ) 
cvx_end

Internally, CVX will convert this to a semidefinite program and pass it to a compatible solver.

EDIT: I take that back, I do believe you can determine the solution analytically, but it's not easy, and there still is not a closed-forum solution. This will certainly be quicker for you.

edited Apr 13 '17 at 12:19

Community

1

answered Mar 09 '15 at 15:19

Michael Grant

19,450

Thanks a lot, @Michael Grant. How such a problem can be converted to an ordinary semidefinite program? Actually, my problem is to find a very scalable way to solve this problem. Could you give me some hint about the way CVX convert this problem to a semidefinite program? Do you have any suggestions, How to make this problem more scalable? – user85361 Mar 09 '15 at 21:04
Could you give tell me how to determine the solution analytically, and is it faster? – user85361 Mar 09 '15 at 21:23
I'm afraid I am out of time today. But in short I would construct the dual problem. My belief is that the dual can be solved with a single generalized eigenvalue decomposition. – Michael Grant Mar 09 '15 at 21:34

Is this function of Semi-definite matrices, convex?

2 Answers2