 Convexity of SDP solution with respect to barrier penalty

(Rajiv Singh) #1

I have an interior point optimization question. The problem I am looking at it is a standard SDP:
minimize trace(C’X)
subject to
trace(A_i X) = b_i, i = 1,2,…,N
X>=0

X is a square matrix; X>=0 means positive definiteness. The interior point algorithm replaces the X>=0 condition with a barrier function so that the (relaxed) objective becomes trace(C’X) - 1/t log det (X) . t is a scalar controlling the severity of the barrier. As t->inf, the solution X*(t) to the relaxed objective approaches that of the true objective X*(inf). That is, lim t->inf X*(t) = X*(inf).

The question: Can it be proven (or contradicted) that trace(C’X*(t)) is a convex function of t? It seems logical but I have failed to find a proof.

(Erling D.Andersen) #2

Since it is CVX unrelated then this question belongs elsewhere e.g. stack exchange.

To me the answer seems no though.

(Rajiv Singh) #3

Thanks, cross-posted to stack exchange. Any hints on why you think the answer might be no?

(Erling D.Andersen) #4

To me it seems you ask whether the central path is convex. The central path is the set of all X(t).

The central is definitely not convex. Why should it be that?

(Rajiv Singh) #5

You are right and my mistake. I need to track the value of trace(C’X*(t)) and prove/disprove that it is a convex function of t.