I have a convex optimization problem that is essentially a linear objective function over some linear constraints and also a semidefinite matrix in the following form: $ M= \left[ {\begin{array}{cc} a & \sqrt{u} \\ \sqrt{u} & b \\ \end{array} } \right] \succeq 0$ Is this problem an instance of a semidefinite programming problem?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Your question isn't clearly stated. It's perfectly possible to have $M$ being a 2 by 2 symmetric and positive semidefinite matrix:
$M=\left[ \begin{array}{cc} M_{1,1} & M_{1,2} \\ M_{2,1} & M_{2,2} \end{array} \right] $
$M \succeq 0$.
Presumably you want to write other constraints into your problem that involve the elements of this $M$. The question is what kinds of constraints do you want to put on the elements of $M$. For example, if all that you mean by putting $\sqrt{u}$ in the off diagonal elements is that these elements must be nonnegative, that's easy to do.
answered Feb 10, 2013 at 19:46
-
$\begingroup$ Thanks for the comment. What I have is a convex optimization problem that is essentially a linear objective function over some linear constraints and also a semidefinite matrix in the following form. $\endgroup$– StarCommented Feb 10, 2013 at 22:24
-
$\begingroup$ Just to be clear, your other constraints are linear in $u$, $a$, and $b$? Your objective is linear in $u$, $a$, and $b$? $\endgroup$ Commented Feb 10, 2013 at 23:44
-
$\begingroup$ Assuming that the problem is linear in $a$, $b$, and $u$, Let $c=\sqrt{u}$, and you have a problem which is quadratic in $a$, $b$, and $c$. Assuming that the problem is convex in $a$, $b$, and $c$, then you're all set. Any convex quadatrically constrained quadratic programming problem can be formulated as an SDP. See the book by Boyd and Vandenberghe for example. $\endgroup$ Commented Feb 11, 2013 at 0:03
-
$\begingroup$ Thanks for your comment Brian. Assume that the optimization problem under consideration has variables $a$,$b$,$c$,$d$. All the constraint are linear in them but there is an additional constraints that states $ab-cd \geq0$. My problem should be an instance of a convex optimization problem. But, in order to assure the polynomially solvable, I need to transform it to an SDP. $\endgroup$– StarCommented Feb 11, 2013 at 8:48
-
$\begingroup$ Where did $d$ come from? The problem that you originally stated had a symmetric positive semidefinite matrix $M$, so this would be $ad-c^{2} \geq 0$ and $a \geq 0$ and $b \geq 0$. In any case, you can reformulate your quadratically constrained quadratic programming problem as an SDP as long as the problem is convex in these variables. However, you need to keep in mind that the square root of $u$ in your original problem is non-convex, and if you aren't careful, it possible that your problem won't be convex in terms of $a$, $b$, and $c=\sqrt{u}$, even if it is convex in $a$, $b$, $u$. $\endgroup$ Commented Feb 12, 2013 at 0:22