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.

$\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 '14 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 '14 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 '14 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$ Nov 14 '14 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 '14 at 0:33
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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