I have the following nonconvex optimization problem, for which I want to formulate the dual:

$\mathcal{P}:\underset{x}{\text{min}} \quad x^\top A x + b^\top x \\ \quad \ \ \text{s.t.} \quad x\in\{0,1\}^n$

where $A$ is p.s.d. I am stuck on encoding both a psuedo-inverse and an image-constraint that pop up in the derivation of the dual problem in a way that looks convex/standard. Here are my steps:

The constraint can be rewritten as the $n$ nonlinear equalities

$x_i(x_i - 1) = 0, \quad \forall i$

With this, we write the Lagrangian

$\mathcal{L}(x,\mu) = x^\top (A + \text{diag} \ \mu)x + (b - \mu)^\top x $.

Let $\Omega(\mu) = (A + \text{diag} \ \mu)$ and $\beta(\mu) = b - \mu$ for notational convenience. Note that these are affine mappings on $\mu$, in case it comes in handy later. Finding the $\tilde{x}$ which minimizes $\mathcal{L}$ gives:

$\tilde{x} = \underset{x}{\text{arginf}} \ \mathcal{L}(x,\mu) = \begin{cases} -2\Omega(\mu)^\dagger \beta(\mu), & \Omega(\mu) \succeq 0 \ \text{and} \ \beta(\mu)\in\text{Im} \ \Omega(\mu) \\ \text{unbounded}, & \text{o.w.} \end{cases}$

where $^\dagger$ indicates the Moore-Penrose pseudo-inverse, see e.g. Boyd's book $\S$A.5.4 or other Boyd reference, $\S$2.2. Making substitutions, I have the dual problem:

$\mathcal{D}: \underset{\mu}{\text{max}} \quad -\beta(\mu)^\top \Omega(\mu)^\dagger \beta(\mu) \\ \quad \ \ \text{s.t.} \quad \Omega(\mu) \succeq 0 \ \text{and} \ \beta(\mu) \in \text{Im} \ \Omega(\mu)$

In the second Boyd reference above, he uses a Schur complement reformulation for a similar problem, but with inequality constraints. I don't directly see how that translates here. Additionally, the image constraint at first glance seems to be nonconvex to me, since it looks bilinear in $\mu$. So, my questions are:

(1) Is the cost of $\mathcal{D}$ concave, as it should be? If so, is there an easy way to reformulate this to more directly see it?

(2) How can the Im constraint be reformulated in an obviously convex way?

  • $\begingroup$ You already solved it, but this problem is also solved on the last page of §A.5.5 of Boyd and Vandenberghe. $\endgroup$ – LinAlg Sep 28 '18 at 21:55

Ok, I figured it out, and it's actually pretty straightforward based on Schur complement.

Introduce $\Delta \leq -\beta(\mu) Q(\mu)^\dagger \beta(\mu)$. Let the cost be to maximize $\Delta$, rearrange terms, and apply Schur complement to get a standard SDP in $(\mu, \Delta)$:

\begin{equation} \mathcal{D}: \underset{\mu,\Delta}{\text{max}} \quad \Delta \\ \quad \quad \text{subject to} \quad \begin{bmatrix} Q(\mu) & \beta(\mu) \\ \beta(\mu)^\top & -\Delta \end{bmatrix} \succeq 0. \end{equation}

Easy peasy!


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.