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?

$\endgroup$
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.

$\endgroup$
  • $\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 Jan 22 '14 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 Jan 23 '14 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 Jan 23 '14 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 Jan 23 '14 at 19:03

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.