MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi all -- what would be good methods (and/or software packages) to try for solving a problem minimizing a quadratic function $f(x) = \sum_{i=1}^N{(x_i - y_i)^2}$, where some constraints are non-linear (and non-differentiable), e.g. $0 \leq x_i \leq 1$, and $\sum_i x_i \mathbf{1}_{x_i>a} < b$ ?

I am thinking about $N \approx 100$. FWIW, Matlab is apparently using an "active set method, similar to that of Gill et al.", which has somewhat uneven performance.

share|cite|improve this question
up vote 6 down vote accepted

The real issue here is the constraint

$\sum_{i} x_{i}1_{x_{i}>a} < b $

whose left hand side has horrible discontinuities.

Rather than using a solver designed for problems with continuous variables, you should formulate this as 0-1 mixed integer nonlinear programming problem, with binary decision variables $z_{i}$ that are 0 when $x_{i} \leq a$ and 1 when $x_{i}>a$. You can then use branch and bound to solve the problem.

share|cite|improve this answer
Thanks, this works :) – laxxy May 24 '12 at 2:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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