Sampling from the set of near-optimal solutions to a quadratic program

Question

I have a quadratic program of the form: \begin{align} \text{minimize} \quad & x^T Q x \\ \text{subject to} \quad & A x \leq b \\ & Cx = d \end{align} I would like to sample from the set of feasible near-optimal solutions, i.e. $$ \{ x : \|x - x^\star\|_p \text{ small},\ Ax \leq b,\ Cx = d\} $$ where $p = 1$ or $p = 2$ are both acceptable. There is no specific bound on $\|x- x^\star\|_p$, but faraway samples will almost surely not be useful for my application.

Answer 1

Here's a simple acceptance-rejection algorithm.

Note that $Cx=d$ defines a plane and $Ax\leq b$ defines a convex polytope.

We can express the space $V:= \{x:Cx=d\}$ in an orthogonal basis $B$ and define a distribution over this basis (e.g., multivariate Gaussian). Then, start generating points $q$ in $V$, each time checking if $\|q - x^\star\|_p <\epsilon$ and $\ Ax \leq b$ for some $\epsilon > 0$

One problem with this is if the feasible region has a very small probability given your basis and chosen distribution over that basis, then you'll end up rejecting a lot of points before you accept one.

You can probably improve your acceptance rate by centering the mode of your distribution (assuming it's unimodal) at the optimal point.

An alternative is to implement Markov Chain Monte Carlo sampling, which will make it easier to avoid crossing the constraint boundaries. There's a nice program called Stan that makes this relatively straightforward.

Answer 2

Here's an alternative approach. I can't say whether it's better or worse than the other suggestions.

Solve the original QP, but with a slightly perturbed $Q$. The solution will be feasible. You can do acceptance/rejection on whether the optimal solution to the perturbed problem is close enough to the optimal solution of the original QP.