2
$\begingroup$

I am considering an optimization problem of the form: \begin{equation} \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} \end{equation} 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: \begin{equation} C(s) = \left( \begin{array}{cc} C_{1}(s) & 0 \\ 0 & 0\end{array} \right), \end{equation} 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: \begin{equation} 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). \end{equation} 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)$?

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Aug 1, 2020 at 15:20

2 Answers 2

1
$\begingroup$

Yes, this is convex because the objective function and all constraints are convex.

The objective function is affine (linear), which is convex. The semidefinjite constraint on X is convex. The trace equality constraint on X is affine (linear), and therefore is convex.

$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Marc
    May 14, 2018 at 12:49
  • 2
    $\begingroup$ I answered a different question than you intended. I addressed the question of whether the optimization problem, for a fixed value of s, is convex. You apparently are viewing f(s) as the optimal objective value of the optimization problem for that value of s; and then inquiring as to the convexity of f(s) as a function of s. $\endgroup$ May 14, 2018 at 13:09
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.