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

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.

• Do you already know $x^*$? – user408433 Nov 16 '17 at 1:47
• Yes, I am solving the QP just before I do the sampling. – japreiss Nov 16 '17 at 2:01

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.

• That is exactly what I'm doing now :) The problem is that the optimal solution is usually tight on several of the constraints, so when sampling a ball (gaussian) around the optimal solution, each tight constraint rejects approx 1/2 of the candidates - so if more than 1 or 2 constraints are tight, I need to reject almost every candidate. – japreiss Nov 16 '17 at 4:36
• @japreiss ouch...yea that is the problem with acceptance-rejection sampling. FYI - for future questions, please mention what you’ve already tried so we don’t reinvent the wheel for you. – user408433 Nov 16 '17 at 4:52
• @japreiss if you know the active constraints, why not add them to the plane you are sampling over? They will be equality constraints at that point. – user408433 Nov 16 '17 at 4:55
• but I want to also sample solutions that are not tight at that constraint, even if the optimal solution is. – japreiss Nov 16 '17 at 4:59
• @japreiss you may want to consider MCMC sampling using Stan stat.columbia.edu/~gelman/research/published/nuts.pdf – user408433 Nov 16 '17 at 5:12

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.