0
$\begingroup$

Hello all,

I am dealing with some SDP optimization, and I come across the following problem.

The optimization problem is given by

\begin{aligned} &\operatorname*{min}_{t_1,\ldots,t_m,X}\ \sum t_i \\\ &\;\text{s.t.}\ \ \begin{bmatrix} A(X)+B & e_i \\\ e_i^T & t_i \end{bmatrix} \succeq 0,\ \ \ i=1,\ldots,m\ \ \ \ \ \\\ &\ \ \ \ \ \ \ \;X\succeq 0,\ \ \ \ \ \ \ \text{trace}(X) = C \end{aligned}

where $X\in\mathbb{R}^n$, $(t_i)_{i=1}^m$ are postive scalar, and $e_i$ is the unit vector in $\mathbb{R}^m$. It is known that the both matrices $A$ (for every $X$) and $B$ are positive definite. Also, it's known that $A(X)$ is a linear function in $X$, and hence this optimization problem is convex. Note that $B$ is independent on $X$ and on $(t_i)_i$.

My question: is it true that the above minimization has the same optimal solution, $X^o$, which the following minimization problem has ("just" ignoring $B$)

\begin{aligned} &\operatorname*{min}_{t_1,\ldots,t_m,X}\ \sum t_i \\\ &\;\text{s.t.}\ \ \begin{bmatrix} A(X) & e_i \\\ e_i^T & t_i \end{bmatrix} \succeq 0,\ \ \ i=1,\ldots,m\ \ \ \ \ \\\ &\ \ \ \ \ \ \ \;X\succeq 0,\ \ \ \ \ \ \ \text{trace}(X) = C. \end{aligned}

If I am not wrong, a feasible solution of the second problem is also feasible for the first one. But, are these two problems has the same solution $X^o$?

$\endgroup$
2
$\begingroup$

I don't see any reason why the two problems should have the same optimal solution.

Consider both SDPs with $A(X)=X$, $B=[25\ \ {-10};\ {-10}\ \ 20]$, and $C=1$, and $m=1$. Let the matrices be $2\times 2$.

Then, the first SDP has the optimal solution \begin{equation*} t = .1502,\qquad X = \begin{bmatrix} 0.4257 & 0.4945\\\\ 0.4945 & 0.5743 \end{bmatrix} \end{equation*}

While the second SDP has the optimal solution $t=2$, $X=(1/2)11^T$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hmm yes you right. Maybe my specific problem has further properties which I miss while presenting the "generalization" I asked here. In the simulations of my specific problem, $B$ does not effect the solution. Weird! Thank you! $\endgroup$ – Josh Sep 5 '12 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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