# Is this parametrized semidefinite program convex?

I am considering an optimization problem of the form: $$\begin{split} f(s) &= \min_{X} \mathrm{tr}(C(s)X) \\ &\;\;\;\;\;\;\;\;\;\;\; X \ge 0, \\ &\;\;\;\;\;\;\;\;\;\;\; \mathrm{tr}(A_iX) = a_i, \;\; 1 \le i \le M, \end{split}$$ where the minimization is over $n\times n$ Hermitian matrices $X$. Further, $A_i$ for $1 \le i \le M$ denote some $n\times n$ Hermitian matrices which together with $a_i \in \mathbb{R}$ determine linear constraints on $X$. Finally, the matrix-valued function $C(s)$ is of the block form: $$C(s) = \left( \begin{array}{cc} C_{1}(s) & 0 \\ 0 & 0\end{array} \right),$$ where the upper left block $C_1(s)$ is of size $(n_1 + 1) \times (n_1 + 1)$ for some $n_1 < n$, and is given by: $$C_1(s) = \left( \begin{array}{ccccc} I_{n_1\times n_1} & -ic \mathbb{I}_{n_1\times n_1} & \cdot & \cdot \\ i c \mathbb{I}_{n_1\times n_1} & \cdot & -i \frac{s}{2} \mathbb{I}_{n_1\times n_1} & \cdot \\ \cdot & i \frac{s}{2} \mathbb{I}_{n_1\times n_1} & \cdot & \cdot \\ \cdot & \cdot & \cdot & s^2\end{array} \right).$$ Here, $c \in \mathbb{R}$, $I_{n_1\times n_1}$ is the $n_1 \times n_1$ matrix of ones and $\mathbb{I}_{n_1\times n_1}$ denotes the $n_1 \times n_1$ identity matrix (whereas all entries indicated by $\cdot$ vanish).

Can it be shown that $f(s)$ is convex?

If not, which further requirements has the optimization to fulfill in order to guarantee convexity of $f(s)$?

• Probably a bit late to be asking this, but anyway: what is $s$ - a real parameter? Also: the way I read $C_1(s)$ it has $3n_1 +1$ rows and columns. This does not align with your statements. Can you clarify? – Fabian Wirth Aug 1 '20 at 15:20

• Thanks a lot for your answer! Is it difficult to see that this proofs convexity in $s$? If yes, can you give me a reference for this sort of statements? Does convexity also hold for the dual optimum as a function of $s$ (where the $s$-dependence appears in the constraints)? – Marc May 14 '18 at 12:49
Consider the following argument for a slightly changed problem (with $$s^2$$ in $$C(s)$$ replaced by $$-s^2$$) . Not sure if this would be of any help, but writing it anyway. Note that due to concavity of $$-s^2$$ in C(s) and the rest of the terms being either constant or linear in $$s$$ (in $$C(s)$$), we have: $$C(\lambda s_1 + (1-\lambda)s_2) \succeq \lambda C(s_1) + (1-\lambda)C(s_2).$$ Therefore, $$f(\lambda s_1 + (1-\lambda)s_2) \geq \min_{X\in \Gamma} \left\{ \lambda \mbox{Tr}(C(s_1)X) + (1-\lambda)\mbox{Tr}(C(s_2)X) \right\} \geq \lambda \min_{Y\in \Gamma} \left\{ \mbox{Tr}(C(s_1)Y)\right\} + (1-\lambda) \min_{Z\in \Gamma} \left\{ \mbox{Tr}(C(s_2)Z)\right\} = \lambda f(s_1) + (1-\lambda)f(s_2).$$ And hence $$f(.)$$ is concave in $$s$$.