1
$\begingroup$

I have a quadratic programming problem with constraints of the general form:

Minimize w.r.t. x:

f(x) = (1/2) x^T * Q * x + c^T * x

subject to one or more constraints of the following form:

A * x <= b (inequality constraint)

E * x = d (equality constraint)

My problem is that I want to have an inequality constraint like x<=u where x is the vector being minimized and u is a vector(!) which is constant.

I also considered something like norm(x)<=norm(u) as a better constraint, but I can't express it/ implement it.

I tried with JOptimizer and ojAlgo but it does only work when u is not a vector but a constant.

So, how can I achieve an inequality constraint "x<=u" or "norm(x)<=norm(u)" where x and u are vectors?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

x<=u is exactly in the form A*x<=b, trivially from A=I and b=u. Most solvers allow you to specify bounds explicitly though (i.e, you specify A, b, E, d, and lower bounds l and upper bounds u)

A bound norm(x) <= u (Euclidean norm) cannot be represented using linear constraints. It leads to a so called second-order cone constraint. Changing the norm to the 1-norm (sum of absolute values) or the infinity-norm (largest absolute value) leads to a model which can be represented using linear constraints, and thus allow you to use a simple QP solver.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you! So, I'll try out another solver because I can't specify my constraints with JOptimizer. I can't set A and b there, at least I haven't succeeded so far. $\endgroup$
    – colorblind
    Commented Jan 22, 2014 at 21:02
  • $\begingroup$ Not sure which constraint you refer to as problematic for JOptimizer. Everything you've discussed above can be implemented in JOptimizer (the norm-constrant would use the SOCP capabilities, or written as $x^Tx \leq d$ by squaring it, and then using the QCQP solver) $\endgroup$
    – Johan Löfberg
    Commented Jan 23, 2014 at 6:59
  • $\begingroup$ I need to check that x<upperbound. At first I thought, a comparison based on the norm would suffice, but although e.g. (1000, 0) is longer than (1, 1) it is not ">", as 0 < 1 is true. So, I implemented a component-wise check: x_i < upperbound_i for all i from 1 to dim(x). I did this with adding dim(x) linear constraints to the inequalities. So, now I fear this is not very efficient, but haven't found the right functionClasses (QuadraticMultivariateRealFunction() didn't work, for instance) to compare the whole vectors. I'm new to QP, so maybe I'm blind in seeing the solution. $\endgroup$
    – colorblind
    Commented Jan 23, 2014 at 18:01
  • $\begingroup$ There is no easier way to express a bound. If x is 1000x1, you need 1000 bound constraints. THere is nothing inefficient about this. This is included in many models. Solvers will typically exploit bound constraints and deal with them efficiently. $\endgroup$
    – Johan Löfberg
    Commented Jan 23, 2014 at 19:03

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.