Best way to convert a generic QCQP into standard form in JuMP

Dear All,

I am solving nonconvex quadratically constrained quadratic optimization problems (QCQPs) in JuMP+Gurobi for teaching a recitation class on power system course at MIT (I am a teaching assistant for the course). I am using SDP relaxations of these QCQPs to compute a lower bound. This nonconvex QCQP can be formulated and solved via JuMP+Gurobi without any problem. However, to compute the SDP relaxation of the QCQP, I need to go through the following steps. While these might be trivial to many in JuMP community, for completeness, I describing my steps as follows.

Step 1. Convert the original QCQP into a standard form: Convert the original QCQP model (with the problem modeling real life constraints and objective) to the standard form nonconvex QCQP (the matrices are just symmetric and not PSD):

p^\star = \min_{x}\{x^{\top}A_{0}x+b_{0}^{\top}x+c_{0}\mid x^{\top}A_{i}x+b_{i}^{\top}x+c_{i}\leq0,\quad i=1,\ldots,m.\}\quad (1)

by manually vectorizing the original decision variables of the original QCQP (note that the matrices $A_i$​ for i=0,\ldots,m are only symmetric and not positive-semidefinite).

Step 2. Convert (1)​​ into rank-1 nonconvex SDP. After that, I define X= xx ^T ​​​​, which leads to the equivalent rank-1 nonconvex SDP:

p^{\star}=\min_{X,x}\{\mathbf{tr}A_{0}X+b_{0}^{\top}x+c_{0}\mid X=xx^{\top},\quad\mathbf{tr}A_{i}X+b_{i}^{\top}x+c_{i}\leq0,\quad i=1,\ldots,m\}\quad(2)

Step 3. Construct convex SDP by dropping the rank constraint. Finally dropping the rank-1 constraint and using the Schur’s complement I construct the convex SDP relaxation of (1):

p_{\textrm{lower}}^{\star}=\min_{X,x}\{\mathbf{tr}A_{0}X+b_{0}^{\top}x+c_{0}\mid\begin{bmatrix}X & x\\ x^{\top} & 1 \end{bmatrix}\succeq0,\;\mathbf{tr}A_{i}X+b_{i}^{\top}x+c_{i}\leq0,\quad i=1,\ldots,m\}\quad(3)

which gives us a lower bound on the original problem, i.e., p^\star_\textrm{lower} \leq p^\star.

While the process is straightforward, Step 1, where I need to vectorize the original variables to take into form (1), is very very tedious. The manual vectorization for different problem setups is also prone to human errors. My question is what is the best way to code converting an ugly-looking QCQP into the standard form QCQP such as (1)​​​​? Is there any tips/tricks that I could do to automate this process? Any tips/suggestions from the JuMP community will be much appreciated!

I don’t think there’s an easy way to do this in JuMP.

There are two complicated ways:

2 Likes

I see, okay thanks @odow ! Both are very interesting approaches, so I will definitely go through them in detail!

There’s no super easy way, but if it’s just for the purposes of demonstration, then the route of extracting the coefficients from the JuMP model (Oscar’s first suggestion) is likely more direct than working at the MOI level.

1 Like

Okay, thanks @miles.lubin !

I taught the SDP relaxation thing yesterday in my recitation session. Basically, I picked a simple QCQP that can be converted to SDP by hand, and then solved the QCQP using Gurobi and the SDP using Mosek. For the purpose of the course probably it suffices.

That being said, for a research project I am using somewhat of a similar process (converting a QCQP into rank-1 SDP), so your suggestion will be useful in automating the process!