2
$\begingroup$

On Wikipedia, I encountered a statement that the semidefinite relaxation of a quadratically constrained quadratic program can be solved more efficiently (using only LP) in the case that no variable is ever multipled by itself; a nonlinear term may only multiply a variable by a different variable. Since a problem I'm interested in fits that requirement—in fact, it's bilinear in the sense that there is an explicit bipartition of the set of variables and a variable from one part may only be multiplied by a variable from the other part—I went to check out the source for this claim: Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods by Kimizuka et al.

That paper is primarily about a particular application (the pooling problem), but its middle part considers quadratic programming in general, and indeed provides a proof of the stated claim: if there are no square terms in the QP ("Assumption 4.1" in the paper) then a linear relaxation of it attains the same optimal value of the objective function as the semidefinite relaxation of it. Both Wikipedia and the introduction of the paper present the result in that manner. However, after looking at the proof it seems to me that they in fact prove something that goes even farther (though perhaps is not as publishable): in these cases, the semidefiniteness contraint is trivially satisfiable and thus pointless. It's not so much that a clever linear relaxation provides as good an approximation as the semidefinite one, but rather that the semidefinite relaxation provides an approximation every bit as poor as a rather coarse linear relaxation, which suggests it probably isn't doing a very good job of addressing the nonlinearity of the original QP. :-(

But I'm new to QP, so it's quite possible there is something I've overlooked. Thus my question becomes: Is this analysis correct—is the semidefiniteness constraint in fact pointless?

The relaxations in question

A general QCQP may be stated as:

over all $w \in \mathbb{R}^n$ minimise $w^\mathrm{T} Q_0 w + \beta_0^\mathrm{T} w + \gamma_0$ subject to $w^\mathrm{T} Q_k w + \beta_k^\mathrm{T} w + \gamma_k \leqslant 0$ for all $1 \leqslant k \leqslant m$

where $Q_0,\dotsc,Q_m$ are symmetric $n \times n$ matrices, $\beta_0,\dotsc,\beta_m \in \mathbb{R}^n$, and $\gamma_0,\dotsc,\gamma_m \in \mathbb{R}$.

The relaxations are carried out for a reformulation of this, which instead takes as variable a $(1+n) \times (1+n)$ matrix $\bar{W} = \begin{pmatrix} w_{00} & w^{\mathrm{T}} \\ w & W \end{pmatrix}$ (for ease of reference, the matrices are named as in Kimizuka et al., even if simplifications could be in order). Also define the helper matrices $\bar{H}_0 = \begin{pmatrix} 1 & \mathbf{0}^\mathrm{T} \\ \mathbf{0} & \mathsf{0} \end{pmatrix}$ and $\hat{Q}_k = \begin{pmatrix} \gamma_k & \tfrac{1}{2}\beta_k^\mathrm{T} \\ \tfrac{1}{2}\beta_k^\mathrm{T} & Q_k \end{pmatrix}$ for $k=0,\dotsc,m$. Finally write $\langle A, B\rangle$ for the Frobenius inner product $\sum_{i,j} A_{i,j} B_{i,j} = \operatorname{Tr}(A B^\mathrm{T})$ of two matrices $A$ and $B$. Now the QCQP can be restated as:

minimise $\langle \hat{Q}_0, \bar{W} \rangle$ subject to $\langle \hat{Q}_k, \bar{W} \rangle \leqslant 0$ for $1 \leqslant k \leqslant m$, $\langle \bar{H}_0, \bar{W} \rangle = 1$, and $W = w w^\mathrm{T}$.

The final $W = w w^\mathrm{T}$ here is the constraint that will be the subject of the relaxation steps. $\langle \bar{H}_0, \bar{W} \rangle = 1$ is just saying $w_{00}=1$. With that in mind, the various $\langle \hat{Q}_k, \bar{W} \rangle$ are direct transcriptions of the original quadratic constraints and objective function.

Semidefinite (SDP) relaxation

By replacing $W = w w^\mathrm{T}$ with the constraint that

$\bar{W}$ is symmetric and positive semidefinite,

we arrive at the SDP relaxation, for which efficient methods are available (even if one could wish for them to be faster).

Second-order cone programming (SOCP) relaxation

A necessary (but far from sufficient) condition for $W$ to be positive semidefinite is that $x^\mathrm{T} W x \geqslant 0$ for any test vector $x \in \mathbb{R}^n$ with at most two nonzero elements; if these are at positions $i$ and $j$, this condition is moreover equivalent to the claim that the $2 \times 2$ matrix $\begin{pmatrix} W_{ii} & W_{ij} \\ W_{ji} & W_{jj} \end{pmatrix}$ is positive semidefinite, which in turn is equivalent to the claim that the determinant $W_{ii} W_{jj} - W_{ij} W_{ji}$ and its diagonal elements all are nonnegative. Hence a further relaxation of the positive semidefiniteness is that

$W_{ii} \geqslant 0$ for all $1 \leqslant i \leqslant n$ and $W_{ij}^2 \leqslant W_{ii} W_{jj}$ for all $1 \leqslant i < j \leqslant n$.

This can apparently be restated as SOCP constraints, which though still nonlinear are easier to handle than SDP constraints. The exact details are not so important, because we shall continue with the linear relaxation.

Linear (LP) relaxation

Another way of looking at $W_{ij}^2 \leqslant W_{ii} W_{jj}$ is that $\vert W_{ij}\vert \leqslant \sqrt{W_{ii} W_{jj}}$, i.e., an off-diagonal element of $W$ is (in absolute value) bounded from above by the geometric mean of its same row/column diagonal elements. Since the geometric mean in turn is bounded from above by the arithmetic mean, we have that $-(W_{ii}+W_{jj}) \leqslant 2W_{ij} \leqslant W_{ii}+W_{jj}$ is a relaxation of $W_{ij}^2 \leqslant W_{ii} W_{jj}$. In other words we have now arrived at a fully linear relaxation of the original QCQP:

minimise $\langle \hat{Q}_0, \bar{W} \rangle$ subject to $\langle \hat{Q}_k, \bar{W} \rangle \leqslant 0$ for $1 \leqslant k \leqslant m$, $\langle \bar{H}_0, \bar{W} \rangle = 1$, $W$ is symmetric, $W_{ii} \geqslant 0$ for all $1 \leqslant i \leqslant n$, and $-(W_{ii}+W_{jj}) \leqslant 2W_{ij} \leqslant W_{ii}+W_{jj}$ for all $1 \leqslant i < j \leqslant n$.

No squares assumption

It appears all of the above was well known. The new observation Kimizuka et al. make is that if all the diagonal elements in all of the $Q_k$ are zero, then the inner products $\langle \hat{Q}_k, \bar{W} \rangle$ have no contribution from the diagonal elements $W_{11}$ through $W_{nn}$ of $W$, so changing these do not affect the original quadratic constraints or the objective function. In particular, one may take any feasible solution $\bar{W}$ to the linear relaxation of the problem and add to the $W$ part a suitable multiple $\alpha I$ of the identity matrix (the authors suggest any $\alpha$ larger than the largest eigenvalue of $w w^\mathrm{T} - W$) to obtain a new $\bar{W}$ with the same values for all $\langle \hat{Q}_k, \bar{W} \rangle$ that is furthermore positive (semi)definite—thus a feasible point for the semidefinite relaxation, with the same value for the objective function. Hence all three relaxations have the same optimal value for all instances of QP where the $Q_k$ diagonals are all zeroes.

The catch is that all three relaxations in these cases lack any inequality that puts an upper bound on the $W$ diagonal elements, so one may always look at these last. Instead of starting from a feasible point for the above linear relaxation, one can start with a feasible point for the even further relaxed

minimise $\langle \hat{Q}_0, \bar{W} \rangle$ subject to $\langle \hat{Q}_k, \bar{W} \rangle \leqslant 0$ for $1 \leqslant k \leqslant m$, $\langle \bar{H}_0, \bar{W} \rangle = 1$ and $W$ is symmetric,

then proceed with increasing the diagonal elements as above to achieve semidefiniteness. But this last relaxation is exactly the same as the SDP relaxation minus the semidefiniteness constraint, so that constraint appears to be completely pointless: it does nothing to constrain the set of vectors $w$ that the solver might return as solutions to the relaxed problem!

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.