2
$\begingroup$

I am looking for an efficient way of finding a linear fit $Mx = y$ subject to an inequality constraint:

$\frac{|x_2|}{\sqrt{x_3^2 + x_4^2}} \geq a$, with $a \geq 1$.

The rectangular matrix $M$ is about 1000 x 4 (~1000 observation points), and $x$ is 4-dimensional. If I square the constraint, it looks like a quadratically constrained quadratic programming (QCQP) problem:

$min_x \; x^T (M^TM) x - (2y^TM) x$ s.t. $x Q x \leq 0$

The problem is that Q is diagonal with diagonal entries (0, -1, $a^2$, $a^2$), and because of that -1 eigenvalue is not positive-definite. That, in my understanding, implies that the QCQP problem is nonconvex.

Is there a way to possibly reformulate the problem and solve it more efficiently than with a global constrained minimization? Perhaps something to do with having only one constraint as opposed to nonconvex QCQP cases in the literature that deal with multiple ones? This is to be solved thousands of times in my application, so any hints for a more efficient, case-specific implementation (using R or any other open-source library, or an algorithm reference to code after it) would help.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I believe the domain, although not convex, is the union of two convex regions: one for each sign of $x_2$. (Each is a Cartesian product $F\times \mathbb{R}$ where $F$ is one nappe of a cone.) Why not, then, solve the problem separately for $x_2 \ge 0$ and $x_2 \le 0$? $\endgroup$
    – whuber ♦
    Nov 13, 2014 at 20:37
  • $\begingroup$ Thanks for the hint. I can find out the sign of $x_2$ from problem-specific considerations. Let's say we add $x_2 \leq 0$ constraint. Would that mean a local optimization solver would do since I'd be searching within one nappe of a cone? Could the problem be reformulated as some convex quadratic or conical programming if the sign of $x_2$ is fixed? $\endgroup$
    – qcqp
    Nov 13, 2014 at 21:31
  • $\begingroup$ It's a quadratic program no matter what. But by adding a sign constraint on $x_2$ you can hope to be successful with solvers that assume the domain is convex. Since the cone's equation is differentiable (except at the origin, which you could treat separately), its derivative is easily obtained and can be exploited (via KKT in the usual way). You don't actually need to know the ultimate sign of $x_2$, by the way: you can solve the problem for both signs and pick the best solution between the two. $\endgroup$
    – whuber ♦
    Nov 13, 2014 at 22:10
  • $\begingroup$ If performance is a concern, I suggest not using R, or at least using Rcpp instead of pure R code $\endgroup$
    – shadowtalker
    Nov 14, 2014 at 3:17
  • $\begingroup$ Indeed R is generally not for performance I understand, just mentioned it since the majority of this forum seems to use it. $\endgroup$
    – qcqp
    Nov 15, 2014 at 0:33

1 Answer 1

Reset to default
1
$\begingroup$

Turns out that the search domain is indeed composed of 2 convex regions as whuber pointed out (thank you!). The constraint equation is basically a cone in ($x_2$, $x_3$, $x_4$) coordinates. It is a convex problem for a fixed sign of $x_2$. In fact, looking into the KKT conditions, it was possible to reduce the problem to a lovely system of 4 algebraic equations in ($x_2$, $x_3$, $x_4$) and a Lagrange multiplier $\lambda$. Thus, we essentially went from a potentially NP-hard nonconvex QCQP to an algebraic system! The solution was verified numerically using a general nonlinear optimization solver.

Improve this answer
$\endgroup$

Your Answer

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

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