Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 0 down vote favorite

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?

share|improve this question

1 Answer

up vote 2 down vote

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.

share|improve this answer
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. – Star Feb 10 at 22:24
Just to be clear, your other constraints are linear in $u$, $a$, and $b$? Your objective is linear in $u$, $a$, and $b$? – Brian Borchers Feb 10 at 23:44
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. – Brian Borchers Feb 11 at 0:03
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. – Star Feb 11 at 8:48
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$. – Brian Borchers Feb 12 at 0:22

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.