Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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! –  Josh Sep 5 '12 at 4:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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