1
$\begingroup$

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?

$\endgroup$
1
  • $\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, 2018 at 21:55

1 Answer 1

1
$\begingroup$

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!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .