2
$\begingroup$

I have many quadratic programming problems of the following form: $$\min_{x\in\mathbb{R}^n} { \tfrac{1}{2} {\lVert Cx-d \rVert}^2} $$ $$\textrm{s.t.}\ x_1\le 0,\ x_n\le 0,\ x_n\le a_1^\top x_{1:n-1},\ \dots,\ x_n\le a_m^\top x_{1:n-1},$$ where $a_1,\dots,a_m\in\mathbb{R}^{n-1}$, and where $x_{1:n-1}$ is a vector containg the first $n-1$ elements of $x$.

I have been trying to solve these numerically using a standard quadratic programming solver (OSQP). However, the problem is numerically ill-conditioned, with huge differences in scale across elements of $R$, $d$ and $a_1$ to $a_m$. I have experimented with various normalizations of these quantities, but they have all resulted in extremely inaccurate "solutions". (The solver found these "solutions" much more easily, but this is still not very helpful.)

I was wondering if the special structure of my problem would permit a more direct solution method which would preserve greater numerical accuracy.

In particular, given a point $x$ that is not necessarily feasible, we can convert it into a feasible point by setting: $$x_1\leftarrow \min{\lbrace x_1,0\rbrace}$$ $$x_n\leftarrow \min{\lbrace x_n,0,a_1^\top x_{1:n-1},\dots,a_m^\top x_{1:n-1} \rbrace}.$$

Can this fact be used to produce an efficient algorithm for the problem? (Non-negative least squares style, perhaps.)

$\endgroup$

1 Answer 1

5
$\begingroup$

I would recommend you try an interior-point based optimizer. As far I recall OSQP employs a first-order method which is less robust than interior-point based optimizers.

Also, I would recommend you remove the square in the objective and hence minimize the norm directly. That often leads to a better-conditioned problem. If you do that, then you need a conic optimizer.

Personally, I prefer Mosek for obvious reasons.

PS. The second sin shown at

https://nhigham.com/2022/10/11/seven-sins-of-numerical-linear-algebra/

explains one potential reason for the ill-conditioning of using the QP formulation.

PPS: Reformulating the QP as a conic problem does not lead to a loss in computational complexity. Hence, no one can prove the QP formulation is superior in theory.

$\endgroup$
3
  • $\begingroup$ As I read the question, I was thinking what Erling would say. Then I scrolled down,, saw you answered, and that's exactly what you said. I guess you taught me well!! Yes, OSQP uses ADMM osqp.org/docs/solver/index.html . $\endgroup$ Commented Nov 7, 2022 at 17:18
  • $\begingroup$ I was following the OSQP advice and putting the Cx-d into a constraint (see osqp.org/docs/examples/least-squares.html ) rather than forming C'C. Inspired by your suggestion, I have now tried replacing C with R from a QR decomposition of C, and replacing d with Q'd. (I should have done this to start with I guess.) But it has not helped much. I will try Mosek! It seems slightly amazing to me that the conic formulation could be better behaved than the QP one, but I'm sure you know best. $\endgroup$
    – cfp
    Commented Nov 7, 2022 at 17:38
  • 1
    $\begingroup$ @MarkL.Stone glad to hear I am consistent. $\endgroup$ Commented Nov 8, 2022 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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