---
title: Bilinear constraints
robots: noindex, nofollow
tags: convex relaxation, bilinear constraints, twitter
---

# Bilinear constraints

This is a quick note in response to [this tweet](https://twitter.com/JalalKazempour/status/1370411395972542466):

<blockquote class="twitter-tweet"><p lang="en" dir="ltr">An optimization question: How can we derive the dual problem of this bilinear optimization? Is there any way to formulate a dual problem which is independent of x and y, and is convex in \mu? Any answer (or a reference) will be highly appreciated! <a href="https://twitter.com/hashtag/orms?src=hash&amp;ref_src=twsrc%5Etfw">#orms</a> <a href="https://t.co/oUkxSVvKND">pic.twitter.com/oUkxSVvKND</a></p>&mdash; Jalal Kazempour (@JalalKazempour) <a href="https://twitter.com/JalalKazempour/status/1370411395972542466?ref_src=twsrc%5Etfw">March 12, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

Consider the optimization problem

\begin{align*}
\begin{array}{ll}
\mbox{minimize} & c^Tx \\
\mbox{subject to} & Ax=b \\
& x \in K \\
& x^TP_ix \leq d_i, \ i=1,\ldots,m
\end{array}
\end{align*}

where $K \subset \mathbb{R}^n$ is a convex cone and $P_1,\ldots,P_m$ are symmetric and of order $n$ (but not necessarily positive semidefinite). For example, $x^TP_ix$ may be a bilinear function in which case $P_i$ has zeros on the diagonal.

The Lagrangian may be expressed as

\begin{align*}
L(x,\mu,z,\lambda) &= c^Tx+\mu^T(Ax-b) - z^Tx + x^T P(\lambda)x - d^T\lambda\\
&=x^T P(\lambda)x + (c+A^T\mu-z)^Tx - d^T\lambda - b^T\mu
\end{align*}

where $P(\lambda) = \sum_{i=1}^m \lambda_i P_i$. The dual function is defined as

\begin{align*}
g(\mu,z,\lambda) &= \inf_x \,L(x,\mu,z,\lambda)\\
&=
\begin{cases}
-\frac12 (c+A^T\mu-z)^TP(\lambda)^\dagger (c+A^T\mu-z) - b^T\mu -d^T\lambda, & P(\lambda) \succeq 0, z \in K^*, \lambda \succeq 0, c+A^T\mu-z\in \mathrm{Range}(P(\lambda)), \\
-\infty, & \text{otherwise},
\end{cases}
\end{align*}

and the dual problem may be expressed as

\begin{align*}
\begin{array}{ll}
\mbox{maximize} & -t - d^T\lambda -b^T\mu \\
\mbox{subject to} &\begin{bmatrix}
t & (c+A^T\mu -z)^T\\
c+A^T\mu-z & P(\lambda) \end{bmatrix} \succeq 0 \\
& z \in K^*, \ \lambda \succeq 0.
\end{array}
\end{align*}

The dual function is unbounded below unless $P(\lambda) \succeq 0$ and $c+A^T\mu-z \in \mathrm{Range}(P(\lambda))$. As a consequence, the dual problem is not very interesting unless $P(\lambda) \succeq 0$ for some $\lambda \neq 0$. For example, this is the case if $x^TP_ix$ is a bilinear function for all $i$. In this case, any feasible dual variable $(\mu,z,\lambda)$ must have $\lambda = 0$, and hence the dual problem is basically equivalent to the dual problem that you would obtain by dropping the bilinear constraints $x^TP_ix \leq d_i$, i.e.,

\begin{align*}
\begin{array}{ll}
\mbox{maximize} & -b^T\mu \\
\mbox{subject to} & c+A^T\mu -z = 0\\
& z \in K^*.
\end{array}
\end{align*}

Now suppose the set $\{ x \mid Ax=b, x\in K\}$ is contained in a Euclidean ball with radius $R$ and center $0$. In other words, we can safely add the redundant constraint $\|x\|_2 \leq R$, or equivalently, $x^TP_{m+1}x \leq d_{m+1}$ with $P_{m+1} = I$ and $d_{m+1} = R^2$. This increases the dimension of the dual space by $1$, i.e., we now have $P(\lambda) = \sum_{i=1}^{m+1} \lambda_i P_i$ and $d=(d_1,\ldots,d_{m+1})$ which implies that $P(\lambda) \succeq 0$ for some $\lambda \neq 0$. Note, however, that the dual optimal value depends on $R$ since $d_{m+1} = R^2$.