Skip to main content
Brian Borchers's user avatar
Brian Borchers's user avatar
Brian Borchers's user avatar
Brian Borchers
  • Member for 14 years, 3 months
  • Last seen more than a month ago
awarded
answered
Loading…
Loading…
revised
Loading…
revised
Loading…
Loading…
comment
A non-convex quadratically constrained quadratic program
If you want to learn more about this subject, I'd suggest looking at "A survey of the S-Lemma" by Imre Polik and Tamas Terlaky, from SIAM Review, Vol 49, No. 3, p 371-418, 2007. In particular, look at section 6 of the paper that discusses problems with rank limitations (you want your B matrix to be rank 1.) After reviewing this paper and thinking about your problem a bit, I can't see how to apply the S-Lemma approach to your particular problem.
comment
A non-convex quadratically constrained quadratic program
CSDP (and all of the other SDP solvers) support block diagonal matrices and also allow for blocks which are stricted to being block diagonal. If $B$ is of size $N$ by $N$, then your X matrix will have one block of size $N+1$ by $N+1$, holding $B$, $\beta$, and the $1$. You'll need one equality constraint to specify that this first element is 1. Your X matrix will also have a diagonal block of size $N$ to hold the slack variables. There's no need for constraints to make those off diagonal elements 0. If you're using the MATLAB interface to CSDP, then you'd have K.s=N+1 and K.l=N.
comment
A non-convex quadratically constrained quadratic program
The general result is that if you have a quadratically constrained quadratic programming problem with only one non-convex constraint, then you can formulate it exactly as an SDP. That's why I believe that this relaxation will be exact in this case. However, I haven't looked into this for several years, so the details escape me at the moment. If I get a chance I'll try to sit down and work through the details.
comment
A non-convex quadratically constrained quadratic program
See appendix B of "Convex Optimization" by Boyd and Vandenberghe.
comment
A non-convex quadratically constrained quadratic program
On second thought, although approach I sketched out is sufficient to show that the SDP is a relaxation of the original problem, it's not enough to show that the relaxation is exact (I forgot to account for the $L^{T}CL$ term in the constraint. I'm afraid that you need the machinery of the S-lemma to show that the relaxation is exact.
comment
A non-convex quadratically constrained quadratic program
As I recall, you can also get to this formulation using the S-lemma.
comment
A non-convex quadratically constrained quadratic program
There are several software packages for solving such an SDP, including SDPA (written in C++) and CSDP (in C)
Loading…
answered
Loading…
Loading…
comment
Proof that polynomial evaluated at roots of unity is DFT
Your notation seems a bit confused (and perhaps suggests why you're unable to establish this result.) You haven't explained what $a_{0}$, $a_{1}$, $...$ are.
comment
Robust optimization in matlab using fmincon
The poster has also put this same question up on scicomp.stackexchange.com, where she's somewhat more likely to get a useful answer, provided that she can clarify the question.
answered
Loading…
revised
Loading…
1 2 3
4
5
17